算法思想(第1部分)

你将学到什么

能够思考和解决更高抽象层次中的计算问题，创建更简单更高效的程序。

课程概况

每提出一个科学问题，电脑专家就要完成一系列步骤来提供解决方案，这些步骤包括：(1)理解问题；(2)用数学方式表达问题；(3)设计算法；(4)实现算法；(5)解决最初的科学问题。大家可以遵循这五个步骤，锻炼自己的算法思维，解决实际问题。

理解问题需要与该领域的专家交流，了解问题参数，能为电脑程序提供哪些数据，希望得到怎样的答案等等。用数学方式表达问题就是把一个用英文描述的问题转变成数学式，从而进一步实现计算分析。

课程强调算法的实现，同时解决需要算法辅助的原始问题。课程大部分内容针对第三个步骤，即算法设计，介绍不同的算法设计策略以及论证算法正确性与效率的数学工具。

Experienced Computer Scientists analyze and solve computational problems at a level of abstraction that is beyond that of any particular programming language. This two-part course builds on the principles that you learned in our Principles of Computing course and is designed to train students in the mathematical concepts and process of “Algorithmic Thinking”, allowing them to build simpler, more efficient solutions to real-world computational problems.

In part 1 of this course, we will study the notion of algorithmic efficiency and consider its application to several problems from graph theory. As the central part of the course, students will implement several important graph algorithms in Python and then use these algorithms to analyze two large real-world data sets. The main focus of these tasks is to understand interaction between the algorithms and the structure of the data sets being analyzed by these algorithms.

Recommended Background – Students should be comfortable writing intermediate size (300+ line) programs in Python and have a basic understanding of searching, sorting, and recursion. Students should also have a solid math background that includes algebra, pre-calculus and a familiarity with the math concepts covered in “Principles of Computing”.

课程大纲

周1
完成时间为 4 小时
Module 1 - Core Materials
What is Algorithmic Thinking?, class structure, graphs, brute-force algorithms
15 个视频（总计 180 分钟）, 2 个阅读材料, 1 个测验

周2
完成时间为 5 小时
Modules 1 - Project and Application
Graph representations, plotting, analysis of citation graphs
3 个阅读材料, 3 个测验

周3
完成时间为 2 小时
Module 2 - Core Materials
Asymptotic analysis, "big O" notation, pseudocode, breadth-first search
9 个视频（总计 109 分钟）, 1 个测验

周4
完成时间为 4 小时
Module 2 - Project and Application
Connected components, graph resilience, and analysis of computer networks

预备知识

具备与“计算机原理”（PoC）课程同级别的数学和编程经验，没上过这门课也没关系，但是要能够用Python语言编写中等规模（300行以上）的程序，并且对搜索、分类和递归有一个基本的了解；学生应具备坚实的数学基础，其中包括代数、微积分，以及《计算机原理》课程中所涉及的数学概念。开课第一周，同学们可以选择参加等级考试，帮助你们正确评估自己是否具备必须要的背景知识。