算法设计与分析 习题4 学习课件

习题四

1.设计搜索算法求解最大团问题，输入是一个图，输出是这个图最大的全连通子图

2.设计搜索算法求解最大独立子集合问题，输入一个图，输入这个图的最大顶点集合，满足该集合中任意两个顶点之间都不存在边

3.设计搜索算法求解有向图图的强连通分量问题，输入一个图，输出这个图的所有强连通分量

4.设计搜索算法求解子图匹配问题，输入图G和图P,输出图G是否包含和P同构的子图

5.设计搜索算法求解0-1背包问题，即给定一个容量为C的背包和n个物品，其中每个物品i的重量为wi,价格为vi,要求物品的重量之和小于C,且价格之和最大

6.证明KMP算法的正确性

7.扩展Rabin-karp算法，设计一个矩阵匹配算法，即输入矩阵A和矩阵B,找到矩阵A中和矩阵B匹配的子阵

8.给定一棵树T,在每条边上有一个标签，该标签包含一个或多个字符，给定一个模式P,T中子路径的标签定义为该路径上所有边上标签依次相连得到的字符串，问题是找到所有从根出发路径的子路径，其标签和P匹配要求运行时间和树中所有标签的字符数与P长度之和相等

9.给出一个例子，令Robin-karp算法的时间复杂度为0mn其中m是模式的长度，n是字符串长度，要说明例子并证明这个时间复杂度

10.给出一个例子，令Robin-karp算法的时间复杂度为0nin其中m是模式的长度，n是字符串长度，要说明例子并证明这个时间复杂度。