【MIT 6.006】Lecture 1 Notes
本文件内容源自麻省理工学院开放课程资料平台，根据官方英文讲义翻译而成，由 ChatGPT 初步翻译，并经人工精校润色。打印版参见：https://linmoh.github.io/mit6.006/l1.html 算法导论：6.006 麻省理工学院 讲师：Erik Demaine、Jason Ku 和 Justin Solomon 讲座 1：导论 本课程的目标是教会你如何解决计算问题，并说明你的解决方案是正确且高效的。 问题 问题输入与正确输出之间的二元关系 通常不会为所有输入指定每一个正确输出（太多了！） 提供一个可验证的谓词（属性），正确输出必须满足它 6.006 研究的是大规模、通用输入空间上的问题 非通用：小输入实例 例子：这个房间里是否有两位同生日的学生？ 通用：任意大的输入 例子：给定任意 n 位学生，是否存在一对同生日的学生？ 若生日只在 365 天中选，对于 n > 365，根据鸽巢原理，答案一定为真 假设生日的精度超过 n（包含年份、时间等） 算法 一个过程：将每个输入映射到一个输出（确定性） 若算法对每个问题输入都返回正确输出，则称其解决了该问题 例子：一个解决同生日问题的算法 保持一个姓名和生日的记录（初始为空） 按某个顺序询问每个学生 ∗ 若生日已在记录中，返回这对学生！ ∗ 否则，将姓名和生日加入记录 若全部学生都询问完仍无结果，则返回 None 正确性 程序/算法是有限大小，如何证明其正确？ 对于小输入，可使用情况分析 对于任意大的输入，算法必须以某种方式使用递归或循环 必须使用数学归纳法（递归在计算机科学中的关键原因） 例子：生日匹配算法的正确性证明 对 k 归纳：记录中已有的学生数量 假设：若前 k 位中有匹配，算法在询问第 k+1 位前就返回 基础情况：k = 0，前 k 位无匹配 假设归纳假设对 k = k₀ 成立，考虑 k = k₀ + 1 若前 k₀ 位已有匹配，算法已返回（由归纳） 否则，若前 k₀ + 1 位有匹配，匹配一定包含第 k₀ + 1 位 那么算法直接检查第 k₀ + 1 位学生的生日是否已在记录中 效率 算法生成正确输出的速度有多快？ ...