自动机理论

Automata

课程概述 我很高兴能够免费提供自动机理论这一在线课程。这门课的设计是基于我在斯坦福大学长期讲授的CS154课程…

斯坦福大学

分享

自动机理论
  • 分类: 计算机
  • 平台: Coursera
  • 语言: 英语

课程概述

我很高兴能够免费提供自动机理论这一在线课程。这门课的设计是基于我在斯坦福大学长期讲授的CS154课程。学生可以观看讲座视频,做测试题目,做作业,参加考试,过程中接受常规性反馈,参加论坛讨论。成功学完这门课的学生将获得结业证书。你需要有良好的互联网环境才能访问课程材料,你也可以通过智能手机观看这些视频。

这门课包含四大领域:(1)有限自动机和正则表达式、(2)上下文无关语法、(3)图灵机和可判定性、(4)难解性理论或NP-完备性问题

为什么要学习自动机理论?

这一主题不仅仅针对想进入复杂性理论领域的同学,不过以此为目标的同学也可以把这门课当作一个良好的开始。这门课真正重点强调的是,实践中人们用到的那些理论。有限自动机、正则表达式、上下文无关语法是经得起实践检验的一些概念,对于编译器而言,它们是必不可少的工具。更重要的是,很多系统所需要的输入远远没有完整编程语言那么复杂,但又比按一个键要复杂很多,这些概念还被用于很多这样的系统中。

不可判定问题和难解问题这些概念则服务于不同目的。不可判定问题是计算机解不可能存在的问题,而难解问题则是有强烈证据证明计算机解存在、但解起来效率很差的有用实践问题。理解这一理论,特别是获得证明问题属于哪类的能力,将让你能够采取下一步方法化简问题或是写代码逼近问题的解。

课程期间,我将证明一些内容。这些证明的目的并不是为了折磨你,或是把你搞糊涂,也不仅仅是为了让你确信我讲的是正确的,而是为了让你理解这些证明,特别是归纳证明,这能让你更好地理解自己的工作。我并不主张证明程序是正确的,但是,但凡你在尝试比较复杂的问题时,脑海中进行一些归纳证明总是必需的,这能保证你的成果在所有情况下正常工作。

课程大纲

第一周:有限自动机
第二周:正则表达式和正规语言性质
第三周:上下文无关语法和语言
第四周:上下文无关语言性质、图灵机简介
第五周:图灵机和不可判定性
第六周:难解问题(NP-完备性)

背景知识

你应该有一些计算机科学课程的基础,包括基本数据结构(例如列表、树、哈希表)和基本算法(例如树遍历、递归编程、大O运行时间)。此外,离散数学中的命题逻辑、图、归纳证明也是对这门课非常有价值的背景知识。
如果你需要复习或学习上述主题,我们推荐一本免费在线教材:《计算机科学基础》,由阿尔·阿霍和我编写,教材链接http://i.stanford.edu/~ullman/focs.html。推荐内容包括:第二章(递归和归纳)、第三章(程序运行时间)、第五章(树)、第六章(列表)、第七章(集合)、第九章(图)、第十二章(命题逻辑)。教材的第十和十一章还有有限自动机、正则表达式、上下文无关语法的介绍。阅读第十章能为本课程第一周的学习做好准备。
这门课包括两次编程练习,这就要求对Java或Python的了解。但是,这些练习是选做的。你将会得到自动反馈,但结果不计算在本课程的评分范围内。所以,就算不熟悉Java和Python,你仍然可以毫无顾虑地选修这门课。

参考资料

这门课的内容紧密围绕《自动机理论,语言和计算导论》第三版(2007),约翰·霍普克洛夫特、拉杰夫·莫特瓦尼、杰弗里·乌尔曼著,艾迪生-韦斯利出版社出版。 不过,你不需要专门去买这本书。这门课完全是自给自足的,所有作业和考试都将完全基于视频讲座中所讲授的概念。

授课形式

每周3-4个讲座视频。很多视频都长于一般MOOC视频,你可以随时暂停,按照你自己的需要将它分成几段来看。

每周将有1-2次笔头作业,总共占课程成绩的50%。你可以重复做这些题目,直到全部做对。每次作业提交时间是相关视频公布后的下下周一。

这门课还有两次选做的编程挑战。

常见问题

完成这门课后,我能否得到结业证书?
能,成功学完这门课的学生将得到授课老师签发的结业证书。

这门课的授课形式是怎样的?
这门课包含一些课程视频,视频都被分成小段,每一段通常是15到45分钟。其中一些视频中会包含测试问题。课程还有一些单独存在、不属于视频中的笔头作业,一些可选编程作业,以及一个期末考试(必须参加)。

学习这门课,我需要花多少时间?
你需要每周5-10小时学习时间才能完成这门课。你每周大约需要观看2小时的视频,包括做视频内不评分的测试题。每周还有评分的选择题作业要做。

(译文转自网易Coursera)

声明:MOOC中国收录之课程均源自下列机构,版权均归他们所有。本站仅作报道并尊重其著作权益,感谢他们对MOOC事业做出的贡献!(排名不分先后)
  • Coursera
  • edX
  • OpenLearning
  • FutureLearn
  • iversity
  • Udacity
  • NovoEd
  • Canvas
  • Open2Study
  • Google
  • ewant
  • FUN
  • IOC-Athlete-MOOC
  • World-Science-U
  • Codecademy
  • CourseSites
  • opencourseworld
  • ShareCourse
  • gacco
  • MiriadaX
  • JANUX
  • openhpi
  • Stanford-Open-Edx
  • 网易云课堂
  • 中国大学MOOC
  • 学堂在线
  • 顶你学堂
  • 华文慕课
  • 好大学在线CnMooc

Copyright © 2008-2015 MOOC.CN 慕课改变你,你改变世界