全部版块 我的主页
论坛 数据科学与人工智能 数据分析与数据科学 SAS专版
1610 2
2011-11-06
Consider an instance of SAT with m clauses, where every clause has exactly k literals.
(a) Consider a simple randomized algorithm that assigns each variable to TRUE or FALSE
uniformly at random.  What exactly is the expected number of clauses that are satisfied?
(b) Give a derandomization of the above randomized algorithm using the method of conditional
expectations.  Show your reasoning.

求求各位了~~~看不懂~~~求解!!
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

全部回复
2011-11-6 23:04:34
考虑一个有m个子句的SAT实例,每个子句都有且仅有k个文字。
考虑简单随机算法对变量随机赋值为对或错,子句的期望值是多少比较合适?
用条件期望的方法给定一个关于上述随机算法的解随机处理,给出你的解释。
可能有的不是很专业,大概就是这样吧
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2011-11-7 08:42:38
小梧桐树 发表于 2011-11-6 23:04
考虑一个有m个子句的SAT实例,每个子句都有且仅有k个文字。
考虑简单随机算法对变量随机赋值为对或错,子句 ...
谢谢~~~关键是解~~~没学过这一块~~完全不明白~~
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

相关推荐
栏目导航
热门文章
推荐文章

说点什么

分享

扫码加好友,拉您进群
各岗位、行业、专业交流群