1、School of Computer Science and Technology . SDIBT 刘培强 山东工商学院 计算机科学与技术学院1Before the class starts算法设计与分析本讲内容n本课程u与其他课程的关系是什么？u解决什么问题？u讲什么内容？u怎么学？u参考资料山东工商学院 计算机科学与技术学院 - 2学习计算机专业一二三四五n三 个基本能力，包括u演绎能力u归纳能力u类比推理能力；n四 大核心内容，即u可计算理论 解决能不能的问题；u复杂性理论 解决行不行的问题；u程序正确性理论 解决可信不可信的问题；u软件方法和技术理论 解决能不能造出来的问题。n两 个层
2、次的转变，u一是从 “知 ”到 “智 ”的转变；u二是从 “鱼 ”到 “渔 ”的转变，n在此基础上， “一 ”就是指实现一个跨越：u从计算手段到计算思维再到问题求解的跨越。山东工商学院 计算机科学与技术学院 3这是一个悟道的过程。五理论上可计算理论上与现实上的可计算性n 算法至少具有指数时间：理论上可计算 难解的n 多项式时间的算法：现实上可计算 多项式时间可解的n 对数多项式时间的算法：高度并行可解的山东工商学院 计算机科学与技术学院 - 4现实上可计算高度并行可计算 理论上不可计算山东工商学院 计算机科学与技术学院 - 5先修课程n 离散数学n 数据结构n 高级程序语言 (C/Java/C
3、+)山东工商学院 计算机科学与技术学院 - 6计算机专业课程群自然科学基础课程群计算机科学理论课程群计算机硬件课程群软件基础课程群山东工商学院 计算机科学与技术学院 - 7计算机科学理论课程群*组合数学*形式语言与自动机*模糊数学 *数理逻辑算法设计与分析 *可计算性理论 *算法分析 计算复杂性理论离散数学其中： *为研究生课程 数据结构山东工商学院 计算机科学与技术学院 88图灵机9Enigma Bomba 课程简介n课程名称：u算法分析与设计uDesign and Analysis of Algorithmsn课号： 176112 n基本目的：u掌握组合算法设计的基本技术u掌握算法分析的基本方法u了解计算复杂性理论的基本概念及其应用山东工商学院 计算机科学与技术学院 - 10
