计算机科学引论chap2概要.ppt

计 算 机 科学引 论 (计算机科学与技术方法论) 要点回顾 ACM、IEEE-CS及其攻关组 计算学科的定义、根本问题 CC2005报告:5个分支学科 学科知识体的3个层次 计算学科二维定义矩阵 本讲内容提要 Seven Bridges Problem L.Euler 的研究结论(1736)：解不存在 L.Euler 七桥问题的思想、方法 L.Euler 七桥问题的思想、方法 另一个著名的图论问题---“哈密尔顿回路问题” 哈密尔顿的“周游世界游戏” 狄拉克定理与哈密尔顿图 哈密尔顿图的必要条件 设无向图G=(V,E)是哈密尔顿图，V1是V的任意非空子集，则P(G-V1) ≤|V1|。 P(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得图的连通分量数。 |V1|为V1中包含的顶点个数。 “哈密尔顿回路”与“欧拉回路”的区别 “棋盘骑士问题” 哥尼斯堡七桥问题 ?尝试求解：七桥问题无解 ?理论分析： 抽象的方法 欧拉图、欧拉路径的定义及其判定规则 ?拓展： 哈密尔顿图等 棋盘骑士问题 §2.3.1汉诺塔(Hanoi)问题 梵天塔问题 世界末日 §2.3.1 梵天塔问题 梵天塔问题的抽象与递归方法 梵天塔问题的求解思想与算法 梵天塔问题的求解思想与算法 梵天塔问题的解---盘子的移动次数 梵天塔问题的解---世界末日在何时？ 梵天塔问题的计算机求解---“能行性” 另一个类似问题---“宰相的麦粒” §2.3.1 梵天塔问题 参考文献---“从1到无穷大” 汉诺塔问题 ?求解方法：递归。 ?问题的解： n个盘子的梵天塔问题需移动 次 264-1=18446744073709551615 ?问题的计算机求解---“能行性”： 理论上可以计算的问题，实际上并 不一定能行。 §2.3.2 算法复杂性中的难解性问题、P类问题和NP类问题 算法分析与算法复杂性 §2.3.2 算法复杂性中的难解性问题、P类问题和NP类问题 算法的时间复杂性与空间复杂性 算法的时间复杂性举例 算法的时间复杂性举例 算法的时间复杂性举例 算法的复杂性度量 难解性问题 P类问题和NP类问题 §2.3.3 证比求易算法 国王与公主的童话 §2.4.4 证比求易算法 真因子 §2.3.3 证比求易算法 国王与公主的童话---(顺序算法) 国王与公主的童话---(并行算法) 顺序算法的时间复杂性及并行算法的空间复杂性 §2.3.3 证比求易算法 对并行算法的一种误解 阿姆达尔(G.Amdahl)定律 §2.3.4 P = ? NP P类问题和NP类问题 §2.3.4 P = ? NP P = ? NP 上讲要点回顾 欧拉回路、欧拉路径 哈密尔顿回路 梵天（汉诺）塔问题 算法复杂性 难解性问题、P类问题、NP类问题 证比求易算法 NP完全性问题及库克和卡尔普的成果 典型的NP完全性问题 密码学 2.3.5 RSA公开密钥密码系统 由R.Rivest、A.Shamir和L.Adleman于1978年提出的。 RSA公钥密码系统的形式化描述： RSA=p ,q , n ,m ,e , d, k, c， 其中： p和q为不同质数,n=p×q (e,n ）: 公开密钥; （d,n）:秘密密钥。 m为原始报文，mn c为加密后的报文 1 1 c = me mod n m = cd mon n 2.3.5 RSA公开密钥密码系统 构建RSA公开密钥密码系统的步骤 选择两个不同的质数p和q 求e，使得e与(p-1)×(q-1)互质 求d，使得 为真。 加密和解密： 对原始报文m加密，加密后的报文 c=me mod n 根据加密后的报文c，求原始报文 m=cd mon n RSA应用例题 例1.设p=3，q=11，则n=33，构造一个RSA公开密钥密码系统，并对报文9加密和解密。 构造步骤： 求e： (p-1)×(q-1)=20，e与20互质，e可取3 求d：存在k，使得ed =k(p-1)(q-1)+1 =20k+1 d=（20k+1）/3 k取1，则d=7 RSA:公钥为（3,33）； 私钥为（7,33） 加密解密： 加密： c=me mod n =93 mod 33=3 解密： 收到密文c=3， m=cd mon n= 37 mod 33=9 RSA应用例题 例2.设p=223092827，q=218610473，则n=487704284333771171，构造一个RSA公开密钥密码系统。 构造步骤： 求e： (p-1)×(q-1)=48770427991673872，e与其互质互质，e可取3 求d：存