当前位置：文档之家 › 唐常杰翻译的计算理论导引(课堂PPT)

唐常杰翻译的计算理论导引(课堂PPT)

  • 格式：ppt
  • 大小：1.48 MB
  • 文档页数：59

下载文档原格式

  / 59

合集下载

翻译理论与技巧第一讲总论(课堂PPT)

翻译理论与技巧第一讲总论(课堂PPT)
“化”、“讹”具有一脉相承，彼此呼应的意义。翻 译的作用“诱”，难以避免的毛病“讹”和翻译的最 高境界“化”联系一起。翻译的过程就是引“诱”、 避“讹”、求“化”的过程。 文学翻译的最高理想可以说是“化”。把作品从一国 文学转变为另一个国文字，既能不因语文习惯的差异 而露出生硬牵强的痕迹，又能完全保持原作的风味， 那就算得入于“化境”。
——Thomas Huxley, Prolegomena to Evolution and Ethics.
可以有把握地想象，二千年前，在凯撒到达不列颠南部 之前，从我正在写作的屋子的窗口，可以看到整个原野 是处在一种所谓“自然状态”之中。
赫胥黎独处一室之中，在英伦之南，背山而面野，槛外 诸景，历历如在几下。乃悬想二千年前，当罗马大将凯 撒未到时，此间有何景物。计惟有天造草昧，人功未 施……
深奥才能达意，是复古的思想。核心是译作的文学价 值和艺术价值比较高。
13
It may be safely assumed that, two thousand years ago, before Caesar set foot in southern Britain, the whole countryside visible from the windows of the room in which I write, was in what is called “the state of Nature”.
洋学说和文学的做法，对他们惯用的“转述译法”提 出挑战，采用新的译法——忠实于原文的白话文的直 译法。
20
“易解”和“丰姿”的双标准： “力求易解”和“保存原作丰姿”：既要通顺、又要
忠实，是对“信达雅”的传承和发展。
“以直译为主，以意译为为辅” “以信为主，以顺为辅”

计算理论14哈米尔顿NP完全

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

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

唐常杰翻译的计算理论导引09.
Bad idea: “depth first”. This approach can get lost in never-halting paths.
Good idea: “breadth first”. For time step 1,2,… we list all possible configurations of the nondeterministic TM. The simulating TM accepts when it lists an accepting configuration.
可计算理论 2019/10/18
CS_Dept.Sichaun Univ.
12/82
Breadth First 注意，有两种前途，路径不定长，所以广度优先好复习补充
Let b be the maximum number
of children of a node. C2
Any node in the tree can
be uniquely identified by a string {1,…,b}*.
C5
C6
C1
t=1
C3
C4 t=2
t=3 “reject”
Example: location of the rejecting configuration is (3,1). “accept”
With the lexicographical listing , (1), (2),…, (b), (1,1), (1,2),…,(1,b), (2,1),… et cetera, we cover all nodes.
be uniquely identified by a string {1,…,b}*.

第二讲翻译的标准PPT课件

第二讲翻译的标准PPT课件
function）（意义的分类，文本功能的分类）
第7页/共42页
3.从美学角度提出的翻译原则
• 傅雷的“神似”(similarity in spirit) 说：《高老头重译序》中 提出来的：“以效果而论，翻译应当像临画一样，所求的不再 形似而在神似”。“神似”即要传达原文的意蕴和韵味，“把 原文的意义、神韵把握住”。
• The moon sheds her liquid light silently over the leaves and flowers, in the floating transparency of a bluish haze from the pond, look as if they had just been bathed in milk, or like a dream wrapped in a gauzy hood.（见《中国翻译》 1992年第2期）
第26页/共42页
2．他的不合作态度使这个项目进展十分缓慢。
The project makes less progress because of his incooperation.
第27页/共42页
3．你们谁想参加春游就在星期五之前报名并交费。
You whoever wants to go spring outing please sign up your name and pay dues before Friday.
第24页/共42页
修改下列误译的句 子
第25页/共42页
1．中国人有在正月十五晚上吃元宵、赏花灯的习 俗。
Chinese have the custom that they eat sweet dumplings made of glutinous rice flour and appreciate festive lanterns at the night of January 15.

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

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

内容 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

唐常杰翻译的计算理论导引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

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

唐常杰翻译的计算理论导引
the intersection A1 A2 , and the complement Ā1= *\A1 are not CF languages.
直观解释：PDA资源不够多，，记忆能力不够， 不能作复杂集合(如CFL)的减法
One proves this with specific examples of languages (see homework).
The problem lies in the informal notion of a description. Consider: { n | n>2,a,b,c: an+bn = cn } 费马问题，已解决,是空集
{ x | in year x the first female US president }
让历史告诉未来
{ x | x is “an easy to remember number” }
描述太含糊
We have to define what we mean by “description” and “method of deciding
可计算理论 2024/5/10
CS_Dept.Sichaun Univ.
让历史告诉未来
{ x | x is “an easy to remember number” }
描述太含糊
We have to define what we mean by “description” and “method of deciding”.
可计算理论 2024/5/10
CS_Dept.Sichaun Univ.
,{x| x mod 3 =0}
什么是操作系统 代表元：Windows, Unix
什么internet

中西方翻译理论汇总PPT课件

中西方翻译理论汇总PPT课件

theories (e.g. general translation theory, polysystem theory);
research methods (e.g. descriptive, empirical);
CHENLI
redefine the concepts ‘literal’ and ‘free’ in operational terms, to describe ‘meaning’ in scientific terms, and to put together systematic taxonomies of translation phenomena.
even the syntax contains a mystery – I render not word-for-word,
11
but sense for sense. (St Jerome 395 CE /1997: 25)
many modern theoreticians concur that the main problem with the writings on translation in this period was that the criteria for
容易。”
所谓“五不翻”，即五种不意译而是用音译的情形：
1、秘密故不翻。具有神秘色彩的词语应该不翻。如六字
真言“唵嘛呢叭咪吽”意为“哦!莲花里的珠宝”。不照
字面意义翻译出来，保持了佛语的神秘和庄重。
2、含多义故不翻。如梵语“薄伽梵”一词具有六种意义：
“自在、炽盛、端严、名称、吉祥、尊贵”，这些词无法
精通梵文，熟悉正确的翻译方法，不失梵文所载的义理。
5
·薄阅苍雅，粗谙篆隶，不昧此文，其备八也。

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

唐常杰翻译的计算理论导引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 教授）

翻译的方法——大学笔译课件PPT

翻译的方法——大学笔译课件PPT
据悉联军给养不足。 It is reported that the coalition troops are short of supplies.
他没有再言语，听任老板在那里滔滔不绝。 Withholding his opinion for the moment, he listened to his boss holding forth.
China's modernization is inseparable from her economic cooperation and trade ties with other nations
我们要逐步推进商业、外贸、金融、保险、证券、电信、旅游和中介服 务等领域的对外开放。 merce, foreign trade, banking, insurance, securities, telemunications, tourism and intermediary services should be gradually opened to the outside world.
外表往往是靠不住的。 Appearances are often deceptive.
美国不失体面地接受了这项和平方案。 The U.S.A accepted the peace proposal with dignity.
我完全同意。 I can't agree with you more.
你们大错特错了。 We couldn't be more mistaken.
• 我们必须坚持社会 • We must adhere to the
主义道路，坚持人
socialist road, the people's
民民主专政，坚持

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

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

第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 。

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

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

定理８.11
可计算理论
CS_Dept.Sichaun Univ.
10/94
８.3.2 博弈的必胜策略
P187
•博奕论-The Game Theory
日光浴者 海滩 1/4 3/4
博奕论：关于包含相互依存情况中理性行为 的研究。
可计算理论
CS_Dept.Sichaun Univ.
11/94
８.3.2 博弈的必胜策略
CS_Dept.Sichaun Univ.
30/94
8.3.3 广义地理学
P189
•广义地理学游戏样例
•选手I必胜
从节点5出发， 选手I，可以选 节点6，7，8
7
1
3
5 1 8
6
可计算理论
CS_Dept.Sichaun Univ.
31/94
8.3.3 广义地理学
P189
•广义地理学游戏样例
•选手I必胜
28/94
8.3.3 广义地理学
P189
•广义地理学游戏样例
•选手I必胜
1 3
节点3，选手II 只有1条路径可 选，即节点5
5 1
可计算理论
CS_Dept.Sichaun Univ.
29/94
8.3.3 广义地理学
P189
•广义地理学游戏样例
•选手I必胜
1
3
5 1
选手II，只 能选节点5
可计算理论
1 3 6 5 1
可计算理论
CS_Dept.Sichaun Univ.
13/94
８.3.2 博弈的必胜策略 表达式 •TQBF语言问题
TQBF={<f>| f是真的全量词化布尔公式}

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

唐常杰翻译的计算理论导引
证明思路: › A的运行时间显然是多项式界限的。 › 设X是它输出的顶点集合，H是有标记的边的集合。因为G的每一 条边要么属于H，要么与H中的一条边相邻，因此X与G的所有边 关联，因此X是一个顶点覆盖。 › 证明X的大小不超过最小顶点覆盖Y的大小的2倍。
X的大小是H的2倍 H不大于Y
•. •2020/8/7
•. •2020/8/7
•9
概率算法
概率算法使用随机过程的结果。典型包含一 条“扔硬币”的指令，并且扔硬币的结果可 能影响算法后面的执行和输出。
BPP类 素数性 只读一次的分支程序
•. •2020/8/7
•10
概率图灵机
概率图灵机M是一种非确定型图灵机，它的每 一非确定步，称作掷硬币步，并且有两个合法 的下次动作。定义分支b的概率如下，其中k是 在分支b中出现的掷硬币步的步数。
近似算法是为了求近似最优解而设计的。
•. •2020/8/7
•3
顶点覆盖问题
若G是无向图，则G的顶点覆盖是节点的一 个子集，使得G的每条边都与子集中的节点 之一相关联。
1 2
5 4
3
1 2
•. •2020/8/7
5 4
3
•4
最小顶点覆盖的一个近似算法
下述多项式时间算法近似地解这个最优化问题，它给出一个顶点 覆盖，其大小不超过最小顶点覆盖的大小的2倍。
Chap 10 复杂性理论中的高级专题 (同学报 告）
可以从下列文件获得ＰPT素材： 13_10-复杂理论高级专题-同学报告素材.doc
本章提纲 10.1 近似算法、 10.2 概率算法 10.3 交错式 10.4 交互证明， 10.5 并行计算 10.6 密码学
•.
•1

计算理论导引 0_绪论

计算理论导引 0_绪论
7
主要内容
0.0 课程性质 0.1 自动机、可计算性与复杂性 0.2 数学概念和术语 0.3 定义、定理和证明 0.4 证明的类型 0.5 作业
8
0.1 自动机、可计算性与复杂性
什么是计算？ 计算机的基本能力和局限性是什么？ 计算复杂性理论
把问题分成容易计算和难以计算的
可计算理论
布尔逻辑
合取、析取、非、异或
12
主要内容
0.0 课程性质 0.1 自动机、可计算性与复杂性 0.2 数学概念和术语 0.3 定义、定理和证明 0.4 证明的类型 0.5 作业
13
0.3 定义、定理和证明
定义：描述了我们使用的对象和概念。 证明：是一种逻辑论证。 定理：是被证明为真的数学命题。 引理：有助于证明另一个更有意义的命题的命题。
5
课程说明
教材处理
讲要点，前后次序有少数调整 略讲或自学的部分，要求了解主要思想 快讲的部分，需要一般了解的章节，要求了解主要方法和演绎框架 要求深入掌握的部分——能作题目或作难题，通过考试
6
课时安排
第0章 绪论——2学时 第1章 正则语言——5学时 第2章 上下文无关文法——3学时 第3章 丘奇-图灵论题——2学时 第4章 可判定性——2学时 第5章 可归约性——2学时 第6章 可计算理论高级专题——2学时 第7章 时间复杂性——4学时 第8章 空间复杂性——3学时 第9章 难解性——3学时 第10章 复杂性理论高级专题——4学时
京: 清华大学出版社. (美) John E.Hopcroft等著. 孙家骕等译.自动机理论、语言和计算导
论(原书第3版). 北京: 机械工业出版社.
4
课程说明
作业

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

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

- pushes an element

(nondeterministically)
CS_Dept.Sichaun Univ.
10/65
Formal Description PDA定义2.8 ep103
形式化定义 cp70
A Pushdown Automata M is defined by a
PDAs are recognizing automata that have a single stack (= memory): “硬件” 增加了栈
Last-In First-Out pushing and popping
对应于 可用 if ，goto, 读，和栈操作 的C程序
Difference: PDAs are inherently nondeterministic. (They are not practical machines.) 天生不确定
可计算理论 2019/10/18
CS_Dept.Sichaun Univ.
5/65
2.2 Pushdown Automata, ep101, cp69
Pushdown automata are for context-free languages what finite automata are for regular languages. PDA :描述CFL的设备
Lecture Notes for Computation Theory
Book :《计算理论导引》
Introduction to the Theory of Computation
Section 2.2 -2.3 PDA –CFL
Prof : 唐常杰
TangChangjie@ /~chjtang

翻译理论入门中国篇PPT课件

翻译理论入门中国篇PPT课件
• （3）经文原文的论述，往往不厌其烦，尤其是颂文 部分，更是反复再三，翻译时被删减；
• （4）经文在长行之后，另有偈颂复述，内容重复， 有时是五百字，有时达一千字，在翻译时也被删去；
• （5）经文中讲完一事便告一段落，要转述别的事时13
佛经翻译的代表人物(二)
• “三不易”：有三件事决定了翻译并非易事：
• 支谦：字恭 明，原为月 支人。汉献 帝 （ 189200 ） 末 年 ，避乱入吴 ，深得孙权 的赏识。
8
佛经翻译的代表人物(一)
• 天竺言语，与汉异音。云其书为天书，语
为天语。名物不同，传实不易。••••••将炎
虽善天竺语，未备晓汉。其所传言，或得
胡语，或以义出音，近于质直。仆初嫌其
辞不雅。维祗难曰：“佛言，依其义不用
点。 • 3、说明我国译论从一开始便深植
于传统文化土壤之中。
10
佛经翻译的代表人物(二)
• 道安 （312—385）：又 名释道安，俗姓卫，常 山扶柳（今河北冀州） 人。18岁出家，因其形 貌黑丑，初时未受到重 视。但由于他的博闻强 记，数年后，他的师傅 改变态度，让他受具足 戒，并准许他出外参学 。
24
明末清初翻译活动的代表人物（一）
• 徐光启的翻译思想： • 1、求知、求真理。 • 2、抓重点，抓“急须”，能
够从哲学方法论角度着眼。 • 3、想要超越前人和外国人，
就必须对对方的语言等进行 彻底的了解，在此之前必须 先学会翻译。 • 徐光启与利马窦合作翻译了 欧几里得的《几何原本》。
• Elements of Geometry 25 by Euclid
• “五失本”、“三不易 11 ”的翻译思想 。
“五失本” （five deviations） “三不易” （three difficulties）
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

XXXXX
2
CS_Dept.Sichaun Univ.
9/59
概率算法
概率算法使用随机过程的结果。典型包含一条“扔硬币” 的指令，并且扔硬币的结果可能影响算法后面的执行和输 出。
BPP类 素数性 只读一次的分支程序
XXXXX
2
CS_Dept.Sichaun Univ.
10/59
概率图灵机
概率图灵机M是一种非确定型图灵机，它的每一非确定步， 称作掷硬币步，并且有两个合法的下次动作。定义分支b的 概率如下，其中k是在分支b中出现的掷硬币步的步数。
定义M接受ω的概率为
Pr[b] 2k
Pr[M接受]＝ Pr[b] b是接受分支
XXXXX
2
CS_Dept.Sichaun Univ.
11/59
BPP类
对于0<=ε<1/2，如果满足下面的条件则称M以错误概率ε识 别语言A。
A蕴涵Pr[M接受] 1 A蕴涵Pr[M拒绝] 1
BPP是多项式时间的概率图灵机以错误概率1/3识别的语言 类。
如果不存在这样的顶点，则输出当前的割并且停止。”
XXXXX
2
CS_Dept.Sichaun Univ.
8/59
定理1０.2
定理11.2：B是最大割集的2-优的多项式近似算法。 证明：
割的大小不超过G的边数，故B是多项式时间的。 证明B输出的割X至少包含G中的所有边的一半。
X的每个顶点的割边>=非割边。 X的所有顶点的割边数和＝ X的割边总数×2。 X的所有顶点的非割边数和＝ X的非割边总数×2。 X的割边数和>= X的非割边数和 X的割边数 >= G的所有边数/2 G的所有边数>=最大割边数
运行次数指数下降。
XXXXX
2
CS_Dept.Sichaun Univ.
13/59
素数性
定理11.6：
例子：
如果p是素数，且a p，则a p1 1(mod p)。
p通过在a的p费 马7, 测a 试2是指2(71) 26 64, 64 mod 7 1
如果一个数p 能 6通, a过所2有关于2(6小1)于它25且与32它, 互3素2 m的o数d 5的费2马测
1 2
XXXXX
2பைடு நூலகம்
5 4
3
1 2
CS_Dept.Sichaun Univ.
5 4
3 4/59
最小顶点覆盖的一个近似算法
下述多项式时间算法近似地解这个最优化问题，它给出一个顶点覆 盖，其大小不超过最小顶点覆盖的大小的2倍。
A＝ “对于输入<G>，这里G是一个无向图： 重复下述操作直至G中所有的边都与有标记的边相邻。 在G中找一条不与任何有标记的边相邻的边。 给这条边作标记。 输出所有有标记边的顶点。 ”
如果p是伪素数则能通过全部测试，如果p不是伪素数则至多能通过全部测试的
一半。于是它通过全部k个随机选择的测试的概率不大于 ，因此该算法以错
2/59
近似算法
在最优化问题中，通常试图在可行解中寻找最好的解，即最 优解。
在实践中，可能并不一定非要最优解不可，一个接近最优的 解可能是足够好的，而且可能更容易找到。
近似算法是为了求近似最优解而设计的。
XXXXX
2
CS_Dept.Sichaun Univ.
3/59
顶点覆盖问题
若G是无向图，则G的顶点覆盖是节点的一个子集，使得 G的每条边都与子集中的节点之一相关联。
X的大小是H的2倍 H不大于Y
XXXXX
2
CS_Dept.Sichaun Univ.
6/59
k-优算法
如果一个最小化问题的近似算法总能找到不超过最优解k 倍的可行解，则称这个算法是k-优的。
对于最大化问题，一个k-优近似算法总能找到不小于最 优解大小的1/k的可行解。
XXXXX
2
CS_Dept.Sichaun Univ.
7/59
最大割集的近似算法
5 1
4
把顶点集V划分成两个不相交的子集S和T，称为无向图中的割。顶点分 别在两个子集 中的边称为割边，割边的数目称为割2 的大小。
3
B＝ “对于输入<G>，这里G是顶点集为V的无向图：
令S＝Ø和T＝V。
如果把一个顶点从S移到T或者从T移到S，使割的大小变大，则做这 样的移动，并且重复这一步。
1/59
Chap 10 复杂性理论中的高级专题 (同学报告）
可根据 提供的ＰPT素材+参考以前同学的报告， 修改成为有自己见解的讨论报告
建议：
底色用浅色（象牙白， 浅黄， 白色等） 适合色盲 色弱 观众 字体颜色选择余地大 在投影机 效果差时 也还能能看见
XXXXX
2
CS_Dept.Sichaun Univ.
XXXXX
2
CS_Dept.Sichaun Univ.
5/59
定理1０.1
定理11.1：A是一个多项式时间算法，它给出G的一个顶点覆盖，其大 小不超过最小顶点覆盖的大小的2倍。 证明思路:
A的运行时间显然是多项式界限的。 设X是它输出的顶点集合，H是有标记的边的集合。因为G的每一 条边要么属于H，要么与H中的一条边相邻，因此X与G的所有边 关联，因此X是一个顶点覆盖。 证明X的大小不超过最小顶点覆盖Y的大小的2倍。
XXXXX
2
CS_Dept.Sichaun Univ.
12/59
引理10.5
引理11.5：设ε是一个固定常数，且0<ε<1/2。又设M1是一台
错误概率为ε的多项式时间概率图灵机，则对于任意的多项式
poly(n)，存在与M1等价的错误概率为
的多项式时间概
率图灵机M2。
证取明这思些路运：行M结2果用中如的下多方数式作模为拟计M2算1：结po运l果y(n行。) M错1误多概项率式将次随，M并1且的
Chap 10 复杂性理论中的高级专题 (同学报告）
可以从下列文件获得ＰPT素材： 13_10-复杂理论高级专题-同学报告素材.doc
本章提纲 10.1 近似算法、 10.2 概率算法 10.3 交错式 10.4 交互证明， 10.5 并行计算 10.6 密码学
XXXXX
2
CS_Dept.Sichaun Univ.
试，则称这个数为伪素数，其中可能包含卡米切尔数和素数
。
a p1 1(mod p)
XXXXX
2
CS_Dept.Sichaun Univ.
14/59
测试伪素数的多项式概率算法
PSEUDOPRIME “对于输入p： 在p中随机地选取a1, , ak 对于每一个i，计算ai( p1) mod p 如果所有计算出来的值都等于1，则接受；否则拒绝”