计算机科学基础/算法与程序
一个算法可以定义为解决特定问题的一组步骤。例如，厨师在准备特定类型的食物时可能会使用食谱。类似地，在计算机科学中，算法是用来创建程序的概念解决方案。重要的是要区分算法和程序。算法的实现被称为程序。
计算机是关于信息过程的。一旦信息使用不同的符号模式具体地表示出来，就可以对其进行处理以得出新的信息。我们了解到计算机在内部使用二进制系统将所有内容表示为比特序列 - 零和一。《比特爆炸》一书的第一章谈到了比特的数字爆炸，这是计算和技术创新的结果，这些创新使我们能够将信息转换为比特并以前所未有的速度进行共享。
创建信息过程是本章的主题。我们将了解到，信息过程始于对问题的概念解决方案，然后可以以机器可以理解的方式进行实现（编码）。概念解决方案称为算法，可执行的实现称为程序。
算法是一个相当花哨的名字，它代表一个简单的想法：解决问题的一步一步的解决方案。阿维·维格德森曾经说过，算法是自然、人类和计算机的通用语言。这个想法已经存在很长时间了。你已经熟悉了许多算法，比如系鞋带、冲咖啡、发送电子邮件，以及根据食谱烹饪菜肴。计算中的算法是为计算机设计的。想象一下，我们建造了一台可以执行第一章中描述的单一位加法过程的机器。回想一下，该过程使用简单的表格查找来执行加法。如果我们给机器两个数字并让它执行操作，它会返回两个数字作为答案。当然，输入和输出中的数字必须正确地表示（编码）。即使机器不理解加法，它也应该能够正确地执行加法。但是，机器不会执行加法，除非它被指示这样做。指示机器执行加法的命令（带输入值）称为指令。我们已经想象到，使用加法过程来创建其他更复杂的程序来执行更令人印象深刻的活动并不难。在我们能够创建这些程序之前，我们必须确定一个问题并找到一个概念解决方案。通常情况下，概念解决方案是可以通过人手工执行的解决方案。这种概念解决方案就是算法。
算法是计算机科学学科的核心部分。正如我们在第一章中讨论的那样，计算可以通过简单的设备盲目地或纯粹地机械地完成。任何计算（信息过程）的智能都体现在定义它的算法中。
为了使算法有用，它必须是正确的 - 步骤必须合乎逻辑，并且特定于机器可以执行的 - 并且必须是有效的 - 它必须在合理的时间内完成。算法的正确性和效率是算法研究中的两个关键问题。
研究算法使我们能够以概念的方式解决问题，而与执行解决方案的机器无关。算法必须以一种明确且人类可以理解的方式传达概念解决方案。用于描述算法的符号系统应该允许我们描述和推理纸上的想法。一旦在纸上验证了算法的正确性，就可以将其作为特定机器可以理解的程序来实现。
艾伦·图灵是第一个从数学角度研究算法的人，他创建了一个通用机器模型，后来被称为图灵机。他还证明了在某些情况下计算是不可避免的 - 我们必须对结果进行计算，这将计算与数学区分开来（计算机科学的诞生）。图灵机可以以标准形式表示/编码信息，并根据规则（算法）解释和更新表示，这也是表示的一部分。这个机器模型简单而强大。事实上，它是计算机科学家已知的，最强大的计算模型。图灵机可以执行我们所能构建的任何机器所做的任何计算。图灵机等价物是基于这个想法定义的。
图灵机模型使我们能够抽象地研究算法。例如，我们可以将每个算法视为一个状态机：算法总是从一个状态开始 - 由输入和内部信息的数据表示表示 - 并通过一系列状态移动到其最终状态，作为执行算法中规定的操作的结果。当可能的初始状态数量接近无穷大时，同一个算法可以生成可能无限多的计算。这解释了为什么很难通过测试来验证算法的正确性，因为初始状态可能太多，无法穷举枚举。
算法只是一组步骤，使我们能够解决特定问题。步骤是工作单元，它是明确的，并且可以在固定时间内完成。例如，将一壶水烧开是制茶过程/算法中的一个步骤。在计算中，我们处理信息的表示（数据），因此一个步骤可以是添加两个整数并将结果存储到变量中。我们将在后面解释如何定义和使用变量。
工作单元的定义取决于执行工作的代理能够做什么。计算中的算法必然会受到计算机器能力的影响。回想一下，算法必须以机器可以理解的编程语言实现/描述，然后机器才能执行该任务。存在许多不同的编程语言，因此表达相同算法的不同方式。特定机器唯一可以理解的语言称为机器语言。机器语言是用由零和一（二进制位）组成的指令编写的，因为计算机从根本上来说是能够操纵两种类型符号的机器。每种类型的机器都被设计为理解自己的本机语言——零和一的模式——因为它们的计算硬件可能非常不同。正如你能想象的那样，用机器语言编写程序可能非常困难。通常我们编写程序用高级语言表达我们的算法 - 接近自然语言的语言，例如英语。然后，我们使用工具（编译器和解释器）将我们用高级语言编写的程序翻译成机器语言，这类似于在国外旅行时使用个人口译员，因为我们不理解本机语言。要在不同的机器上运行同一个程序，我们只需重新编译它或使用不同的解释器。高级语言隐藏了机器之间的差异，使我们能够以机器无关的方式编写程序，这节省了大量时间。当我们用高级语言编写程序时，我们使用所有计算机都支持的抽象。例如，如果高级语言允许表达加法，我们假设所有计算机都可以做到。
编程语言（高级或机器级）是用于向机器表达算法的工具。当我们创建算法来概念化地解决问题时，我们希望使它们独立于语言。一个设计良好的食谱应该适用于不同厨房的不同厨师。因此，工作步骤或工作单元必须用更高的抽象来定义——所有语言都支持的一组通用数据结构、操作和控制结构。通过使用抽象概念化地创建算法，允许我们人类在更接近我们所知的问题域的更高层次上思考。当算法在特定语言中实现时，抽象步骤可以映射到语言中的特定表达式。我们有信心我们拥有的工具链可以将解决方案转换为机器级可执行代码。下图显示了相同的算法可以在多种编程语言中实现，并且生成的程序可以在不同的机器模型上执行（可能经过一些转换）。
以下是我们可以假设所有高级语言都支持的常见操作和控制结构
- 数据结构：单值变量和值列表。
- 操作：算术运算、比较和关系运算（和、或和非）
- 控制结构：顺序（一个接一个）、条件（根据条件选择）和重复
这里是一个用伪代码（自然语言）定义的算法。该算法查找数字列表中的最大数字，步骤如下：
- 将最大值（一个变量）设置为列表中第一个数字的值（存储和检索值）。
- 遍历列表，一次比较一个数字与最大值，如果该数字大于最大值，则用该数字替换最大值（条件和重复）。
- 存储在最大值中的值就是答案。
我们知道该解决方案是正确的，因为它很简单。我们知道如何手动执行它，但我们当然不会使用伪代码中表达的过程来解决问题。有必要以这种详细的方式设计和表达算法以供计算机使用。请记住，计算机是机械地执行计算的机器，因此指令必须是特定的。即使伪代码使用自然语言，也必须使用前面提到的对计算机通用的结构（数据结构、操作和控制结构）。您可能想知道为什么我们不能要求计算机查看整个列表并像我们人类一样识别出最大的数字。计算机是简单的机器，不会思考。它们被设计为执行简单的操作，例如通过符号操作添加两个数字。即使我们作为人类，也无法扫描一个长列表，比如一百万个数字，并一眼找到最大的数字。我们编写的算法必须用计算机可以做的事情来表达，并且可以扩展到任意大小的输入（数据集）。我们刚刚研究的算法可以处理任何大小的列表。事实上，对于计算机来说，列表有三个数字还是三百万个数字几乎没有区别。
另一种表达相同算法的方法是使用称为流程图的图形符号。
该图表更清晰地显示了解决方案的逻辑。有两个条件——检查条件和作为结果采取的相应操作。最上面的条件定义了一个重复（循环），因为它们是一个无条件的分支，回到条件，如没有标签的箭头所示。
伪代码和流程图都描述了对同一个问题的相同解决方案。它们是同一个想法的不同表现形式。下图显示了该算法在 Scratch 中的实现。
如您所见，算法的具体实现必须使用特定实现语言中可用的构建“块”。图中没有显示的是从文件或用户输入填充列表的部分。代码的结构类似于流程图。
总之，构建和研究算法允许我们以与语言和计算环境无关的方式研究（算法）问题的解决方案。我们可以使用“查找最大数字”算法作为单个块来形成更复杂的算法，但我们需要记住这个块不是一个工作单元，因为涉及的步骤数量取决于输入大小（列表的长度）。我们将在未来讨论函数分解（使算法简单）和算法复杂度分析（计算算法的成本）时重新讨论此主题。
程序 每个软件程序归根结底都包含两个组件——数据（结构）和算法。我们将研究计算机科学中的一些基本算法和数据结构。
按照这个http://csunplugged.org/sites/default/files/activity_pdfs_full/unplugged-02-image_representation.pdf 图像表示活动来了解图像如何在传真机中编码、传输和复制。
按照这个http://⁰csunplugged.org/sites/default/files/activity_pdfs_full/unplugged-04-error_detection.pdf 错误检测活动来了解算法如何检测并纠正单个位错误。
一个类似的算法，Luhn 算法，用于验证信用卡号码。
文本压缩 是计算中的另一项重要任务。以下活动演示了压缩算法的工作原理：http://csunplugged.org/sites/default/files/activity_pdfs_full/unplugged-03-text_compression.pdf
为什么搜索很重要？我们每天都在做。这也是一项好生意。谷歌的使命是整理世界信息并使其普遍可访问和使用。显然，能够快速找到我们需要的 信息非常有用且有利可图。
我们可以通过顺序遍历信息列表并检查每个信息来始终找到一条信息。你能用伪代码或流程图符号描述算法吗？结构上，该算法应该类似于“查找最大数字”算法。该算法需要两个输入：列表和我们要查找的目标项目。重复步骤是获取下一个项目并将其与目标进行比较。用于比较的信息也称为键，因为它决定搜索是否成功。例如，如果我们有一个学生列表，我们可以按姓氏、出生日期或鞋码来搜索学生，这些都是搜索键。
顺序搜索很简单，但如果我们经常需要执行它，则成本可能很高。但是，如果列表按搜索键排序，我们可以利用数据的这种排序属性来使用更好的算法。想想一本教科书的索引、电话簿或字典。它们都是以某种方式排序的。例如，电话簿中的家庭电话号码通常按所有者的姓氏排序，而商务电话号码按商务类型排序。字典或教科书的索引中的条目按字母顺序排序。当我们搜索信息时，这种有序性如何帮助我们？它允许我们估计搜索目标的位置。 数字猜测游戏很好地说明了这个想法。如果数字列表是随机的但按升序排序，我们总是可以猜测目标数字位于搜索范围的中间（最初是整个列表）。如果我们运气不好，我们可以消除一半的候选者——如果中间的数字大于搜索目标，新的搜索范围将是先前搜索范围的前半部分，否则是后半部分。想象一下比较次数的减少！我们将在讨论算法复杂度时详细研究该算法。
请观看以下视频 算法如何塑造我们的世界。你能解释算法正在以哪些方式塑造我们的世界吗？
在计算的世界里，我们通过量化信息来存储和处理数据（信息的表示）。这种量化过程将世界简化为可计数和可衡量的事物，并强调抽象和效率（速度）。我们不能被现实的抽象所迷惑，认为它们就是真实的世界，就像抽象主义那样。正如弗雷德里克·布鲁克斯警告我们，“模型是对现实世界中令人恐惧的复杂问题的有意简化，以帮助我们解决问题。地图并非地形。”