唐常杰翻译的计算理论导引22
- 格式：doc
- 大小：555.50 KB
- 文档页数：17
下载文档原格式
合集下载
3上下文无关文法及语言
S yields 0n1n according to S 0S1 00S11 … 0nS1n 0n1n
长翅膀的规则 与 前后文无关，只管自己长, （我行我素） 比较简单，当然描述能力原比较有限
2012-7-26 10/53
Context-Free Grammars (Def.2.1) ep94
复习 补充定理 ：正则语言之交正则。上次讲过。
预备引理 Ex1.39问题： { 0n1m | n,mN}=0*1*,是正则语言
Let C = { w | w中0,1 个数一样多} 求证它不是RL 反证法: Assume that C is regular Take the regular F = { 0n1m | n,mN}, then for the intersection: CF = { 0n1n | nN } But we know that CF is not regular Conclusion: C is not regular
Introduction to the Theory of Computation
特别鸣谢:唐常杰教授提供的素材及原稿
Chapter2 Context-Free Languages (CFL)
2012-7-26
1/53
(20பைடு நூலகம்7.2.24 Xing-hua park)
2012-7-26
2/53
2012-7-26
7/53
Context-Free Languages (Ch. 2)
前后文无关语言
Context-free languages allow us to describe nonregular languages like { 0n1n | n0}
长翅膀的规则 与 前后文无关，只管自己长, （我行我素） 比较简单，当然描述能力原比较有限
2012-7-26 10/53
Context-Free Grammars (Def.2.1) ep94
复习 补充定理 ：正则语言之交正则。上次讲过。
预备引理 Ex1.39问题： { 0n1m | n,mN}=0*1*,是正则语言
Let C = { w | w中0,1 个数一样多} 求证它不是RL 反证法: Assume that C is regular Take the regular F = { 0n1m | n,mN}, then for the intersection: CF = { 0n1n | nN } But we know that CF is not regular Conclusion: C is not regular
Introduction to the Theory of Computation
特别鸣谢:唐常杰教授提供的素材及原稿
Chapter2 Context-Free Languages (CFL)
2012-7-26
1/53
(20பைடு நூலகம்7.2.24 Xing-hua park)
2012-7-26
2/53
2012-7-26
7/53
Context-Free Languages (Ch. 2)
前后文无关语言
Context-free languages allow us to describe nonregular languages like { 0n1n | n0}
翻译理论学习知识.docx
《翻译理论与实践》考试理论部分复习提纲一、翻译定义：1.张培基——翻译是用一种语言把另一种语言所表达的思维内容准确而完整地重新表达出来的语言活动。
3.刘宓庆——翻译的实质是语际的意义转换。
4.王克非——翻译是将一种语言文字所蕴含的意思用另一种语言文字表达出来的文化活动。
5.泰特勒——好的翻译应该是把原作的长处完全地移注到另一种语言，以使译入语所属国家的本地人能明白地领悟、强烈地感受，如同使用原作语言的人所领悟、所感受的一样。
6.费道罗夫——翻译就是用一种语言把另一种语言在内容与形式不可分割的统一中所业已表达出来的东西准确而完全地表达出来。
7. 卡特福德——翻译的定义也可以这样说：把一种语言（Source Language）中的篇章材料用另一种语言（Target Language）中的篇章材料来加以代替。
8.奈达——翻译就是在译入语中再现与原语信息最切近的自然对等物，首先就意义而言，其次就是文体而言。
“ Translating consists in reproducing in the receptor language the closest natural equivalent of the source language message, first in terms of meaning and secondly in terms of style.” ---Eugene Nida纽马克——通常（虽然不能说总是如此），翻译就是把一个文本的意义按作者所想的方式移译入另一种文字（语言）。
“ Translation is a craft consisting in the attempt to replace a written message and/or statement in one language by the same message and/or statement in another language”. --- Peter Newmark10. “ Translation is the expression in one language (or target language 译入语 ) of what has been expressed in another language (source language 原语), preserving semantic and stylistic equivalences.” --- Dubois12.13.Translation or translating is a communicative activity or dynamic process in which the translator makes great effort to thoroughly comprehend a written message or text in the source language and works very hard to achieve an adequate or an almost identical reproduction in the target language version of the written source language message or text.二、翻译标准1.翻译的标准概括为言简意赅的四个字：“忠实（faithfulness）、通顺（ smoothness）”。
计算理论14哈米尔顿NP完全
Professor :
唐常杰
TangChangjie@
/~chjtang
Students : Ph.D.2000-- 2006, SCU
Style
可计算理论 2016/5/26
: Lecture / Seminar
wbfeng@ 1/55
变量与数表的对应
子句号数
+x1
–x 1
1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1
2 0 1 1 0 0 0 1 0 0 0 1 1
3 0 0 0 1 0 1 0 0 0 0 0 0 1 1
4 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1
Ep270 Cp179
… because 11 cannot be made out of {2,4,8} 问题的形式化描述：
可计算理论
2016/5/26
wbfeng@
3/55
7.5 几个NP-完全问题
复习 定理7.21 子集和 问题 Subset-Sum 属于NP cp165 当时作 为自学内容。 问题的直观实例 (1)不找补 购物 (2) 装背包， 又称背包问题
3CNF formula:
( x1 x 2 x 3 ) ( x1 x 2 x 4 ) (x2 x2 x3 ) ( x1 x 3 x 4 )
y1
Z1
1 1
0 0 1 1
0 0 0 0 1 1
+x2 –x 2 +x2
–x 3 +x4 –x 4
y2 Z2 y2
Z3 y4 Z4
今日要点
Section 7.5: P-completeness of Subset-Sum Hamiltonian Path 材料详略、次序 与书上不完全一样， 主要考虑便于教学和理解
中国翻译理论
一、佛经翻译时期安世高——小乘佛经的首译者安世高（东汉）：西域安息人，太子，博学多识，笃信佛教，弃王位而向佛，游化西域，后旅居中国，通晓汉语，注重修行，译经20多年，多是直译。
“义理明晰，辩而不华”，《明度五十校计经》，开后世禅学之源。
支谦——《法句经序》支谦（三国）：月支人，博览经籍，莫不谙究。
世间伎艺，多所综习。
遍学异书，通六国语。
孙权时（二二二―二五二）拜为博士，辅导太子孙亮。
谦以经多梵文，集众本译为汉文行于世。
约三十年间，译经八十八部、一百一十八卷。
其翻译以大乘“般若性空”为重点。
反对译文尚质，主张“曲得圣义，辞旨文雅”，首创“会译”，译文加注也始于他，《法句经序》是中国首篇重要译论。
鸠摩罗什——最著名的佛经翻译大师鸠摩罗什（六朝），印度人，我国著名佛教学者、佛经翻译家。
出家后，通晓大乘经论，后到了中国长安，前后所译的经论，有380多卷。
鸠摩罗什倾向于意译，“其文约而诣（畅达），其旨婉而彰”，提出了表现原作文体风格问题，促进了六朝佛学繁荣和隋唐佛教诸宗形成。
释道安——五失本，三不易释道安（晋代）：著名佛教学者，讲授《般若经》。
他不懂梵文，通过同本异译比较研究翻译。
他貌丑心慧，“穷览经典，钩深致远”后，对佛经进行注释，凡二十二卷。
利于佛教的广泛传播，为后世佛经注释作出范例。
还总结出翻译的“五失本，三不易”学说，具有翻译本体论意义。
(一)胡语里边，倒装句很多，翻译时必须要改过来，使之顺从汉语语法，适应中文的结构；(二)胡语的经典文字质朴，而中国人喜好文字华美，翻译时为了适合中国人好文的习惯，在文字上不得不加以润饰，以便流通；(三)胡经原原本本，十分详细，尤其是颂文部分，同一意义往往要反复三、四次，翻译时，对这些重复的句子要加以删略；(四)胡经中在长行之后，另有重颂，复述长行的内容，翻译时往往也得删除，才能使译文洗练；(五)胡经中，每说完一事，再说另一件事时，往往还要把前边那件事重说一遍，因此翻译时，也不得不对这些重复的话一并删除。
唐常杰翻译的计算理论导引
内容 Chapters 0 - 8.3 (up to the PSPACE-completeness of TQBF)
27.02.2019 1
关于选择教材的体会
2001-2002 我们采用教材为： Lewis, Harry R., and Papadimitriou, Christos H., Elements of the Theory of Computation, 2nd ed. Prentice-Hall, 1997.
27.02.2019
27.02.2019 2
电子教案下载
电子教案可在下面三个网址 下载： 川大计算机学院： /~tangchangjie/teach/tang_teaching.htm 川大教师主页： /waim03/scu_cs/teach/tang_teching.htm 后两各地址 可能更新 及时一些。
2003-2006 采用 Sipser, Michael, Introduction to the Theory
of Computation. PWS Publishing Company, 1997. (Both first and second printing are okay.)
这两本书 是目前世界上主要大学采用最多的教材。 经验表明，如果学生数学基础好，用前者较好，如学生计算机 基础好，用后者更受学生欢迎。 目前欧美大学中计算机专业 用后者的大学越来越多。网上赞誉 甚多
四川大学计算机学院 可计算理论 课程说明和教学计划（2006.2-7）
学分3 时间 周学时 4 每周三 8:00-11:35 任课教师 唐常杰 地点 研 3-301
教材 Material: Michael Sipser (MIT)
唐常杰翻译的计算理论导引20
第8章 空间复杂性 (学生讨论用ＰPT 素材)作为教学科研的基本训练的一个重要环节，学生应该能根据教材，作出有自己特色的PPT 发言稿. 这里提供一些素材，试图减小学生的工作难度。
PPT 不能仅仅是剪报。
一份好的讨论班PPT 应该有同学的理解和创新.(素材节选自教材 但不能代替教材)从素材作PPT 一般 需要用 读 --减 ---加 三个过程。
（a ） 先充分阅读理解 教材，（b ） 从此素材中删去次要语句，（c ） 增加自己的心得，理解方法，解释和图形。
PPT 应该突出思路，突出要点, 适当的比喻可以帮助理解。
定义8.1 令M 是—个在所有输入上都停机的确定型图灵机。
M 的空间复杂度(space complexity ) 是一个函数f ：N →N ，其中f (n )是M 在任何长为n 的输入上扫描带方格的最大数。
若M 的空间复杂度为()n f ，则称M 在空间()n f 内运行。
定义8.2 令f ：N →R +是一个函数。
空间复杂性类SPACE （()n f ）和NSPACE （()n f ）定义如下：SPACE(()n f ) = {L |L 是被O(f (n ))空间的确定型图灵机判定的语言}NSPACE(()n f ) = {L |L 是被O(f (n ))空间的非确定型图灵机判定的语言}例8.3 第7章介绍了NP 完全问题SAT ，现在证明用线性空间算法能求解SAT 问题。
因为SAT 是NP 完全的，所以SAT 不能用多项式时间算法求解，更不能用线性时间算法求解。
因为空间可以重用，而时间不能，所以空间的能力显得比时间强得多。
M l ＝“对输入＜φ＞，φ是布尔公式：1）对于φ中变量x 1，x 2…，x m 的每个真值赋值2） 计算φ在该真值赋值下的值。
3）若φ的值为l ，则接受；否则拒绝。
”显然机器M 1是在线性空间内运行，这是因为每一次循环都可以复用带子上的同一部分。
该机器只需存储当前的真值赋值，则只需要消耗O (m )空间。
唐常杰翻译的计算理论导引
四川大学计算机学院 可3
周学时 4
任课教师 唐常杰
时间 每周三 8:00-11:35
地点 研 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)
CS_Dept.Sichaun Univ.
3
本电子教案由机械工业出版社出版
可计算理论 2020/9/11
CS_Dept.Sichaun Univ.
4
请提改进意见
任课教师 ： 唐常杰 联系信息 四川大学计算机科学与技术系 主任。 博士生导师 中国计算机学会数据库专业委员会副主任 下载教案网址 机械工业出版社网址 或 下列网址
内容 Chapters 0 - 8.3 (up to the PSPACE-completeness of TQBF)
可计算理论 2020/9/11
CS_Dept.Sichaun Univ.
1
关于选择教材的体会
2001-2002 我们采用教材为： Lewis, Harry R., and Papadimitriou, Christos H., Elements of the Theory of Computation, 2nd ed. Prentice-Hall, 1997.
川大计算机学院： /~tangchangjie/teach/tang_teaching.htm
周学时 4
任课教师 唐常杰
时间 每周三 8:00-11:35
地点 研 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)
CS_Dept.Sichaun Univ.
3
本电子教案由机械工业出版社出版
可计算理论 2020/9/11
CS_Dept.Sichaun Univ.
4
请提改进意见
任课教师 ： 唐常杰 联系信息 四川大学计算机科学与技术系 主任。 博士生导师 中国计算机学会数据库专业委员会副主任 下载教案网址 机械工业出版社网址 或 下列网址
内容 Chapters 0 - 8.3 (up to the PSPACE-completeness of TQBF)
可计算理论 2020/9/11
CS_Dept.Sichaun Univ.
1
关于选择教材的体会
2001-2002 我们采用教材为： Lewis, Harry R., and Papadimitriou, Christos H., Elements of the Theory of Computation, 2nd ed. Prentice-Hall, 1997.
川大计算机学院： /~tangchangjie/teach/tang_teaching.htm
中国的翻译理论简介
马克思主义著作的翻译是“五四” 后我国翻译事业的另一个重要方面， 我国早期马克思主义著作翻译家主要有李大钊、李汉俊、李达、李立三、 王一飞、艾思奇等，其中最有影响的译作是陈望道翻译的《共产党宣 言》，它对中国的新民主主义革命起着决定性的作用，其次就是郭大力 译介的《资本论》。
著名文学翻译家鲁迅
傅雷主要译作：伏尔泰、巴尔扎克、罗曼·罗兰 的重要作品。有《约翰·克利斯朵夫》 、传记 《贝多芬传》 、 《托尔斯泰传》 、 《米开朗琪 罗传》；巴尔扎克名著《高老头》 、 《欧也 妮·葛朗台》 、 《贝姨》 、 《邦斯舅舅》 、 《夏倍上校》 、 《幻灭》 ；伏尔泰的《老实 人》 、 《天真汉》 ；梅里美的《嘉尔曼》 、 《高龙巴》等等共三十余部作品。
南怀仁
南怀仁为清朝廷制造的6件天文仪器，至今还保存 在北京古观象台上。在南怀仁逝世300周年的时候， 中国政府向比利时鲁汶大学南怀仁基金会赠送了 “天球仪”（即南怀仁设计制造的大型天文仪器之 一）的模型，至今保存在南怀仁厅前。
比利时鲁汶大学建立的怀仁厅
中国近代翻译家之一：严复
严复（1854年1月8日－1921年10月27日）乳名体干，初名传初， 改名宗光，字又陵，后名复，字几道，晚号野老人，福建侯官 （后并入闽县，称为闽侯，今福州市）人。他系统地将西方的社 会学、政治学、政治经济学、哲学和自然科学介绍到中国，是清 末很有影响的资产阶级启蒙思想家，翻译家和教育家，是中国近 代史上向西方国家寻找真理的“先进的中国人”之一。
二十世纪中国学派的六大翻译理论
第一个翻译理论家是严复，他在《天演论》(Evolution and Ethics and other Essays)中提 出了“译事有三难：信、达、雅”（ faithfulness, expressiveness, elegance） ，即“信、 达、雅”三原则。这三个字的影响之大，可以说是“世界之罪”。因为二十世纪的中国译 者几乎没有不受这三个字影响的 (已衍生出“信达切”(刘重德)、“信达贴”（蔡思果）、 “信达优”（许渊冲）、“信达似”（裘克安）、信达+X等) 。“信”是强调译文必须忠 实于原文，“达”是强调译文应该通顺易懂，“雅”在严复时代指的是桐城派风格，现在 一般赋予“雅”新的涵义，即要求译文有文才。
著名文学翻译家鲁迅
傅雷主要译作：伏尔泰、巴尔扎克、罗曼·罗兰 的重要作品。有《约翰·克利斯朵夫》 、传记 《贝多芬传》 、 《托尔斯泰传》 、 《米开朗琪 罗传》；巴尔扎克名著《高老头》 、 《欧也 妮·葛朗台》 、 《贝姨》 、 《邦斯舅舅》 、 《夏倍上校》 、 《幻灭》 ；伏尔泰的《老实 人》 、 《天真汉》 ；梅里美的《嘉尔曼》 、 《高龙巴》等等共三十余部作品。
南怀仁
南怀仁为清朝廷制造的6件天文仪器，至今还保存 在北京古观象台上。在南怀仁逝世300周年的时候， 中国政府向比利时鲁汶大学南怀仁基金会赠送了 “天球仪”（即南怀仁设计制造的大型天文仪器之 一）的模型，至今保存在南怀仁厅前。
比利时鲁汶大学建立的怀仁厅
中国近代翻译家之一：严复
严复（1854年1月8日－1921年10月27日）乳名体干，初名传初， 改名宗光，字又陵，后名复，字几道，晚号野老人，福建侯官 （后并入闽县，称为闽侯，今福州市）人。他系统地将西方的社 会学、政治学、政治经济学、哲学和自然科学介绍到中国，是清 末很有影响的资产阶级启蒙思想家，翻译家和教育家，是中国近 代史上向西方国家寻找真理的“先进的中国人”之一。
二十世纪中国学派的六大翻译理论
第一个翻译理论家是严复，他在《天演论》(Evolution and Ethics and other Essays)中提 出了“译事有三难：信、达、雅”（ faithfulness, expressiveness, elegance） ，即“信、 达、雅”三原则。这三个字的影响之大，可以说是“世界之罪”。因为二十世纪的中国译 者几乎没有不受这三个字影响的 (已衍生出“信达切”(刘重德)、“信达贴”（蔡思果）、 “信达优”（许渊冲）、“信达似”（裘克安）、信达+X等) 。“信”是强调译文必须忠 实于原文，“达”是强调译文应该通顺易懂，“雅”在严复时代指的是桐城派风格，现在 一般赋予“雅”新的涵义，即要求译文有文才。
唐常杰翻译的计算理论导引05.
递归结构，增加 一个运算符号 的 构造方法
可计算理论 2019/10/18
ChjTang CS_Dept.Sichaun Univ.
9/47
Thm 1.28: RL ~ RE ep66 cp40（读一下）
Thm 1.28 L is RL there exists RE E such that L=E
11/47
Thm 1.28: RL ~ RE ep66 cp40（读一下）
Thm 1.28 L is RL there exists RE E such that L=E
通常 L={ ..|….}
E形如 (a+b)C+(d.g)*
(无穷) 集合表达式
有限字母 有限运算 构造，可计算
We need to prove both ways: 左边 右边
Given an alphabet , R is a regular expression if
1. R = a, with a
2. R =
递归基础
3. R =
4. R = (R1R2), with R1 and R2 regular expressions 5. R = (R1R2), with R1 and R2 regular expressions 6. R = (R1*), with R1 a regular expression
• 10.1， XXX XXX （导师 XXX 教授）
• 10.2 XXX XXX （导师 XXX 教授）
• 10.3 XXX XXX （导师 XXX 教授）
•18 周 讨论 第10章 4人
• 11.1--11.2， XXX XXX （导师 XXX 教授）
mybible
一．计算机基础理论1>算法与数据结构***(1)《The art of computer programming》Vol 1,2,3,4The Art of Computer ProgrammingAuthor: Donald.E.Knuth/~knuth/t aocp.htmlBook Info: 这部书被誉为20世纪最重要的20部著作之一,与Einstein的<<相对论>>并列,是计算机科学领域的权威著作.全书共分7卷,目前已经出版了3卷,被誉为"计算机程序设计理论的荷马史诗","可与牛顿的<<自然科学的数学原理>>媲美的巨著".作者数学方面的功底造就了本书严谨的风格,虽然本书不是用当今流行的程序设计语言描述的,但这丝毫不损伤它"程序设计史诗"的地位.道理很简单,它内涵的设计思想是永远不会过时的.The Art of Computer Programming 原计划要出七册,但目前只完成了三册.该书有日文,俄文,西班牙文等许多国的版本.其中,中文版由国防大学出版社发行.The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition)Author: Donald.E.KnuthPublisher: Prentice HallAmazon Reviews: Book Info: 卷1为基础运算法则,该书以基本的编程概念和技术为开始,然后讲述信息结构--计算机内信息的表示法,数据元素间的结构关系以及处理它们的有效方法.主要应用于模拟,数字方法,符号计算,软件和系统设计.许多简单和重要的运算法则和技术已添加到前一版本中,精确的初步计算部分已经修改,以适应当前趋势.The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition) Author: Donald.E.KnuthPublisher: Prentice HallAmazon Reviews: Book Info: 第2卷对半数值算法领域做了全面介绍,分"随机数"和"算术"两章.本卷总结了主要算法范例及这些算法的基本理论,广泛剖析了计算机程序设计与数值分析间的相互联系.第3版中特别值得注意的是Knuth对随机数生成程序的重新处理和对形式幂级数计算的讨论.The Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition)Author: Donald E.KnuthPublisher: Prentice HallAmazon Reviews: Book Info: 卷3为分拣和搜索,这是本书的第1个修订版,它是对计算机分拣和搜索的一流技术的最全面的研究,它扩展了卷1中数据结构的处理方法,将大小数据库以及内存和外部存储都包含在内.本书包括对计算机方法仔细检查的选择方案,和其效率的大量分析.本书该版的独特之处在于优化了的分拣,以及对通用散列法和排列法的新的理论论述.作者简介:Donald.E.Knuth(唐纳德.E.克努特,中文名高德纳)是算法和程序设计技术的先驱者,是计算机排版系统TeX和METAFONT的发明者,他因这些成就和大量创造性的影响深远的著作(19部书和160篇论文)而誉满全球,在计算机科学领域享有崇高的威望,是计算机科学界公认的大宗师.作为斯坦福大学计算机程序设计艺术的荣誉退休教授,他当前正全神贯注于完成其关于计算机科学的史诗性的七卷集.这一伟大工程在1962年他还是加利福尼亚理工学院的研究生时就开始了.Knuth教授获得了许多奖项和荣誉,包括美国计算机协会图灵奖(ACM Turing Award),美国前总统卡特授予的科学金奖(Medal of Science),美国数学学会斯蒂尔奖(AMS Steele Prize),以及1996年11月由于发明先进技术荣获的极受尊重的京都奖(KyotoPrize).现与其妻Jill生活于斯坦福校园内.Donald.E.Knuth人生最辉煌的时刻在斯坦福大学计算机系渡过,获得了美国计算机协会图灵奖,成为本领域内当之无愧的泰斗.英文原版下载/redirect.php?tid=347 54计算机程序设计艺术第1卷基本算法（第3版）（英文影印版） / Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition)Donald E.Knuth / E.KNUTH / 2002-11-1 / 清华大学出版社 / 第1卷:基本算法(第3版)[英文影印版] / 80.00计算机程序设计艺术第2卷半数值算法（第3版）（英文影印版） / Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition)（美）Donald E.Knuth / 2002-09-01 / 清华大学出版社 / 83.0 / 精装计算机程序设计艺术(第3卷)-排序和查找(英文影印版) / Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition)（美）Donald E.Knuth / 2002-9-1 / 清华大学出版社 / 85.0 / 精装***(2)《Introdution to algorithm》Author:Thomas H.Cormen ,Charles E.Leiserson ,Ronald L.Rivest ,Clifford SteinAmazon Reviews: Book Info: 简称为CLRS的<<算法导论>>,被称作"计算机算法的圣经".本书的主要作者来自麻省理工大学计算机,作者之一Ronald L.Rivest 由于其在公开秘钥密码算法RSA上的贡献获得了图灵奖,目前是算法的标准教材,美国许多名校的计算机系都使用它,国内有些院校也将本书作为算法课程的教材.另外许多专业人员也经常引用它.由于TAOCP只出版了3卷,CLRS比较起前者来则显得内容更为全面,基本包含了所有的经典算法.本书程序全部由伪代码实现,这更增添了本书的通用性,使得利用各种程序设计语言的程序员都可以作为参考.语言方面通俗,很适合作为算法教材和自学算法之用.国内的很多作品名为数据结构,从本书中断章取义,把数据结构与算法混为一谈,搞得作者自己都迷迷糊糊.这也是我不十分愿意向大家推荐国内作品的原因.你会发现现在基本上所有的数据结构与算法书籍都会将本书作为参考文献之一,更可以说明一个问题,本书是作为读者进行算法学习的最佳选择.作为本书的补充内容,我愿意向大家推荐下面的学习资料:你可以通过这个地址找到本书的所有练习答案:http://www.itu.dk/people/beetle/ .为了更好的学习本书中的内容,最好的指导当然是来自作者本身讲述本书的课程,读者们可以通过http://18.89.1.101/sma/5503fall2001/index55 03fall2001.html获得课程的录像.中文版/thread-31351-1-1.htm l习题及答案/thread-33989-1-1.htm l算法导论（第二版影印版） / Introduction to Algorithms(Second Edition)（美）科尔曼（Corrmen,T.H.） / 2002-5-1 / 高等教育出版社 / 68.0 / 平装***(3).Data Structure & Algorithm Analysis in C (Second Edition)Author:Mark Allen WeissPublished:September 1996Web site:/~weiss/Amazon Reviews: Book Info: 本书曾被评为20世纪顶尖的30部计算机著作之一,作者Mark Allen Weiss在数据结构和算法分析方面卓有建树.他的数据结构和算法分析的著作尤其畅销,并受到广泛好评.已被世界500余所大学用作教材.***(4)Programming Pearls, 2nd EditionAuthor: Jon BentleyPublisher: Addison-Wesley Professional; 2 edition (September 27, 1999) Amazon Reviews: Book Info: 如果让程序员们列出他们最喜欢的书籍,Jon Bentley的<<编程珠玑>>通常可以位于经典之列.如同珍珠来自于曾经折磨牡蛎的沙粒,程序设计的珍珠也来自曾经折磨程序员的实际问题.Bentley的珍珠建立在坚实的工程学基础上,在洞察力和创造力的王国中为那些恼人的问题提供了独特而巧妙的解决方案.通过一些精心设计的有趣而且颇具指导意义的程序,本书对众多实用程序设计技巧及基本设计原则作了清晰而机智的描述.因此,<<编程珠玑>>得到各个层次程序员的青睐并不让人感觉意外.为了反映当今的程序设计方法和环境,Bentley在本书中彻底更新了第一版里的大多数素材.此外,他还增加了以下三个方面的内容:1.测试,调试和计时 2.集合表示 3.字符中问题对原来的所有程序都重新进行了改写,并生成了等量的新代码.您可以从本书网站()获取所有程序的C 或C++实现.McConnell <<Code Complete>>***(5)The Mythical Man-Month: Essays on Software Engineering, 20th Anniversary EditionAuthor: Frederick P, Brooks,Jr.Publisher: Addison-Wesley Professional; 1st edition (August 2, 1995)Amazon Reviews: Book Info: IBM大型电脑之父 Fred Brooks 二十余年开发经验的汇集,远谋深虑,字字珠玑.技术之巧与人文之美的完美结合.本书自第一版以来,畅销二十余年不衰,是软件领域绝无仅有的必读经典.作者简介:Frederick P 曾荣获美国计算机领域最具声望的图灵奖(A.M.Turing Award)桂冠.美国计算机协会(ACM)称赞他"对计算机体系结构,操作系统和软件工程做出了里程碑式的贡献."Brooks 博士是北卡罗莱纳大学 Kenan-Flagler 商学院的计算机科学教授.他被认为是"IBM 360系统之父",曾担任了360系统的项目经理,以及360操作系统项目设计阶段的经理.凭借在上述项目中的杰出贡献,Brooks博士以及Bob Evans和Erich Bloch在1985年荣获了美国国家技术奖(National Medal of Technology).Brooks博士早期曾担任IBM 公司Stretch和Harvest计算机的体系结构设计师.Brooks 博士创立了北卡罗莱纳大学的计算机科学系,并在1964～1984年期间担任系主任.他还曾任职于美国国家科技局和国防科学技术委员会.他目前的教学和研究方向是计算机体系结构,分子模型绘图和虚拟环境设计.***(6)The Pragmatic ProgrammerAuthor: Andrew Hunt,David ThomasPublisher: Addison WesleyPublished: November 24, 1999Amazon Reviews: Book Info: 本书直击编程阵地,穿过了日益增长的现代软件开发的规范和学术,对核心过程进行了审视----该过程采取了供需结合的工作方式和令人欣喜的可维护代码.本书包含的内容从个人责任和职业发展到保持代码的灵活性,使之易于改编和重用.本书由各个相对独立的章节组成,其间不乏好玩的轶事,详细的实例和有趣的对话,描述了软件开发各个方面的最好实践和主要缺陷.无论你是一个新入门的编码者,一个有经验的程序员,还是负责软件项目的经理,通过每日学习这些课程,都会在个人生产力,准确率和工作满意度上有快速的增长.你所学到的技巧和开发习惯和态度将为你在职业生涯中取得长期成功奠定基础.你将成为又一Pragmatic Programmer.数据结构C++语言描述》58.00(Data Structures C++) William Ford,William Topp 刘卫东沈官林数据结构算法与应用-C++语言描述》49.00Sartej Sahni 汪诗林孙晓东等机械工业出版社计算理论导引（第2版） / Introduction to the Theory of Computation（美）西普塞 / 2006-7-1 / 机械工业出版社 / 36.0 / 平装 / 唐常杰自动机理论、语言和计算导论（原书第2版） / Introduction to Automata Theory,Languages,and Computation,Second Edition程序设计语言：原理与实践（第二版） / Programming Languages:Principles and Practice,Second Edition程序设计语言-实践之路 / Programming Language Pragmatics（美）斯科特 / 2005-3-1 / 电子工业出版社 / 88.0 / 平装 / 裘宗燕计算机程序的构造和解释(原书第2版) / Structure and Interpretation of Computer Programs,Second Edition[美]艾伯森等 / 2004-02-01 / 机械工业出版社 / 45.0 / 平装 / 裘宗燕《Algorithm in c/c++/java 》【Data structure andalgorithm】1。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第9章 难解性 ( 同学讨论ＰPT 素材)作为教学科研的基本训练的一个重要环节，学生应该能根据教材，作出有自己特色的PPT 发言稿. 这里提供一些素材，试图减小学生的工作难度。
PPT 不能仅仅是剪报。
一份好的讨论班PPT 应该有同学的理解和创新.(素材节选自教材 但不能代替教材)从素材作PPT 一般 需要用 读 --减 ---加 三个过程。
（a ） 先充分阅读理解 教材，（b ） 从此素材中删去次要语句，（c ） 增加自己的心得，理解方法，解释和图形。
PPT 应该突出思路，突出要点, 适当的比喻可以帮助理解。
9.1 层次定理通常的直觉是给图灵机更多的时间或空间就能扩大它所能求解的问题类。
例如，在时间3n 内，图灵机应能比在时间2n 内判定更多的语言。
在一定条件下，这种直觉是正确的。
层次定理(hierarchy theorems )证明了这种直觉在满足某些条件下的正确性。
采用术语层次定理，是因为这些定理中的每一个都证明了时间和空间复杂性类不全相同—它们形成一个层次结构，其中时空界限较大的类比时空界限较小的类包含更多的语言。
空间复杂性层次定理比时间复杂性层次定理稍简单一些，故首先介绍它。
在实际陈述定理之前，引入下面的定义。
定义9.1 函数N N f →：，()n f 至少为O (n log )，如果函数f 把1n 映射为()n f 的二进制表示并且该函数在空间()()n f O 内是可计算的1称为空间可构造的(space constructible )。
换言之，如果存在某个TM M ，在()()n f O 空间内运行，而且在输入1n 时总能停机，停机时)(n f 的二进制表示出现在带子上，则f 是空间可构造的。
为了具有时间和空间可构造性，如n log n 2和n 这—类带小数的函数被向下舍入到紧邻的较小的整数上。
例9.2 通常出现的复杂度至少为O(n log )的函数都是空间可构造的，包括n log 2，n log n 2，2n 。
例如，2n 是空间可构造的，因为机器以1n 为输入，通过数1的数目得到n 的二进制形式，采用标推的方法将n 自乘，输出2n 。
全部空间消耗是)(n Ο，当然也是)(2n Ο。
1其中，1n 的意思是n 个1的字符串。
当证明等于()n o 的函数)(n f 是空间可构造的时候，如同在8.4节定义亚线性空间复杂性那样，有—条单独的只读输入带。
例如，这种机器可以如下计算把1n 映射为n log 2的二进制表示的函数。
随着只读头沿着输入带移动，它在工作带上以二进制形式计算输入中1的数目。
然后，因为n 以二进制形式放在工作带上，它通过数n 的二进制表示中的位数可以计算出n 2log 。
从下面的讨论中可以理解空间可构造性在空间层次定理中的作用。
若()n f 和()n g 是两个空间界限，()n f 渐近地比()n g 大，则机器在()n f 空间内所能计算的语言比在()n g 空间内多。
然而，假如()n f 超过()n g 的那部分数量非常小而且难以计算，那么机器可能无法有效地利用多出来的那部分空间，因为光是计算多出来的空间数量所需消耗的空间就可能比所获得的空间还要多。
在这种情况下，机器在()n f 空间内所能计算的语言不会比在()n g 空间内更多。
规定()n f 是空间可构造的就可避免这种情况，这样就可以证明机器所能计算的语言比它在任何渐近更小的界限内所能计算的语言更多，如下面的定理所示。
定理9.3空间层次定理 对于任何空间可构造函数N N f →：，存在语言A ，在空间()()n f Ο内可判定，但不能在空间()()n f o 内判定。
证明思路 必须显示一个语言A 具有两个性质，第一，A 在()()n f Ο空间内可判定，第二，A 不能在()()n f o 空间内判定。
通过给出判定算法D 来描述A 。
算法D 将在()()n f Ο)空间内运行，从而保证了第一个性质。
进而，D 将保证A 不同于任何在()()n f o 空间内可判定的语言，从而保证了第二个性质。
不要指望关于语言A ，能够象迄今为止已出现在本书中的其他语言那样，有一幅简单明了的图像。
语言A 则不同，它只能通过算法来描述，没有更简单的、非算法的定义。
为保证A 不能在()()n f o 空间内判定，设计D 用以实现定理4.9中证明停机问题A TM 不可解时所采用的对角线法。
如果M 是在()()n f o 空间内判定一个语言的机器，则D 保证A 与M 的语言至少存在—点不同的地方。
是哪个地方？就是对应于描述M 自己的地方。
看一看D 的运算方式。
简单地讲，D 把它的输入看作是TM M 的描述。
(如果输入不是任何TM 的描述，则D 在该输入上的动作是无意义的，所以武断地让D 拒绝即可。
)然后D 在同一输入，即＜M ＞上，在空间界限()n f 内运行M 。
如果M 在这么大空间内停机,则D 接受的充分必要条件是M 拒绝。
如果M 不停机，则D 拒绝。
所以如果M 在空间()n f 内运行，则D 有足够的空间保证它的语言不同于M 的语言。
否则，D 没有足够的空间算出M 的结果，但幸运的是并没有要求D 的行为与不能在()()n f o 空间内运行的机器不同，所以D 在该输入上的动作是无关紧要的。
该描述抓住了证明的本质，但忽略了几个重要的细节。
如果M 在()()n f o 空间内运行，则D 必须保证它的语言不同于M 的语言。
但是即使M 在()()n f o 空间内运行，它也可能对于小的n ，消耗比()n f 多的空间，只要这种渐近行为还没有“消亡”，D 有可能没有足够的空间在输入＜M ＞上把M 运行完，从而使D 失去一次避开M 的语言的机会。
于是， 一不小心，D 就可能与M 判定同—语言，而定理无法得证。
通过修改D ，给它另外的机会来避开M 的语言可以弥补这一问题。
不是只在D 收到输入＜M ＞时才运行M ，而是只要收到形式为*><10M 的输入，即形式为＜M ＞后面跟着一个l 和一些0的输入，就运行M 。
那么，如果M 真的在()()n f o 空间内运行，则由于渐近行为最终肯定是要消亡的，所以对于某个大的k 值，D 将有足够的空间在输入k10M ><上把M 运行完。
渐近行为最终肯定是要消亡的，所以对于某个大的k 值，D 将有足够的空间在输入k 10><M 上把M 运行完。
最后一个技术问题是，当D 在某个字符串上运行M 时，M 可能陷入死循环而占用有穷空间。
但是D 应该是一个判定机，所以必须保证D 在模拟M 时不会循环。
任何在空间()()n f o 内运行的机器只消耗))n (f (o 2时间。
修改D ，使它计算在模拟M 中用掉的步数。
如果计数超过))n (f (o 2，则D 拒绝。
证明 下面的()()n f Ο空间算法D 判定的语言A 不能在()()n f o 空间内判定。
D ＝“对输入w ：1) 令n 是w 的长度。
2) 利用空间可构造性计算()n f ，并划分出这么多带空间。
如果后面的步骤企图使用更多的空间，就拒绝。
3) 如果w 不是形如*><10M ，其中M 是某个TM ，则拒绝。
4) 在w 上模拟M ，同时计算模拟过程中使用的步数。
如果计数超过)n (f 2，则拒绝。
5) 若M 接受，则拒绝。
若M 拒绝．则接受”。
在步骤4，为了确定消耗的空间数量，需要给出补充的模拟细节。
被模拟的机器M 有任意的带字母表，而D 有固定的带字母表。
所以用D 的带子上的几个单元来表示M 的带子上的一个单元。
因此模拟过程在消耗的空间上增加了一个常数倍的开销。
换言之，如果M 在)(g n 空间内运行，那么D 需要)(g n d 空间来模拟M ，d 是依赖于M 的常数。
D 的每—步都在有限时间内运行，所以D 是—个判定机。
设A 是D 判定的语言。
显然， 因为D 的缘故，A 是在空间()()n f Ο内可判定的。
下面，证明A 不是()()n f o 空间可判定的。
假定其反面成立，即某个图灵机M 在空间()n g 内判定A ，其中()n g 等于()()n f o 。
如前面所提，D 可以在空间()n dg 内模拟M ，d 是某个常数。
因为()n g 等于()()n f o ，所以存在某个常数n 0，使得()n dg ＜()n f 对所有n ≥n 0成立。
因此只要输入的长度不小于n 0，D 对M 的模拟就能运行完。
考虑D 在输入0n 10M ><上运行时的情况。
该输入比n 0长，所以第4步的模拟可以完成。
因此D 与M 在同一输入上的判定结果相反。
于是M 不判定A ，这与假设矛盾。
所以A 不是在()()n f o 空间内可判定的。
推论9.4 对于任意两个函数N N :f f 21→，，其中()n f 1等于()()n f o 2))n (f (o 2，2f 是空间可构造的，有()()()()n f SPACE n f SPACE 21⊂1该推论允许把不同的空间复杂性类彼此分开。
例如，容易证明对于任何自然数c ，函数c n 是空间可构造的。
因此对于任意两个自然数1c ＜2c ，可以证明()()21c c n SAPCE n SAPCE ⊂。
再做一点努力就可以证明对于任何有理数c ＞o ，c n 是空间可构造的，从而把前面的包含关系推广到对任何有理数0≤1c ＜2c 都成立。
注意到在任何两个实数ε1＜ε2之间总存在两个有理数1c 和2c 使得ε1＜1c ＜2c ＜ε2。
于是得到下面补充的推论，它表明在PSPACE 类中存在一个良好的层次结构。
推论9.5 对于任意两个实数0≤ε1＜ε2，有()()21n SPACE n SPACE εε⊂也可以用空间层次定理来分离前面碰到的两个空间复杂性类。
推论9.6 NL ⊂PSPACE证明 萨维奇定理说明NL ⊆SPACE(log 2n )，空间层次定理说明()()n SPACE n log SPACE 2⊂，所以推论成立。
正如在8.5节所考察的那样，就对数空间可归约性而言，TQBF 是PSPACE 完全的，所以TQBF ∉NL 。
现在建立本章的主要目标：证明存在理论上可判定而实际中不可判定的问题，即可判定而难解的问题。
每一个类()kn SPACE 包含在类()n log n SPACE 中。
后者又严格包含在类()n 2SPACE 中。
所以得到下面补充的推论，把PSPACE 与()k n k 2SPACE EXPSPACE =分开。
1 A ⊂ B 表示A 是B 的真子集。
推论9.7 PSPACE ⊂ EXPSPACE就判定过程必须消耗多于多项式的空间这一意义而言，该推论证明存在难解的但可判定的问题。
语言本身有—些不太自然—它们只是为了分离复杂性类才有意义。