计算机科学基础
算法与程序
算法的定义
算法可以定义为解决特定问题的一组步骤。例如，厨师在准备特定类型的食物时可能会使用食谱。同样，在计算机科学中，算法是用于创建程序的概念性解决方案。需要明确区分算法和程序：算法的实现被称为程序。
定义信息处理
计算机的核心在于信息处理。一旦信息被用不同符号模式具体表示，就可以对其进行处理以推导新信息。我们了解到，计算机内部使用二进制系统将所有内容表示为比特（0 和 1）的序列。《Blown to Bits》第一章提到了由于计算和技术的创新，数字化信息爆炸导致我们可以以前所未有的速度将信息转换为比特并共享。
创建信息处理
本章的主题是创建信息处理过程。我们将学习，信息处理始于问题的概念性解决方案，随后可以以机器可理解的方式实现（编码）。这些概念性解决方案称为算法，而可执行的实现称为程序。
什么是算法？
算法是一种逐步解决问题的方法。著名计算机科学家 Avi Wigderson 曾说，算法是自然、人类和计算机之间的共同语言。这一想法由来已久，你可能已经熟悉许多算法，例如系鞋带、煮咖啡、发送电子邮件或根据食谱烹饪菜肴。
算法在计算中的作用
在计算中，算法是为计算机设计的步骤。例如，想象一个能执行第一章中描述的单数字加法的机器。该机器通过简单的查表操作完成加法，但它需要明确的指令来执行这些操作。这些指令（包括输入值）称为指令。复杂算法通常从简单算法开始，通过一步步组合形成更多复杂的过程，而这些过程都始于对问题的概念性解决方案，也就是算法。
为什么要学习算法？
算法是计算机科学的核心。正如第一章讨论的那样，计算可以通过简单设备盲目地或纯机械地完成。任何计算过程的智能都在于定义它的算法。
关键点
- 正确性：算法的步骤必须逻辑清晰且特定，以便机器执行。
- 效率：算法必须在合理的时间内完成任务。
正确性和效率是算法研究的两个关键问题。
程序是算法的实现
学习算法使我们能够在概念层面上解决问题，而不依赖具体执行解决方案的机器。算法必须以明确且易于人类理解的方式传达解决方案。通过一个符号系统描述算法可以让我们在纸上推理和验证想法。一旦算法的正确性在纸上得到验证，就可以实现为特定机器可理解的程序。
算法的正式定义
图灵机模型
阿兰·图灵是第一个用数学方法研究算法的人，他创建了一个通用机器模型（后被称为图灵机）。他还证明了在某些情况下计算是不可避免的，这将计算与数学区分开来（也标志着计算机科学的诞生）。
图灵机能够以标准形式表示/编码信息，并根据表示中包含的规则（算法）解释和更新表示。这个模型虽然简单，但非常强大，实际上是已知的最强大的计算模型。图灵机可以执行任何已知机器能够完成的计算，这一特性奠定了图灵等价的定义。
算法的抽象研究
图灵机模型让我们能够在抽象层面研究算法。例如，可以将每个算法视为一种状态机：
- 算法总是从某种状态开始（由输入和内部信息的表示组成）。
- 执行算法中定义的操作后，状态逐步变化，最终达到结果状态。
当初始状态的数量接近无穷时，同一个算法可以生成潜在的无限计算结果。这也解释了为什么通过测试验证算法的正确性如此困难，因为初始状态的数量可能多到无法穷举。
通过学习算法，我们不仅能更有效地解决问题，还能更深入地理解计算的本质，这在计算机科学中具有核心意义。
定义算法
算法的基本概念
算法是一组允许我们解决特定问题的步骤。每个步骤是一个明确的工作单元，并且可以在固定时间内完成。例如，“将一锅水烧开”是制茶过程中的一个步骤。在计算中，我们处理的是信息的表示（数据），因此一个步骤可以是“将两个整数相加并将结果存储到变量中”。我们稍后会解释如何定义和使用变量。
工作单元的定义
工作单元的定义取决于执行工作的主体（代理）能够做什么。在计算中，算法的设计必须符合计算机的能力。算法必须用计算机可理解的编程语言实现或描述，计算机才能执行任务。
编程语言与机器语言
-
机器语言
每台计算机的唯一可理解语言是其机器语言，由零和一（比特）组成的指令构成。这是因为计算机本质上是操作两种符号的机器。不同类型的机器有不同的硬件，因此机器语言也不同。直接用机器语言编写程序非常困难。 -
高级语言
通常，我们用高级语言（接近自然语言的语言，如英语）来编写程序以表达算法。然后，使用编译器或解释器将高级语言翻译成机器语言，就像出国旅行时使用翻译工具一样。同一个程序可以通过重新编译或使用不同的解释器运行在不同的机器上。高级语言隐藏了机器之间的差异，使我们可以独立于机器编写程序，从而节省大量时间。
抽象与通用性
编程语言（无论高级还是机器语言）是用来向计算机表达算法的工具。然而，当我们在概念上创建算法以解决问题时，希望算法独立于具体语言。例如，一个设计良好的食谱可以适用于不同的厨师和厨房。因此，步骤或工作单元需要在更高的抽象层面上定义——一个由所有语言支持的通用数据结构、操作和控制结构组成的集合。
通过使用抽象以概念化方式创建算法，能让我们以更接近问题领域的高级思维进行设计。一旦算法用某种语言实现，抽象步骤可以映射到该语言的具体表达。工具链可以将解决方案翻译成机器可执行代码。
支持的常用结构
以下是所有高级语言支持的常用结构：
- 数据结构：单值变量和值的列表。
- 操作：算术运算、比较操作和关系运算（如 and、or 和 not）。
- 控制结构：顺序（依次执行）、条件（根据条件选择性执行）和重复（循环）。
示例算法
以下是用伪代码（自然语言）定义的算法：找到数字列表中的最大值，步骤如下：
- 将变量
max设置为列表中第一个数字的值（存储和检索值）。 - 遍历列表中的每个数字，与
max进行比较。如果当前数字大于max，则将max替换为当前数字（条件和重复操作）。 - 存储在
max中的值即为结果。
算法分析
- 正确性
我们知道该算法是正确的，因为它非常简单且直观。我们可以手动完成这个过程，但通常不会以这种形式解决问题。对计算机来说，必须以这种详细的方式设计和表达算法，因为计算机是机械执行计算的机器，因此指令必须明确。 - 计算机的局限性
计算机无法像人类一样直接“看”整个列表并找到最大值。计算机是简单的机器，只能执行诸如通过符号操作将两个数字相加等简单操作。即使对于人类，要从一百万个数字的列表中“一眼”找到最大值也不可能。因此，算法必须以计算机可执行的方式表达，并且能适应任意大小的数据集。 - 可扩展性
这个算法适用于任意大小的列表。对于计算机来说，无论列表包含三个数字还是三百万个数字，差别都很小。
总结
算法的定义和设计必须基于计算机的能力，同时以清晰和抽象的方式表达，以确保它们既正确又高效。通过设计良好的算法，可以为不同的问题提供通用的解决方案。
用流程图表示算法
另一种表示同一算法的方法是使用一种图形化表示法——流程图。
流程图解析
该流程图展示了如何找到数字列表中最大值的步骤。
- 流程图更清晰地显示了解决方案的逻辑。
- 它包含两个条件判断：一个是检查条件，另一个是根据结果采取相应的操作。
- 顶部的条件判断定义了一个循环，因为有一个无条件的回到条件判断的分支（通过没有标注的箭头表示）。
伪代码与流程图
伪代码和流程图描述的是同一问题的同一解决方案，它们只是对同一思想的不同表示方式。
算法的具体实现
以下展示了用 Scratch 语言实现该算法的示例：
- 该实现使用了 Scratch 提供的构建块来实现算法。
- 示例中未显示的是从文件或用户输入中填充列表数据的部分。
- 代码的结构与流程图类似。
构建与研究算法的意义
- 通用性
构建和研究算法使我们可以在中立于语言和计算环境的情况下解决问题。例如，“找到最大值”算法可以作为一个模块构建更复杂的算法。 - 注意事项
需要记住，这个模块并不是一个固定的工作单元，因为所需步骤的数量取决于输入大小（列表的长度）。在将来讨论功能分解（保持算法简单）和算法复杂度分析（评估算法成本）时，我们会重新探讨这一点。
程序：数据与算法的结合
每个软件程序都由两部分组成：
- 数据（结构）
- 算法
在计算机科学中，我们将学习一些基本算法和数据结构。
示例算法
-
图像编码/表示
可以通过 图像表示活动 了解传真机如何编码、传输和再现图像。 -
错误检测
通过 错误检测活动 学习算法如何检测和纠正单比特错误。例如，Luhn 算法被用来验证信用卡号码。 -
文本压缩
文本压缩是计算中的另一个重要任务。通过 文本压缩活动 学习压缩算法的工作原理。 -
搜索
为什么搜索很重要？
搜索在我们的日常生活中无处不在，同时也是一项重要的商业活动。例如，Google 的使命是“组织世界的信息，使其普遍可访问且有用”。显然，能够快速找到我们需要的信息既非常实用，也极具商业价值。
顺序搜索
一种直接的方法是顺序检查列表中的每一项来找到信息。- 描述：这种算法可以用伪代码或流程图来描述。从结构上看，这种算法与“寻找最大值”的算法类似。
- 输入：算法需要两个输入——一个列表和我们要查找的目标项。
- 步骤：重复操作包括获取列表中的下一个元素并将其与目标项进行比较。
- 搜索键：用于比较的部分信息被称为“搜索键”，它决定搜索是否成功。例如，在学生名单中，可以通过姓氏、生日或鞋码作为搜索键。
尽管顺序搜索简单直观，但如果需要频繁进行搜索，这种方法的成本可能很高。
优化搜索：利用排序特性
当列表按照搜索键排序时，可以利用数据的有序特性采用更高效的算法。例如：- 书的索引：条目通常按照字母顺序排列。
- 电话簿：家庭电话号码通常按所有者姓氏排序，商业电话号码则按业务类型排序。
- 字典：条目按字母顺序排列。
排序带来的优势
排序让我们可以大致推测目标的位置。例如：- 假设一个递增排序的数字列表，我们可以猜测目标数字可能在搜索范围的中间位置。
- 如果中间数字大于目标数字，可以排除后半部分；否则排除前半部分。
二分搜索的效率
这种方法显著减少了比较的次数。例如：- 初始搜索范围是整个列表，但每次比较后范围缩小一半。
- 通过这种方式，大大提高了搜索效率。
数字猜测游戏的类比
二分搜索的思想类似于“数字猜测游戏”。在递增排序的数字列表中：- 每次猜测目标数字位于当前范围的中间。
- 如果猜测不正确，可以将搜索范围缩小到一半。
这种方法通过减少候选项的数量显著提高了搜索效率。我们将在研究算法复杂度时详细探讨这一算法。
社会影响
请观看视频“算法如何塑造我们的世界”。思考算法如何在多个方面改变我们的生活。
算法与现实的抽象
在计算领域，我们通过量化信息存储和处理数据。量化过程将世界简化为可计数和可测量的内容，并强调抽象与效率。然而，正如 Frederick Brooks 警告的那样：“模型是有意的简化，用于帮助我们应对现实生活中复杂的问题。地图并非地形。”我们不能被抽象迷惑而认为它就是现实。