Talk:Randomized Algorithms (Spring 2010): Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
---- | ---- | ||
尹老师，你好！上次去听了你的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比较大）才能得到一次正确结果，即使是人工验证也是很难的。不知道是否想错误了。 | |||
望老师有空解答下。 | |||
Revision as of 11:55, 3 March 2010
请大家点击页面上方的“edit”进行留言和讨论 --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比较大）才能得到一次正确结果，即使是人工验证也是很难的。不知道是否想错误了。 望老师有空解答下。