循环调度的分治算法实现实验报告_gxl
深圳大学实验报告
课程名称:算法设计与分析
实验项目名称:分治算法
-矩阵乘法的Strassen算法和时间复杂性分析
或--循环调度的分布式算法实现
或多项式积问题的方差算法和时间复杂性分析
学院:
专业,班级:
指导教师:
报告员:学校编号:
实验时间:
实验报告提交时间:
教务处制
实验的目的和实验内容
1.1实验目的
通过本设计实验,了解递归算法以及分割统治算法的基本思想。 了解Strassen矩阵乘法的理论分析或循环比赛时间表的分布式算法及编程实现。 掌握多项式积的方差方法。 可以设计、分析递归算法和分布式算法。
这门课的实验目的是验证、加强和补充课堂上讲授的理论知识。 学生独立设计算法,初步具备对给定算法进行复杂性分析的能力,为后续课程和实际工作奠定基础。
1.2实验主题(三道题中的任意一道) ) ) ) )。
主题1 )设计并编程实现矩阵相乘的Strassen算法,进行算法的时间复杂性分析。 其中,考虑到n为2的幂的情况,乘积矩阵C=A*B,a=(AIJ ) n*n,b=(bij ) n*n )1)取n=8实现方差递归; )2)考虑到n是偶数而不是2的幂,设计结合传统方法的Strassen算法的矩阵乘法算法,采用n=12实现方差递归(可在多个方案中实现); 矩阵a、b元素自动生成,限定矩阵元素在0-10之间。
主题2 )设计满足以下要求的循环比赛时间表() ) ) ) )。
(1)每名选手必须与其他n-1名选手各进行一次比赛。
)2)每个运动员一天只能打一次比赛。
)3) n为奇数时,每班n天,n为偶数时,每班n-1天。
主题3 )设计多项式乘积问题的方差算法,进行算法的时间复杂性分析
1.3实验要求:
主题1具体要求:
(1)矩阵次数n由用户输入)注意n为2k以外时的处理);
)2) n阶矩阵a、b调用随机函数自动生成,限定矩阵元素在0-10之间;
(3)输出a、b及C=A*B
其中,输出传统定义的矩阵乘积结果和Strassen矩阵乘积结果,验证分治算法的正确性;
(4)直接计算)对矩阵积、Strassen矩阵积进行运行时间统计,分别标记为T1、T2,并给出对比和时间复杂性分析。
主题2具体要求:
)1)选手数n由用户输入(注意n为奇数时和偶数时的处理差异);
)2)验证n=2k的比赛时间表
)3)完成n=2k 1和n=2k的不同处理,输出如下表所示的比赛时间表。 这里,k是【5、7】之间的整数;
1
2
3
4
5
6
7
8
9
10
2
1
5
3
7
4
8
9
10
6
3
8
1
2
4
5
9
10
6
7
4
5
9
1
3
2
10
6
7
8
5
4
2
10
1
3
6
7
8
9
6
7
8
9
10
1
5
4
3
2
7
6
10
8
2
9
1
5
4
3
8
3
6
7
9
10
2
1
5
4
9
10
4
6
8
7
3
2
1
5
10
9
7
5
6
8
4
3
2
1
表分治法n=10的比赛时间表
主题3具体要求:
针对教材第114页的第21题数据,完成两个多项式乘积的分布式算法:
多项式pn(x )的n和QM ) x )的m由用户输入;
直接输出多项式积和分治算法多项式积的计算结果,验证分治算法的正确性;
对直接计算多项式积、分段托管算法多项式积进行运行时间统计,分别标记为T1、T2,并给出对比和时间复杂性分析。
对于p4(x )=x4x3x2- x1和q5(x )=X53x-10,根据要求从(1) )到(3)完成两个多项式乘积的分割算法。
开发环境
VC 6.0编程软件
算法概述
总体思路:通过分而治之的策略,将一切分成两半,n名选手可以由n/2名选手设计的比赛时间表决定。 通过递归地将选手分成两部分,分割成只剩下两个选手。
n为奇数时,可以虚拟增加一名选手,对N 1名选手的时间表进行编程,最忽略虚拟选手参加的比赛。 对分割时的N/2情况也进行特殊处理,与没有参加上一个N/2回合比赛的选手参加下一场比赛。
解决模型
编程(方案)说明)例如,如何实现矩阵分割、矩阵结果的合并