算法设计与分析入门-郭丹教授

"这是一份关于《算法设计与分析》课程的资料，由郭丹在2012年9月于计算机与信息学院教授。课程主要涵盖了算法的基础、设计、分析以及经典算法和难解问题的探讨。" 《算法设计与分析》是计算机科学中的核心课程，它涉及到如何设计有效的算法以及如何对算法的性能进行评估。在这个课程中，郭丹老师将带领学生深入理解算法的本质和应用。课程的目的是使学生具备独立设计和分析算法的能力，这对于解决复杂的计算问题至关重要。 课程的时间和考核方式如下： - 上课地点：西二101 - 课时：32个课时，持续1-8周 - 考核构成：作业占20%，考勤及课堂参与占20%，考试占60% 推荐的教材包括： 1. 《算法之道》：作者邹恒明，机械工业出版社出版，适合初学者，易于理解。 2. 《算法导论》：由科曼等人著，潘金贵等译，机械工业出版社出版，是最经典的算法教材。 3. 英文原版《Introduction to Algorithms》：作者包括Cormen、Leiserson、Rivest和Stein，由The MIT Press出版，是深入学习的权威参考书。 4. 《数据结构与算法分析》：作者Mark Allen Weiss，人民邮电出版社出版，侧重于数据结构与算法的分析。 课程内容分为四个部分： 1. 算法基础篇：介绍算法的基本概念、思维和方法，如算法思想与基础手段。 2. 算法设计篇：探讨常见的设计策略和思想，如分治法和递归。 3. 算法分析篇：讲解除基本时间复杂度分析外的其他重要分析手段。 4. 经典算法篇：讲解三个经典的算法，可能包括排序、查找等。 5. 难解与无解篇：讨论可解性、NP完全问题以及无解问题的近似算法。 在第一章“什么是算法？”中，郭丹老师将引导学生理解算法从概念到实现的过程，以及1.1节“意念与现实（从无有到无穷）”的内容，这部分可能会涵盖算法的概念、基本特征和实例，旨在帮助学生建立起对算法的初步认识。后续章节则会逐步深入到更具体的算法设计和分析技术。