爱丁堡大学 计算机科学专业 大二

INFR08026 算法与数据结构导论

爱丁堡大学计算机科学专业大二的算法与数据结构导论(INFR08026)课程旨在让学生学习一些标准算法和数据结构，这些算法和数据结构是所有计算领域的基础。学生还将应用一些数学概念来分析算法的理论复杂性及其实际行为。

算法与数据结构导论(INFR08026)主要涵盖了以下内容：

渐近符号和算法分析；顺序数据结构(列表、堆栈、队列)；基本和高级排序算法；树形数据结构、堆和优先级队列；哈希和字典；图形和图形算法；动态规划；P类和NP类。

算法与数据结构导论(INFR08026)课程结束后，学生应该能够：

1、解释算法的“最佳”、“预期”和“最差”情况行为之间的区别，并使用渐近符号分析算法的时间和空间复杂性。使用递归关系确定递归定义算法的时间复杂度。

2、描述抽象数据类型(例如，堆栈、队列、集合、字典、优先级队列)的属性、典型实现和示例应用用例，并讨论动态和静态数据结构实现的成本和好处。

3、能在给定伪代码或任务说明的情况下，使用一系列数据结构实现基本算法。进行实证研究，比较同一算法或数据类型在不同输入(或同一问题的不同算法)上的不同实现的性能，并解释从实证分析中可以学到而从渐近分析中不能学到的东西(反之亦然)。

4、描述各种算法策略(例如，蛮力、贪婪、分治、递归回溯、动态编程)，并给出包括语言处理和信息检索在内的一系列应用领域的例子。手动模拟一系列算法，例如搜索、排序、散列、解决图形问题的算法，以及动态编程的例子。给出使用每种算法的示例应用程序，并选择适当的算法用于示例问题。

5、非正式地定义类P和NP，并给出NP中问题的例子。解释停机问题及其重要性。