[未归类] CS 11/04 SUB题目讨论帖！！ [复制链接]

Rank: 2

声望: 0
寄托币: 290
注册时间: 2006-7-9
精华: 0
帖子: 2

5楼

发表于 2006-11-4 18:42:15 |只看该作者

原帖由 yt_May 于 2006-11-4 18:36 发表
"NPComplete，我觉得除了算法第一个显然是p，后面那两个最长简单路径都不是":
这道题我觉得有向无环图DAG的最长简单路径是p，可以先进行拓扑排序，然后各个点的先后顺序就知道了，因为没有环，所以最长 ...

一个是 if (x!=0 && (y/x == z))和 if（y/x==z && x!=0）有什么不同，
能解释一下吗？

十指飞舞
UID：2228487

Rank: 2

声望: 0
寄托币: 290
注册时间: 2006-7-9
精华: 0
帖子: 2

6楼

发表于 2006-11-4 18:46:09 |只看该作者

原帖由 wutherings 于 2006-11-4 18:31 发表
amdahl's law:应该是10倍。其实我做到这题的时候心中小小感叹了一下：虽然这个定理是做并行处理的人用的，但是却昭示了，即使我做处理器并行再努力，也只能提高这么多，如果有瓶颈的话。而小小一个算法，就能提高 ...

1.yes
2.yes

wutherings UID：198481 wutherings 当前离线最后登录 2015-3-5 在线时间 42 小时寄托币 4335 声望 3 注册时间 2005-3-2 阅读权限 5 帖子 46 精华 4 积分 3982 UID 198481 禁止发言声望 3 寄托币 4335 注册时间 2005-3-2 精华 4 帖子 46 关注TA 加好友标签发消息	7楼发表于 2006-11-4 18:47:11 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽

	使用道具举报

wutherings UID：198481 wutherings 当前离线最后登录 2015-3-5 在线时间 42 小时寄托币 4335 声望 3 注册时间 2005-3-2 阅读权限 5 帖子 46 精华 4 积分 3982 UID 198481 禁止发言声望 3 寄托币 4335 注册时间 2005-3-2 精华 4 帖子 46 关注TA 加好友标签发消息	8楼发表于 2006-11-4 18:50:54 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽

	使用道具举报

Rank: 2

声望: 0
寄托币: 149
注册时间: 2005-5-7
精华: 0
帖子: 1

9楼

发表于 2006-11-4 18:59:21 |只看该作者

可是顶点4没有入度，其他顶点无法到达4，这样对4而言就不是强连通（双连通），所以我觉得应该把4分出来，这样理解不知对否？

wutherings UID：198481 wutherings 当前离线最后登录 2015-3-5 在线时间 42 小时寄托币 4335 声望 3 注册时间 2005-3-2 阅读权限 5 帖子 46 精华 4 积分 3982 UID 198481 禁止发言声望 3 寄托币 4335 注册时间 2005-3-2 精华 4 帖子 46 关注TA 加好友标签发消息	10楼发表于 2006-11-4 19:28:12 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽

	使用道具举报

Rank: 2

声望: 0
寄托币: 149
注册时间: 2005-5-7
精华: 0
帖子: 1

11楼

发表于 2006-11-4 19:29:31 |只看该作者

倒数第三题，关于一个什么工作流的问题。就是一张无向图，每条边上有概率1/3,1/2,1什么的，求S到T的什么方面的概率，具体忘了？大家选的什么？我乱选的...

还有一个hash表 16位的输入映射到8位的hash值，求对任意的1000个输入的组合中至少有k个输入映射到同一个hash值时k的最大值。是不是3，我好像选错了...

wutherings UID：198481 wutherings 当前离线最后登录 2015-3-5 在线时间 42 小时寄托币 4335 声望 3 注册时间 2005-3-2 阅读权限 5 帖子 46 精华 4 积分 3982 UID 198481 禁止发言声望 3 寄托币 4335 注册时间 2005-3-2 精华 4 帖子 46 关注TA 加好友标签发消息	12楼发表于 2006-11-4 19:31:42 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽

	使用道具举报

Rank: 2

声望: 0
寄托币: 149
注册时间: 2005-5-7
精华: 0
帖子: 1

13楼

发表于 2006-11-4 19:34:28 |只看该作者

原帖由 wutherings 于 2006-11-4 19:28 发表

双联通的定义是：这个connected component里面没有articulation point，就是割点

如果把四去掉的话，不会造成234567不联通，所以4不是articulation point
所以1234567是biconnected component，我是这么理解的

按照我对你说的理解，原图中8只有入度，去掉8也不会造成1234567不连通，所以8也不是articulation point，那这样不是12345678也是biconnected component？

Rank: 2

声望: 0
寄托币: 149
注册时间: 2005-5-7
精华: 0
帖子: 1

14楼

发表于 2006-11-4 19:37:09 |只看该作者

原帖由 wutherings 于 2006-11-4 19:31 发表

我选5/6，感觉就这个还算靠谱

那个是4，抽屉原则

两题和你一样。但是第二题应该怎么理解，我总觉得是3，不知道怎么会选4的...