第六讲-数据与算法-邓俊辉.ppt

邓俊辉邓俊辉 ******@tsinghua. ******@tsinghua. 2017 2017 年年2 2月月 20 20日星期一日星期一数据与算法数据与算法 1 清华大学·电子信息科学与技术导引·数据与算法,邓俊辉 2 清华大学·电子信息科学与技术导引·数据与算法,邓俊辉 3 清华大学·电子信息科学与技术导引·数据与算法,邓俊辉数据数据+ + 算法算法= = 计算计算计算是求解问题的过程计算是求解问题的过程数据是计算的对象与产物,算法是计算过程的形式化描述数据是计算的对象与产物,算法是计算过程的形式化描述与理论与实践一样,计算也是探索自然规律与本质的重要形式与理论与实践一样,计算也是探索自然规律与本质的重要形式计算机作为计算的工具,古往今来无所不在,其本质大同小异计算机作为计算的工具,古往今来无所不在,其本质大同小异 4 清华大学·电子信息科学与技术导引·数据与算法,邓俊辉借助绳索的计算借助绳索的计算?输入:任给直线 l 及其上一点 A 输出:经过 A 做 l 的一条垂线?算法//2000 . ,埃及人取 12 段等长的绳索,首尾联接成环任取一结,固定于点 A //奴隶甲将 4 段绳索沿 l 抻直至点 B //奴隶乙沿另一方向找到第 3 段绳索的端点 C //奴隶丙移动点 C,直至其所有绳索抻直//奴隶丙...... ?这里的计算机是什么? lA lA B C5 清华大学·电子信息科学与技术导引·数据与算法,邓俊辉使用尺规的计算使用尺规的计算?输入: 平面上任一线段 AB 输出: 将 AB 三等分?算法从 A 发出一条与 AB 不重合的射线?在?上取 AC' = C'D' = D'B' 联接 B'B 经 D' 做 B'B 的平行线,交 AB 于D 经 C' 做 B'B 的平行线,交 AB 于C ?这里的计算机是什么? ?子程序:过直线外一点,做平行线?AB C' D' B'DC6 清华大学·电子信息科学与技术导引·数据与算法,邓俊辉图灵机图灵机纸带纸带读写头读写头规则集规则集字母表字母表 7 清华大学·电子信息科学与技术导引·数据与算法,邓俊辉数据数据是客观事物的符号表示、信息的载体是客观事物的符号表示、信息的载体源自生产实践、社会实践、实验观测或模拟计算 dare → datum → data (to give) →(something given) →(givens) 8 清华大学·电子信息科学与技术导引·数据与算法,邓俊辉数据的形式多种多样数据的形式多种多样 9 清华大学·电子信息科学与技术导引·数据与算法,邓俊辉数据数据究其本质,都可归结为数字究其本质,都可归结为数字... ... "All things are numbers." "God made the integers; all else is the work of man ."