数据结构 01 绪论.pdf

1.绪论 1.绪论 (a) 计算 (a) 计算 Computer science should be called  computing science, for the same reason  邓俊辉 why surgery is not called knife science. 邓俊辉 ‐E. Dijkstra deng@ deng@ 绳索计算机及其算法 绳索计算机及其算法 问题 输入：任给直线l及其上一点A 问题 输入：任给直线l及其上一点A 输出：经过A做l的一条垂线 输出：经过A做l的一条垂线 算法（2000 B.C. ，埃及人） 算法（2000 B.C. ，埃及人） 取12段等长的绳索，首尾联接成环 C 取12段等长的绳索，首尾联接成环 从A点起，将4段绳索沿l抻直并固定 从A点起，将4段绳索沿l抻直并固定 沿另一方向找到第3段绳索的终点 沿另一方向找到第3段绳索的终点 移动该点，将剩余的8段绳索抻直 移动该点，将剩余的8段绳索抻直   l B A 这里的计算机是什么？ 这里的计算机是什么？ l A 它能够解决什么问题？不能解决什么问题？ 它能够解决什么问题？不能解决什么问题？ Data Structures  Algorithms (Fall 2012), Tsinghua University 1 尺规计算机及其算法 尺规计算机及其算法 输入：平面上任一线段AB 输入：平面上任一线段AB A B 输出：将AB三等分 输出：将AB三等分  算法 从A发出一条与AB不重合的射线 算法 从A发出一条与AB不重合的射线 在上取AC = CD = DB 在上取AC = CD = DB B 联接BB 联接BB D 经D做BB的平行线，交AB于D 经D做BB的平行线，交AB于D 经C做BB的平行线，交AB于C 经C做BB的平行线，交AB于C C 这里的计算机是什么？ 这里的计算机是什么？ A