Close Banner

可计算性、复杂性和算法

算法的强大之处和局限所在

高级

大约 0 个礼拜

6小时每周 (按照自己的节奏)

由以下企业参与制作:
加入成千上万的全球学员

开始免费课程

加入课程
免费
可享受
课程视频
实战练习
高级

大约 0 个礼拜

6小时每周 (按照自己的节奏)

由以下企业参与制作:
加入成千上万的全球学员

课程概述

这门课程在佐治亚理工学院开设为 CS6505 课程,属于在线硕士学位 (OMS) 的课程之一。但是在优达学城学习这门课程并不能获得 OMS 学位学分。

在这门课程里,我们将提出各种问题:“什么是计算机?计算存在哪些限制?有没有计算机无法解决的问题?有没有计算机无法快速解决的问题?我们可以高效解决哪些问题?如何开发这些算法?”了解算法的强大之处和局限所在,可以帮助我们开发让现实生活中的计算机更加智能、速度更快、更安全的工具。

为什么学习这门课程?

你将学习各种工具和技巧,当你遇到棘手的问题时,这些工具和技巧会帮助你找到有效的解决方案。如果不使用这些工具和技巧,你将花费大量的时间去解决问题,结果一无所获或者白费力气做重复的工作。

先修要求

学员应该熟练掌握离散数学基本知识。Ken Rosen 的《离散数学和其应用情形》是本课程的最佳先修读物。

如果对于以下任何问题,你的答案是否定的,那么建议你在学习本课程之前或学习期间掌握一些背景知识。

  1. 你能演示证明 1 到 n 之间所有数字的和是 n(n+1)/2 吗?你能用归纳法证明吗?
  2. 你能用 O(n log n) 算法对 n 个数字排序吗?
  3. 假设有一个 nxn 的矩阵 A 以及 n 维的矢量 b,你能用多项式时间算法算出 Ax=b 中的矢量 x 吗?

查看使用优达学城的技术要求

学习计划

第 1 课:可计算性

  • 语言和可数性
  • 图灵机
  • 丘奇-图灵论题
  • 普遍性
  • 不可判定性

第 2 课:复杂性

  • P 和 NP
  • NP 完全性
  • NP 完全问题
  • 金奖券

第 3 课:算法

  • 动态程序设计
  • 快速傅里叶变换
  • 最大流量
  • 最大二部图匹配
  • 线性编程
  • 二元性
  • 随机算法
  • 近似算法

讲师与合作伙伴

Charles Brubaker

Charles Brubaker

Charles Brubaker 在 2009 年获得佐治亚理工学院计算机科学博士学位。随后的四年在高中教授计算机科学,同时在亚特兰大的佩斯学院 (Pace Academy) 担任篮球教练。在 2012 年,受优达学城启发,他开始在平板电脑上录制课程,创建在线测试题,并通过系统自动对作业评分向学生提供即时反馈。这次创业的成功让他坚信优达学城代表教育的未来趋势,于是他在 2013 年夏天加入优达学城。

Lance Fortnow

Lance Fortnow

Lance Fortnow is professor and chair of the School of Computer Science of the College of Computing at the Georgia Institute of Technology. His research focuses on computational complexity and its applications to economic theory.

Fortnow received his Ph.D. in Applied Mathematics at MIT in 1989 under the supervision of Michael Sipser. Before he joined Georgia Tech in 2012, Fortnow was a professor at Northwestern University, the University of Chicago, a senior research scientist at the NEC Research Institute and a one-year visitor at CWI and the University of Amsterdam. Since 2007, Fortnow holds an adjoint professorship at the Toyota Technological Institute at Chicago.

Hariharan Venkateswaran

Hariharan Venkateswaran

H. Venkateswaran obtained his Ph.D. in Computer Science from the University of Washington in 1986. He then joined the faculty of Georgia Institute of Technology as an Assistant Professor, where he has pursued his research interests in Complexity Theory, Information Security, and Parallel Computation. A renowned teacher on campus, he was awarded "The William A “Gus” Baird Faculty Teaching Award" in 2008.

官方微信公众号二维码

优达学城(Udacity)微信