不插电计算机科学中文版.pdf

不插电的计算机科学 董荣胜主持编译 计算思维及应用研究室 桂林电子科技大学 2008 年10 月 桂电“计算机科学导论”参考资料 （内部资料，仅供学习参考之用） 不插电的计算机科学 不插电的计算机科学（Computer Science Unplugged，简称Unplugged 项目） 是Tim Bell, Mike Fellows and Ian Witten 领导的一个非赢利性项目，在很多国家 都有捐助者（包括新西兰、美国、瑞典、澳大利亚、中国、韩国、台湾和加拿大）。 团队包括的成员或关键组织的成员有 ACM K-12 委员会、ACM 课程委员会、 CSTA （CS 教师协会），也包括那些将此项目作为他们研究的校长、教师、大学 outreach coordinators ，研究生等。它链接到Google 赞助的CS4ALL 项目（UW、 CMU 和UCLS ），并将为一些项目提供资源和支持，如NCWIT （National Center for Women Information Technology ，妇女与信息技术国家中心）和 TECS(Teacher Enrichment in Computer Science，计算机科学教师强化) 。现在正在 建立一个国际顾问团队为该项目提供指导，包括K-12 教育的代表（小学和中学）， 专业团队（如ACM 、CSTA ），国际捐助者（如Google、Microsoft ）。 Unplugged 项目在全世界已经实施超过 16 年了，可以在教室、科学中心， 家里，甚至是公园的游园活动中进行。其主要目标是将计算机科学（以及通常的 计算）作为一种有趣的、迷人的、智力上刺激的学科，从而向年轻人推广。该项 目希望激发人们的想象力，并希望表达那些不依赖于特定软件或系统的基本原理 以及那些到2020 年仍不会过时的概念。Unplugged 项目适合所有年龄段的人， 从小学到大学，可以跨越国界和文化背景。通过该项目可以实施踏平高科技教育 解决方案难以实施的障碍，跨越资讯富有和资讯贫乏之间、发达国家和发展中国 家之间的鸿沟。 1 目 录 活动1 进位的计算--二进制数…………………………………………1 活动2 数字表示色彩— 图像表示…………………………………… 6 活动3 文本压缩……………………………………………………… 11 活动4 卡片魔术—检错与纠错……………………………………… 14 活动5 20 次猜测——信息理论……………………………………… 18 活动6 战舰--搜索算法……………………………………………… 23 活动7 排序算法……………………………………………………… 39 活动8 敲钟——排序网……………………………………………… 45 活动9 泥泞的城市—最小生成树…………………………………… 50 活动10 橙子游戏--网络中的路由和死锁……………………………54 活动11 寻宝——有限状态机…………………………………………57 活动12 排序——编程语言……………………………………………65 活动13 贫穷的制图师——图形着色…………………………………68 活动14 旅行城镇——支配集…………………………………………77 活动15 冰冻之路—Steiner 树…………………………………………82 活动16 分享秘密——信息隐藏协议…………………………………91 活动17 秘鲁人掷硬币问题——密码协议………………………… 94 活动18 公钥加密…………………………………………………… 102 活动19 巧克力工厂人性化界面设计…………………………… 106 活动20 计算机对话— 图灵测试…………………………………… 115 2