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
算法定义 定义1（计算） 可由给定计算模型机械执行的计算步骤序列称为该模型的一个计算。 定义2（算法（直观定义）) 算法(algorithm)就是任何良定义的计算过程，该过程取某个值或值的集 合作为输入并产生某个值或值的集合作为输出。 定义3（算法（形式定义）) 算法是满足下列特征的计算(Donald Knuth): ●输入：必须有零个或以上的输入量。 。输出：应有一个或以上输出量作为算法计算的结果。 。确定性：算法的描述无歧义，每一步都是严格定义和确定的动作。 ·有穷性/终止性：通常要求算法有限步内必须停止。 ·能行性：每一个动作都能够被精确地机械执行。 6/40
算法定义 定义 1 (计算) 可由给定计算模型机械执行的计算步骤序列称为该模型的一个计算。 定义 2 (算法(直观定义)) 算法 (algorithm) 就是任何良定义的计算过程，该过程取某个值或值的集 合作为输入并产生某个值或值的集合作为输出。 定义 3 (算法(形式定义)) 算法是满足下列特征的计算(Donald Knuth)： 输入：必须有零个或以上的输入量。 输出：应有一个或以上输出量作为算法计算的结果。 确定性：算法的描述无歧义，每一步都是严格定义和确定的动作。 有穷性/终止性：通常要求算法有限步内必须停止。 能行性：每一个动作都能够被精确地机械执行。 6 / 40
算法的应用 ·自然资源采集：地震数据处理算法 。自然环境研究：大气/洋流模拟、中长期天气预报 。产品设计：计算几何、3D建模 。国防工业：核爆炸模拟 ·生产与销售组织：运筹学算法、数据挖掘算法 ·证券金融：计算机交易系统、建模/预测、基础架构支持 ●医疗卫生：基因组测序、蛋白质折叠、3D重建 ●休闲娱乐：图形/图象算法、虚拟现实、多媒体编解码 。信息系统：云计算、物联网、大数据、人工智能 ·嵌入式系统：片上系统、网关、路由器 微电子相关：器件仿真、电路仿真、逻辑仿真、综合、布局布线、芯片系 统级设计、软硬件协同设计 77g0
算法的应用 g,] Ê8µ/数‚?né{ g,ǸԃµåÌ/6 [!•œUÌ˝ ¨设OµOéA¤!3D Ô IìÛíµÿ ø [ 生Üù售|ѵ$ Æé{!数‚˜é{ y 7KµOéÅ¥X⁄!Ô /˝ˇ!ƒ:e|± ö•生µƒœ|ˇS!xüÚU!3D Ô >sÑWµ„//„ñé{!J[y实!ıxN?)Ë &EX⁄µ Oé!‘È !å数‚!fÉ'µÏáï˝!>¥ï˝!‹6ï˝!n‹!Ÿ¤ŸÇ! °X ⁄?设O!^Má”设O 7 / 40
国际顶尖学校相关计算机系统课程的先导知识要求 MIT UC-Berkeley Stanford University CMU Great Ideas in Compu Computer Organizat Computation Str Introduction to Comp 课程名称 ter Architecture Ma ion and Systems (C uctures uter System(ICS chine Structures 开设专业 EE、CS cs cs cs 门电路→功能部 C语言→汇编→指令 C语言一汇编→指令 件一→单周明和流 C语言一汇编一指令： →微体系结构：编 一微体系结构：编译 水线CPU: 应用级并行一数据级 译一链接装入一 链接一装入一→执 课程描述 C语言一汇编一→ 并行一线程级并行一 执行：程序性能优 行：程序性能优化、 指令→过程一进 指令级并行一→寄存器 化、存储器结构与 存储器结构与管理、 程：并行、性能 传送级硬件描述 管理、并发和修线 并发和多线程、网络 评价 程、网络编程 编程 C"K&R"+COD"P&H" APP"B&O"+C"K& APP"B&O"+C"K& 教材” 未指定（讲义） +WSCB&H R" R. 模型机 自定义(RISC) MIPS RISC IA32 1A32 了解程序设计语 先行课程 了解和掌握C语言程序 了解和掌握C语言程 了解和掌握C语言程 言，具备电子技 或要求 设计技术 序设计技术 序设计技术 刀QC 术基础知识 8/40
国际顶尖学校相关计算机系统课程的先导知识要求 图: 先导知识要求 8 / 40
为什么要学算法？ A Real-Time FPGA-Based Accelerator for ECG Analysis and Diagnosis Using Association-Rule Mining XIACOI GU.YONOXIN ZHU,SHENGYAN ZHOU,and CHAOJUN WANG A POCE色S56sF花A 四 四 e也中国口，n Theery af Notoel Ry Werde and作BCXC mettos-nule mnne t时llienoot ing.F0A Cloud We can design new algorithms for hardware execution. 图：硬件加速算法示意 +口4y,。生4三，2QG 9/40
为什么要学算法？ 图: 硬件加速算法示意 9 / 40
为什么要学算法？ An FPGA-Based Cloud System for Massive ECG Data Analysis Xu Wan2.Siden:Nemb求IEE Yon会Xin∠hu.Se?or Member:IBEE.YnII.Senior Meniber.I飞. Meikang Cin.Sentor Member IEE.and 'nan Ilang.Srudene Afemther /iisis Embaddad Mamory subaystem Microprocessor DDR3 DDR3 SRAM Abstract-In this hrief,we propose a stand-alone SOPC (Sys- temn on a Programmable Chip)based cloud system to accelerate AXI Interconnect massive ECG data analysis.The proposed system tightly couples network TO handling hardware to data prucessing pipelines Network ECG procassing in ia single FPGA,oflliding hoth nelworking operations and Data Assignment ECG data analysis.In this system,we tirst propose a massive- 10 GEthernet钟 sessions optimized TCP/IP hardware stack using a macro- TCP/IP Stack Fuaturs Extraction pipellne archltecture to accelerate network packet processlng. XAUI Intarface Second,we propose a streamlng arehltecture to accelerate ECG Classification signal proessing,indluding QRS detection,fealur extraction wedesignC Fig 1:SOPC based architecture that tightly couples petwork using real ECG data.Compared to commerclal servers.our system shows up to 38%improvement in performance and 142X (handling and C(i data processing. Improvement in enerey emclency. atiment F T:mgKTAous cn Chomfs ang 5ystomog 0.LGom99 PE Pipeine FE Plpeine We can accelerate classic FE Plpeine TCP/IP algorithms defined in software. bDR3 Fig.4:Architecture of the ECCi data processing module.C 10/40
为什么要学算法？ 图: 硬件加速算法示意 10 / 40