模块 01：什么是计算？

书架上有四本书，你想知道《The Hobbit》在哪里。你可以沿着书架逐本阅读书名，找到后便停下来。这个简单过程已经包含计算的基本要素：信息、明确的问题、一系列步骤和结果。

计算是按照规则转换信息的过程。信息可以描述数字、文字、图像、动作或关系。计算机使用物理机器执行这些规则；人也可以用纸笔完成同一个小规模计算。计算机科学研究如何表示问题、构造并分析求解过程、组织系统，以及理解计算能做什么、不能做什么。

程序设计让我们用机器能够执行的形式表达一个过程。计算机科学还会追问：过程是否回答了正确的问题？是否一定结束？需要多少工作？如何融入更大的系统？即使换一种编程语言，这些问题仍然存在。

我们已经做出几项决定：顺序有意义，匹配必须完全相等，允许重复书名，未找到也有明确结果。“找一本书”本身并没有说明这些要求。消除这种歧义是计算工作的起点。

问题规约说明输入与输出之间应满足的关系。算法是实现这一关系的步骤。程序则用具有明确执行规则的编程语言实现这些步骤。同一个问题可以有多种算法，同一个算法也可以有多种程序实现。

假设是前置条件：开始执行前必须成立的条件。承诺的输出和输入不变性是后置条件：返回后必须成立的条件。它们共同构成操作的约定，也称契约。后续模块会把这一思想用于数据结构、网络协议和数据库事务。

用户可能希望“dune”也能匹配“Dune”。这需要新的匹配规则，例如不区分大小写。不能悄悄改变含义，却仍然声称遵守原来的约定。

线性搜索按给定顺序检查项目。伪代码表达步骤，而不依赖特定编程语言：

依次遍历从第一个到最后一个位置 i：
    如果位置 i 的书名等于目标：
        返回 i
返回 -1

最后一个返回语句仅在所有项目都检查完后执行。循环内部的返回会立即结束整个搜索。因此，即使书名重复出现，结果仍然是第一个匹配位置。

算法运行时具有状态，即描述当前执行位置所需的信息。本例中变化的状态包括当前位置；如果测量工作量，还包括比较次数。执行轨迹逐步记录这些状态。

这次执行不会检查第四本书。运行代码之前先预测轨迹，可以帮助你区分“我认为它会做什么”与“它实际做了什么”。

进行三次实验：查询 Dune，解释为什么不会访问索引 3；查询 Solaris，统计比较次数；选择空目录，解释为什么无需比较任何书名就能返回 -1。演示把“列表已经耗尽”单独显示为一步；这一步不属于书名比较。

例子展示某次具体执行，而推理需要覆盖满足约定的所有输入。后面会学习形式化证明；这里先使用一个简短的推理模式。

正确性：什么始终成立？

检查位置 i 之前，前面已经检查的位置都不包含目标。这是一条循环不变式，在循环推进时保持成立。开始检查索引 0 时，前面没有位置，因此成立。如果当前书名不匹配，把它加入已检查的前缀后，该性质仍成立。如果匹配，不变式说明前面没有更早的匹配，因此返回 i 满足约定。如果列表耗尽，说明所有书名都不匹配，返回 -1 也满足约定。

终止性：什么在推进？

对长度为 n 的列表，每次未成功匹配的迭代都前进一个位置。尚未检查的项目数减少一，并且不可能无限减少到零以下。找到匹配则会更早结束。因此，一个有限且搜索期间不变的列表能够保证终止。

工作量：先定义要统计的操作

我们把一次书名相等性检查作为统计单位。非空列表中，第一个位置就匹配时需要一次比较；最后一个位置匹配或目标不存在时，需要 n 次比较；空列表需要零次比较。项目数翻倍，最坏情况下的比较次数也翻倍。

这是一个模型，不是实际耗时。比较两个很长的字符串可能需要逐字符检查，因此当书名长度变化时，一次书名比较未必是常数时间。机器、实现方式和数据也会影响秒数。模块 05 将进一步区分这些概念并介绍大 O 表示法。现在要做到的是明确统计单位，并正确计数。

抽象保留任务所需的性质，同时隐藏其他细节。把目录看成有序列表，我们就能推理位置，而不必知道某台机器如何保存字符串。把搜索封装成函数，程序的其他部分就能使用结果，而不必重复搜索步骤。

抽象必须保留关键性质。若把有序列表换成没有有意义顺序的集合，“第一个索引”就失去含义。若只保留书名并丢弃作者，就无法在不增加信息的情况下查询作者。

运行脚本时，CPU 不会直接理解书名或“找到第一个匹配项”这句自然语言。语言实现和机器指令把这些含义连接到物理操作。你可以先学会推理搜索过程，再逐步学习底层机制。

这种分层也有助于定位故障：需求可能规定了错误的匹配规则；算法可能跳过索引 0；程序可能把 return -1 放进循环；运行环境可能无法打开文件。修改代码之前，先判断哪一层职责出了问题。

准备 Python 3.11 或更新版本、文本编辑器和终端。这些实验仅使用 Python 的基本功能，不需要安装第三方包，也不需要下载数据集。下载下面的脚本，或把代码复制到同名文件。在该目录的终端中运行 python lab1_trace.py。Windows 也可使用 py -3 lab1_trace.py；若系统中的命令名是 python3，则使用该命令。

"Dune" 这样的带引号值是字符串；方括号表示列表。for 重复执行缩进的代码块；enumerate 提供索引和项目；if 在条件成立时执行代码块；== 比较值；= 给名称赋值。缩进是 Python 语法的一部分。这里仅介绍实验所需记法，模块 03 会系统讲解程序设计。

目标：连接伪代码、状态与实际执行。时间：30 分钟。先预测会打印哪些行，再运行脚本，与下面实际运行捕获的输出比较。为方便对照，两种语言的页面使用相同的代码、书名和输出。

下载 lab1_trace.py

"""Module 01, Lab 1: trace a search, one comparison at a time."""

books = ["Dune", "Foundation", "The Hobbit", "Dune"]
target = "The Hobbit"
found = -1

for index, title in enumerate(books):
    print(f"inspect {index}: {title}")
    if title == target:
        found = index
        break

print(f"result: {found}")

inspect 0: Dune
inspect 1: Foundation
inspect 2: The Hobbit
result: 2

found = -1 在开始搜索前设置“未找到”结果。匹配后，break 退出循环，但最后的打印语句仍会执行。引号前的 f 允许把花括号中的值插入输出字符串。

1. 把目标分别改为 Dune 和 Solaris。运行前先写预测轨迹。
2. 设置 books = []，解释为什么循环体不执行。
3. 删除 break 后查询 Dune。为什么结果变成 3？违反了哪条约定？
4. 恢复原代码，解释“退出循环”与“从函数返回”的区别。

目标：检查空列表、缺失目标、边界位置与重复值。时间：35 分钟。def 定义函数；return 提供结果并结束本次调用；assert 在条件不成立时终止脚本。正常运行，不要使用会禁用断言的 Python -O 选项。

下载 lab2_contract.py

"""Module 01, Lab 2: make a contract executable with examples."""


def find_first(items, target):
    """Return the first matching index, or -1 if target is absent."""
    for index, item in enumerate(items):
        if item == target:
            return index
    return -1


cases = [
    ([], "Dune", -1),
    (["Dune"], "Dune", 0),
    (["Dune"], "Solaris", -1),
    (["Dune", "Solaris"], "Solaris", 1),
    (["Dune", "Solaris", "Dune"], "Dune", 0),
]

for items, target, expected in cases:
    actual = find_first(items, target)
    assert actual == expected, (items, target, expected, actual)
    print(f"{items!r}, {target!r} -> {actual}")

print("5 cases passed")

[], 'Dune' -> -1
['Dune'], 'Dune' -> 0
['Dune'], 'Solaris' -> -1
['Dune', 'Solaris'], 'Solaris' -> 1
['Dune', 'Solaris', 'Dune'], 'Dune' -> 0
5 cases passed

1. 解释这五个案例分别覆盖了约定的哪些部分。
2. 增加 (["Dune"], "dune", -1)，确认区分大小写的精确匹配。
3. 把 return -1 移入循环，放在 if 代码块之后。先预测哪些检查失败或结果改变，再运行。
4. 修复函数。增加一个检查，确认调用后输入列表没有改变。

目标：区分输入规模与一次执行的工作量。时间：35 分钟。脚本返回两个值：结果和比较次数。range(size) 产生从零到 size 之前的整数，不包含 size；list 把它们收集起来。同样的相等性搜索过程也适用于数字。+= 1 把计数器增加一。

下载 lab3_cost.py

"""Module 01, Lab 3: count comparisons instead of timing the computer."""


def search_with_cost(items, target):
    comparisons = 0
    for index, item in enumerate(items):
        comparisons += 1
        if item == target:
            return index, comparisons
    return -1, comparisons


for size in [0, 1, 4, 8, 16]:
    items = list(range(size))
    missing_index, missing_cost = search_with_cost(items, -1)
    first_index, first_cost = search_with_cost(items, 0)
    print(f"n={size:2}: absent={missing_cost:2}, first={first_cost:2}")
    assert missing_index == -1 and missing_cost == size
    assert first_index == (0 if size else -1)
    assert first_cost == (1 if size else 0)

n= 0: absent= 0, first= 0
n= 1: absent= 1, first= 1
n= 4: absent= 4, first= 1
n= 8: absent= 8, first= 1
n=16: absent=16, first= 1

1. 预测长度 32 的列表中两种查询的比较次数。
2. 使用目标 size - 1 增加最后一个位置的查询。size 为 0 时，目标仍不存在。
3. 在长度 16 的列表中查询目标 8。为什么需要九次比较？
4. 说明非空列表中最佳与最坏比较次数，并解释为什么单凭耗时不能证明这些公式。

先尝试，再展开解答。★ 表示直接应用，★★ 表示结合多个概念，★★★ 表示修改约定或构造推理。

def find_first_ascii_ignore_case(items, target):
    for index, item in enumerate(items):
        if item.lower() == target.lower():
            return index
    return -1

assert find_first_ascii_ignore_case(["Dune"], "dune") == 0
assert find_first_ascii_ignore_case([], "dune") == -1

选择答案查看反馈。分数统计已经回答的题目；重置后可以重做。如果禁用脚本，可以展开下方答案表。

阅读官方文档中的 Python 列表介绍，以及 for、range、break 和函数定义。重点阅读实验用到的结构，暂时跳过其他控制流特性。

写下为什么空列表执行零次循环，为什么 range 不包含终点，以及 return 的作用。然后解释这些语言规则如何支持搜索算法。这次阅读的重点是区分语言规则与问题要求。

现在你能把模糊的搜索请求变成明确约定，跟踪过程，解释为什么返回第一个匹配，说明它如何终止，并统计比较次数。你也能指出这次计算在计算机运行层次中的位置。

关闭页面，从记忆中写出伪代码。分别跟踪空列表、重复匹配和目标缺失的情况。解释哪个假设保证终止。如果某个解释不确定，先回到相应章节，再勾选最后一个学习时段。

下一模块是信息表示：位如何编码整数与文字，为什么某些数字无法精确表示。课程概览链接到全部 14 个模块。