[CS363] 关于期末复习与还书

[Xiaofeng Gao]

各位同学，

为了方便大家复习，本课程课件特别制作了Compact Print Version，大家可以去课程主页相应位置下载。

另，今天收到通知，英语班的课本应统一退还给陈芸老师，故请大家自行组织将课本直接给陈老师，不需要在考试时候还给我。

Lab 5和Lab 6的答案将于明天送至班长魏晅中处，请大家联系班长复印。

还有任何问题请随时与我联系。

-----------

Sincerely Yours,

Xiaofeng Gao, PH.D.（高晓沨）
Assistant Professor
Department of Computer Science and Engineering
Shanghai Jiao Tong University
Email: gao...@cs.sjtu.edu.cn
Office: Telecom Bldg 3-543 Phone: 021-34207407

[Zuo Zeng]

能不能把用到的符号，尤其是那种不常见的，集中起来讲下，或者考试的时候可以问？

[Xiaofeng Gao]

比如说什么符号？

---

-----------

Sincerely Yours,

Xiaofeng Gao, PH.D.（高晓沨）
Assistant Professor
Department of Computer Science and Engineering
Shanghai Jiao Tong University
Email: gao...@cs.sjtu.edu.cn
Office: Telecom Bldg 3-543 Phone: 021-34207407

On Sat, 9 Jun 2012 21:17:55 +0800, Zuo Zeng wrote:
> 能不能把用到的符号，尤其是那种不常见的，集中起来讲下，或者考试的时候可以问？
>

> 在 2012年6月7日 下午1:47，Xiaofeng Gao 写道：
>
>> 各位同学，
>>
>> 为了方便大家复习，本课程课件特别制作了Compact
>> Print Version，大家可以去课程主页相应位置下载。
>>
>>
> 另，今天收到通知，英语班的课本应统一退还给陈芸老师，故请大家自行组织将课本直接给陈老师，不需要在考试时候还给我。
>>
>> Lab 5和Lab
>>
> 6的答案将于明天送至班长魏晅中处，请大家联系班长复印。
>>
>> 还有任何问题请随时与我联系。
>>
>> -----------
>>
>> Sincerely Yours,
>>
>> Xiaofeng Gao, PH.D.（高晓沨）
>> Assistant Professor
>> Department of Computer Science and Engineering
>> Shanghai Jiao Tong University

>> Email: gao...@cs.sjtu.edu.cn [1]

>> Office: Telecom Bldg 3-543 Phone: 021-34207407
>
>
>

> Links:
> ------
> [1] mailto:gao...@cs.sjtu.edu.cn
> [2] mailto:gao...@cs.sjtu.edu.cn

[Zuo Zeng]

比如

f | A

f(x,y)\simeq y

[Xiaofeng Gao]

各位同学，

谢谢曾笮同学的建议，我新做了SymbolList已经挂在课程主页上，基本涵盖了本课程用到的全部符号，大家可以去下载参考。也欢迎大家查漏补缺，尽量把list做得完整些。

-----------

Sincerely Yours,

Xiaofeng Gao, PH.D.（高晓沨）
Assistant Professor
Department of Computer Science and Engineering
Shanghai Jiao Tong University
Email: gao...@cs.sjtu.edu.cn
Office: Telecom Bldg 3-543 Phone: 021-34207407

On Sat, 9 Jun 2012 21:30:06 +0800, Zuo Zeng wrote:
> 比如
> f | A
> f(x,y)simeq y

>
> 在 2012年6月9日 下午9:05，Xiaofeng Gao 写道：
>
>> 比如说什么符号？
>>
>> ---
>>
>> -----------
>>
>> Sincerely Yours,
>>
>> Xiaofeng Gao, PH.D.（高晓沨）
>> Assistant Professor
>> Department of Computer Science and Engineering
>> Shanghai Jiao Tong University

>> Email: gao...@cs.sjtu.edu.cn [3]

>> Office: Telecom Bldg 3-543 Phone: 021-34207407
>>
>> On Sat, 9 Jun 2012 21:17:55 +0800, Zuo Zeng wrote:
>>
>>>
>>
> 能不能把用到的符号，尤其是那种不常见的，集中起来讲下，或者考试的时候可以问？
>>>
>>> 在 2012年6月7日 下午1:47，Xiaofeng Gao 写道：
>>>
>>>> 各位同学，
>>>>
>>>> 为了方便大家复习，本课程课件特别制作了Compact
>>>> Print
>>>> Version，大家可以去课程主页相应位置下载。
>>>
>>
> 另，今天收到通知，英语班的课本应统一退还给陈芸老师，故请大家自行组织将课本直接给陈老师，不需要在考试时候还给我。
>>>
>>>> Lab 5和Lab
>>>
>>
> 6的答案将于明天送至班长魏晅中处，请大家联系班长复印。
>>>

>>>> stant Professor
>>>> Department of Computer Science and Engineering
>>>> Shanghai Jiao Tong University

>>>> Email: gao...@cs.sjtu.edu.cn [1] [1]

>>>>
>>>> Office: Telecom Bldg 3-543 Phone: 021-34207407
>>>>
>>>> Links:
>>>> ------
>>>> [1] mailto:gao...@cs.sjtu.edu.cn [2]

>>>> [2] mailto:
>>> f...@cs.sjtu.edu.cn" target="_blank">gao...@cs.sjtu.edu.cn

>
>
>
> Links:
> ------
> [1] mailto:gao...@cs.sjtu.edu.cn
> [2] mailto:gao...@cs.sjtu.edu.cn

> [3] mailto:gao...@cs.sjtu.edu.cn
> [4] mailto:gao...@cs.sjtu.edu.cn

[js05212]

 

老师辛苦啦~

 

问下questionlist中第七章的5（e）中，\phi_x\neq 0 的含义是‘\phi_x is total and \phi_x \neq \mathbf{0}’还是只是‘\phi_x \neq \mathbf{0}’呢？

 

 

2012-06-10

---

js05212

---

发件人：Xiaofeng Gao

发送时间：2012-06-10 02:54

主题：[CS363] SymbolList

收件人："sjtu_cs363"<sjtu_...@googlegroups.com>

抄送：

[Xiaofeng Gao]

不需要total这个条件，只要\neq 0就可以了。


On Sun, 10 Jun 2012 13:45:10 +0800, js05212 wrote:
> 老师辛苦啦~
>
> 问下questionlist中第七章的5（e）中，phi_xneq 0

> 的含义是‘phi_x is total and phi_x neq
> mathbf{0}’还是只是‘phi_x neq mathbf{0}’呢？
>
> 2012-06-10
>

> -------------------------
>
> js05212
>
> -------------------------
>
> Xiaofeng Gao
> 2012-06-10 02:54
> [CS363] SymbolList
> "sjtu_cs363"

[Xiaofeng Gao]

CheckList第4页表格中{x: \phi_x=\mathbf{0}}不是r.e. set，应该更正为{x: \phi_x(x)=0}

---
-----------

Sincerely Yours,

Xiaofeng Gao, PH.D.（高晓沨）
Assistant Professor
Department of Computer Science and Engineering
Shanghai Jiao Tong University
Email: gao...@cs.sjtu.edu.cn

[银月游侠]

那请问正下方的不等于0的那个是不是也要改？

发自我的 iPhone

在 2012-6-10，15:33，"Xiaofeng Gao" <gao...@cs.sjtu.edu.cn> 写到：

[CHEN Xilun]

目测那个是对的啊

Sent from my iPhone

[Xiaofeng Gao]

是的。

[银月游侠]

我现在有点糊涂了，那意思就是productive的集合的补集不一定是r.e.的？
顺便再问一下，是不是所有的集合要么是r.e.要么是productive？

发自我的 iPhone

在 2012-6-10，16:49，"CHEN Xilun" <chenxl....@gmail.com> 写到：

[CHEN Xilun]

productive的补集不一定r.e.啊
比如total和not total

Sent from my iPhone

[js05212]

 

请问下如果两个set是effectively recursively inseparable,是不是就意味着他们也是recursively inseparable呢？如果是的话那么Questionlist Chapter 7-17（c)为什么是分别是分别证明的呢？

 

 

2012-06-10

---

js05212

---

发件人：CHEN Xilun

发送时间：2012-06-10 16:59

主题：Re: [CS363] CheckList 更正

收件人："sjtu_...@googlegroups.com"<sjtu_...@googlegroups.com>

抄送：

[CHEN Xilun]

我觉得是反过来啊，如果都不recursively separable，就更不能effectively separable了啊

Sent from my iPhone

[js05212]

 

逆否命题？

所以结论是对的吗？

 

 

2012-06-10

---

js05212

---

发件人：CHEN Xilun

发送时间：2012-06-10 17:51

主题：Re: 回复: Re: [CS363] CheckList 更正

[CHEN Xilun]

不对……似乎我说的不对，还是你说的那个对~

Sent from my iPhone

[js05212]

‘如果都不recursively separable，就更不能effectively separable了’不对？

 

2012-06-10

---

js05212

---

发件人：CHEN Xilun

发送时间：2012-06-10 18:21

主题：Re: 回复: Re: 回复: Re: [CS363] CheckList 更正

[Xilun Chen]

‘如果都不recursively separable，就更不能effectively separable了’ 

的意思不就是recursively inseparable则effectively recursively inseparable了吗？所以我说反了

2012/6/10 js05212 <js0...@gmail.com>

--

Best Regards,

---------

CHEN Xilun

[js05212]

 

请问r.e. T-degree是不是不一定只包含r.e. set呢？还是一定只包含r.e. set？

 

2012-06-11

---

js05212

---

发件人：CHEN Xilun

发送时间：2012-06-10 17:51

主题：Re: 回复: Re: [CS363] CheckList 更正

[Xiaofeng Gao]

统一回答一下:

1、请问r.e. T-degree是不是不一定只包含r.e. set呢？还是一定只包含r.e. set？
-------------------------> r.e. T-degree一定只包含r.e. set

2、请问下如果两个set是effectively recursively inseparable,是不是就意味着他们也是recursively
inseparable呢？----------------------------> 是的。e.r.i可以推出r.i.

如果是的话那么Questionlist Chapter
7-17（c)为什么是分别是分别证明的呢？----------------------->你也可以只证明e.r.i，然后证明e.r.i.=>r.i.

3、{x|\phi_x \neq 0}和{x|\phi_x(x)\neq 0}都是productive set.

另，明天大家考完试请先不要离开，趁所有人都在想和你们照张合照（本课程唯二的全勤就是期中考试+期末考试……┭┮﹏┭┮）

[CHEN Xilun]

K和\overline{K}不是属于同一个T degree的吗？
为什么r.e. Tdegree只包含r.e. set？

Sent from my iPhone

[Xiaofeng Gao]

嗯，1题是我写的不对，应该是

对任意 r.e. T-degree of set A，它包含的set不一定都是r.e. set，但是一定都是A-r.e. set。

谢谢Xilun修正。

-----------

Sincerely Yours,

Xiaofeng Gao, PH.D.（高晓沨）
Assistant Professor
Department of Computer Science and Engineering
Shanghai Jiao Tong University
Email: gao...@cs.sjtu.edu.cn
Office: Telecom Bldg 3-543 Phone: 021-34207407

[Xiaofeng Gao]

Lab 5的4(a)答案有误，必须保证 x \in W_x iff f(x) \in E_{f(x)}，而不是f(x) \in
E_x。因此可以设

f(x,y)=y if x \in W_x, otherwise diverge. Then by s-m-n theorem we can
easily get the m-reduction.

谢谢罗珞订正。