《信息（information）-天津大学》由会员分享，可在线阅读，更多相关《信息（information）-天津大学（54页珍藏版）》请在金锄头文库上搜索。
1、计算思维/“不插电”的计算机科学 CS4HS中小学师资培训项目,天津大学 软件学院 李春,目录,信息（Information）,计算机系统处理的大量数据被称为“信息” 需要一种度量信息的方法两图中的“信息量”并不相同,信息（Information）,如何度量“信息量”-“惊奇值” 对比如下信息 “我今天走路上学了”-“我今天打了直升飞机来上学” 1000页写满“废话 废话 废话”的纸 1000页的电话簿 500页的电话簿 1000页空白纸 所有的事物都可以成为消息,信息（Information）,1.Yes/No问题：用猜中消息的次数来衡量消息中的信息量 可以一人从1100中任选数字，由另一人
2、提问，前一人只能回答“Yes”或“No”，寻找得到答案的最少提问次数。 可借助下表和两枚硬币来标记区间,信息（Information）,1.Yes/No问题： 当数字范围扩大到1000，需要的猜测次数是多少？ 猜测次数并没有扩大10倍，扩大了多少？ 比如14次可猜中110000中的一个数字，这个消息中的信息量时14比特,信息（Information）,2.决策树 在决策树中用二进制数字代替“yes”“no”，猜中次数（信息量）就是二进制表示该数字所使用的比特数。 设计一颗决策树用以猜中015的目标数字。,信息（Information）,3.丢失的文字 用决策树的方法猜文本 单词“compter
3、”中缺少的字母，第一次猜什么？ 猜中字母的次数反映该字母信息量 计算机压缩文本的原理,信息（Information）,当消息出现的概率为，其信息量为-log2 如掷硬币反面出现概率为1/2，信息量为1 如消息出现的概率为1，信息量为0 信息理论（香农理论）对于理解和发展数据传输、生物学（基因信息）和化学（构造分子架构）的相关技术很有用。,程序设计（Programming）,在计算机中 词汇-指令-程序 由简单指令组合可以描述完成某项任务的复杂过程 程序：为了执行某个特定任务的指令序列 程序语言：指令和它们组合在一起的方式,程序设计（Programming）,依照指令行事： 依下列精确指令画出一
4、幅图像 1.在一张白纸的中间画一个点。 2.从白纸的左上角开始画一条直线，笔直的穿过这个点到达右下角。 3.从白纸的左下角开始再画一条直线，笔直的穿过这个点直到右上角。 4.在页面左边的三角形正中写下你的名字。,程序设计（Programming）,依照指令行事： 找两位同学A和B，A来描述B来画，A可以在B画的过程中观看和指导，然后互换角色，最后比较完成时间和质量。,程序设计（Programming）,依照指令行事： 其实用小元素如“画一条直线”、“画一个圈”，比用“画一个笑脸”更精确。程序语言就是使用简单的指令完成所有复杂的系统。 重复刚才的游戏，只能描述但是不能指导，画画的人可以提问。 重
5、复刚才的游戏，只能描述不能指导，画画的人也不能提问。-程序员编程的方式 这种方式产生的错误就是bug 软件使用前的测试就是寻找bug,程序设计（Programming）,介绍现有的程序设计语言 C、C+、C#、Perl、Python、PHP、Javascript、Basic、SQL 程序中的错误可能造成严重的后果 1996年，欧洲航空局斥资1亿元打造的阿波罗5号航空飞行器在发射后一分钟炸毁 有些程序庞大到很多人多年完成，没有人能够完全了解其结构,搜索（Searching）,查找是计算机的重要功能 数据集异常庞大 需要有效、快捷的搜索方式 算法：完成特定任务的方法，通常由一个指令序列来描述，即计
6、算机程序。,搜索（Searching）,快速算法很重要： 在Internet上找指定内容的网页 寻找货车投递包裹的最佳路径又要节省燃料 设计一天之内所有班级都有课程安排最合理的时间表 关键词：计算机需要搜索的数据,搜索（Searching）,1.线性搜索战舰 甲乙二人各拿25张写有随机4位数卡片 每人从手上挑选一张卡片作为自己的“战舰”并告诉对手这艘战舰的数字，然后洗牌并将卡片的背面朝上、乱序摊开在你面前，对手也要这样做 每人依次从对方那里选一张卡片翻开，第一个找到对方战舰的人胜利。 记录花费的次数 记录最少、最多的次数 第一次猜中的概率 平均多少次 如果数字不在卡片中要猜多少次 搜索时从头开
7、始找直到找到指定数据时查找结束的方法称为线性搜索 如超市共有10000件商品，计算机每秒扫描1000件商品条码，查看全部商品需要10秒钟,搜索（Searching）,2.二分法搜索战舰 由小到大排列战舰 从中间开始判断 如果秘密战舰的数字大于中间战舰的就到右半边继续搜索，否则到左半边继续搜索 重复这个过程直到找到或找不到 记录花费的次数 记录最少、最多的次数 第一次猜中的概率 平均多少次 如果数字不在卡片中要猜多少次 如超市共有10000件商品，计算机每秒扫描1000件商品条码，查看全部商品需要14次，两百分之一秒,搜索（Searching）,3.哈希法搜索战舰 将关键词分类 取每张卡片四位数
8、和的个位归类记录花费的次数 记录最少、最多的次数 第一次猜中的概率 平均多少次 如果数字不在卡片中要猜多少次 哈希法是最佳搜索算法，但它的速度取决于类别中对象的数量和类别的数量。 在计算机中类别的数量总是比每类包含的对象数量多，所以通过简单计算往往能直接锁定关键词储存的位置。,战舰2345-2+3+4+5=14-类4,搜索（Searching）,二分法搜索速度快，但不适合插入 二叉树搜索 哈希法的类被称为“桶”，在桶中使用线性搜索 二叉树搜索和哈希搜索被数据库广泛使用 信用卡 网站 哈希表的冲突 40人班级生日相同概率90% 57人班级生日相同概率99% 367人生日相同概率100% 7人（如
9、果生在同一月）生日相同概率50% 30个类7艘战舰冲突概率50% 365个类40艘战舰冲突概率90%,排序（Sorting）,计算机中有很多数据需要排序（时间、字母、数字、类型） 排序用于方便查找 计算机每一次只能对两个数据进行比较,排序（Sorting）,1.选择排序 使用天平、放有硬币或弹珠的胶卷盒甚至是卡片做道具 记录找到最轻物体的方法、次数 找到一个用来计算在n个重物中找到最轻被测物所需要进行比较次数c的公式 在排序算法中比较次数很重要体现算法效率，与算法耗费时间成正比 方法是： 选一个最轻重物放在一边 在剩下重物中挑选最轻的那个 重复上述步骤直到所有重物都被挑选出来,排序（Sorti
10、ng）,1.选择排序 随机排列的8个重物找到第一个最轻重物需要比较7次，找到次轻重物需要比较6次，依此类推，总比较次数为 7+6+5+4+3+2+1 该方法对1000个数据排序需要比较50万次,排序（Sorting）,2.插入排序 在一个未排序的序列中依次移出每个对象将他们插入到有序序列中正确的位置 随机挑出一个对象作为左侧有序序列中的第一个物品 从右侧未排序的序列中选择第二个对象用天平来决定它与第一个对象的大小 选取第三个对象，用天平来决定同前一次比较中较大者之间大小，如较大放在左侧序列的最右端，否则与第一个对象比较。 重复前面过程直到插入完成 记录比较次数 插入排序比选择排序快，对1000
11、个对象排序需要比较25万次,排序（Sorting）,3.冒泡排序 需要将整个序列反复扫描，并交换所有相对位置错误的相邻数据的方法。 效率不高，是排序算法中最差的一个。 易于理解。 用8个重物随机排列，演示冒泡排序 比较次数为7+6+5+1=28次,排序（Sorting）,三种方法的平均比较次数不同 最坏情况下比较次数都为n(n-1)/2 称为n2排序或二次排序法 如何计算1+2+3+1000,排的更快(Sorting Faster),插入、选择、冒泡排序法的效率相差无几 快速和归并排序法速度更快，对一百万个对象排序速度快20000倍,排的更快(Sorting Faster),1.快速排序 任取
12、一重物放在天平一端（称为“基准”pivot） 将剩下所有重物与之比较，轻的放在左侧，重的放在右侧，并将基准放在两组之间 对基准两侧的对象采用相同的方法“分裂” 重复上面的过程直到每组中只有一个对象 递归（recursion) 分而治之(divide and conquer),排的更快(Sorting Faster),2.归并排序 将待排序序列随机分成两组且两组对象数相同 对两组对象排序 仍然使用归并排序（分而治之） 对两组对象归并 不断移出两组对象最前端较小的那个记录对8个重物排序次数并比较不同方法,排的更快(Sorting Faster),要想使用好排序算法还应知道不同排序算法的存储方式 归
13、并排序法一般会合并大的数据序列，适合处理硬盘上的数据 快速排序法总是将数据移动到不同的位置，适合处理内存中的数据 快速排序法的平均比较次数为1.39nlog2n 归并排序法的平均比较次数为nlog2n 归并排序法需要占用大量临时空间，快速排序法更常用 美国2008年大选前，google采访奥巴马时问道“对一百万个32位整数进行排序的最佳方法”，回答道“冒泡排序法绝对不是正确答案” 实际上，冒泡需要比较499999500000次，快速需要20000000次，比冒泡快25000倍,并行排序（Sorting in Parallel）,计算机的速度已经接近极限 采用多个处理器同时处理问题的不同部分并行
14、计算 多核、网格、超级计算机 易于分解的问题，如图像处理 不易于分解的问题，问题中的各部分必须严格按照某一先后逻辑来处理 同时进行多次比较来让排序更快,并行排序（Sorting in Parallel）,1.排序网络 可以在地上画出排序网络，找6位同学一起玩，也可以用棋盘和6个棋子一个人来玩 每一步6个数字沿着箭头移到圆圈中比较，小的向上，大的向下 可多次测试看结果 每个数需要比较多少次 并行网络速度比单机系统快2倍，需要3倍数量的设备资源,并行排序（Sorting in Parallel）,1.排序网络 自己设计一个排序3个数字的网络？比较下面两个排序4个数字的网络哪个更快，为什么？判断右面
15、网络用处？,并行排序（Sorting in Parallel）,1.排序网络 判断下面方法能被加速吗？ 更多人用更多铁锹能将一个9米长的排水渠挖的更快吗？ 更多人用更多铁锹能将一个9米长的土壕挖的更快吗？ 做一顿饭的过程中哪些步骤可以并行操作，哪些不能？ 洗衣服的过程中哪些步骤能并行操作，哪些不能？,并行排序（Sorting in Parallel）,目前计算机科学家正在着手研究出能自动设计并生成排序网络的算法 用程序自动生成另一个程序 编译程序 对6个对象排序网络的测试需要720次 对象的不同排放顺序被称为排列,网络（Networks）,网络随处可见（电话网络、公共补给网络、计算机网络、交通
16、网络） 需要解决的问题 用最少的道路将房子连接起来 建立更高效而不是过多考虑如何节省网线的网络 节点 路由,网络（Networks）,1.泥泞城市 没有道路的城市下雨后非常泥泞 必须铺设足够的道路，让每个人都能从家里沿着铺好的道路到达别人的房子 所花费的经费越少越好（铺路用砖越少越好）,网络（Networks）,1.泥泞城市 3栋房子3条路，从A到C铺哪条路？ 从A到C怎么走？,A,B,C,3,2,2,网络（Networks）,1.泥泞城市 5栋房子，至少要铺哪些路？ 从A到D怎么走？ 从B到E怎么走？ 最小生成树(the minimal spanning tree) 图 节点,A,B,C,3,1,2,D,E,3,3,2,1,网络（Networks）,2.大一点的泥泞城市 找出铺设道路的最佳路径 画出这座城市对应的图结构,网络（Networks）,实际中的网络往往含有冗余 关节点、重连通图 最短路径（旅行商问题） 世界旅行商问题：寻找世界上1904711座不同城市的最佳访问路径（2002） 7524170.430千米-2002 7512218.268千米（被证明的下界）-2007 7515947.511千米-2008,
