陈钟-第二届计算机类专业高峰论坛-杭州-演讲-v2

北京大学计算机系人才培养新举措——推进拔尖创新人才培养的思索与实践陈钟北京大学计算机科学技术系[e-mail]2013年11月30日杭州第二届高等学校计算机类专业人才培养高峰论坛PekingUniversityCSDepartment内容提要•设计•实施：小班研讨型教学改革–神1：计算机系统导论–神2：算法设计与分析–课程选择–教学方式–课程组织•效果•拔尖创新人才培养的思索PekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartment神一PekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartment小班课老师定期交流例会PekingUniversityCSDepartmentCMUBryantO’Hallaron院长2012年6月5日在北大与师生交流PekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartmentPekingUniversityCSDepartment为什么选择《算法》课？•学校推动小班研讨型教学改革•计算机系小班教学的选择–计算机系统导论--Programmers’Perspective–算法设计与分析--TheoreticalTrainingTheorySystemsPekingUniversityCSDepartmentCC2013课程体系结构:核心系统(Systems)核心:3门课•程序设计方法学与抽象•计算机组织与系统•计算机系统与网络原理理论(Theory)核心:3门课•计算机科学的数学基础•面向计算机科学家的概率论•数据结构与算法TheorySystemsPekingUniversityCSDepartment算法设计与分析PekingUniversityCSDepartment《算法设计与分析》课程教材选择PekingUniversityCSDepartment神二《算法设计与分析》课程教师团队•《算法设计与分析》主讲教师：–实验班：汪小林–大班课：肖臻•小班课教师：–赵海燕、郭耀、张铭、李文新、陈一峯、陈钟、熊英飞、周明辉、邓志鸿、张岩、肖臻、汪小林（实验班1）、刘田（实验班2）•助教：•学生人数–实验班：30人–普通班：150人PekingUniversityCSDepartment应该怎么上算法课？•在传统优势的基础上进行改革和创新–学生基础好：有利于培养拔尖创新人才，理论与应用并重–分类教学、分别考核：实验班+普通班–Project+SelectedPaperReading•国际化–请进来：CornellUniversity的KenBirman和JoeHalpern暑期课–走出去：2013年SummerVisitingStudentsPekingUniversityCSDepartment2012年考核方法•平时（35%）–上机作业（15%）+书面作业（10%）–选题报告（10%）–上机练习+平时表现课堂积极参与可加分•期末考试（65%）–机考（25%）在上进行–期末笔试（40%）PekingUniversityCSDepartment2013年考核方法•平时成绩（50%）–作业（20%）–论文阅读（15%）：小班报告与分析、论文考试–LabProject（15%）：提交Project报告、答辩•小班自选–期中考试（0%）–论文阅读考试（0%）•期末成绩（50%）PekingUniversityCSDepartment2012年成绩分布情况•最高分100分，优秀率35%，及格率为99%•总成绩分布比较均匀•平时成绩明显优于期末考试和笔试成绩PekingUniversityCSDepartment2013年成绩分布情况•普通班154人，满分100分，优秀率28.76%•实验班27人，满分100分，优秀率37%PekingUniversityCSDepartment课程内容的教学组织•基本概念–问题与问题求解–算法设计、分析、证明、应用–算法形式化描述与分析工具、证明方法（等价、归约…）–算法时间、空间开销，上、下界，复杂度：最好/最坏/平均，•从问题出发–调度：总时间最少。n个任务、时间，总时间PekingUniversityCSDepartment一、算法的数学基础•函数的渐进的界–f:NN–渐进的上界：f(n)=O(g(n))–渐进的下界：f(n)=Ω(g(n))–渐进的紧的界：f(n)=Θ(g(n))•几类函数–多项式函数：f(n)=a0+a1n+a2n2+…+adndf(n)=O(nd),f(n)=Θ(nd)–指数函数：f(n)=rn–阶乘函数：f(n)=n!PekingUniversityCSDepartment一、算法的数学基础（续）•求和的方法：–等差(ak)、等比(aqk)、调和(1/k)级数•递推方程求解方法–一阶迭代归纳法、二阶以上化简+迭代（差销法）–许多递归方程不能求出精确解，但可以估计出函数的阶–递归树模型–主定理：——直接给出了某些常用递归方程的解–某些递推方程有取整的底函数或顶函数，可以用尝试法。–例子：•Hanoi塔：递归方程T(n)=2T(n-1)+1,解是T(n)=2n-1•插入排序：W(1)=0,W(n)=W(n-1)+n-1,W(n)=n(n-1)/2=O(n2)•二分归并排序：W(1)=0,W(n)=2W(n/2)+n-1,PekingUniversityCSDepartment二、分治策略•设计算法的常用技术，通常用于设计递归算法。–基本思想–分治算法的分析技术–改进分治算法的途径•通过代数变换减少子问题个数•利用预处理减少递归内部的计算量–典型实例•快速排序算法•选择问题（选最大、选最小、选中位数、选第k大等）PekingUniversityCSDepartment三、动态规划•用于组合优化问题的算法设计，对应目标函数和约束条件。–最短路径问题、矩阵链的乘法问题、最大效益投资问题、背包问题、最长公共子序列问题、图像压缩问题、最大子段和问题、最优二分检索树问题、RNA的最优二级结构问题等•设计思想–多起点、多终点的最短路径问题•特征：组合优化，求解过程是多步判断，从小到大依次求解每个子问题，最后求解的子问题就是原始问题。子问题目标函数的最小值之间存在依赖关系，将子问题的解记录下来以备后面求解使用）–使用动态归划技术的必要条件•优化原则、最优子结构性质•设计要素–子问题的划分和递推方程–递归实现–迭代实现•典型应用–投资问题、背包问题、最长公共子序列LCSPekingUniversityCSDepartment四、贪心法•通用的算法设计技术，在许多最优化问题求解中得到了广发应用。–最小生成树Prim算法和Kruskal算法、单源最短路径的Dijkstra算法，数据压缩的Huffman算法等。–NP难的组合优化问题，用于设计近似算法。–贪心与动归的不同：也是多步判断，但每步判断时不考虑子问题计算的结果，而是根据当时情况采取某种“只顾眼前”的策略来决定取舍。计算工作量比动归小因此高效，但由于“短视”可能导致局部最优而不是全局最优。–因此，怎样选择合适的贪心策略并证明该策略的正确性是关键。•设计思想•正确性证明•对得不到最优解情况的处理•典型应用–最小生成树、单源最短路径(Dijkstra算法）PekingUniversityCSDepartment五、回溯与分支限界•回溯技术•基本思想和适用条件–8皇后问题、0-1背包问题、货郎问题（TSP）–适用条件：多米诺性质。否则，不能得到正确解，构造反例•设计步骤–步骤：–递归实现与迭代实现–典型例子：装载问题、图的m着色问题。•平均效率和改进途径•分支限界–回溯算法的变种，用于求解组合优化问题。（极大化问题）–背包问题、最大团问题、货郎问题、园排列问题、连续邮资问题PekingUniversityCSDepartment六、计算复杂度•平凡下界–必须扫描完所有输入才能得到解，求下界。对输入或输出进行计数。•直接计数求解该问题所需要的最少运算–找最大、•决策树–特别适合于分析搜索问题、排序问题等以比较作为基本运算的问题。•检索算法的时间复杂度分析•排序算法的时间复杂度分析–冒泡、堆排序、–排序算法的决策树与算法类时间复杂度的下界•选择算法的时间复杂度分析–找最大和最小问题、找第二大问题、找中位数问题、•通过归约确认问题计算复杂度的下界PekingUniversityCSDepartment七、NP完全性•计算复杂性理论、–NPC理论：在某种意义下这些问题具有相同的难度：如果其中一个有有效算法则所有这些问题都有有效算法；如果证明其中的一个是难解的则所有这些问题都是难解的。–一个问题被证明是NPC的就意味着这个问题很可能是难解。•P类与NP类–易解与难解问题–判定问题•多项式时间变换与NP完全性•几个NP完全问题–最大可满足性与三元可满足性–顶点覆盖、团与独立集哈密尔顿回路与货郎问题、恰好覆盖，子集合、背包、装箱与双机调度PekingUniversityCSDepartment八、近似算法•近似算法及其近似比•多机调度问题–贪心的近似算法–改进的贪心近似算法•货郎问题–最临近法、最小生成树法、最小权匹配法、•背包问题PekingUniversityCSDepartment九、随机算法•在算法中加入随机性。•概率论•对随机快速排序算法的分析•随机算法的分类及其局限性•素数检验和多项式恒等检验•随机游动算法PekingUniversityCSDepartment十、处理难解问题的策略•NPC是基于最坏情况下的复杂性度量。当考虑平均情况时会发现有些NPC问题在平均复杂度下是易解的。•对问题施加限制–二元可满足性问题、霍恩公式可满足性问题•固定参数算法•改进指数时间算法•启发式算法•平均情形的复杂性•难解算例生成•基于统计物理的消息传递算法•量子算法PekingUniversityCSDepartment有争议的改革：论文阅读与讨论•MathematicalAnalysisofAlgorithmsKnuthProceedingsofIFIPCongress71Amsterdam,North-Holland,1972,pp19-27PekingUniversityCSDepartmentPaperReading(selected5papers)•必读5篇–[1975]Backtrackprogrammingtechniques,J.R.Bitner,E.M.Eeingold,CACM,18(11):651-656,1975–[1972]ReducibilityamongCombinationalProblems,RichardM.Karp,UCB,[NSFGrantGJ-474]–[1979]ALowerBoundtoFindingConvexHulls,AndrewChi-ChihYao,STAN-CS-79-733–[1995]ARandomizedLinear