(厦门大学计算机科学系,361005，厦门）
计算机专业学什么？
... 计算机的实用层面：Windows使用，Office办公软件使用，Photoshop图像处理，收发Email，QQ聊天，上网，英汉翻译软件，语音识别…
... 计算机的应用层面：高级语言程序设计，数据结构，算法设计，操作系统，编译原理，汇编语言，计算机组成原理，嵌入式系统，数据库基础，计算机网络，计算机安全，图像处理，人工智能…
... 计算机的理论层面：计算理论，计算复杂性，形式语义学，体系结构，分布式算法，密码学，数理逻辑，图论与集合论…
课程简介
... 计算机，会计算的机器。又称电脑，这个名字更形象。什么叫计算？
... 计算机科学：也称计算科学。
... 艺术：还未形式化的东西，还未知计算方法的。
... 科学：计算科学中的理论层面，一般来说是形式化的，数字化的，还处于研究阶段的。
... 技术：计算科学中的技术层面，一般来说是已经成熟的，工艺化的。
计算科学的起源－从逻辑开始
... 中文的“逻辑”显然音译自英文的“logic”。logic又来自中古拉丁文的logica，logica又源自希腊文logos（λóγｏｓ）。logos一般翻译为“逻格斯”，接近于中文里的“道”。
... 中文的“道”和希腊文“logos”都有以下两层意思：
1 各种事物的定义或者各种活动的规则（西方各门学科的名字都以 -logy缀后的习惯）
2 言说，言谈
... 这两层意思也是相互关联的。言谈是为了揭示事物的道理，道理一般也通过言谈得以开显。
逻辑的发展
... 在言谈和辩论中，渐渐发展出逻辑学这一领域。从地域来分，古代逻辑学可以分为希腊逻辑学（亚里士多德），印度逻辑学（因明学）和中国逻辑学（墨子名学）。
... 亚里士多德三段论：
... 大前提：所有人都是有死的。
... 小前提：苏格拉底是人。
... 结论：苏格拉底是有死的。
逻辑四大基本定律
... 同一律：指概念在同一思维过程中必须保持同一。
... 矛盾律：亚里士多德在《形而上学》中说：“同一事物，不可能在同一时间内既存在又不存在，也不允许有以同样方式与自身相对立的东西。”
... 排中律：亚里士多德：“在对立的陈述之间不允许有任何居间者，而对于同一事物必须要么肯定要么否定其某一方面。”
... 充足理由律：首先由莱布尼兹提出。所谓充足理由律是指：“任何一件事如果是真实的或实在的，任何一个陈述如果是真实的，就必须有一个为什么这样而不那样的充足理由，虽然这些理由常常不能为我们所知道的。”
故事：为什么小子
... 在《聪明的一休》里，大家都躲着好奇小子，因为好奇小子老爱问“为什么”，常常会把大家问得无言以对。
... 公主：一休是我一个人的朋友！
... 为什么小子：为什么你一个人要霸占他？
... 公主大声叫：这件事用不着你管！
... 为什么小子：为什么不用我管呢？
... 公主：＠＃＠￥＃￥
... 为什么小子：“为什么你脸上的表情这么好笑呢？”
... 公主：……倒
逻辑与哲学的关系
... “哲学”一词出自古希腊文“philo-sophia”，意为“爱智慧”，原意为热爱智慧追求智慧
... 逻辑与哲学是密切相关的，一直伴随着哲学的发展，从亚里士多德的《工具论》到弗雷格的《算术基础》。当代西方哲学的一个重要方向分析哲学(语言哲学)的发展史就是逻辑学的发展史。
... 当代西方哲学的另一个重要方向现象学与逻辑也存在密切关系，现象学祖师胡塞尔就是从逻辑研究走向了现象学。
... 此外，逻辑学给哲学研究提供了一个思维基础，现在哲学的各个子学科基本上都要求有逻辑的基础。比如伦理学也有规范伦理学。

... 当然，逻辑也是科学的基石和立柱。你看，现代学科都要加上“-logy”的后缀。
... 科学学科都包含了归纳推理和演绎推理的方法。

... 在以往，逻辑学是哲学的一个分支。1800中期后，逻辑学也成为数学的一个分支。近代以来，逻辑学成为计算机科学的重要基础。根据应用的领域，逻辑可以分为哲学逻辑，数理逻辑和计算逻辑。
... 当代逻辑的发展，包含以下几位重要的人物：弗雷格、罗素、维特根斯坦、哥德尔、图灵
现代逻辑的发展
... “万一发生争执，正像两个会计员之间无须乎有辩论，两个哲学家也不需要辩论。 因为他们只要拿起石笔，在石板前坐下来，彼此说一声（假如愿意，找个朋友作证）：我们来算算，也就行了。” －－莱布尼兹

... 德国思想家莱布尼兹是有史以来最伟大的思想家之一。他与牛顿分别独立发现了微积分，后世使用的微积分主要使用莱布尼兹的符号；
... 他提出了通用计算的思路，使用计算来代替思考。他的这种想法，对于后来数理逻辑、计算机科学和分析哲学有重大影响；他提出了可能世界思想。如果某世界与现有世界并不矛盾，那就是可能的世界。他的可能世界思想后来被克里普克发展为可能世界语义，广泛用于非经典逻辑的语义解释；他还系统提出了二进制，这是现代计算机使用的内部语言。

... 弗雷格对于我们也许是陌生的名字，然而弗雷格是上世纪最伟大的思想家之一。他的《概念语言》一书，系统提出了现代逻辑，用严格清晰的数学符号来研究逻辑学。因此，他开创的现代逻辑学又称为数理逻辑，或符号逻辑。为什么说他是上世纪最伟大的思想家之一，这一点没有夸张。

... 他开创的数理逻辑对上世纪的科学和哲学两大领域都有重大影响。一方面，顺着罗素，希尔伯特，哥德尔，计算机之父图灵机，人工智能之父麦卡锡这个方向，他开创的数理逻辑思想被广泛用到计算机科学，被广泛用到人工智能和程序证明。另一方面，顺着罗素，维特根斯坦，卡尔纳普，奎因，普特南这个方向，他开创的数理逻辑及概念分析法发展成分析哲学。而分析哲学，是当前西方哲学的主流方向之一。

... 罗素的头衔很多，哲学家，数学家，逻辑学家，社会活动家，文学家。他在逻辑学方面的成就，主要是与他的老师怀特海编写了《数学原理》，使得弗雷格开创的数理逻辑更加系统更加完善。

... 如果说弗雷格是数理逻辑的开山祖师，那么罗素就是数理逻辑的集大成者。罗素继续弗雷格的逻辑主义，想把数学归结到逻辑上。然后，他自己提出的罗素悖论使这一努力失败。

... 布劳维尔：荷兰数学，自立门户，提出了直觉主义思想，反对康托尔集合，认为罗素悖论是根源于非构造性的数学，强调构造性证明，反对基于无穷集的排中律。

... “我们必须知道，我们必将知道。”－－希尔伯特
... 数学基础出现了矛盾，以确定性追求为己任的数学家如何受得了。集合论的矛盾弥漫开来，有人也怀疑算术是否也有矛盾。为了捍卫古典数学的尊严，作为当时数学界的领袖，希尔伯特当仁不让，接过了这个挑战。

... 继1900在数学家大会上提出著名的希尔伯特23个问题后，1904年，希尔伯特在数学家大会上又提出一个证明算术无矛盾性的思路。
... 这个思路也称为形式主义纲领，它的核心思想是将算术表达为一种形式系统或称公理系统，然后用有穷步骤证明该系统的无矛盾性。希尔伯特的目的是试图对形式系统的无矛盾性给出让大家都可以接受的证明，以便克服悖论所引起的危机，一劳永逸地消除对数学基础以及数学推理方法可靠性的怀疑。对于这个纲领，希尔伯特信心十足，在哥尼斯堡演讲中说出了上面的话。

... 哥德尔研究了希尔伯特纲领，给出否定的答案，宣告希尔伯特纲领的失败。1930年提出的哥德尔第二不完备性说，任何包含一阶算术的形式系统，该形式系统的无矛盾性，在该形式系统内无法通过有穷的步骤得到证明。在定理的证明中，哥德尔还提出了很多有用的理论，比如如何把符号编码为自然数，还有使用递归函数来研究有穷证明的能力范围。

... 哥德尔的工作揭示了有些问题是不可通过有限的步骤得以证明的，那么什么问题是可以通过有限的步骤证明的？沿着这个问题，哥德尔的很多工作，被应用到了可计算性的研究。什么是可以有穷证明的，从可计算性的角度来说对应于，什么是可以计算的。

... 哥德尔不完备定理出世后，在剑桥大学的图灵设想：能否有这样一台机器，通过某种一般的机械步骤，能够解决所有可以解决的数学问题。以上机器就是他提出来的图灵机。图灵机可以计算的问题，就称为图灵机可计算。

... 它由一个控制器和一条两端可无限延长的工作带组成：工作带起着存储器的作用，它被划分为无穷多个可写可擦的方格。控制器则可以在带上左右移动，控制带有一个读写头，读写头可以读出当前方格内的符号，然后根据预先设计的状态转换指令，选择改写或抹去这一符号，然后选择往左移一格，往右移一格或者不移动，并进入下一个状态。当状态转换到停机状态，则停止运行。

... 图灵机的出现，奠定了计算机科学的理论基础，计算机的出现已经主要是技术实现的问题了。据说，图灵在二战期间主持设计了一台计算机。但资料比较多的，1946年，数学家冯...诺依曼主持设计了第一台计算机。但不管如何，图灵被广泛认为是“计算机之父”。现代计算机的计算能力，还是在图灵机的计算能力之内，当然速度是越来越快了。图灵开辟了一条大路，后来的科学家又开辟了一些中路小路，我们则行走在前人铺就的路上。
... 　　

... 1966年，美国计算机协会设立以图灵为名的“图灵奖”，用于表彰在计算机科学领域做出突出贡献的科学家。图灵奖的得主有： Ken Thompson ，Dennis M. Ritchie， Minsky，“人工智能之父”McCarthy，Dijkstra，Knuth，Backus，Floyd，Hoare，Codd，Cook，Thompson，Wirth，姚期智，RSA三人，“互联网之父”Cerf和Kahn……

逻辑与计算机科学的关系
... 在第三次数学危机中，随着罗素悖论等难题的出现，经典数学的方法受到了空前的置疑：反证法、实无穷。学者们思考这样一个问题：什么样的数学，是确定的？
... 在对经典数学的批判过程中，一些构造性的计算模型成长了起来：递归函数论、公理系统、图灵机和lambda演算等。在这些计算模型之上，学者们提出了何谓“计算”。
... 有趣的是，这些计算模型的计算能力是相同的。因此，目前人们对于“计算”的理解，就是基于这些计算模型之上的计算能力。量子计算的计算能力还是在这个范围之内。
... 其次，因为这些计算模型的等价性，图灵机的计算问题也可以化为在逻辑层面上的逻辑问题。比如P与NP是否相等的问题，也可以在逻辑层面上进行思考。
逻辑的局限
... 逻辑定理的有效性，依赖于公理和推理规则的有效性。
... 逻辑定理的有效性，已经包含在前提之中了。在这个意义上，维特根斯坦说定理都是废话。当然了，这些废话埋藏得如此之深，以致于人类不能一下子知道它是废话。这时候，机器可以帮助人类。人类给出前提，机器快速自动推出定理。
... 这就是当前计算机的价值和局限。未来，能不能发展出能听能看能认识外界能自己进行归纳的机器？
归纳
... 培根：“知识就是力量”
... 培根：“读史使人明智，读诗使人聪慧，演算使人精密，哲理使人深刻，论理学使人有修养，逻辑修辞使人善辩”
... 所谓归纳，是指从许多个别的事物中概括出一般性概念、原则或结论的思维方法。
... 比如张三有死，李四有死，…，故而归纳出“所有人都是有死的”。
... 又如鸽子会飞，大雁会飞，…，故而归纳出“所有鸟都是会飞的”。
休谟难题
... 以前每天太阳都会升起，那么明天的太阳是否必然也会升起？如果回答是必然，请问如何证明？
... 最早对归纳法提出置疑的是英国哲学家休谟，所以归纳法的合理性问题也称为“休谟问题”。
... 因为在科学研究中，特别是经验科学如物理学，经常进行实验再使用归纳法来得出知识。所以，休谟问题其实也是“知识如何保证”的问题。
... 因为休谟提出这个问题，有学者就认为休谟反对理性，这有点奇怪，难道要信仰“理性万能”才理性吗？难道能提出理性局限的人不是更理性吗？

... 休谟认为：“说到过去的经验那我们不能不承认，它所给我们的直接的确定的报告，只限于我们所认识的那些物象和认识发生时的那个时期。但是这个经验为什么可以扩展到将来，扩展到我们所见的仅在貌相上相似的别的物象；则正是我所欲坚持的一个问题。”他认为归纳推理的合理性不可证明，宣称这类推理只是一种心理“习惯”。
... 休谟虽然否认归纳法有逻辑的合理性，但是，休谟并不否认归纳法对于人们的指导作用。作为一名经验主义者，休谟在生活中很推崇归纳法。
... 几百年来，哲学家们尝试想攻克“休谟问题”，比如康德，始终以失败告终。当然，也有一些成果。比如使用概率来解释归纳。虽然有“休谟问题”，虽然不能证明知识是必然正确的，但与休谟一样，我们还是使用归纳法来获得科学知识，因为这些科学知识很实用。

计算模型之一：递归函数
　递归函数论是由厄布朗、哥德尔、克林等发展起来的计算理论。

    三个初始函数：
    (1) s(x)＝x＋1  （后继函数）；
    (2) z(x)＝0     （零函数）；
    (3) Pj(n)(x1，x2，…，xn)＝xj  （射影函数）。
　　三个算子：复合算子，递归算子，取极小算子。
    由初始函数通过有限次使用算子可以构造的函数，称为递归函数。

常用函数
... 加函数可以如下递归定义：
f1(m,0)=m;
f1(m,n+1)=s(m+n);
... 乘函数可以如下定义：
f2(m,0)=z(m);
f2(m,n+1)=f1(m,f2(m,n));
... 减一函数可以如下定义：
　p(0)=0;
p(n+1)=n;
... 常用的函数，都可以这样定义出来。

计算模型之二：图灵机
... 它由一个控制器和一条两端可无限延长的工作带组成：
... 工作带起着存储器的作用，它被划分为无穷多个可写可擦的方格。
... 控制器则可以在带上左右移动，控制带有一个读写头，读写头可以读出当前方格内的符号，然后根据预先设计的状态转换指令，选择改写或抹去这一符号，然后选择往左移一格，往右移一格或者不移动，并进入下一个状态。当状态转换到停机状态，则停止运行。

图灵可计算函数
... 可以在图灵机上构造实现的函数，称为图灵可计算函数。以下函数都是图灵可计算的，大家可以思考一下具体的构造过程。
... 自然数如何编码？
... 零函数：
... 后继函数：
... 射影函数：
图灵机的计算能力等价于递归函数的计算能力
... 如何来证明递归可计算的函数，一定是图灵可计算的？
... 三个初始函数是图灵可计算的。
... 三个算子形成的复合函数也是图灵可计算的。
... 如何来证明图灵可计算的函数，一定是递归可计算的？
图灵机的优点
... 图灵机的计算能力与其他计算模型是等价的。
... 图灵机的优点是模拟人类的纸和笔的功能，比较符合人类对于“何为计算”的直观理解。
... 图灵机简洁的构造和运行原理隐含了存储程序的原始思想，深刻地揭示了现代通用电子数字计算机最核心的内容。

...（Knuth对算法的定义）算法是对特定问题求解步骤的一种描述。此外，算法的规则序列须满足如下五个条件：
... (1) 有穷性。算法必须总是在执行有穷步之后结束；
... (2) 确定性。算法的每一个步骤必须是确切地定义的；
... (3) 输入。算法有零个或多个输入；
... (4) 输出。算法有一个或多个输出，即与输入有某个特定关系的量；
... (5) 能行性。算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上都是能够精确地进行的，而且用笔和纸做有穷次就可以完成。

...算法设计的要求
...评价一个好的算法有以下几个标准:
...(1) 正确性(Correctness )   算法应满足具体问题的需求。
...(2)可读性(Readability)   算法应该好读。以有利于阅读者对程序的理解。
    (3)健状性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
...(4)效率与存储量需求   效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。
算法的表示
1、自然语言描述;
2、程序流程图描述 ;
3、N-S图描述;
    例如：求1＋2＋……+100之和

...算法的自然语言描述
1.sum赋初值为0;变量i赋初值为1；
2. 让i从1变化到100，执行以下循环：
  将i的值累加到sum中去。
3.输出sum中的值，即为所求的结果。

...算法的程序流程图描述

二、设计程序（Programming）
...一般地说，对任何一个问题，如果有了解决该问题的算法，就可以编制相应的程序。所谓程序，是一种事先编制好了具有特殊功能的指令序列。
...其中，指令既可以是机器指令，汇编语言指令，也可以是高级语言的语句命令，甚至未来还可能是用自然语言描述的运算、操作命令。
常见程序设计语言
1.  机器语言 (机器可以直接读懂）
指令格式：操作码＋地址部分
2.  汇编语言 (使用助记符,几乎和机器语言一一对应)
3.  高级语言（C、 Pascal、 Basic、    Foxpro、Fortune、perl ……)
4.  专门领域的开发语言:
(VHDL(电路板开发), Lisp (AI) ,Prolog (AI)…
5.   面向对象语言:
Visual C++, Visual Basic, Visual C#, Delphi, java

三、C 语言简介
1、C 语言的发展历史
C 语言的出现源自于计算机操作系统的编写
...69年 美国贝尔实验室研究员Ken Thompson 和Dennis M. Ritchie 用汇编语言编写Unix
...70年 为了提高程序可读性和可移植性，Ken在BCPL (Basic Combined Programming Language)语言基础上开发B语言；
...72-73 Denis在B语言的基础上开发了C语言

...73年 他们再次合作,用C重写了Unix
...78年 合著了《The C Program Language》
...87年 美国国家标准学会(ANSI)对C规范，成为国际标准。

2、C 语言程序的结构示例
#include <stdio.h> 　//头文件
void main()  //主函数
{
printf(“Hello World.”); //输出语句
}
例：求两个自然数的最大公约数。
解答：
  step1：分析问题
  step2：确定算法
  step3：算法描述
  step4：编码
  step5：调试运行

...算法的自然语言描述
1、输入x, y 的值，算法将求它们的最大公约数。
2、让minxy等于x与y的最小值。
3、让i从minxy变化到1，执行以下循环：
  如果i可以整除x和y，那么跳出循环。
4、输出i的值，即为所求。

＃include<stdio.h>
void main()
{
  int i, x,y, minxy;
  scanf(“%d%d”,&x,&y);
  minxy=x<y?x:y;
        for(i=minxy; i>=1;i--)
      if(x%i==0 && y%i==0) break;

  printf(“%d”,i);
}
以下使用欧几里德算法

...记gcd(x，y)为x与y的最大公因数。
...我们首先从函数gcd(x，y)的性质出发来求解。函数gcd(x，y)具有如下性质：
...(1) gcd(a，b)＝gcd(b，a)
...(2) gcd(a，b)＝gcd(―a，b)
...(3) gcd(a，0)＝|a|
...(4) gcd(a，b)＝gcd(b，a mod b)，
0≤a mod b＜b
例如：gcd(18,12)=gcd(12,6)=gcd(6,0)=6

...根据以上性质，我们可以设计如下算法：
1、 输入x，y；z是辅助变量；
2、 当y≠0，重复执行如下操作步骤：
         z←y，y←x mod y，x←z；
3、 输出x，算法停止．

例如：gcd(18,12)=gcd(12,6)=gcd(6,0)=6

＃include<stdio.h>  //宏定义，包含头文件
void main()
{
  int x,y, z;
  scanf(“%d%d”,&x,&y);//输入两数x,y
  while(y!=0)
    {
         z= y;
         y= x%y;
         x=z;
    }
    printf("%d\n",x);
}

上机环境（VC++ 6.0）简介
工作流程示意（简图）：