下载文档原格式
《算法设计与分析》上机实验报告专业软件工程班级1101学号学生姓名完成日期2013-11-081.上机题目及实验环境1.1上机题目：最大k乘积问题1.2实验环境：CPU：3.20GHz内存：3.21GB操作系统：Microsoft Windows XP软件平台：Microsoft Visual C++2. 算法设计与分析设w(h,k) 表示从第1位到第k位所组成的十进制数;设m(i,j)表示前i位分成j段所得的最大乘积;则可得到如下经典的DP方程：if(j==1)m(i,j) = w(1,i) ;if(j >1 && j<=i )m(i,j) = m(d,j-1)*w(d+1,i) //其中：1<=d< i (即从1开始一直到i-1 中找最大值if(i < j)m(i,j) = 0 ;//i一直小于等于n，j一直小于等于k3. 核心代码void maxdp(int n,int k,int *a){ int i,j,d;long temp,max;for(i=1; i<= n ; i++) //分成1段m[i][1] = w[1][i];for(i=1 ; i<= n ; i++) //DP 过程for(j=2; j<= k ; j++){max = 0;for(d=1; d < i ; d++)if ( (temp = m[d][j-1]*w[d+1][i]) > max)max = temp ;m[i][j] = max ;}}4. 运行与调试图1图2图35. 结果分析和小结（1）对结果的分析。
分析结果可以采用图或者表的形式给出。
图4 图5图6 图7图8 图9（2）本次上机实验的收获、心得体会。
通过本次试验，我又一次复习了C语言的有关知识，对于C语言的认识可谓是更加深刻，巩固了以往所学的内容。
同时，对于动态规划也有了更好的理解，尤其是弄清了最优子结构那方面的知识，从中学到了许多新的编程思想。
基于熵权法的Stacking算法包志强; 胡啸天; 赵媛媛; 赵研【期刊名称】《《计算机工程与设计》》【年(卷),期】2019(040)010【总页数】6页(P2885-2890)【关键词】堆叠泛化; 熵权法; 分散度; 差异性; 预测精度【作者】包志强; 胡啸天; 赵媛媛; 赵研【作者单位】西安邮电大学通信与信息工程学院陕西西安710121【正文语种】中文【中图分类】TP1810 引言堆叠泛化法(Stacking)[1,2]是由Wolpert提出的一种通用集成技术，是一个重要的分类器组合模型。
将多个分类器通过某种融合策略产生更好的分类，从而实现其优越的泛化性能[3,4]。
其中改变1-层训练集的输出类型与分布是改进Stacking算法的关键[5,6]。
基于投票的Stacking算法[7]是根据基分类器对类输出的预测情况进行投票，将基分类器输出类别的投票结果作为1-层训练集；一种适用于卷积神经网络的Stacking算法[8]，针对多个卷积神经网络输出的特征向量，使用PCA 降维后的特征作为1-层训练集；基于原始虚假数据的堆叠技术[9]，在1-层训练样本中加入0-层预测的原始虚假数据，从而增强1-层成员分类器之间的差异性。
上述算法在不同的数据集中提升效果有限，在重构1-层训练集时没有充分利用类别之间的预测信息，忽略了输出信息的重要性和差异性，从而无法有效利用预测信息的统计特性，导致有些泛化效果明显下降。
本文把熵权原理融入到基于类输出向量构成的1-层训练集中，提出一种熵权法ELFMF。
采用ELFMF计算类别权重时，利用每个预测类别的统计特性，对每个分类结果融入投票信息和基分类器的预测效果，同时考虑预测结果与类别的关系可以更为准确地表示输出结果。
此算法能够充分利用每个基分类器的预测信息，通过增强分类器之间的差异性归纳出熵权类别和实际类别的关系，得到元分类器。
1 基于类输出的Stacking算法1.1 Stacking网络系统的原理堆叠泛化的方法提供了一种将经过训练的网络组合在一起的方法，包括两个不同的阶段，即0级和1级阶段。
第一章绪论学习要求：✧常用通信术语；✧模拟信号与数字信号的定义；✧通信系统的组成、分类、和通信方式；✧数字通信系统的优缺点；✧离散消息的信息量、平均信息量（信源熵）的计算；✧衡量模拟通信系统和数字通信系统的性能指标；✧传码率、传信率、频带利用率、平均传信率和最大传信率的计算及其关系；✧误码率和误信率的定义及计算。
一、简答题1．消息、信息、信号，通信的含义是什么？通信系统至少包含哪几部分？2．试画出模拟和数字通信系统的模型图，并指出各组成部分的主要功能，说明数字通信系统有什么特点？3．举例说明单工、半双工及全双工的工作方式及其特点。
4．举例说明如何度量信息量。
5．通信系统的性能指标是什么？这些性能指标在模拟和数字通信系统中指的是什么？二、综合题1.设有四个符号，其中前三个符号出现的概率分别为1/4，1/8，1/8，且各符号的出现是相对独立的。
试计算该符号集的平均信息量。
H x 1.75 bit/符2.一个由字母A、B、C、D组成的字，对于传输的每一个字母用二进制脉冲编码，00代替A、01代替B、10代替C，11代替D，每个二进制脉冲宽度为5ms。
（1）不同字母是等可能出现时，试计算传输的平均信息速率；（2）若每个字母出现的可能性分别为1 1 1 3P A ，P B ，P C ，P D5 4 4 10 试计算传输的平均信息速率。
R b max 200 bit/sR b 198.5 bit/s3.国际莫尔斯电码用“点”和“划”的序列发送英文字母，“划”用持续3单位的电流脉冲表示，“点”用持续1单位的电流脉冲表示；且“划”出现的概率是“点”出现概率的1/3。
（1）计算“点”和“划”的信息量；（2）计算“点”和“划”的平均信息量。
I 2 bit I. 0.415 bitH x0.81 bit/符4.设一信息源的输出由128个不同的符号组成，其中16个出现的概率为1/32，其余112出现的概率为 1/224。
实验4 Tomasulo算法1 实验目的(1)加深对指令级并行性及开发的理解。
(2)加深对Tomasulo算法的理解。
(3)掌握Tomasulo算法在指令流出、执行、写结果各阶段对浮点操作指令以及load和store指令进行了什么处理。
(4)掌握采用了Tomasulo算法的浮点处理部件的结构。
(5)掌握保留站的结构。
(6)给定被执行的程序片段，对于具体某个时钟周期，能够写出保留站、指令状态表以及浮点寄存器状态表内容的变化情况。
2 实验平台采用Tomasulo算法模拟器。
3 实验内容和步骤首先要掌握Tomasulo算法模拟器的使用方法(见随附的ppt)。
1)、假设浮点功能部件的延迟时间为：加减法2个时钟周期，乘法10个时钟周期，除法40个时钟周期，Load部件2个时钟周期。
(1) 对于下面的代码段，给出当指令MUL.D写结果时，保留站、Load缓冲器以及寄存器状态表中的内容。
L.D F6，24(R2)L.D F2，12(R3)MUL.D F0，F2，F4SUB.D F8，F6，F2DIV.D F10，F0，F6ADD.D F6，F8，F2当指令MUL.D写结果时，保留站中内容如下表所示：当指令MUL.D写结果时，load缓冲器中内容如下表所示：当指令MUL.D写结果时，寄存器状态表中的内容如下表所示：(2) 按单步方式执行上述代码，利用模拟器的对比显示功能，观察每一个时钟周期前后各信息表中内容的变化情况。
观察分析：周期1：取出第一条指令L.D F6, 24(R2)，地址偏移量24写入LOAD1，LOAD1名存入寄F6。
周期2：取出第二条指令L.D F2, 12(R3)，地址偏移量12写入LOAD2，LOAD2名存入寄器F2，同时第一条指令开始执行，LOAD1上写入绝对地址。
周期3：取出第三条指令MUL.D F0, F2,F4，第一条指令完成，第二条指令开始执行,LOAD2上写入绝对地址。
保留站中存入待运算的操作数和操作。
一、选择题（共15题）1、有一离散无记忆信源X ，其概率空间为⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡125.0125.025.05.04321x x x x P X ，则其无记忆二次扩展信源的熵H(X 2)=(B )A 、1.75比特/符号；B 、3.5比特/符号；C 、9比特/符号；D 、18比特/符号。
2、信道转移矩阵为112132425363(/)(/)000000(/)(/)000000(/)(/)P y x P y x P y x P y x P y x P y x ⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦，其中(/)j i P y x 两两不相等，则该信道为DA 、一一对应的无噪信道B 、具有并归性能的无噪信道C 、对称信道D 、具有扩展性能的无噪信道3、设信道容量为C ，下列说法正确的是：（ A ）A 、互信息量一定不大于CB 、交互熵一定不小于CC 、有效信息量一定不大于CD 、条件熵一定不大于C4、在串联系统中，有效信息量的值（ B ）A 、趋于变大B 、趋于变小C、不变D、不确定5、若BSC信道的差错率为P，则其信道容量为：（C ）A、() H pB、()12log1ppp p-⎡⎤-⎢⎥⎢⎥⎣⎦C、() 1H p -D、log()P P-6、设信道输入为 xm，输出为y，若译码准则是当P(y | xm’)≥P(y | xm)，对所有m ≠ m’时，将 y判为m’，则称该准则为（D ）A 最大后验概率译码准则B 最小错误概率准则C 最大相关译码准则D 最大似然译码准则7、线性分组码不具有的性质是（C）A 任意多个码字的线性组合仍是码字B 最小汉明距离等于最小非 0重量C 最小汉明距离为3D 任一码字和其校验矩阵的乘积 cmHT=08.条件熵H（X∣Y）C H（X）。
（A）小于（B）大于（C）小于等于（D）大于等于9.联合熵()nXXXH⋯⋯，21,C1logniiX-∏。
（A ）小于 （B ）大于（C ）小于等于 （D ）大于等于10.相对熵总是 D 。
选择：1.算法的性质包括输入、输出、（ A ）、有限性。
A. 确定性B. 随机性C. 复杂性D. 渐近复杂性2.备忘录法是那种算法的变形（ B ）。
A、分治算法B、动态规划算法C、贪心算法D、回溯法3.具有最优子结构的算法有（ D ）。
A．概率算法B．回溯法C．分支限界法D．动态规划法4.回溯法解旅行商问题时的解空间树是（ B ）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树5.下面哪种函数是回溯法中避免无效搜索采取的策略（ C ）。
A、递归函数B、随机函数C、剪枝函数D、搜索函数简答：（1）算法的概念：算法是指解决问题的一种方法或一个过程。
（2）算法的性质：算法是若干指令的有穷序列，满足性质：（1）输入：有外部提供的量作为算法的输入。
（2）输出：算法产生至少一个量作为输出。
（3）确定性：组成算法的每条指令是清晰，无歧义的。
（4）有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
（5）可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现。
（3）程序的概念：程序是算法用某种程序设计语言的具体实现（4）算法与程序的不同：（1）算法是给人来读的，直接将算法输入计算机是不能运行的（2）程序可以不满足算法的“有限性”。
（5）算法复杂性：算法所需要的计算机资源，所需资源多，算法的复杂性高；反之则复杂性低。
【时间复杂性（指令数）、空间复杂性（存储器大小）、渐近复杂性】（6）计算复杂性：是用计算机求解问题的难易程度。
其度量标准：一是计算所需的步数或指令条数（时间复杂度），二是计算所需的存储单元数量（空间复杂度）。
（7）渐近复杂性的基本分析方法（8）可操作性最好且最有实际价值的是最坏情况下的时间复杂性。
（9）算法渐近复杂性分析中常用函数：单调函数；取整函数；多项式函数；指数函数；对数函数；阶乘函数；第2 章递归与分治策略（1）分治法的基本思想：将一个问题不断分割成若干个小问题，然后通过对小问题的求解再生成大问题的解。
（2）分治法所能解决问题具有的特征：将要求解的较大规模的问题分割为k 个较小规模的子问题。
对这k 个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k 个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
（3）分治法与动态规划算法的相同点和不同点是什么：分治法与动态规划的相同点：分治法与动态规划，二者要求原问题具有最有子结构，都是将问题分而治之分解成若干个规模较小的子问题；不同点：动态规划是将原问题分解为多个子问题，通过计算出子问题的结果构造一个最优解。
动态规划通过迭代法自底向上求解，动态规划将分解后的子问题理解为相互间有联系，有重叠的部分；算法的应用：装配线，矩阵乘法，最长公共子序列，构造最优的二叉树分治法是将原问题分解为多个子问题，利用递归对各个子问题独立求解，最后利用各子问题的解进行合并形成原问题的解。
分治法将分解后的子问题看成是相互独立的。
（4）二分搜索方法的基本思想：将n 个元素分成个数大致相同的两半，取a[ n / 2 ]与欲查找的x 作比较，如果x = a[ n / 2 ]则找到x，算法终止；如果x < a[ n / 2 ]，则只要在数组a 的左半部继续搜索x（这里假设数组元素呈升序排列）。
如果x > a[ n / 2 ]，则只要在数组a 的右半部继续搜索x。
！（5）二分搜索方法的程序设计：充分利用了元素间的次序关系，采用分治策略（6）棋盘覆盖问题的基本思想：棋盘覆盖问题初看起来很难下手解决，但仔细思考后可以采用分治策略设计针对该问题的一个巧妙解法：如下图所示，当k > 0 时，将2k ×2k 棋盘分割为4 个2k-1 ×2k-1 子棋盘，如图(a) 所示。
显然特殊方格必位于图(a) 中4 个较小子棋盘之一中，其余3 个子棋盘中则无特殊方格。
为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L 型骨牌覆盖这 3 个较小棋盘的会合处，如图(b) 和(c) 所示。
从而将原问题转化为4 个较小规模的棋盘覆盖问题。
递归地使用这种分割，直至棋盘简化为棋盘1×1（易于求解）。
（7）合并排序基本思想是：（1）将待排序元素分成大小大致相同的两个子集合，（2）分别对两个子集合进行排序，（3）最终将排好序的子集合合并成为所要求的排好序的集合。
（8）快速排序基本思想：排序子数组a[ p : r ]，步骤如下：（1）分解：以a[ p ] 为基准元素将a[ p : r ] 分成 3 段：a[ p : q - 1 ]、a[ q ]、a[ q + 1 : r ]。
满足条件：a[ p : q - 1 ] 中任何一个元素<= a[ q ]；a[ q + 1 : r ] 中任何一个元素>= a[ q ]。
下标q 在划分过程中确定。
（2）递归求解：通过递归调用快速排序算法分别对a[ p : q - 1 ] 和a[ q + 1 : r ] 进行排序。
（3）合并：对a[ p : q - 1 ] 和a[ q + 1 : r ] 的排序在各自的范围内进行，因此排好序后不需任何运算整个数组a[ p : r ] 即完成排序。
第3 章动态规划（1）动态规划的基本思想及其要素：基本思想：将待求解问题分解成若干个子问题。
要素：最优子结构性质和重叠问题性质。
（2）矩阵连乘问题！（3）备忘录方法的概念：备忘录方法是动态规划方法的变形。
与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上的。
备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
（4）最长公共子序列：一个数列，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。
（5）最大子段和的基本概念：（6）0-1背包问题的基本思想第4 章贪心算法（1）贪心法的思想：当一个问题具有最优子结构性质时，可用动态规划法求解。
但有时会有更简单有效的算法。
（2）活动安排问题：活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，该问题要求高效地安排一系列争用某一公共资源的活动。
（3）贪心算法的基本要素：贪心选择性质和最优子结构性质。
与动态规划算法的差异：（1）贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
（2）动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
（3）对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
回溯法的基本思想：：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
基本概念：是一种系统地搜索解空间树而求得问题解的搜索算法。
计算：1.2.3.使用分治算法找一组数的最大最小数。
采用如下设计思想：将数据集S 均分为S1 和S2；求解S1 和S2 中的最大和最小值；最终的最大和最小值可以计算得到：min( S1, S2 ), max( S1, S2 )；采用同样的处理方法递归处理S1 和S2。
可以得到该算法复杂性的递推公式如下：根据递推公式推导出该复杂性表达式。
4.下面给出了非递归形式的二分搜索方法代码，请补充下划线处的代码。
5.利用动态规划法设计如下的矩阵连乘最小次数问题，写出动态规划法求解过程。
A1：40×25 A2：25×25 A3：25×15解：m[0][0]=m[1][1] =m[2][2] =m[3][3]=0r=2 i=1 j=2m[1][2]=40*25*10=10000i=2 j=3m[2][3]= 25*10*15=3750r=3 i=1 j=3m[1][3]= m[1][1]+ m[2][3]+ 40*25*15=18750 k=2t= m[1][2]+ m[3][3]+ 40*10*15=16000m[1][3]=t=160006.上机实验：用分治法找最大最小数7.上机实验：编辑距离8.上机实验：数字三角形证明：1.2.证明上述问题具有“贪心选择性质”和“最优子结构性质”。
算法：1.有一个箱子容量为V（正整数），同时有n 个物品，每个物品有一个体积（正整数）。
要求n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
编写程序实现，自定义输入和输出。
【提示】使用二维数组f[ i ][ j ], 表示前i 个物品装入容量为j 的箱子能获得的最大体积，则状态转移方程：f[ i ][ j ] = max( f[ i - 1 ][ j ], f[ i -1 ][ j - a[ i ] ] + a[ i ] );2.用回溯法搜索排列树的算法是什么？void Backtrack ( int t ){if ( t > n ) output( x );{elsefor ( int i = t; i <= n; i++ ){swap( x[ t ], x[ i ] );if ( Constraint( t ) && Bound( t ) ) Backtrack( t + 1 );swap( x[ t ], x[ i ] );}}}3.对批处理作业调度问题：作业需要机器处理时间的表如下，如果调度方案为：1，2，3，计算完成时间和。
作业调度方案：1，2，3（必须考虑机器的空闲时间）：作业1 在机器1 上完成的时间为2，在机器2 上完成的时间为3（2 + 1）作业2 在机器1 上完成的时间为5（2 + 3），在机器2 上完成的时间为6（5 + 1）作业3 在机器1 上完成的时间为7（2 + 3 + 2），在机器2 上完成的时间为10（7 + 3）完成时间和：3 + 6 + 10 = 19。
