Talk:Randomized Algorithms (Spring 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比较大）才能得到一次正确结果，即使是人工验证也是很难的。不知道是否想错误了。望老师有空解答下。