无标题无名氏No.60466973

2023-12-08(五)17:47:18 ID: 22b93o1 (PO主)

https://y.music.163.com/m/song/4336908

归并排序为何是合理的？为什么这种方法可以将列表从小到大排序？也许许多人已经感觉出来了它的正确性，但是算法不需要感觉，只需要证明。

归并排序由两段重复组成：重复的分解和重复的拼接。分解这个步骤仅提供拼接的顺序，或者说“分解”本身就是对于这种拼接顺序的解释。

我们将这种重复的拼接定义为一种循环（loop）。循环就是不停地做一件事，在这里就是不停地以排序的方式合二为一。在每一个循环中，所有小的列表被两两相拼，使其数量减半，长度翻倍（在假设列表长度是2的次方的情况下）。

在循环的时候，我们希望每个被拼接的列表保持一个特质，那就是它们都是有序的，是从小到大排列的。这种在循环中保持的特性被称为“循环不变式（loop invariant）”。

我们用数学归纳法（如果不知道这个是什么，请先自行了解数论基础，或者试着直接理解以下内容）看看循环不变式在循环中有没有被保持。

在拼接开始的时候，每一个列表仅有一个元素。一个元素的列表我们在这里默认已经从小到大排序，所以循环开始的时候所有列表是有序的。

在每一个循环中，一个列表由两个小列表拼接而成。拼接方式是比较列表中数的大小，大的摆后面，小的摆前面，如前文所叙述的一样。通过这种摆法，我们保证了没有大的数在小的数前面，即列表在循环后依然有序。

循环的结束条件是所有列表归一。因为列表在拼接后始终有序，最后所得的列表也是有序的。

论证完毕，循环不变式成立，循环后可以得到有序列表。

列表在每个循环中慢慢变好，Getting Better all the time。

无标题无名氏No.60467010

2023-12-08(五)17:50:58 ID: 22b93o1 (PO主)

在每个循环中，我们以算法所规定的方式“维护”了循环不变式，使其保持而不是消失，而这个循环不变式保证了最后所得列表有序。

这种“维护”和对于数据结构的维护在本质上是一致的——利用某种方法来保证某一有用性质不消失。

无标题无名氏No.60579607

2023-12-18(一)23:47:36 ID: 22b93o1 (PO主)

http://music.163.com/album/2064268/

接下来，我会讲为什么我们要排序。

除了符合我们人类对于秩序的喜好外，一个排序的列表最大的特点是便于搜索。

在这里，搜索特指这个问题：输入一个数字n和一个列表l，能否从列表中找到一个元素的索引i，使该元素（标为l[i]，指代位于列表第i-1个的元素）和给定的数字n相等。如果列表中不存在和这个数字相等的元素，则输出-1以表示列表中没有匹配元素。

可以理解为，在一个图书馆（列表）里找到想要的书（数字）。

一个列表可以有重复的数字元素，输入的数字可能匹配到多个元素，此时只要找到任意一个对应元素所在的索引即可。

这里稍微谈谈索引的概念：元素在这个列表中从左到右排第N个，索引即为N-1。

或者我们可以这样理解：对于[1, 4, 1, 4]这个列表，l0[0,0]指代1，l1[0,1]为4，l2[0,2]为1，l2[0,3]为4。

为什么从0开始为列表中的元素标索引？现在我的解释是因为索引在计算机中也表示成二进制数字，而0000 0000显然比0000 0001更适合作为索引的开始。我们之后会从储存地址的角度做更严谨的解释。

我们现在使用的列表储存的都是数字，接下来可能会储存“不可能一样”的数据类型或者“用途一样，但储存在不同地方”的数据类型，在谈地址的时候也会更明确地谈论这一点。

搜索问题定义完成，我们继续谈论如何搜索。首先我们先看看对于一个无法通过前N项元素推断出第N+1项元素有何性质的列表（注意，这个定义比“随机数字”更加广泛和固定，我们可以不知道X岛的下一条回复是什么，但这个回复不会是根据某种分布随机生成的数字）来说该如何搜索。

最简单，最合适，最保守的搜索方式是从列表的第0个元素开始（从这里开始我们从索引的角度描述列表），将每个元素和输入的数字n比对。如果一样，就结束算法，输出目前元素所在的索引，如果不一样就比对下一个。这个索引可以通过保持一个变量，每搜索一次就进一位（increment）的方式维护。这是最初级的循环不变式：我们维护的这个变量在循环中一定等于目前比对过元素的索引。如果比对所有元素但没有输出过数字，则输出-1，因为全对比了也找不到匹配元素。

我们评估一下这种算法。在最差（即需要进行最多运算）的情况下，我们需要O(n)的时间复杂度来输出一个-1或者最后一个索引。不知道时间复杂度的，还是建议看算法导论或其他教程。

在最优情况下，我们只需要进行一次对比即可，时间复杂度为O(1)。

我们再从搜索空间（search space）的角度来看。搜索空间即答案可能处于的集合。换句话说，就是列表中可能和输入数字相等的元素。

在没有比对的时候，任何列表中的元素都有可能是我们想要的那个，但是我们不知道。此时搜索空间等同于列表。

在我们对比的过程中，我们确定了一些元素不可能和输入数字相等，那么搜索空间的大小就变小了，我们只需要从更小的空间中搜索元素了。当搜索空间为0，即没有元素的时候，我们一定能得到一个结果：这个空的搜索空间中不可能存在我们想要搜索到的元素。

在我们提到的一个个去对比的算法中，搜索空间在每一次对比后被删除一个元素，因为对比后我们知道这个元素不可能是结果（或者就是结果，那么我们可以直接结束算法）。初始搜索空间大小为n，每一次对比必定使大小减一。在越来越狭小的空间里，我们可以越来越逼近答案。

Hawkwind的In Search of Space专辑让我迷醉：一点太空，一点迷幻，一点硬摇滚。冷淡高傲的嗓音，宇宙般无处不在，平淡却宏伟的bassline，在深沉幻想中拨动的吉他riff，并不刻意去愉悦或者折磨耳朵的合成音，我不敢相信身处他们的live中该有多震撼。

无标题无名氏No.60579613

2023-12-18(一)23:48:21 ID: 22b93o1 (PO主)

专辑封面不能忘

无标题无名氏No.60639992

2023-12-25(一)00:23:38 ID: 22b93o1 (PO主)

https://y.music.163.com/m/song/22448942

对于一个从小到大排序的列表来说，我们有更好的方式来搜索这个列表：首先将要搜的数字n与列表最中间的第x/2个元素做比较，x为列表长度，即其所包含的元素个数（推荐没有接触过这种算法的读者先自行拟一个列表试一试下面的算法，可以让你快速理解那些让人头大但不得不写的原理阐述）。

如果n比这个元素小，则证明n在列表的第零个元素到第x/2-1个元素之间，因为这些元素小于等于第x/2个元素，而第x/2个元素大于n，换句话说，第x/2+1到第x个元素不可能存在n，因为n<第x/2个元素<第x/2+1和之后的元素；如果n比这个元素大，则n在第x/2+1到第x个元素之间。

如果n和第x/2个元素一样大...那我们已经找到了结果。

简而言之，对于目前的列表，将n与中间元素作比较，然后要么得到结果，要么抛去一半的列表得到新的“目前的列表”，不断重复直到得到结果。

这个算法叫二分算法（binary search），或者说折半算法。每一次比较，我们都可以将搜索空间减半，抛去一半必然不可能存在结果的元素。其时间复杂度为O(log(x))（这是什么意思？请自行参照书本）。

顺带一提，在这里，我们可以初步看到离散数学和连续数学的区别。对于一段数轴来说，你不可能通过这个算法在有限的时间内找到一个无理数，因为“日取其半，万世不竭”（为什么？提示：在数轴上随机选中任意数的可能性为0）；而对于一个存在有限个数字的列表来说，你可以将搜索空间不断折半，缩小到1，然后通过最后一次对比判断n是否在列表中，是否需要输出-1。

列表这个数据类型的特性是“读取列表中任意索引的元素都只需要固定的常数时间”，提取第0个元素和第x/2个元素消耗都是固定的，这也是支撑二分搜索时间复杂度为O(log(x))的前提条件。如果提取第x/2个元素需要一路扫过去，消耗时间大于提取第0个元素，这个算法就不是那么有效了。

为什么我们假设列表具有这样的特性？因为我们在现实中可以利用数据磁盘来做到几乎相同时间的读取，与列表性质吻合，所以这种假设所得的算法对于数据磁盘上的数据操作是有用的。“列表这种数据类型在现实中有用”的证明就涉及到计算机硬件了。

抛去不必要的东西这件事，本身就很有必要。就像Afraid to Shoot Strangers这首歌，精髓全在两段solo上，其他部分就显得可有可无了。

无标题无名氏No.60640070

2023-12-25(一)00:29:03 ID: 22b93o1 (PO主)

>>No.60639992
这一段的“数轴”，特指开始和结尾为有理数的数轴

无标题无名氏No.62933040

2024-06-30(日)17:31:12 ID: 22b93o1 (PO主)

https://y.music.163.com/m/song/20045591

除了排序后列表这种最基础的数据结构，算法界常用的数据结构还有树（Tree），图（Graph），哈希表（Hash Table，又名散列表），队列（Queue），栈（Stack），链表（Linked List）等。

其中，树可以被看做是满足特殊规则的图，队列和栈可以被看做是所带函数更加受限的列表。

但这不代表树就是比图更加“低端”，或者更加没用。原因主要有二：第一，人们更容易将树与一些应用联系起来，为这些应用设计或实现树的算法，并将图与另一种应用联系起来；第二，一个树常常比同等大小的图有更少的排列组合可能性，使得其在被筛选时复杂度更低，这就像瑞士军刀固然功能性多，但匕首用起来更干脆利落。

每一个数据结构都有一堆对应的，利用该数据结构特性的算法。因为各种数据结构的性质，有些适用于图的算法也可以用于树，适用于队列的算法也可以用于列表。

但可以用≠高效，毕竟如果不是要创造出对应的高效算法，何必多此一举创造出规则更特殊的数据结构呢？

在此，po不多赘述其他数据结构和对应算法，尽管知道它们对于了解计算机科学（和通过大厂笔试）来说是非常重要的。一个合格的程序员在看见一个问题的那一刻，心里就应该有几种备选的数据结构与算法方案。

对于这些数据结构和算法的研究也从未终止过，并且这些研究很多都在为所谓的PNP问题以及更难的类似问题做出贡献。由于这个问题非常难以表述，请读者自行查阅。理解PNP问题需要先理解常见算法与数据结构→集合论→图灵机与可计算性→逻辑与SAT问题→库克理论。

数据结构大家族就像马戏团，每个成员都以特殊——有时候看起来甚至可笑——的形式出现，但都有其不可替代的意义。

无标题无名氏No.63221477

2024-07-26(五)16:52:12 ID: 22b93o1 (PO主)

http://music.163.com/album/1603461

编程语言

人们对程序员的定义就是“能够使用编程语言达成预期目的的职业”。并且，计算机科学研究中非常神奇的一点就在于99%的研究成果可以直接用编程语言来复现。这种高效的理论-产品转化率也是计算机科学蓬勃发展的原因之一。

那么什么是编程语言？在了解编程语言之前，我们需要先知道什么是计算机科学范畴下的符号与语言。

>符号
语言由符号组成。从集合论的领域来说，我们称一个符号是它从属于的符号集Σ中的一个元素，符号集Σ是由符号组成的集合（听不懂就请先自行了解集合论基础理论）。

例如对于二进制语言来说，Σbinary={0, 1}。0与1为符号，Σbinary为二进制符号集。类似的，英语符号集包含了26个英语字母和英语标点符号。

符号集容纳了一个语言可能使用到的所有符号（文字）。一个由符号集Σ中符号构成的，任意长度排列组合叫做语句。例如，1001是二进制语言的一个语句，Rock&Roll是英语的语句。

在离散数学中，我们不是一笔一划地“写下”一个语句，而是从符号集中按顺序选择一个个符号来形成语句。

如果没有语法（grammar）限制，一个非空符号集所能构成的语句的集合Σ*中有无限个元素，并且所有只含某符号集内符号的排列组合都是该符号集的语句。但很可惜，我们有语法来规范什么语句是合法的，什么语句是非法的。

>语法
语法是任何将一个符号集中符号的排列组合分割为合法语句与非法语句的筛选规则。我们定义满足语法的语句是合法的，否则是非法的。一般来说，我们并不讨论非法的语句，除非我们想利用某种规则将其改成合法的。

例如，我们可以定义一种二进制语言的语法是必须要以1为开头，那么100是一句合法语句，而0110则不是。

语法也可以很复杂，特别是自然语言的。例如根据复杂的英语语法，I is fishes是不合法的，而Am I a fish?则是合法的。

一个语言可以有自下而上的数套语法一齐规范。例如在自然语言处理（Natural Language Processing，NLP）的理论中，英语有三重语法，分别是词义（lexical），句法（syntactic）和语义（semantic）。例如I am a waorker中含有错误拼写的词语，不符合词义语法。I a worker am并没有按主谓宾的结构排列，不符合句法。而I am a TV则在语义上没什么道理，只适合在前卫摇滚中出现。

我们想要有一种方式来系统化/自动化地判断一种符号的排列组合是否满足某语法。为此，我们发展/利用了许多理论，例如状态机（State Machine），无上下文语法（Context Free Grammar，CFG）等。利用基于诸如此类的理论所创造工具，程序可以自动判断你写的句子是否符合某种语法，甚至还能纠错。

>语言
我们定义语言为一套符号集与其对应的语法。取决于人们的需求，语言可以是二进制数字，中文，说出来的话，手语，音乐，图片，分子的理论运动轨迹（考虑到量子的离散性）等等等等，因为它们都是符号的排列组合，都可以用符号的排列组合来精准定义。

对于语言这种抽象概念的广泛存在，一些最早将前卫要素引入金属乐的人已经意识到了。音乐也可以是图片，或者文字。Images & Words.

无标题无名氏No.63247282

2024-07-28(日)21:26:58 ID: 22b93o1 (PO主)

https://y.music.163.com/m/song/1809425

>符号，数学与功能

我们已经知道了在程序员的语言学中语言是由符号集和语法组成的。接下来，我将简单聊聊为何如此定义语言，语言是如何做到编程的，编程语言是如何与我们想用其实现的功能所对应的。

在此之后，我们会深入到编程语言本身，讲述编程语言需要具有的性质，并由底层开始简述编程语言的运行原理（这一段只是为了让我不至于忘了下面该讲什么）

>哥德尔不完备定理，图灵机与可判定性问题

这一段涉及到一些与编程语言无关，但发展出现在我们使用的编程语言符号学的理论的历史。如果对此不感兴趣，可以跳过其中的大多数段落，包括这个回复的下面的所有内容。我会在编程语言强相关段落的开头加上###以让大家有选读的选择。

一切的一切都要从一个问题谈起，那就是可判定性问题（Entscheidungsproblem）。

1928年，大卫•希尔伯特（现代数学之父）与威廉•阿克曼（算法与大数领域的著名数学家）提出了可判定性问题：是否有一算法，输入任何命题，都能根据命题的普遍正确性输出“是”（该命题在任何情况下都正确）和“否”（该命题不是在任何情况下都正确）。

如果这样的算法存在，那么可以说所有数学问题都可以被证明或者证伪。不管是“素数是否有无限个”还是“是否任何大于2的偶数都能写作两素数之和”，都是可以在人类智慧的努力下推论出“是”或者“否”的正确答案的。

然而，哥德尔在1931年证明：只要命题基于正式的数学语言（准确来说，基于含皮亚诺算术公理的自洽形式系统），都存在无法被证明或证伪的可能性。这个定理被称为哥德尔不完备定理。

在计算机科学中有一个与可判定性问题类似的问题，叫做决定性问题（Decision Problem）。决定性问题泛指输入数据，根据数据输出“是”或者“否”的问题。例如输入一个数，输出这个数是否是素数；或输入一个列表，输出这个列表是否从小到大排列。

图灵与邱奇跟着在1936年几乎同时分别独立证明了并非所有决定性问题都（在图灵机的范畴下）存在对应的解决算法，他们使用的方法与哥德尔类似。

不管怎么说，数学与计算机的世界都因为这两个证明而变得残缺了。因为不管如何努力，总存在我们探寻的问题根本就不可解的客观可能性。

接下来，我会先讲哥德尔是如何通过符号与数字的转化来证明可判定性问题的不完备，再讲图灵是如何通过图灵机这种基于符号与集合的数学系统来证明世界上存在不能用算法解决的决定性问题的。

虽然哥德尔和图灵等人从根本上否定了许多科学家所做事业可能存在的意义，但这两个定理还是有一点好处的。

那就是，对于一个问题，科学家们可以理直气壮地说出：I Don't Know!