2计算学科中的科学问题 2.ppt

第二章 计算学科中的科学问题; 科学问题的定义;科学问题的主要特征;第2章 计算学科中的科学问题;例：配袜子;4、体系结构 5、操作系统 6、网络计算 7、程序设计语言 8、人-机交互 ;9、图形学和可视化计算 基本问题：;例：分数维(Fructal)图形;10、智能系统 11、信息管理 12、软件工程 13、社会和职业的问题 14、科学计算;反映计算学科某一方面本质特性的典型实例;1 哥尼斯堡(Konigsberg)七桥问题;Konigsberg 七桥问题;哈密尔顿回路问题;2、Hanoi塔;解题过程（3个圆盘问题）;Hanoi塔;;解: 将一个较大的问题归约为一个或多个子问题的求解，子问 题比原问题简单，且结构与原问题相同（递归） h(n)=2h(n-1)+1 =2(2h(n-2)+1)+1=22h(n-2)+2+1 =23h(n-3)+22+2+1 … =2nh(0)+2n-1+ … +22+2+1 =2n-1+ … +22+2+1=2n-1 264-1=18446744073709551615 1次/秒，264-1秒)=5849亿年(世界末日) 264-1/1000万次=58490年 能行问题 o(2n) P=？NP问题;3、P类问题与NP类问题;顺序算法和并行算法;（2）阿尔达定律——（并行）加速比的局限;（3）P=？NP; NP完全性问题例：可满足性问题 判定一个布尔公式是否可满足的 SAT = { ? ? ?是可满足的布尔公式 } 库克结论 SAT ? P，当且仅当 P = NP; 公约密码系统 RSA 加密密钥公开，解密密钥私有 很难从加密密钥求其解密密钥（NP完全问题）; 旅行商（货郎担）问题（Traveling Salesman Problem）;4、哲学家共餐问题;5、GoTo语句问题 P38;6、图灵测试;7、J.R.Searle 的 “中文屋子”;8．博弈树有哪些信誉好的足球投注网站（信息科学导论 ）;;8、博弈树有哪些信誉好的足球投注网站