第5章 并行算法的一般设计策略
习题例题:
1、 令n是待排序的元素数,p=2d是d维超立方中处理器的数目。假定开始随机选定主元x,并将其播送给所有其他处理器,每个处理器按索接收到的x,对其n/p个元素按照≤x 和>x进行划分,然后按维进行交换。这样在超立方上实现的快排序算法如下:
算法5.6 超立方上快排序算法
输入:n个元素,B = n/p, d = log p
输出: 按超立方编号进行全局排序
Begin
(1)id = processor’s label
(2)for i=1 to d do
(2.1) x = pivot / * 选主元 * /
(2.2) 划分B为B1和B2满足B1 ≤B<B2
(2.3) if第i位是零 then
(i) 沿第i维发送B2给其邻者
(ii) C = 沿第i维接收的子序列
(iii) B= B1∪C
else
(i) 沿第i维发送B1给其邻者
(ii) C = 沿第i维接收的子序列
(iii) B= B2∪C
endif
endfor
(3)使用串行快排序算法局部排序B = n/p个数
End
① 试解释上述算法的原理。
② 试举一例说明上述算法的逐步执行过程。
2、 ① 令T = babaababaa。P =abab,试用算法5.4计算两者的匹配情况。
② 试分析KMP算法为何不能简单并行化。
3、 给定序列(33,21,13,54,82,33,40,72)和8个处理器,试按照算法5.2构造一棵为在PRAM-CRCW模型上执行快排序所用的二叉树。
4、 计算duel(p, q)函数的算法如下:
算法5.7 计算串匹配的duel(p, q) 的算法
输入: WIT〔1: n-m+1〕,1≤p<q≤n-m+1,(p - q) < m/2
输出: 返回竞争幸存者的位置或者null(表示p和q之一不存在)
Begin
if p=null then duel= q else
算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程3班 学号 20122668 姓名王建君 指导教师尹治本 2014年10月
实验四 矩阵相乘次序 一、问题提出 用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n },其中A i 与A i+1是可乘的,i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为: (1)单个矩阵是完全加括号的; (2)矩阵连乘积A 是完全加括号的,则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号,即A=(BC)。 例如,矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式:(A 1(A 2(A 3A 4))),(A 1((A 2A 3)A 4)),((A 1A 2)(A 3A 4)),((A 1(A 2A 3))A 4),(((A 1A 2)A 3)A 4)。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序,这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵,B 是一个q ×r 矩阵,则计算其乘积C=AB 的标准算法中,需要进行pqr 次数乘。 (3)为了说明在计算矩阵连乘积时,加括号方式对整个计算量的影响,先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100,100×5,5×50。加括号的方式只有两种:((A 1A 2)A 3),(A 1(A 2A 3)),第一种方式需要的数乘次数为10×100×5+10×5×50=7500,第二种方式需要的数乘次数为100×5×50+10×100×50=75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见,在计算矩阵连乘积时,加括号方式,即计算次序对计算量有很大的影响。于是,自然提出矩阵连乘积的最优计算次序问题,即对于给定的相继n 个矩阵{A 1,A 2,…,A n }(其中矩阵Ai 的维数为p i-1×p i ,i =1,2,…,n ),如何确定计算矩阵连乘积A 1A 2…A n 的计算次序(完全加括号方式),使得依此次序计算矩阵连乘积需要的数乘次数最少。 二、求解思路 本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是: 1)计算最优值算法MatrixChain():建立两张表(即程序中的**m 和**s ,利用二维指针存放),一张表存储矩阵相乘的最小运算量,主对角线上的值为0,依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量,其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得,最后一次求得的值即为n 个矩阵相乘的最小运算量;另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback():矩阵结合即是给矩阵加括号,打印出矩阵结合方式,由递归过程Traceback()完成。分三种情况: (1)只有一个矩阵,则只需打印出A1; (2)有两个矩阵,则需打印出(A1A2); (3)对于矩阵数目大于2,则应该调用递归过程Traceback()两次,构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为)(n 3 O 。 四、实验源代码
3.用梯度法求下列无约束优化问题:MinF(X)=x12+4x22,设初始点取为X(0)={2,2}T,以梯度模为终止迭代准则,其收敛精度为5。 1)求初始点梯度▽F(X) ▽F(X)={2x1,8x2}T▽F(X(0))={4,16}T (2)第一次搜索 |▽F(X(0))|=16.5,S(0)=- ▽F(X(0))/16.5=-{0.243,0.97}T α(0)=2.157 X(1)=X(0)+α(0)S(0)={1.476,-0.923}T ▽F(x(1))={2.952,-0.738}T |▽F(x(1))|=3.043<5.0 故满足要求,停止迭代。 最优点X*={1.476,-0.0923}T 最优值F(X*)=2.21 4.
5.
6. 用外点法求解约束优化问题: ()()12211221min ..0()0 f X x x s t g X x x g X x =+=-≤=-≤ , 收敛准则:(1) ()0.10.01k k X X εδ+-≤=,约束容限= 解:(1)利用外点法惩罚法构造无约束优化问题 () ( ) 12()22()212121(min ,()() k k k x x X r x x r x x r x +??Φ=?++-+-??可行域内)(可行域外) (2)此例只是为了说明外点法的思路,用微分法求解上述无约束优化问题。 用极值条件求解: 在可行域内:偏导数不可能等于0,即可行域内无极值 在可行域外,令: ()2()11211 ()2122 14()2012()0k k k r x x x r x x r x x x ?Φ =+-+=??Φ =--=?
《ACM算法与数据结构设计》课程大作业报告 题目:五位以内的对称素数 学生姓名 班级学号 学生学院计算机软件学院 学生专业计算机科学与技术 联系电话 电子邮 指导教师 指导单位计算机学院软件工程系 日期2011.5.24
注意事项 (1)课程大作业从《ACM算法与数据结构设计》课程实验二(2011年4月19日)或实验三(2011年5月10日)中任选一个课题完成。(2)课程大作业内容包括课题名称、课题内容和要求、课题分析、概要设计、详细设计、测试数据及其结果分析、调试过程中的问题、参考资料列表、课程小结等。 (3)课程报告可以打印,也可以手写,但前面两页内容、大作业撰写纲要、课程小结不可遗漏和更换。 (4)课程小结给出ACM程序设计过程的收获、遇到的问题,遇到问题解决问题过程的思考、程序调试能力的思考等,需要手写签字。(5)课程大作业提交时间为2011年5月24日(第14周星期二)晚19:00~20:00,地点:计算中心A机房。
一、课题名称: 五位以内的对称素数 二、课题内容和要求: 题目:判断一个数是否为对称且不大于五位数的素数。 要求:判断输入的一组数据(正整数)是否是五位以内的对称素数,逐个判断并输出“yes”或“no” 三、课题分析: 定义两个函数分别判断数据是否为素数(bool isprime(int n)),是否是对称数(bool issym(int n));在main()函数中利用if()语句来判断该数据是否是五位以内的数。只有同时满足三个条件,才能判断一个数据是五位以内的对称素数,输出“yes”;否则输出“no”。 输入输出方案: 输入: 输入数据含有不多于50个的正整数(0 《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”, 由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成 绩记入课程总成绩。 客观题部分: 一、选择题( 每题1分, 共15题) 1、递归算法: ( C ) A、直接调用自身 B、间接调用自身 C、直接或间接 调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模 较小的字问题, 这些子问题: ( D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是: ( C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的: ( A ) A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是: ( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、 形函数 6、哈夫曼编码是: ( B) A、定长编码 B、变长编码 C、随机编码 D、定 长或变长编码 7、多机调度的贪心策略是: ( A) A、最长处理时间作业优先 B、最短处理时间作业优 先 C、随机调度 D、最优调度 8、程序能够不满足如下性质: ( D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是: ( A ) A、递归算法 B、动态规划算法 C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题: ( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是: ( A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策 有可能导致算法: ( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到: ( C ) A、全局最优解 B、 0-1背包问题的解 C、背包问题的 解 D、无解 14、能求解单源最短路径问题的算法是: ( A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是: 现代设计方法作业习题1 姓名王金昆工程0802班200879250222 2-1.制作一个体积为5m^3的货箱,由于运输装卸要求其长度不小于4m,要求钢板用料最省,试写出该问题的优化数学模型. 解:设该货箱长为x1m、宽为x2m、高为x3m,表面积为S,体积为V.由题意可以建立优化数学模型: S=2*(x1*x3+x2*x3)+x1*x2; V=x1*x2*x3=5; x1>=4; x2>=0; x3>=0; 选择最优化算法求解Smin. 我选择Lingo软件来求解,编程如下: min=fx; fx=2*(x1*x3+x2*x3)+x1*x2; x1*x2*x3=5; x1>=4; x2>=0; x3>=0; 点击Solve出现结果: Local optimal solution found. Objective value: 15.14911 Extended solver steps: 5 Total solver iterations: 112 Variable Value Reduced Cost FX 15.14911 0.000000 X1 4.000000 0.000000 X3 0.7905694 0.1107763E-07 X2 1.581139 0.000000 所以表面积Smin=15.14911 m^2,此时长为4m,宽为1.581139 m,高为0.7905694 m. 2-2.把一根长为L的铜丝截成两段,一段弯成圆形,一段完折成正方形。求截断的两段为何比例才能使圆形和正方形的面积之和最大,试写出该问题的优化数学模型。 解:设弯成正方形的边长为x,所围成的圆形和正方形面积之和为S。建立优化数学模型: 取pai-3.1415926 《算法分析与设计》作业(一) 本课程作业由两部分组成。第一部分为“客观题部分”,由15个选择题组成,每题1分,共15分。第二部分为“主观题部分”,由简答题和论述题组成,共15分。作业总分30分,将作为平时成绩记入课程总成绩。 客观题部分: 一、选择题(每题1分,共15题) 1、递归算法:(C ) A、直接调用自身 B、间接调用自身 C、直接或间接调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题,这些子问题:(D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是:(C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的:(A ) A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是:( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、形函数 6、哈夫曼编码是:(B) A、定长编码 B、变长编码 C、随机编码 D、定长或变长编码 7、多机调度的贪心策略是:(A) A、最长处理时间作业优先 B、最短处理时间作业优先 C、随机调度 D、最优调度 8、程序可以不满足如下性质:(D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是:(A ) A、递归算法 B、动态规划算法 C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题:( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是:(A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法:( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到:(C ) A、全局最优解 B、0-1背包问题的解 C、背包问题的解 D、无解 14、能求解单源最短路径问题的算法是:(A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是:( A ) A、舍伍德算法 B、蒙特卡罗算法 C、拉斯维加斯算法 D、数值随机化算法 主观题部分: 二、写出下列程序的答案(每题2.5分,共2题) 1、请写出批处理作业调度的回溯算法。 #include 2017级《程序设计与算法综合实践》 期末大作业题目及评分标准 有如下情况之一者,为不及格。 (1)未能完成所选题目评分标准的最低要求。 (2)抄袭他人成果。 (3)大作业检查时不带电脑,或电脑没有C语言开发环境。 (4)出勤次数、课堂表现等不符合学校相关教学文件规定等其他情况。 备选题目目录 1.图书购买系统...............................................................................................................- 2 - 2.物流信息管理系统 ....................................................................................................- 3 - 3.PM2.5实时信息管理系统 ............................................................ - 5 - 4.电影评论系统 ............................................................................... - 6 - 5.游戏角色属性分析........................................................................ - 8 - 6.KTV点歌系统 ................................................................................ - 9 - 7.英语词斩系统 ............................................................................. - 11 - 8.校运动会成绩管理系统.............................................................. - 14 - 9.通讯录管理系统 ......................................................................... - 15 - 10.机票购买系统 ............................................................................. - 16 - 11.车辆销售管理系统...................................................................... - 17 - 12.饮品自动贩卖机系统.................................................................. - 18 - 基于贪心算法求解TSP问题 一、TSP问题 TSP问题(Travelling Salesman Problem)即旅行商问题,又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类,一类是对称TSP问题(Symmetric TSP),另一类是非对称问题(Asymmetric TSP)。所有的TSP问题都可以用一个图(Graph)来描述: V={c1, c2, …, ci, …, cn},i = 1,2, …, n,是所有城市的集合.ci表示第i个城市,n为城市的数目; E={(r, s): r,s∈V}是所有城市之间连接的集合; C = {crs: r,s∈V}是所有城市之间连接的成本度量(一般为城市之间的距离); 如果crs = csr, 那么该TSP问题为对称的,否则为非对称的。 一个TSP问题可以表达为: 求解遍历图G = (V, E, C),所有的节点一次并且回到起始节点,使得连接这些节点的路径成本最低。 二、贪心算法 贪心算法,又名贪婪算法,是一种常用的求解最优化问题的简单、迅速的算法。贪心算法总是做出在当前看来最好的选择,它所做的每一个在当前状态下某种意义上是最好的选择即贪心选择,并希望通过每次所作的贪心选择导致最终得到问题最优解。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。 1、贪心算法的基本思路 从问题的某一个初始解触发逐步逼近给定的目标,以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。大致步骤如下: 1)建立数学模型来描述问题; 2)把求解的问题分成若干个子问题 3)对每一个子问题求解,得到子问题的局部最优解 4)把子问题的局部最优解合成原问题的一个解 2、贪心算法的实现框架 贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择,而贪心策略适用的前提是:局部最优策略能导致产生全局最优解。 从问题的某一初始解出发; while (能朝给定总目标前进一步) { 利用可行的决策,求出可行解的一个解元素; } 由所有解元素组合成问题的一个可行解; 3、贪心算法存在的问题 1)不能保证求得的最后解是最佳的; 机电工程学院 现代设计方法大作业基于汽车噪声的TRIZ分析 学号:S314070064 专业:机械工程 学生姓名:*** 任课教师:*** 教授 2015年1月 基于汽车噪声的TRIZ分析 一对技术系统进行初步分析 1.选择系统。 我所选择的系统是汽车。 2.系统的三维图,如图1所示。 图1 汽车的三维图 汽车工作原理:汽车的行驶主要靠发动机来带动,以四冲程汽油机为例,四冲程汽油机是将空气与汽油或柴油以一定的比例混合成良好的混合气,在吸气冲程被吸入汽缸,混合气经压缩点火燃烧而产生热能,高温高压的气体作用于活塞顶部,推动活塞作往复直线运动,通过连杆、曲轴飞轮机构对外输出机械能。四冲程汽油机在进气冲程、压缩冲程、做功冲程和排气冲程内完成一个工作循环。汽油机简图及其具体运动过程如图2所示。 图2 四冲程汽油机工作循环图 (1)进气行程 化油器式汽油机将空气与燃料先在气缸外部的化油器中进行混合,然后再吸入气缸。进气行程中,进气门打开,排气门关闭。随着活塞从上止点向下止点移 动,活塞上方的气缸容积增大,从而气缸内的压力降低到大气压力以下,即在气缸内造成真空吸力。这样,可燃混合气便经进气管道和进气门被吸入气缸。 (2)压缩行程 为使吸入气缸内可燃混合气能迅速燃烧,以产生较大的压力,从而使发动机发出较大功率,必须在燃烧前将可燃混合气压缩,使其容积缩小、密度加大、温度升高,即需要有压缩过程。在这个过程中,进、排气门全部关闭,曲轴推动活塞由下止点向上止点移动一个行程称为压缩行程。 (3)作功行程 在这个行程中,进、排气门仍旧关闭。当活塞接近上止点时,装在气缸盖上的火花塞即发出电火花,点燃被压缩的可燃混合气。可燃混合气被燃烧后,放出大量的热能,因此,燃气的压力和温度迅速增加,所能达到的最高压力约为3-5Mpa,相应的温度则为2200-2800K。高温高压的燃气推动活塞从上止点向下止点运动,通过连杆使曲轴旋转并输出机械能,除了用于维持发动机本身继续运转而外,其余即用于对外作功。 (4)排气行程 可燃混合气燃烧后生成的废气,必须从气缸中排除,以便进行下一个进气行程。当膨胀接近终了时,排气门开启,靠废气的压力进行自由排气,活塞到达下止点后再向上止点移动时,继续将废气强制排到大气中。活塞到上止点附近时,排气行程结束。 汽车的执行机构:轮胎。 作用对象:路面。 3.汽车系统的黑箱图。 汽车的黑箱图如图3所示。 图3 汽车系统黑箱图 4.确定系统主要有益功能和其它功能。 汽车主要有益功能:载运客、货物和牵引客、货挂车。 《软件系统分析与设计》 期末大作业 选题名称:游戏平台管理系统设计人:徐文豪刘青海 赖超宇甘智宏 班级:软工143班 南昌大学软件学院 2016.6.1 目录 一、整体描述 (2) 二、需求分析 (3) 三、系统功能概况 (4) 四、类的属性与方法 (5) 五、系统界面界限 (11) 六、设计模型 (13) 七、设计原则 (17) 八、设计模式······················ 一、整体描述 随着移动通讯的发展,手机应用也越来越多,其中,游戏应用占据了很大的比重,游戏平台管理系统是整合了大量游戏应用,以及玩家线上交流的平台。 主要受众群:拥有移动端或电脑端的人群。 应用前景:移动互联的发展为游戏平台的发展提供了很大的生存空间,应用前景十分广阔 盈利方式:向平台中游戏的开发商收取一定的费用,游戏玩家向游戏中注入资金时,收取一定比例的游戏收入。 面临的困难:游戏平台前期的推广,提高游戏平台本身对开发商和游戏玩家的吸引力,游戏平台能否适应大部分游戏玩家的要求。 玩家首先要注册账号,然后就可以在上面下载游戏应用,上传自己的游戏资源。同时,根据玩家的活跃程度获取相应积分,用积分可以兑换游戏礼包,也会根据玩家等级在游戏装备上给与相应的优惠和等级奖励。玩家在每一款游戏的评论区都可以交流游戏经验,提出意见和建议,以便游戏及时更新,弥补相应不足。玩家也可以建立游戏工会,不同游戏的玩家都可以加入,分享自己的游戏心得或者转赠游戏装备或积分。 二、需求分析 时间when:游戏厂商:随时;注册用户:随时;管理人员:正常工作时间。 地点Where:游戏厂商,管理人员:工作地点;注册用户:随地 人员who:游戏厂商,管理人员,注册用户, What:游戏厂商:推广游戏,管理人员:扩大服务,盈利;注册人员:玩游戏。 Why:游戏厂商:推广力度不大,效果不好,管理人员:方便管理,注册用户:良好的游戏环境。 性能Performance:系统提供服务的效率,响应时间快,由于是手机端的APP吞吐量不需要太大。 成本Cost:实现系统需要付出的代价,耗费****元 时间Time:2016年6月3日 可靠性Reliability: 需要系统长时间正确运行的能力 安全性Security: 由于该平台会涉及资金的流动,所以需要对信息安全的保护能力。 合规性Compliance: 需要符合各种行业的标准,法律法规,规范。技术性Technology:要求基于安卓平台开发。 兼容性Compatibility:需要与一些支付平台进行兼容能力。还有对游戏的兼容性。算法分析与设计作业及参考答案样本
现代设计方法 作业
最新算法分析与设计作业(一)及参考答案讲课讲稿
《程序设计与算法综合实践》期末大作业题目及评分标准
算法设计大作业—求解Tsps问题
现代设计方法大作业
软件系统分析与设计大作业
《算法分析与设计》作业参考答案