唐常杰翻译的计算理论导引

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}

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 材料详略、次序 与书上不完全一样， 主要考虑便于教学和理解

如果不存在这样的顶点，则输出当前的割并且停止。”
18.01.2021
唐常杰翻译计算理论导引
8
定理1０.2
定理11.2：B是最大割集的2-优的多项式近似算法。 证明：
割的大小不超过G的边数，故B是多项式时间的。 证明B输出的割X至少包含G中的所有边的一半。
X的每个顶点的割边>=非割边。 X的所有顶点的割边数和＝ X的割边总数×2。 X的所有顶点的非割边数和＝ X的非割边总数×2。 X的割边数和>= X的非割边数和 X的割边数 >= G的所有边数/2 G的所有边数>=最大割边数
18.01.2021
唐常杰翻译计算理论导引
5
定理1０.1
定理11.1：A是一个多项式时间算法，它给出G的一个顶点覆盖，其大 小不超过最小顶点覆盖的大小的2倍。
证明思路: A的运行时间显然是多项式界限的。 设X是它输出的顶点集合，H是有标记的边的集合。因为G的每一 条边要么属于H，要么与H中的一条边相邻，因此X与G的所有边关 联，因此X是一个顶点覆盖。 证明X的大小不超过最小顶点覆盖Y的大小的2倍。
18.01.2021
唐常杰翻译计算理论导引
13
素数性
定理11.6：
例子：
如p是 果素a 数 p ， ， ap 则 1 且 1 (mp)。 od
p7,a2 2(71)266,46m 4 7 od 1
p通过在pa 的6,a 费 马2测试2(6 是1) 指253,232m5 od 2 如果一个数能通过所有关于ap小1于1(m 它o且pd)与它
18.01.2021
唐常杰翻译计算理论导引
9
概率算法
概率算法使用随机过程的结果。典型包含 一条“扔硬币”的指令，并且扔硬币的结 果可能影响算法后面的执行和输出。

• • • • • • • •
Five Don’ts （transliteration in the five cases） 1)What is mysterious; 2)What is polysemantic; 3)What is too alien to be accepted; 4)What is hereditary; 5)What is philanthropic [filən'θrɔpik] . 博爱的；慈善的；
佛经翻译的代表人物(二)
• “三不易”：有三件事决定了翻译并非易事： • （ 1 ）“圣人”本是按照当时的习俗来说法的， 现在时代不同了，要改古适今，很不容易； • （ 2 ）“圣人”的智慧本不是凡人所能比得上 的，而要把千年前古代圣哲的微言大义传达给 后世的浅俗之众，很不容易； • （ 3 ）释迦牟尼死后，他的大弟子阿难等人出 经时尚且反复斟酌，兢兢业业，而今过了近千 年，却要平凡人以他们现在的理解来传译原文 的意思，更谈何容易。
中国翻译史上的几次高潮
• 一、东汉到北宋时期的佛经翻译 • 二、明末清初的西方自然科学著作的翻 译 • 三、鸦片战争到五四运动前的翻译活动， 特别是甲午战争后的西学翻译 • 四、五四运动到新中国成立的翻译活动 • 五、新中国成立之后的翻译活动
一、东汉到北宋时期的佛经翻译
• 佛教的创立及特点 • 佛经翻译的发展过程 • 佛经翻译的代表人物
佛经翻译的发展过程
• 佛经翻译从东汉桓帝（公元147年－167 年）末年安世高译经开始，魏晋南北朝 （220－581）时有了进一步的发展，到 了唐代（618－905）达到极盛，北宋 （960－1126）时已经衰落，元（1206 －1341）以后则是尾声了。 • 安世高：西域安息人，安息国的太子， 将王位让与叔叔，出家修道，后到达洛 阳，译出许多经纶。