白本程子末军 SHANDONG UNIVERSITY OF TECINOLOGY 计算机算法设计与分析 Design and Analysis of Computer Algorithms 王红霞 2019.10.26
计算机算法设计与分析 Design and Analysis of Computer Algorithms 王红霞 2019.10.26
归东程子太军 提纲 SHANDONG UNIVERSITY OF TECINOLOGY 华3会个会会学3会是会品 ●课程简介 ●计算机如何解决问题 ●算法在问题求解中的地位 ·算法在计算机科学中的地位 ●研究算法的重要性 ●课程内容 ●教学方法 ● 参考资料 2025年4月3日
2025年4月3日 2 提纲 ⚫课程简介 ⚫计算机如何解决问题 ⚫算法在问题求解中的地位 ⚫算法在计算机科学中的地位 ⚫研究算法的重要性 ⚫课程内容 ⚫教学方法 ⚫参考资料
课程简介 归本程子太军 SHANDONG UNIVERSITY OF TECHNOLOGY 给空安器会的会 《算法设计与分析》是计算机学科的技术 基础和主干必修课 不需要特别的基础知识，已修本科数学分析 (或高等数学)、离散数学和C++语言程序设 计，将有助于更好地理解课程内容 2025年4月3日
2025年4月3日 3 《算法设计与分析》是计算机学科的技术 基础和主干必修课 不需要特别的基础知识，已修本科数学分析 （或高等数学）、离散数学和C++语言程序设 计，将有助于更好地理解课程内容 课程简介
山东程上太军 HANDONG UNIVERSITY OF TECHNOLOOY ●在《算法的出现》中说道： “有两种思想， 像珠宝商放在天鹅绒上的宝石一样熠熠生 辉，一个是微积分，另一就是算法。微积 分以及在微积分基础上建立起来的数学分 析体系造就了现代科学，而算法则造就了 现代世界。” 2025年4月3日
2025年4月3日 4 ⚫在《算法的出现》中说道：“有两种思想， 像珠宝商放在天鹅绒上的宝石一样熠熠生 辉，一个是微积分，另一就是算法。微积 分以及在微积分基础上建立起来的数学分 析体系造就了现代科学，而算法则造就了 现代世界
归理子太程 SHANDONG UNIVERSITY OF TECINOLOGY ● 21世纪的今天，计算机的重要性日益突显，越 来越多的学生选择计算机科学作为自己在高校 主修的专业。对于这些将来从事计算机专业的 人士来说，无论从理论上还是从实践上，学习 算法设计与分析都是十分必要的。 从理论上讲，算法研究已经被公认为是计 算机科学的基石。David Harel,在他的《算法： 计算的灵魂》一书中这样说：“算法不仅是计 算机科学的一个分支，它更是计算机科学的核 心。而且，可以毫不夸张地说，它和绝大多数 的科学、商业和技术都是相关的。” 2025年4月3日
2025年4月3日 5 ⚫ 21世纪的今天，计算机的重要性日益突显，越 来越多的学生选择计算机科学作为自己在高校 主修的专业。对于这些将来从事计算机专业的 人士来说，无论从理论上还是从实践上，学习 从理论上讲，算法研究已经被公认为是计 算机科学的基石。David Harel在他的《算法： 计算的灵魂》一书中这样说：“算法不仅是计 算机科学的一个分支，它更是计算机科学的核 心。而且，可以毫不夸张地说，它和绝大多数 的科学、商业和技术都是相关的
白东理子太军 SHANDONG UNIVERSITY OF TECINOLOGY 信息检索的重要性 2 3 2020 visions 19502nnn orthe first issueof the new decade,Noture asked a selection of leading researchers and policy-makers Search ter Nervig' 2010年的第一期《自然》杂志评选出未来10年内 最重要的技术：互联网搜索技术排在第一位 。在英国皇家学会成立350周年时，评选近几百年 来开创性成果：基于语义的信息检索被列为其中 之一 2025年4月3日 6
2025年4月3日 6 信息检索的重要性 • 2010年的第一期《自然》杂志评选出未来10年内 最重要的技术：互联网搜索技术排在第一位 • 在英国皇家学会成立350周年时，评选近几百年 来开创性成果：基于语义的信息检索被列为其中 之一
归东程子末军 HANDONG UNIVERSITY OF TECINOLOGY 搜索示例：同济大学 3杀 2月济大学Goot接家Windows intemet Bplo阳 世年A-EA0C85aES47 ESADXAme·4XP西蛋 身fo的】同济大字G00ge孩家 登·日·3m·PageSafety,1oe 网质图片蓝出出贵走可荟丰中，更， 装史安魔业过 G00ge同济大号 Go0g%提宝型 转所有网历白中文网顺台局体中文两西 同领出打升百宇箱 固奇大堂 网页排序结果 一似工为王，理工结台，经、需.文、法 拉有机妆会作通目激您如人 据机构财大生荒，结更大利到空司 兔贵堆川物师提要组轨直专家全程支油 医多金留 植的论 性士武业 同不载了 上者9 图中 的动生 人才超 ton某的官其它 问题：搜索引擎怎么知道哪个网页排在前面 大学研究生院 哪个排在后面呢？即如何衡量网页的重要性？ 同请大学2010年招收攻请博士学 业学位讲究生款有网种：MB 9on0auCa/dc值度W4出 上市 厨济大学网铭发育学悦回济大学继铁套州学院国济大学理代远橙鞋育网V20。 融2，淡宝宝维坐程 同清大学调结教有学用，继快软字烷。附教育。远程黎而、学历取商，地结黎育。成人歌有。高 等和商，我代近程敏布、路大学，网上大学，同上教育，学习。上 托票大邵大思售裤级让精干能2勇 付费 上语布n。 Goog白蓝讯：回济大坐 控的商专科本科进格证 广告 公的表科相资格证网上可立询国家 信两用T/15276292 专业自零5月出到坊大学置询现场，不少家长皇题擦租机忙看拍排唇镇位上的招生童传海 地m△兰的热上三4丝00江直±士值撞接白上土 2025年4月3日 7
2025年4月3日 7 搜索示例：同济大学 问题：搜索引擎怎么知道哪个网页排在前面， 哪个排在后面呢？即如何衡量网页的重要性？ 网页排序结果 付费 广告
归求程上太军 SHANDONG UNIVERSITY OF TECINOLOGY 网页排名算法：PageRank ●网页排名是网络搜索引擎的核心 ·PageRank是著名网络搜索引擎Google用于评 测一个网页“重要性”或“影响力”的一种 方法 PageRank 2025年4月3日
2025年4月3日 8 网页排名算法：PageRank ⚫ 网页排名是网络搜索引擎的核心 ⚫ PageRank 是著名网络搜索引擎 Google 用于评 测一个网页 “重要性” 或 “影响力” 的一种 方法
归东露子太军 SHANDONG UNIVERSITY OF TECHNOLOGY 有向图的知识 ◆有向图 ◆顶点的出度(Out-degree) ◆J顶点的入度(In-degree) 例：右图为一个有向图，记为D 顶点组成的集合：V(D)={u,V,w} 弧组成的集合： A(D)={(u,w),(w,u),(u,v）} 顶点u的出度： od (u)=2 如何表示这个图，以便 顶点u的入度 id(u)=1 更好计算PageRank值呢？ 2025年4月3日 9
2025年4月3日 9 例：右图为一个有向图，记为 D 顶点组成的集合：V(D)={u,v,w} 弧组成的集合: A(D)={(u,w),(w,u),(u,v)} 有向图的知识 ◆ 有向图 ◆ 顶点的出度(Out-degree) ◆ 顶点的入度(In-degree) 顶点 u 的出度: 顶点 u 的入度: od(u)=2 id(u)=1 如何表示这个图，以便 更好计算PageRank值呢？
山东程子太军 邻接矩阵 SHANDONG UNIVERSITY OF TECINOLOGY 器会会空会的空3会空是 口为研究需要，我们定义邻接矩阵 6=侧小共中%={及 如果存在从到i的孤 otherwise 对于下例中的有向图，其邻接矩阵为 12345678 0000001 0] 1 10110000 2 10000000 3 01000000 4 G 00110010 00011001 6 00001001 7 0 0001110 8 2025年4月3日 10
2025年4月3日 10 ❑ 为研究需要，我们定义邻接矩阵 对于下例 中的有向图，其邻接矩阵为 邻接矩阵 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8