计算机科学基础_4 - 算法，数据结构

算法入门

• 选择排序，Selection sort
• 大O表示法，Big O notation
• 归并排序 - Merge sort
• Dijkstra 算法

写指数函数，只是无数解决方案的一种，还有其它方案。
用不同顺序写不同语句，也能得到一样的结果，不同的是“算法”，意思是：解决问题的具体步骤。
即使结果一致，有些算法会更好。
一般来说，所需步骤越少越好。不过有时候也会关心其他因素，比如占多少内存。

“算法”一词来自 阿尔●花拉子密，1000多年前的代数之父之一。
如何想出高效算法，是早在计算机出现之前就有的问题，诞生了专门研究计算的领域，然后发展成一门现代学科，计算机科学。

选择排序

记载最多的算法之一是“排序”。比如给名字，数字排序。
排序到处都是，找最便宜的机票，按最新的时间排邮件，按姓氏排联系人等等，这些都要排序。
计算机科学家花了数十年发明了各种排序算法，还起了酷酷的名字，“冒泡排序”， “意面排序”，“选择排序”

比如：
一堆机票价格，都飞往目的地。把价格一组数据存放到一个数组结构。
先找到最小数，从最上面开始，然后和第一个比较，所以看最小的数是否变化，移动位置。重复循环比较，持续移动位置。
意味着，如果要排N个东西，要循环N次，每次循环中再循环N次，共N*N。

算法的输入规模和运行步数之间的关系，叫算法的复杂度。
表示运行速度的量级。
计算机科学家们把算法复杂度叫：大O表示法(big O notation)。

选择排序的算法复杂度O(n^2)效率不高。

归并排序

第一件事是检查数组大小是否>1，如果是，就把数组分成两半。再检查数组大小是否>1,如果是，继续分组，如果不是开始“归并”。
从前两个数组开始，读第一个（也是唯一一个）值，然后开始比较，如果更小，排在之前。重复这个过程，按序排列。然后数组大小增加，再次归并。
同样，取前二个数组，比较第一个数，然后再比较第一个数组的第一个数，第二个数组的第二个数。然后合并成更大有序的数组。
直到排序完整。

归并排序的算法复杂度O(n * logn)，n是需要比较+合并的次数和数组大小成正比，logn是合并步骤的次数。

图搜索

“图”是用线连接起来的一堆“节点”。可以想成地图，每个节点是一个城市，线是公路。
一个城市到另外一个城市，花的时间不同，可以用成本(cost)或权重(weight)来代称，代表要几个星期。
假设想找“高庭”到“凛冬城”的最快路线。
最简单的方法是尝试每一条路，计算总成本。这是“蛮力办法”。

假设用蛮力方法，来排序数组，尝试每一种组合，看是否排好序。
这样的时间复杂度是: O(n!),n是节点数，n!是阶乘。比O(n^2)还糟糕。

从“高庭”开始，此时成本为0，把0标记在节点里，其它城市标记成问号，因为不知道成本多少。Dijkstra 算法总是从成本最低的节点开始，目前只知道一个节点“高庭”，所以从这里开始，跑到所有相邻节点，记录成本，完成一轮算法。
但是还未到“凛冬城”，所以再跑一次Dijkstra 算法。
下一个成本最低的节点，是“君临城”，记录相邻节点的成本，到“三叉戟河”，然而想记录的是，从“高庭”到这里的成本，所以“三叉戟河”的总成本8+5=13。现在走另外一条路到“奔流城”，成本高达25，总成本33，但“奔流城”中最低成本是10，所以无视新数字，保留之前的成本10。现在看了“君临城”的每一条路还没到“凛冬城”所以继续。
下一个成本最低的节点，是“奔流城”，要10周。先看到“三叉戟河”成本，10+2=12，比之前的13好一点,所以更新“三叉戟河”为12，“奔流城”到“派克城”成本是3。10+3=13，之前是14，所以更新“派克城”为13。
“奔流城”出发的所有路径都走了遍，还没到终点，所以继续。
下个成本最低的节点，是“三叉戟河”。从“三叉戟河”出发，唯一没看过的路，通往“凛冬城”。成本是10加上“三叉戟河”的成本12，总成本是22。再看最后一条路，“派克城”到“凛冬城”，总成本是31。
所以最佳线路是：“高庭” -> “奔流城” -> “三叉戟河” -> “凛冬城”。

Dijkstra的语录：
“有效的程序员不应该浪费很多时间用于程序调试，他们应该一开始就不要把故障引入。”
“程序测试是表明存在故障的非常有效的方法，但对于证明没有故障，调试是很无能为力的。”

Dijkstra 算法算法复杂度是：O(n^2)经过改造的Dijkstra 算法复杂度减低为：O(n * logn + l) n是节点数，l是多少条线

数据结构

• 数组，Array
• 字符串，String
• 矩阵，Matrix
• 结构体，Struct
• 指针，Pointer
• 节点，Node
• 链表，Linked List
• 队列，Queue
• 栈，Stack
• 树，Tree
• 二叉树，Binary Tree
• 图，Graph

算法处理的数据，存在内存里的格式是什么。
希望数据是结构化，方便读取，因此计算机科学家发明了“数据结构”。

数组

数组Array，也叫列表(List),或向量(Vector)。有一些区别，在不同语言中基本类似。

数组的值一个个连续存在内存里。可以把多个值存在数据变量里，为了拿出数组中的某个值，要指定一个下标(index)
大多数编程语言中，数组下标都从0开始。
用方括号[]代表访问数组。

j = [5, 3, 7, 21, 82, 4, 19]
a = j[0] + j[5]

数组存在内存里的方式，十分易懂。
为了简单，假设编译器从内存地址1000开始存数组，数组有7个数字，像上图一样按顺序存。
写j[0]，会去内存地址1000，加0个偏移，得到地址1000，拿值: 5。
写j[5]，会去内存地址1000，加5个偏移，得到地址1005，拿值: 4。

数组的用途广泛，所以几乎所有的编程语言，都自带了很多函数来处理数组。

字符串

数组的亲戚是字符串String，其实就是字母，数字，标点符号等，组成的数组。

计算机怎么存储字符?
通过字符对应的ASCII表

写代码时，用引号括起来就行了: j = "STAN ROCKS"

虽然长的不像数组，但的确是数组。

注意：字符串在内存里以0结尾，不是“字符0”，是二进制“0”，这叫字符“null”,表示字符串结尾。
这个字符非常重要，如果调用print()函数，会从开始位置，逐个显示到屏幕，但是得知道什么时候停止下来。否则会把内存里所有东西都显示出来。0告知函数何时停下。

因为计算机经常处理字符串，所以有很多函数专门处理字符串。

矩阵

可以用数组做一维列表，但有时想操作二维数据，比如电子表格，或屏幕上的像素。那么需要 矩阵
Matrix。

可以把矩阵看成数组的数组，内存中的表示：

j = [[10, 15, 12], [8, 7, 42], [18, 12, 7]]

为了拿一个值，需要两个下标，比如j[2][1]，告知计算机在数组2里，位置是1的元素。

结构体

把几个有关系的变量存在一起，会很有用。多个变量打包在一起叫 结构体(Struct)
多个不同类型数据，可以放在一起。

这些数据在内存里，会自动打包在一起，如果写j[0],能拿到j[0]里的结构体，然后拿具体数据。

存结构体的数组，和其它数组一样，创建时就有固定大小，不能动态增加大小。还有，数组在内存中，按顺序存储。在中间插入一个值很困难。但结构体可以创造更复杂的数据结构，消除这些限制。

节点和链表

一个结构体，叫节点(Node)。它存一个变量，一个指针（pointer）
“指针”是一种特殊的变量，指向一个内存地址，因此得名。

用节点可以做链表(linked list)，链表是一种灵活数据结构，能存很多个节点（node）， 灵活性是通过每个节点指向，下一个节点实现的。

假设有三个节点，在内存地址1000,1002,1008。
内存地址隔开，可能是创建时间不同，它们之间有其它数据，可以看到第一个节点，值是7,指向地址1008，代表下一个节点，位于内存地址1008，来到下一个节点，值是112，指向地址1002，往下一个节点，地址1002的值是14的节点，这个节点，指回地址1000，也就是第一个节点，这个叫循环链表。
但链表也可以是非循环的，最后一个指针是0，null,代表链表的尽头。

当程序员用链表时，很少看指针具体指向哪里，而是用链表的抽象模型。

数组大小需要预先定好，链表大小可以动态增减，可以创建一个新节点，通过改变指针值，把新节点插入链表中。

链表也很容易重新排序，两端缩减，分割，倒序等。

因为灵活，很多复杂的数据结构都用链表。

最出名的是 队列(queue)和栈(stack)。

队列和栈

“队列”就像邮局排队，谁先来就排在前面。先进先出(FIFO)。
有个指针，指向链表的第一个节点，第一个节点是Hank，服务完Hank之后，读取Hank的指针，把指针指向下一个人，这样就把Hank“出队”(dequeue)了。

如果想加到队列里，“入队”(enqueue)。
要遍历整个链表到结尾，然后把结尾的指针，指向新人(Nick)。

只要稍作修改，就能用链表做栈，栈是后进先出(LIFO)。可以把“栈”想成一堆松饼，做好一个新松饼，就堆在之前的上面，吃的时候，是从最上面开始吃的。栈出入叫“入栈（push）”,“出栈（pop）”。

树

如果节点改一下，改成2个指针，就能做成树(Tree)
很多算法用了树，这种数据结构，同样程序员很少看指针的具体值，而是把树抽象成：

• 最高的节点叫做“根节点(root)”
• 根节点下的所有节点，都叫“子节点(children)”
• 任何子节点的直属上层节点，叫“父节点(parent node)”
• 没有任何“子节点”的节点，也就是“树”结束的地方，叫“叶节点(leaf)”。

其中有一个特例，节点就2个，叫“二叉树(Binary Tree)”。

节点可以用链表存所有的子节点。
“树”的一个重要性质是（不管是现实还是数据结构中）：“根”到“叶”都是单向的。

如果数据随意连接，包括循环，可以用“图”表示。这种结构，可以用有多个指针的节点表示，因此没有根，叶，子节点，父节点这些概念。可以随意指向节点。

不同数据结构使用于不同场景，选择正确数据结构会让工作简单。

图灵

• 可判定性问题
• Lambda算子
• 图灵机
• 停机问题
• 图灵测试

计算机科学之父，阿兰●图灵。
于1912年出生伦敦，从小就表现出惊人的数学和科学能力。
对计算机科学的建树始于1935年，他开始解决德国数学家提出的问题：可判定性问题，是否存在一种算法，输入正式的逻辑语句，输出准确的“是”或“否”答案？

美国数学家阿隆佐●丘奇于1935年首先提出解决方法，开发了一个叫“Lambda 算子”的数学表达系统，证明了这样算法不存在。
虽然“Lambda 算子”能表示任何计算，但它使用的数学技巧难以理解和使用。

图灵想出了自己办法来解决“可判定性问题”，提出了一种假想的计算机，现在叫“图灵机”。
图灵机提供了简单又强大的数学计算模型，虽然用的数学不一样，但图灵机的计算能力和Lambda 算子一样。同时因为图灵机更简单，所以在新兴的计算机领域更受欢迎。

图灵机是一台理论计算设备，有无限长的纸带，纸带可以存储符号，可以读取和写入纸带上的符号，还有一个状态变量，保存当前状态，还有一组规则，描述机器做什么。规则是根据：当前状态+读写头看到的符号，决定机器做什么。结果可能是在纸带写入一个符号，或改变状态，或把读写头移动一格，或执行这些动作的组合。

简单例子：
让图灵机读一个以0结尾的字符串，并计算1个出现次数，是不是偶数。如果是，在纸带上写一个1，如果不是，在纸带上写一个0。

首先要定义“图灵机”的规则：

• 如果当前状态是偶数，当前符号是1，那么把状态更新为“奇数”，把读写头向右移动。
• 如果当前状态为偶数，当前符号是0，意味着到了字符串结尾。那么在纸带上写一个1,并且把状态改成停机（halt），状态改为“停机”，是因为图灵机已完成计算。
• 还需要2条规则，来处理状态为奇数的情况：
  一条处理 奇数 + 纸带是0的情况
  一条处理 奇数 + 纸带是1的情况
• 最后，要决定机器的初始状态，定成“偶数”。

定义好了 起始状态+规则，就像写好了程序，现在可以输入了，假设把“1 1 0”放在纸带上，有两个1，是偶数。
规则只让读写头向右移动，其它部分无关紧要，为了简单留空。

图灵机开始运行：

1. 机器起始状态为“偶数”，看到的第一个数是1，符合第一条规则，所以执行对应的步骤，把状态更新到“奇数”，读写头向右移动一格。
2. 然后又看到1，但是机器状态是“奇数”，所以执行第三条规则，使机器状态变回“偶数”，读写头向右移动一格。
3. 现在看到0，并且机器状态是偶数，所以执行第二条规则。在纸带上写1，表示“真”的确有偶数个1。
4. 然后机器停机。

如果有足够时间和内存，可以执行任何计算，它是一台通用计算机。
只要有足够的规则，状态和纸带，可以创造任何东西。

所以，图灵机是很强大的计算模型。
事实上，就可计算和不可计算而言，没有计算机比图灵机更强大，和图灵机一样强大的，叫“图灵完备”。

每个现代计算系统，比如笔记本电脑，智能手机，甚至微波炉和恒温机内部的小电脑，都是“图灵完备”。

停机问题

为了回答可判定性问题，把图灵机用于一个有趣计算的问题：停机问题。
简单说就是：给定图灵机描述和输入纸带，是否有算法可以确定，机器会永远算下去还是会到某一点会停机？

有没有办法在不执行的情况，弄清会不会停机呢？一些程序可能要运行好几年，所以在运行前知道，会不会出结果很有用。否则就要一直等啊等，忧虑到底会不会出结果。图灵通过一个巧妙的逻辑矛盾，证明了停机问题是无法解决的。

想象有一个假想图灵机，输入: 问题的描述 + 纸带的数据，输出“yes”代表会停机，输出“no”代表不会停机。

推理：如果有个程序，H（halt的第一个字母）无法判断是否会“停机”，意味着“停机问题”无法解决。
为了找到这样的程序，图灵用H设计了另一个图灵机，如果H说程序会“停机”，那么新机器会永远运行（即不会停机），如果H的结果为No，代表不会停机，那么让新机器输出No，然后“停机”。

图灵机1（H）： 输出yes->停机， 输出no->不会停机
图灵机2：H（yes） -> 不会停机，永远运行， H（no）-> 机器停机，输出no

实质上是一台和H输出相反的机器，如果程序不停机，就机器停机。如果程序停机，就机器永远运行下去。

还需要在机器前面加一个分离器，让机器只接收一个输入，这个输入既是程序，也是输入。把这台新机器叫“Bizzaro(DC漫画的一名反派角色，他的能力和超人相反)”

如果把“Bizzaro”的描述，作为本身的输入会怎样，意味着在问H，当“Bizzaro”的输入是自己时，会怎样。
但如果H说“Bizzaro”会停机，那么“Bizzaro”会进入无限循环，因此不会停机。
如果H说“Bizzaro”不会停机，那么“Bizzaro”会输出No然后停机。
所以H不能正确判定，停机问题，因为没有答案，这是一个悖论，意味着“停机问题”不能用图灵机解决。

图灵证明了图灵机可以实现任何计算。
但是，“停机问题”证明了，不是所有问题都能用计算解决。

丘奇和图灵证明了计算机的能力有极限。
无论多少时间或内存，有些问题，是计算机无法解决的，计算是有极限的，起步了可计算性理论，称之为：“丘奇-图灵论题”。

图灵测试

当时是1936年，图灵只有24岁，在1939年，二次世界大战，图灵的才能很快被投入战争，事实上，在战争开始前一年，已经在英国政府的密码破译研究。工作之一，是破解德国的通信加密，特别是“英格玛机（Enigma）”加密信息。
简单说，英格玛机会加密明文，如果输入字母H-E-L-L-O，机器输出X-W-D-B-J，这个过程叫“加密”。
文字不是随便打乱的，加密由“英格玛机”顶部的齿轮组合决定。每个齿轮有26个可能位置，机器前面还有插板，可以将两个字母互换。总共有上十亿种可能。
知道正确的齿轮和插头的设置，输入 X-W-D-B-J就会输出hello，解密了这条信息。

有数十亿的组合，根本没法手工尝试所有组合。英格玛机和操作员不是完美的，一个大缺陷是：字母加密后绝不会是自己。H加密后绝对不是H。
图灵在前人的基础上，设计了一个机电计算机，叫: Bombe。利用了这个缺陷，它对加密消息尝试多种组合，如果发现字母解密后和原先一样，就知道英格玛机不会这样子做，这个组合会被跳过，接着试另一个组合，Bombe大幅度减少了搜索量，让破译人员把精力花在更有可能的组合，比如在解码文本中找到常用的德语单词。
德国人时不时会怀疑有人在破解，然后升级英格玛机，比如加一个齿轮，创造更多可能组合，甚至还做了全新的加密机，整个战争期间，图灵和同事都在努力破解加密，解密到德国情报，为盟军赢得了很多优势，有些史学家认为他们把战争缩短好几年，战后，图灵回到学术界，为许多早期计算机工作作出贡献。
比如曼切斯特1号，一个早期有影响力的存储程序计算机。但他最有名的战后贡献是“人工智能”。这个领域很新，直到1956年才有名字。

1950年，图灵设想了未来的计算机，拥有和 人类一样的智力，或至少难以区分。
图灵提出如果计算机能欺骗人类相信它是人类，才算是智能。这成了智能测试的基础，如今叫“图灵测试”

想象在和两个人沟通，不用嘴或面对面，而是来回发消息，可以问任何问题，然后会收到回答，但其中一个是计算机，如果分不出哪个是人类，哪个是计算机，那么计算机就通过了图灵测试。

这个测试的现代版叫：“公开全自动图灵测试，用于区分计算机和人类”，简称，验证码，防止机器人发垃圾信息等。

图灵于1954年服毒，年仅41岁。

由于图灵对计算机科学贡献巨大，许多东西以他命名，其中最著名的是“图灵奖”（计算机领域的最高奖项）。

• 可计算性理论
• 判定问题
• 电子计算机
• 人工智能
• 数理生物学
• 图灵试验
• 破解德国的著名密码系统英格玛机（Enigma）