※ [本文转录自 neoneon 信箱] 作者: [email protected] ("爱宕有机奈米负离子猫") 标题: [心得] 正规语言概论 时间: Sun Jul 10 08:26:23 2016 作者: yukuro (魔法师mystery) 看板: NCTU-Teacher 标题: [心得] 正规语言概论 时间: 2011/01/26 Wed 00:00:50 （按Ctrl+v 预览，稍微修一下版面，可让你这篇文章更专业喔^^） ⊕课名⊕ 正规语言概论(英文授课) ▲教授▲ 黄廷禄 ★修课年度★（请加注开课单位 如:大三通识、XX系选修、XX所） 大三资工组必修 ￡教了什麽￡（课程大概内容。或是额外学会了什麽东西。） 1. Finite State Automata and its property(also its theorem) (i) DFA/NFA (ii) Regular expression (iii) Equivalence : DFA/NFA, RE/NFA(DFA) (iv) Pumping lemma (v) The closure property of regular langauge (vi) Myhill Nerode's Theorem and minimize the Finite state automata 2. Context-free grammer (i) CFG and Chomsky Normal Form (ii) Push down automata (iii) CYK algorithm (iv) Inherent Ambiguity proved by Odgen's lemma (v) Decision problem about CFL 3. Turing machine (i) Turing Thesis (ii) What is Turing-recognizable? and What is (Turing-)decidable? What is "emunerate the language"? 4. Decidable and Undecidable 这要看课本,他会开始证明和引用很多很多定理,来说明许多以上automata的 decidable 和 undecidable 性质 另外还有Halting problem 和diagnalization method 最後会有Co-Turing recognizable这个名词的出现,再连到一个decidable language is Turing-recognizble and Co-Turing recognizable. 5. Reduction, computable function, mapping reducible 延续第四章,着重在如何利用reduction的技巧,来证明undecidable 还有Post Correspondence Problem(PCP) 6. Computational Complexity and P/NP problem(包含NP-complete) 这个看课本就知道... 从以上看来,教的东西还不少(千万不要被课本的厚度所骗!!) ◆上课方式◆（投影片、团体讨论、老师教学风格） 1.老师用补充的讲义为主,偶尔会回到课本来说明,另外老师从一开始就强调: 离散数学的Diagnalization method很重要,所以如果听到,千万不要当作耳边风!! 2.另外,从一开始你会感受到这门课不友善的地方,就是一直下定义,给定理,证明. (老师很喜欢导定理喔!) 而且,老师在前两章的内容,教了还蛮多的内容,而且很多都不在(Sipser)课本上, 很多内容可能是从其他书上撷取过来的,前两章会用这种方式教,所以讲义的内容 一定要弄懂!!而且这里会突然生出很多以前没用过的符号,所以要专心才能读懂 3.以上是前两章的运作,但到第三章~第七章就会比较缓慢,老师会很用心和你解释 decidable, emunerable, Turing-recoginizable的意涵,还有再讲定理的时候, 会尽量用比较口语的方式讲,证明为什麽要这样写和证明的意思是什麽 另外,还会补充一些习题的解答,和提醒一些容易犯错的部分 4. 在最後约2个礼拜,会进入Time Complexity的部分,但这个部分全部都是定义定理. 会定义一些名词,导很多定理.如果在3~5章基础不好的话,应该会看不懂 ▼考试作业▼ 两次大考,各40%, 作业+小考20% 第一次作业是设计一些DFA/NFA,这部分学生会比较有机会拿高分 第二次作业,大多数会变很低分. 为什麽呢? 因为全都是证明题!! 一般学生都不想去 作证明吧,而老师是很严谨的人,所以大多数人写得证明,老师都不会太满意 第三次和第四次作业,也都是证明 考试是采Open book,可带任何的纸本(讲义或书籍或笔记),不可带电子的,但还是要认真看 ,才能应付考试喔!(免得脑筋转不过来) 而题型是,是非题+证明或问答题 第一次考20题是非(40%), 30%证明(其中一题可直接抄讲义), 30% 基本的Push down automata 设计 第二次考35题(70%)是非,10%问答,20%证明 ￥其他￥（是否注重出席率or严禁迟到？需要的基础？） 离散的 logic 和 set 的部分非常重要 老师後来不喜欢学生跷课,有一次小考说:为鼓励出席,只要出席就满分,但小考 最重要的是上课专心听,不会考太难的 ￠最後想说的话￠ 如果你的老师用的课本是Sipser的话,那麽这门课就一半以上都是证明了,绝对逃不掉. (Note:黄廷禄老师和陈颖平老师都用这一本) 而杨武老师的班级是用Linz的 An introduction to Formal Language and Automata,这本比较强调Automata和Grammer 的设计想法和实例,所以基本上对初学者来讲,是比较好读的,而Sipser的Introduction to theory of Computaion,就不强调automata和grammer的设计,而是强调这些东西运作的 "性质", 所以是以证明为主.当然,後面不用说了,计算理论和复杂度理论,本来就是由 定义和定理构成的,所以这门课不管修到谁的,都是一大挑战. Note:千万不要以为杨武老师的课会比其他老师难,这很难说= = ＆谁适合修这门课＆ 如果是修黄老师的,一定要对定义,定理和导定理,有深厚的兴趣和一定的能力,不然会修得 很辛苦.不过如果是这样的学生,应该会很喜欢和黄老师讨论问题,喜欢他上课说明的观点. -- ※ Origin: 交大次世代(bs2.to) ◆ From: 218-173-157-90.dynamic.hinet.net 作者从 218-173-157-90.dynamic.hinet.net 修改文章於 2011/01/26 Wed 00:06:33 推 gxlkhhc：推荐这篇文章 01/26 00:11 推 rockmanray：满喜欢廷禄葛格的上课方式，基本上老师都会深入浅出 01/26 00:12 推 rockmanray：不过举例好坏大概一半一半，老师本身满有理想 01/26 00:13 推 rockmanray：虽然一把年纪了XD 另外这门课其实需要一些基础 01/26 00:15 推 rockmanray：就如同原po所说的：离散等等 所以其实要额外再复习一些 01/26 00:16 推 advanding100：推荐这篇文章 01/26 01:18 推 nowar100：推黄老师 这种定理推导课 我也上过老师另一门的数理逻辑 01/26 01:33 → nowar100：如果愿意好好跟不排斥的话 其实跟老师脚步走我觉得很有趣 01/26 01:34 推 dogsbear：写的很清楚 01/26 01:37 推 kougousei：推荐这篇文章 01/26 03:28 推 foxs91092：推荐黄老师 老师上课很清楚，相当严谨 01/26 13:34 推 foxs91092：而且老师教学相当认真，有问题都可以去跟老师讨论 01/26 13:35 推 yukuro：其实我也很好奇,别的老师怎麽上的,感觉上上法很多 01/26 15:40 → yukuro：因为这方面大概有几种可能:着重在Language 或是automata 01/26 15:41 → yukuro：是一种上法,而着重在计算理论,也是一种上法 01/26 15:41 → yukuro：所以希望其他人也多分享 01/26 15:42 推 ken77921：推荐这个老师 01/26 22:59 推 sword：整堂课充满各种数学定理证明 跟着老师学得很充实(′‧ω‧) 01/27 17:39 推 sword：不要需要点数学基础...最少要回忆起大一离散 01/27 17:40 推 icnivad：老师教地好啊~~^^ 01/31 19:08

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: neoneon (106.105.175.48), 07/11/2016 23:46:20