参考教材
1、算法设计与分析 王晓东 清华大学出版社 2、算法分析与设计 （美）Michael T. Goodrich Roberto Tamassia 著人民邮电出版 社 3、算法设计技巧与分析（沙特） M.H. Alsuwaiyel 著 电子工业出版社 4、算法设计与分析 郑宗汉 清华大学出版社 5、算法导论， Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest Clifford Stein 著， 潘金贵等译， 机械工业出版社
Knigsberg桥对应的图 Knigsberg桥对应的图
欧拉图
定理
G是无向连通图，则G是欧拉图G中所有顶点度 数都是偶数。 定义 如果无向连通图G的每条边一次且仅一次的通路称为图 G的欧拉通路。 定理 具有一条连接顶点vi和vJ的欧拉通路的充分条件是vi和vJ 是G中仅有的具有奇数度的顶点。
货郎担问题
Introduction to Algorithms
授课教师：宋玲
E-Mail: song_ling@
山东建筑大学计算机学院(2009年9月)
Lecture 1
What Do You Want?
a good score to be more intelligent the beauty of math the way to research If you listen to me carefully from now and finish every homework,I promise that you will get all of them.
棋盘覆盖 在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格 不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在 棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定 的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌 不得重叠覆盖。
Longest Common Subsequence (LCS)
本课程的难点和学习方法
双语学习 较多的数学知识和推倒(第一部分) 预习-上课认真听讲-复习（重点词汇） 预备的数学知识(p51-57) 本次课和下节课所讲重点内容在教材上划 出。
教辅用书
教材
Introduction to Algorithms(Second Edition)，（美） Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest Clifford Stein，高等教育出版社
本课程的教学目的及要求 (2/2)
解释各主要的排序算法， 解释各主要的排序算法，练习这些算法 的分析及它们所包含的设计策略， 的分析及它们所包含的设计策略，实现 将排序作为子程序的算法， 将排序作为子程序的算法，推算比较排 序法执行时间的下限， 序法执行时间的下限，和解释怎样可以 克服这些界限； 克服这些界限； 实现图论算法和使用图论计算为关键的 算法，分析它们， 算法，分析它们，以及如何使用图来模 拟工程问题； 拟工程问题；
一个货郎要去若干城镇卖货，然后回到 出发地，给定各城镇之间所需的旅行时 间后，应怎样计划他的路线，使他能去 每个城镇恰好一次而且总时间最短？ 实质：无向加权图，寻找最短的Ｈ回路 的问题。
货郎担问题
用图论的术语说，就是在一个赋权完全 图中，找出一个具有最小权的Hamilton 圈（包含图G的每个顶点的圈)。 这个问题目前还没有有效的算法。 30！=265,252, 859,812,191,058,636 308,480,000,000 有兴趣的同学编程序实现，看你能解决 多大规模的问题。
七桥问题
18世纪的七桥问题—穿过Knigsberg城的七 座桥，要求每座桥通过一次且仅通过一次。 Euler1736年证明了不可能存在这样的路线。
Euler 定理
定义（欧拉图） 通过无向连通图G的每条边一次且仅有一次 的回路称为欧拉回路。具有欧拉回路的图为 欧拉图。 定义包含多重图在内，即欧拉回路中允许顶 点重复出现。
注： （1）欧拉道路未必是哈密顿道路，因为 欧拉道路可以经过同一顶点多次。 哈密顿道路未必是欧拉道路，因为哈密顿道路不 一定要经过Ｅ中所有的边。 （2）基本道路必然是简单道路。
四色问题
著名的世界难题“四色猜想” ：一张地图， 用一种颜色对一个地区着色，那么一共只需 要四种颜色就能保证每两个相邻的地区颜色 不同。
课前讨论
在学期中将会有大约4次的讨论课，共四组(大约20 个人为1个小组)，15分钟问题的描述和讲解。题目可以 自己拟定，也可以由教师指定。 目的是让同学们及时复习，培养团队合作以及主动 学习精神，记入平时成绩。
作业以及实验报告中 算法描述要求
当被指定“用一个算法”来解决某个问题。应该 提供以下部分： 1. 算法的描述：伪代码(pseudocode)。 2. 最少以一个工作例子或图表来更明确的显示你 的算法是怎样工作的。 3. 算法正确性的一个证明（或表示）（*）。 4. 算法执行时间的分析。
你能解决以下问题吗？
古城哥尼斯堡，景致迷人，碧波荡漾的普瑞格尔河横贯 其境。普瑞格尔河的两岸及河中的两个美丽的小岛，由七座 桥连接组成了这座秀色怡人的城市（如图）。市民们喜欢四 处散步，于是便产生这样的问题：是否可以设计一种方案， 使得人们从自己家里出发，经过每座桥恰好一次，最后回到 家里。这便是著名的“哥尼斯堡七桥问题”。热衷于这个有 趣的问题的人们试图解决它，但一段时间内竟然没有人能给 出答案。后来，问题传到了著名数学家欧拉那里，居然也激 起了他的兴趣。他从人们寻求路线屡遭失败的教训中敏锐地 领悟到，也许这样的方案根本就不存在。欧拉经过悉心的研 究，1736年，年方29岁的欧拉终于解决了这个问题，并向圣 彼得堡科学院递交了一份题为《哥尼斯堡的七座桥》的论文。 论文不仅仅是解决了这一难题，而且引发了一门新的数学分 支——图论的诞生。
第三部分（Part III） 数据结构（Data Structures） 第十章 基本的数据结构（Elementary Data Structures） 第十一章 散列表（Hash Tables） 第十二章 二叉查找树（Binary Search Trees） 第十三章 红-黑树（Red-Black Trees） 第十四章 扩充的数据结构（Augmenting Data Structures） 第四部分（Part IV） 高级的设计与分析技术（Advanced Design and Analysis Techniques） 第十五章 动态规划（Dynamic Programming） 第十六章 贪婪算法（Greedy Algorithms） 第十七章 分摊分析（Amortized Analysis）
哈密顿图
一. 哈密顿道路问题： １８５９年发明的一种游戏。 在一个实心的正十二面体，20个顶点标上 世界著名大城市的名字，要求游戏者从某一城 市出发，遍历各城市一次，最后回到原地。 这就是“绕行世界”问题。即找一条经过 所有顶点（城市）的基本道路（回路）。
哈密顿图
定义 通过图G的每个顶点一次且仅一次的回路称为 哈密顿回路。具有哈密顿回路的图称为哈密顿 图。哈密顿通路是通过图G的每个顶点一次且 仅一次的通路。
作业要求
在学期中将会指定 多次作业。要求同学上交并给出 成绩，作为部分期末成绩。 作业的目的是让同学有练习掌握课堂内容的机会。 因此，鼓励同学们合作解题。虽然鼓励合作解答题目， 但是，要求独立写下答案，并要求在习题上写下合作者 ， 们的名字。如果没有跟任何人合作，应该写下“合作者： 无”。如果答案是由研究而来(例如：互联网)，注明你 的资料来源，但依你自己的方法写下答案。
相关事项
教学方式：理论(48学时)，实践(16ห้องสมุดไป่ตู้时) 最终的评分会基于作业、平时表现、实 验报告和期末考 先修课程：《离散数学》《数据结构》 《数值分析》《C语言程序设计》 作业：每个部分交一次 答疑时间：周四下午2：30 答疑地点：XX305
Grading policy:
Homework: 8% Experiment Run Results: 8% Experiment Paper: 8% Arrival: 6% Final Exam: 70%
Application: comparison of two DNA strings Ex: X= {A B C B D A B }, Y= {B D C A B A} Longest Common Subsequence: X= AB C BDAB Y= B D CAB A Brute force algorithm would compare each subsequence of X with the symbols in Y
第五部分（Part V） 高级的数据结构（Advanced Data Structures） 第十八章 B-树（B-Trees） 第十九章 二项式堆（Binomial Heaps） 第二十章 斐波纳契堆（Fibonacci Heaps） 第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets） 第六部分（Part VI） 图算法（Graph Algorithms） Part VI Graph Algorithms 第二十二章 基本的图算法（Elementary Graph Algorithms） 第二十三章 最小生成树（Minimum Spanning Trees） 第二十四章 单源最短路径（Single-Source Shortest Paths） 第二十五章 全对的最短路径（All-Pairs Shortest Paths） 第二十六章 最大流（Maximum Flow） 第七部分（Part VII） 精选的主题（Selected Topics） 第二十七章 排序网络（Sorting Networks）
本课程的教学目的及要求 (1/2)
分析算法的渐进效率；掌握最坏， 分析算法的渐进效率；掌握最坏，平均及最好情 况下复杂性的分析； 况下复杂性的分析； 叙述分治法的模式和解释当什么情况算法设计会 需要它，练习使用此模式的算法， 需要它，练习使用此模式的算法，实现并推导出 分治法的递归描述； 分治法的递归描述； 叙述动态规划的模式和解释当什么情况算法设计 会需要它，练习使用此模式的算， 会需要它，练习使用此模式的算，实现并分析动 态规划算法。 态规划算法。 叙述贪心算法的模式和解释当什么情况算法设计 会需要它，练习使用此模式的算法， 会需要它，练习使用此模式的算法，实现并分析 贪心算法； 贪心算法；