唐常杰翻譯的計(jì)算理論導(dǎo)引02

1、可計(jì)算理論 課程說明和教學(xué)計(jì)劃（2006.2-7）學(xué)分3 周學(xué)時(shí) 4 任課教師 唐常杰每周三 8:00-11:35 地點(diǎn) 研 3-301教材 Material: Michael Sipser (MIT) Required Sipser, Michael, Introduction to the Theory of Computation. PWS Publishing Company, 1997. (Both first and second printing are okay. ISBN 0-619-21674-2)中譯本，計(jì)算理論導(dǎo)引(第二版), 唐常杰 陳鵬 向勇 劉齊宏 譯，機(jī)械工業(yè)出

2、版社出版，.7 ISBN 7-111-19028-9)Additional Lewis, Harry R., and Papadimitriou, Christos H., Elements of the Theory of Computation, 2nd ed. Prentice-Hall, 1997. 內(nèi)容 Chapters 0 - 8.3 (up to the PSPACE-completeness of TQBF) 7/26/20221關(guān)于選擇教材的體會(huì)2001-2002 我們采用教材為： Lewis, Harry R., and Papadimitriou, Christos H.

3、, Elements of the Theory of Computation, 2nd ed. Prentice-Hall, 1997. 2003-2006 采用 Sipser, Michael, Introduction to the Theory of Computation. PWS Publishing Company, 1997. (Both first and second printing are okay.)這兩本書 是目前世界上主要大學(xué)采用最多的教材。經(jīng)驗(yàn)表明，如果學(xué)生數(shù)學(xué)基礎(chǔ)好，用前者較好，如學(xué)生計(jì)算機(jī)基礎(chǔ)好，用后者更受學(xué)生歡迎。目前歐美大學(xué)中計(jì)算機(jī)專業(yè) 用后者的大學(xué)越來

4、越多。網(wǎng)上贊譽(yù)甚多7/26/20222電子教案下載電子教案可在下面三個(gè)網(wǎng)址 下載： (機(jī)械工業(yè)出版社）川大計(jì)算機(jī)學(xué)院： 川大教師主頁： 后兩各地址 可能更新 及時(shí)一些。7/26/20223本電子教案由機(jī)械工業(yè)出版社出版7/26/20224請(qǐng)?zhí)岣倪M(jìn)意見任課教師 ： 唐常杰聯(lián)系信息四川大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 主任。 博士生導(dǎo)師中國計(jì)算機(jī)學(xué)會(huì)數(shù)據(jù)庫專業(yè)委員會(huì)副主任下載教案網(wǎng)址 機(jī)械工業(yè)出版社網(wǎng)址 或 下列網(wǎng)址 聯(lián)系email: 028-8546 6105 經(jīng)驗(yàn)表明，教案年年改，年年都有需改處。 請(qǐng)?zhí)岢龈倪M(jìn)意見。 7/26/20225可計(jì)算理論 課程說明和教學(xué)計(jì)劃PT文件名稱說明： 01_1d2_概念

5、_自動(dòng)機(jī)語言06021220.ppt第一周 ，1.2節(jié)開始主要內(nèi)容最后修改時(shí)間7/26/20226可計(jì)算理論 課程說明和教學(xué)計(jì)劃教材詳略處理 講要點(diǎn)，前后次序有少數(shù)調(diào)整，教學(xué)計(jì)劃，大致1618周 最后兩章不講或用討論班形式討論，有了基礎(chǔ)，如果需要，已經(jīng)能自學(xué)。參考國內(nèi)外同行（如Berkeley, MIT等）對(duì)這門課程教材的 處理經(jīng)驗(yàn)，準(zhǔn)備：略講或自學(xué)的部分 ，要求了解主要思想Section 2.2(中文3.2節(jié)）: the proof that CFL = pushdown automataSection 5.1., linear bounded automataSection 5.2 Pos

6、t correspondence problem 快講的部分， 要求一般了解的章節(jié)，要求了解主要方法和演繹框架Section 6.2 decidability of logical theories (Section 6.2), Section 6.3 Turing reducibility (), Chapter 8 space complexity ().其余未列出的部分要求深入掌握（能作題目 或作難題，通過考試）7/26/20227可計(jì)算理論 課程說明和教學(xué)計(jì)劃考查方式(暫定):30% - Homework (one will be dropped) 20% - Midterm 50%

7、- Final 7/26/20228可計(jì)算理論 課程說明和教學(xué)計(jì)劃Homework : 參見 ”作業(yè).PPT”要求用一個(gè)比較好的本子（如硬面，B5以上），作布置和自選題目，記錄研究與思考，作業(yè)本在檢查后歸還，作為學(xué)生自己的永久的紀(jì)念（上課時(shí)參見示范實(shí)例）。（亦可能復(fù)印部分）作業(yè) 參見 Lecture Slides / Tentative Schedule 草案，將在實(shí)施中調(diào)整進(jìn)度，遇節(jié)假日，運(yùn)動(dòng)會(huì)，重要會(huì)議 則順延,在每次課前1-2周發(fā)布最后修改的PPT，可按PPT 預(yù)習(xí)）7/26/20229可計(jì)算理論目錄Lecture Slides / Tentative Schedule （草案）將在實(shí)施

8、中調(diào)整進(jìn)度,每次課程結(jié)束時(shí)預(yù)報(bào)下兩次進(jìn)度在每次課前1-2周發(fā)布相應(yīng)的電子教案最后修改版本遇節(jié)假日，運(yùn)動(dòng)會(huì)，重要會(huì)議 則順延）參見 http:/tangchangjie/tang_teching.htm7/26/202210可計(jì)算理論目錄Lecture Slides / Tentative Schedule 草案，將在實(shí)施中調(diào)整進(jìn)度，遇節(jié)假日，運(yùn)動(dòng)會(huì)，重要會(huì)議 則順延,在每次課前1-2周發(fā)布最后修改的PDF， 下載和閱讀 iamscucsphd可按PDF 預(yù)習(xí)）1周 Chapter 0: Introduction, mathematical notation, proof techniques

9、Chapter 1: Deterministic finite automata (DFA), nondeterministic finite automata (NFA), 84 pages2周 Chapter 1:DFA=NFA, regular expression (RE), 46 pages2周 Chapter 1: RE=NFA, nonregular languages/RE pumping lemma 39 page3周Chapter 2: Context-free grammars (CFG), Chomsky normal form, all RL are CFG 59 p

10、ages4周Chapte r 2: Pushdown automata (PDA), Non-CF languages/CFL pumpin lemma 73 pages7/26/202211可計(jì)算理論目錄5周 51 pages Chapter 3: Turing machines (TMs), TM decidable languages, TM recognizable languages, Equivalence between multitape TMs Chapter 4: Equivalence between nondeterministic TMs and other mode

11、ls, Church-Turing thesis, Decidable languages, decidability RL/PDAs/RE 6 周 Chapter 4: Decidability CFLs/CFGs, Halting problem, counting/diagonalization, Chapter 4: Undecidability of the Halting problem, TM unrecognizable languages 52pages6 周 Chapter 5: Computation histories, examples of undecidable

12、languages Chapter 5: TM computable functions, mapping reducibility 50pages 7 周 Chapters 0-5: Review session 66 pages8 周 專題討論補(bǔ)充材料 半期考試7/26/202212可計(jì)算理論目錄8 周 Chapter 6: Recursion theorem, undecidability by self-reference, undecidability of mathematical theories 45 pages10 周 Chapter 6 + handout: Kolmogo

13、rov complexity/minimal length descriptions, randomness, arguments by incompressibility 69 pages 11 周 Chapter 7: Time-complexity, polynomial time (P), languages in P, Strong Church-Turing thesis Chapter 7: Nondeterministic polynomial time (NP), SAT 4712周 Chapter 7: Polynomial time reductions, NP-comp

14、leteness, 3SAT versus CLIQUE, Cook-Levin Theorem 7/26/202213可計(jì)算理論目錄13 , NP-completeness of SAT and 3SAT, proving NP- completeness . 14 周 Chapter 7: NP-completeness of HAMPATH, SUBSET SUM Chapter 8: Space complexity, Savitchs theorem, PSPACE, PSPACE completeness, TQBF 7/26/202214關(guān)于同學(xué)討論發(fā)言研究生的課程應(yīng)該有同學(xué)的發(fā)

15、言討論。-三章的部分可作為討論內(nèi)容。 在教師講解下，學(xué)完前面章后， 已經(jīng)有了很好的基礎(chǔ)。我們提供了同學(xué)作報(bào)告PPT的部分素材。這是作為教學(xué)科研的基本訓(xùn)練的一個(gè)重要環(huán)節(jié)，學(xué)生應(yīng)該能根據(jù)教材，作出有自己特色的PPT發(fā)言稿. 這里提供一些素材，試圖減小難度。 PPT不能僅僅是剪報(bào)。一份好的討論班PPT 應(yīng)該有同學(xué)的理解和創(chuàng)新.(素材節(jié)選自教材， 但不能代替教材)從素材作PPT一般 需要用 讀 -減 加 三個(gè)過程。先充分閱讀理解 教材，從此素材中刪去次要語句，增加自己的心得，理解方法，解釋和圖形。PPT應(yīng)該突出思路，突出要點(diǎn), 適當(dāng)?shù)谋扔骺梢詭椭斫狻?/26/202215可計(jì)算理論目錄15周 討論

16、第9章 3人 9.1-9.3.1 .3 9.49.616周 討論 第10章 3人 10.1， 10.2 ， 10.317 周 討論 第10章 4人 11.1-11.2， 11.3, 11.4, 11.5-11.618- 19 周 復(fù)習(xí) 20 周 Final exam, Chapters 0-8. Open book open notes.中間可能有節(jié)假日，運(yùn)動(dòng)會(huì)或會(huì)議的耽誤，相應(yīng)時(shí)間安排為自習(xí)，作業(yè)，或網(wǎng)上答疑，全課程可能需要21周7/26/202216關(guān)于引用和標(biāo)注1 本電子教案以 Sipser, Michael, 等著的Introduction to the Theory

17、of Computation（ PWS Publishing Company, 1997）. 為基本教材 ，結(jié)合了教案作者在科研和教學(xué)中的心得體會(huì)（用五角星 符號(hào) 標(biāo)出），教案中引用了原著作中大量材料、圖表，這是教案中必須的引用，在此對(duì)原著作者致謝。電子教案中也引用了在國內(nèi)外會(huì)議、課堂，網(wǎng)絡(luò)上學(xué)習(xí)到的一些資料。有些資料是人們共創(chuàng)、共享和共傳的知識(shí)財(cái)富，一時(shí)難以查出資料的最先出處。一并在此向 所引用內(nèi)容的作者們致謝。2 PowerPoint 頁面 共計(jì) 800 多頁， 隨時(shí)修改增減3 有些頁面是多頁連續(xù)的動(dòng)感頁面，一些淡色字句留下的懸念，會(huì)在下頁用增強(qiáng)色調(diào)突出。7/26/202217關(guān)于引用和標(biāo)注4 本電子教案以在 第一周內(nèi)容 0_0可計(jì)算理論教學(xué)計(jì)劃060724.ppt列出了四川大學(xué)計(jì)算機(jī)學(xué)院2002-2006年度的教學(xué)計(jì)劃。實(shí)踐表明，深度難度基本合適5 本教案作