Lecture1Week12一算法设计与分析基础 绳伟光、祝永新 Email:wgshenghit@sjtu.edu.cn,zhuyongxin@sjtu.edu.cn 上海交通大学 微电子学院 ,口，y，生4三，2QC 1/40
Lecture 1/Week 12 — 算法设计与分析基础 绳ï1!6[# Email: wgshenghit@sjtu.edu.cn, zhuyongxin@sjtu.edu.cn ˛°œåÆ á>fÆ 1 / 40
提纲 算法的概念 ② 问题描述及算法描述方法 算法正确性分析 算法复杂性分析 ⑤标准符号和通用函数 ,口y，生4三，2月0C 2/40
提纲 1 算法的概念 2 问题描述及算法描述方法 3 算法正确性分析 4 算法复杂性分析 5 标准符号和通用函数 2 / 40
提纲 ①算法的概念 @问题描述及算法描述方法 ©算法正确性分析 算法复杂性分析 ©标准符号和通用函数 ,口，4y，生4三2Q0 3/40
提纲 1 算法的概念 2 问题描述及算法描述方法 3 算法正确性分析 4 算法复杂性分析 5 标准符号和通用函数 3 / 40
主要内容 1.算法设计与分析基础 2.分治算法 3.动态规划算法 4.贪心算法 5.均摊分析 6.随机算法与近似算法 7.最大值最小值方法 8.树搜索策略 9.非确定性算法与机器学习基础 ,口，4y+生4三，在QC 4/40
主要内容 1. é{设OÜ©¤ƒ: 2. ©£é{ 3. ƒ5yé{ 4. %é{ 5. ˛©¤ 6. ëÅé{ÜCqé{ 7. ÅåäÅäê{ 8. 树|¢¸— 9. ö(½5é{ÜÅÏÆSƒ: 4 / 40
计算机科学的问题求解过程 计算机科学问题求解过程 可计算否 能行可计算否 算法设计与分析 算法编程语 软件系统 言实 对应学科 数据结构、编程语言 可计算性理论 计算复杂性理论 算法理论和技术 编译技术、软件工程 操作系统、体系结构 高等数学离散数学集合论与图论概率论数理逻辑组合数学 刀aC 5/40
计算机科学的问题求解过程 计算机科学问题求解过程 可 计 算 否 能 行 可 计 算 否 算 法 设 计 与 分 析 算 法 编 程 语 言 实 现 软 件 系 统 可计算性理论 计算复杂性理论 算法理论和技术 数据结构、编程语言 编译技术、软件工程 操作系统、体系结构 高等数学 离散数学 集合论与图论 概率论 数理逻辑 组合数学 对应学科 5 / 40