Talk:Randomized Algorithms (Spring 2010)

2010-03-03T11:55:42Z

172.25.50.12:

请大家点击页面上方的“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比较大）才能得到一次正确结果，即使是人工验证也是很难的。不知道是否想错误了。
望老师有空解答下。

TCS Wiki - User contributions [en]

Talk:Randomized Algorithms (Spring 2010)