Talk:Randomized Algorithms (Spring 2010)

2010-04-29T01:17:24Z

210.28.131.124:

请大家点击页面上方的“edit”进行留言和讨论 --[[User:WikiSysop|etone]] 13:08, 11 January 2010 (UTC)
----
尹老师，你好！上次去听了你的randomized algorithms的课，很不错。但有几点疑问，描述如下：
1、你课件上说randomized algorithms有个特性是“简单”，能否举个例子，最好能跟这个例子的deterministic algorithms做下比较。
2、monte carlo式的randomized algorithms的结果怎么验证？比如min-cut这个例子，假设独立地执行karger算法10次，其中有一次结果是正确的，10次结果如下：
F,F,F,F,T,F,F,F,F,F(T为正确，F为错误),问题是我怎么知道第5次是正确的。甚者，如果执行n（n比较大）才能得到一次正确结果，即使是人工验证也是很难的。不知道是否想错误了。
望老师有空解答下。
:Re:
:(1) randomized algorithm算法简单的例子有很多，例如karger algorithm明显就比确定算法计算min-cut的最大流算法简单。以后还会看到更多。

:(2)课上讲的是：如果可以高效的检验结果的正确性，则poly-time monte carlo algorithm可以通过反复“尝试-验证”的方法转换为expected poly-time las vegas algorithm。

:假如无法高效的检验结果的正确性，则该方法就不行了。例如你说的karger algorithm计算min-cut，我们不知道如何高效的检验一个cut是否最小，所以无法最终确定正确。课堂上讲了，通过反复运行，取所有返回cut中最小的一个cut，我们可以把error probability缩小到足够小，但无法缩小到0，即无法完全确定结果真的正确。（实际上，由于min-cut是P问题，我们可以运行最大流算法去确定地计算min-cut，和karger algorithm返回的cut比较就知道是否正确。理论上讲，这也算“验证”了结果的正确性，但这显然不是你的原意）

:如果对于任何问题人类都知道怎么高效验证一个解的正确性，那么高效monte carlo算法就等同于高效las vegas算法，于是就有ZPP=RP=BPP了。然而目前这还是未知的。
::--[[User:WikiSysop|etone]] 10:07, 18 March 2010 (UTC)

Talk:Randomized Algorithms (Spring 2010)

2010-04-29T01:01:29Z

210.28.131.124:

请大家点击页面上方的“edit”进行留言和讨论 --[[User:WikiSysop|etone]] 13:08, 11 January 2010 (UTC)

我觉得前面的这位同学可以把这种求最小的问题变成判定问题嘛（毕竟寻找最小的结果怎么可能是T，F之类的东西呢）即，是否有切小于c，c是某个常数。这样验证起来就很舒服。虽然和原意还是有一些subtle difference，比如此时如果说没有也不一定真没有。
----
尹老师，你好！上次去听了你的randomized algorithms的课，很不错。但有几点疑问，描述如下：
1、你课件上说randomized algorithms有个特性是“简单”，能否举个例子，最好能跟这个例子的deterministic algorithms做下比较。
2、monte carlo式的randomized algorithms的结果怎么验证？比如min-cut这个例子，假设独立地执行karger算法10次，其中有一次结果是正确的，10次结果如下：
F,F,F,F,T,F,F,F,F,F(T为正确，F为错误),问题是我怎么知道第5次是正确的。甚者，如果执行n（n比较大）才能得到一次正确结果，即使是人工验证也是很难的。不知道是否想错误了。
望老师有空解答下。
:Re:
:(1) randomized algorithm算法简单的例子有很多，例如karger algorithm明显就比确定算法计算min-cut的最大流算法简单。以后还会看到更多。

:(2)课上讲的是：如果可以高效的检验结果的正确性，则poly-time monte carlo algorithm可以通过反复“尝试-验证”的方法转换为expected poly-time las vegas algorithm。

:假如无法高效的检验结果的正确性，则该方法就不行了。例如你说的karger algorithm计算min-cut，我们不知道如何高效的检验一个cut是否最小，所以无法最终确定正确。课堂上讲了，通过反复运行，取所有返回cut中最小的一个cut，我们可以把error probability缩小到足够小，但无法缩小到0，即无法完全确定结果真的正确。（实际上，由于min-cut是P问题，我们可以运行最大流算法去确定地计算min-cut，和karger algorithm返回的cut比较就知道是否正确。理论上讲，这也算“验证”了结果的正确性，但这显然不是你的原意）

:如果对于任何问题人类都知道怎么高效验证一个解的正确性，那么高效monte carlo算法就等同于高效las vegas算法，于是就有ZPP=RP=BPP了。然而目前这还是未知的。
::--[[User:WikiSysop|etone]] 10:07, 18 March 2010 (UTC)

TCS Wiki - User contributions [en]

Talk:Randomized Algorithms (Spring 2010)

Talk:Randomized Algorithms (Spring 2010)