Algorithm-00-BeforeTheClassStarts

1、1,Before the class starts,算法设计与分析,本讲内容,本课程 与其他课程的关系是什么？ 解决什么问题？ 讲什么内容？ 怎么学？ 参考资料,山东工商学院 计算机科学与技术学院 - 2,学习计算机专业一二三四五,三个基本能力，包括 演绎能力 归纳能力 类比推理能力； 四大核心内容，即 可计算理论解决能不能的问题； 复杂性理论解决行不行的问题； 程序正确性理论解决可信不可信的问题； 软件方法和技术理论解决能不能造出来的问题。 两个层次的转变， 一是从“知”到“智”的转变； 二是从“鱼”到“渔”的转变， 在此基础上，“一”就是指实现一个跨越： 从计算手段到计算思维再到问题求解的

2、跨越。,山东工商学院 计算机科学与技术学院3,这是一个悟道的过程。,理论上可计算,理论上与现实上的可计算性,算法至少具有指数时间：理论上可计算难解的 多项式时间的算法：现实上可计算多项式时间可解的 对数多项式时间的算法：高度并行可解的,山东工商学院 计算机科学与技术学院 - 4,现实上可计算,高度并行可计算,理论上不可计算,山东工商学院 计算机科学与技术学院 - 5,先修课程,离散数学 数据结构 高级程序语言(C/Java/C+),山东工商学院 计算机科学与技术学院 - 6,计算机专业课程群,自然科学基础课程群,计算机科学理论课程群,计算机硬件课程群,软件基础课程群,山东工商学院 计算机科学与

3、技术学院 - 7,计算机科学理论课程群,其中：*为研究生课程,数据结构,山东工商学院 计算机科学与技术学院 8,8,图灵机,9,Enigma,Bomba,课程简介,课程名称： 算法分析与设计 Design and Analysis of Algorithms 课号：176112 基本目的： 掌握组合算法设计的基本技术 掌握算法分析的基本方法 了解计算复杂性理论的基本概念及其应用,山东工商学院 计算机科学与技术学院 - 10,主要内容介绍,第1章算法引论 第2章递归与分治策略 第3章动态规划 第4章贪心算法 第5章回溯法 第6章分支限界法,主要内容介绍（续）,第7章概率算法 第8章NP完全性理论

4、 （简介） 第9章近似算法 （简介） 第10章算法优化策略 （简介） 第11章 在线算法设计,学习安排,以课程讲授为主，以编程实验为辅 成绩评定 平时/作业成绩：30% 期末笔试：70%,山东工商学院 计算机科学与技术学院 - 13,教材与参考书,1 计算机算法设计与分析（第3版）, 王晓东, 电子工业出版社. 配套: “算法设计与实验题解”, 王晓东, 电子工业出版社. 2 算法设计技巧与分析（Algorithms Design Techniques and Analysis）, 吴伟昶等译(沙特 M.H.Alsuwaiyel), 电子工业出版社 3 算法导论. 潘金贵 等译. 机机械工业出

5、版社 英文版 Introduction to Algorithms, Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, McGraw-Hill Book Company. 4 算法设计与分析, 朱大铭 等 编著. 高等教育出版社. 5 计算机和难解性NP 完全性理论导引, M. R. 加里, D. S. 约翰逊, 张立昂等译, 科学出版, 社1987. 英文版 Computers and Intractability: A Guide to the Theory of NP-Completeness. Michael R. Garey and David S. Johnson. W. H. Freeman and Co. 1979.,山东工商学院 计算机科学与技术学院 - 14,教学网