18.06 线性代数 或 18.700 线性代数


描述

本课程全面地介绍了离散数学-线性和凸规划，流&匹配理论，随机选择和近似算法中的基本算法技巧。我们将利用这些技巧处理一系列的优化问题并找到其有效算法。

主题包括

• 找到一个图的最大匹配需要多长时间？
• 为什么最大流等于最小割？
• 什么是对偶性，如何利用它？
• Is optimization reducible to random sampling?
• 线性规划是否存在强多项式算法？
• 如何寻找一条最短的旅行售货员途径？
• 如何寻找不交的可行流？

形式

每周课堂3小时，此外学生会有定期的作业和两次课堂考试。还有一个课程项目，可以是理论的（如写一篇报告，解决一个公开问题）或实践的（如evaluate an algorithm).


项目

For the course project you will:

1. Work on a problem and/or experimentally evaluate an algorithm;
2. Write a short report and present your findings to class.

可以独立完成或两人一组
Projects should be set up by the day after session #5.


评分