算法分析在元件折叠当中的应用
算法分析在元件折叠当中的应用
关键词：贪婪算法、最优化、最优解、分而治之算法、动态规划法、回溯、分枝定界、先进先出、元件折叠
在设计电路的过程中有两种为位－片设计和标准单元设计。在前一种方法中，电路首先被设计为一个元件栈。假如每个元件Ci 宽为wi ，高为hi ，而元件宽度用片数来表示。连线可能连接元件Ci 的第j片到元件Ci+1 的第j 片。如果某些元件的宽度不足j 片，则这些元件之间不存在片j 的连线。在V L SI 芯片上为它分配一定数量的空间单元。分配是按空间宽度或高度的限制来完成的。如何将元件栈折叠到分配空间中去，以便尽量减小未受限制的尺度由于其他尺度不变，因此缩小一个尺度（如W）等价于缩小面积。可用折线方式来折叠元件栈，在每一折叠点，元件旋转1 8 0°。一个1 2元件的栈折叠成四个垂直栈，折叠点为C6 , C9 和C1 0。折叠栈的宽度是宽度最大的元件所需的片数。若栈宽各为4，3，2和4。折叠栈的高度等于各栈所有元件高度之和的最大值。在中栈1的元件高度之和最大，该栈的高度决定了包围所有栈的矩形高度。实际上，在元件折叠问题中，还需考虑连接两个栈的线路所需的附加空间。如在C5 和C6 间的线路因C6 为折叠点而弯曲。这些线路要求在C5 和C6 之下留有垂直空间，以便能从栈1连到栈2。令ri 为Ci 是折叠点时所需的高度。栈1所需的高度为5 i =1hi +r6，栈2所需高度为8 i=6hi +r6+r9。在标准单元设计中，电路首先被设计成为具有相同高度的符合线性顺序的元件排列。假设此线性顺序中的元件为C1，.，Cn，下一步元件被折叠成相同宽度的行。1 2个标准单元折叠成四个等宽行。折叠点是C4，C6 和C11。在相邻标准单元行之间，使用布线通道来连接不同的行。折叠点决定了所需布线通道的高度。设li 表示当Ci 为折叠点时所需的通道高度。布线通道1的高度为l4，通道2的高度为l6，通道3的高度为l11。位－片栈折叠和标准单元折叠都会引出一系列的问题，这些问题可用动态规划方法来解决。
一. 等宽位－片元件折叠：定义r1 = rn+1 =0。由元件Ci 至Cj 构成的栈的高度要求为j k= ilk+ ri+ rj + 1。设一个位－片设计中所有元件有相同宽度W。首先考察在折叠矩形的高度H给定的情况下，如何缩小其宽度。设Wi为将元件Ci 到Cn 折叠到高为H的矩形时的最小宽度。若折叠不能实现（如当ri +hi＞H 时），取Wi =∞。注意到W1 可能是所有n 个元件的最佳折叠宽度。当折叠Ci 到Cn 时，需要确定折叠点。现假定折叠点是按栈左到栈右的顺序来取定的。若第一点定为Ck+ 1，则Ci 到Ck 在第一个栈中。为了得到最小宽度，从Ck+1 到Cn 的折叠必须用最优化方法，因此又将用到最优原理，可用动态规划方法来解决此问题。当第一个折叠点k+ 1已知时，可得到以下公式：Wi =w+ Wk + 1 （1 5 - 9）由于不知道第一个折叠点，因此需要尝试所有可行的折叠点，并选择满足（1 5 - 9）式的折叠点。令h s u m(i,k)=k j = ihj。因k+ 1是一个可行的折叠点，因此h s u m(i, k) +ri +rk+1 一定不会超过H。Wn+1 =0，且在无最优折叠点k+ 1时Wi 为∞。可通过递归计算Wn , Wn- 1., W2 , W1 来计算Wi。Wi 的计算需要至多检查n-i+ 1个Wk+ 1，耗时为O (n-k)。因此计算所有Wi 的时间为O (n2 )。通过保留式每次所得的k 值，可回溯地计算出各个最优的折叠点，其时间耗费
算法设计与分析(作业三)
算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程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 。 四、实验源代码
算法分析与设计总结
第一章算法概述 1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。 2.算法的性质： 1)输入：有零个或多个输入 2)输出：有至少一个输出 3)确定性：每条指令是清晰的、无歧义的 4)有限性：每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复 杂性，需要空间资源的量称为空间复杂性 2)三种时间复杂性：最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念：直接或间接调用自身的算法 2.递归函数：用函数自身给出定义的函数 3.递归要素：边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout< 《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 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、快速排序算法和线性时间选择算法的随机化版本是: 算法设计与分析 学院：计算机科学与技术 学号：129074106 姓名：张淼淼 2014 11 14 1、 当问题规模100 N 时，快速排序和插入排序各需多少时间？写清机器配置，列出五种 快速排序所需时间(ms) 插入排序所需时间（ms ） 两者相差多少 N=100 0.00600 0.019000 -0.013000 N=1000 0.074000 0.724000 -0.650000 N=10000 0.032000 64.657000 -64.625000 N=100000 13.300000 50.900000 -37.600000 N=1000000 53.500000 117.700000 -64.200000 Window 7 32位 Cpu ：Inter(R) Core(TM) i3-2120 cpu@3.30GHz AMD Radeon HD 6450 Graphics 程序： #include int b[1000000]; void QuickSort(int low ,int high) { long i,j; int x; i=low; j=high; x=a[i]; while(i 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 《数值分析》计算实习题目 第一题： 1. 算法设计方案 （1）1λ，501λ和s λ的值。 1)首先通过幂法求出按模最大的特征值λt1，然后根据λt1进行原点平移求出另一特征值λt2，比较两值大小，数值小的为所求最小特征值λ1，数值大的为是所求最大特征值λ501。 2)使用反幂法求λs ，其中需要解线性方程组。因为A 为带状线性方程组，此处采用LU 分解法解带状方程组。 （2）与140k λλμλ-5011=+k 最接近的特征值λik 。 通过带有原点平移的反幂法求出与数k μ最接近的特征值 λik 。 （3）2cond(A)和det A 。 1）1=n λλ2cond(A)，其中1λ和n λ分别是按模最大和最小特征值。 2）利用步骤（1）中分解矩阵A 得出的LU 矩阵，L 为单位下三角阵,U 为上三角阵，其中U 矩阵的主对角线元素之积即为det A 。 由于A 的元素零元素较多，为节省储存量，将A 的元素存为6×501的数组中，程序中采用get_an_element()函数来从小数组中取出A 中的元素。 2.全部源程序 #include 《算法分析与设计》作业（一） 本课程作业由两部分组成。第一部分为“客观题部分”，由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 算法设计与分析 实 验 报 告 班级： 姓名： 学号： (备注：共给出5个参考实验案例，根据学号尾数做对应的实验，即如尾号为1，则模仿案例实验123；尾号2，则模仿案例实验234；尾号3，即345；尾号4，同1.) 目录 实验一分治与递归 (1) 1、基本递归算法 (1) 2、棋盘覆盖问题 (2) 3、二分搜索 (3) 4、实验小结 (5) 实验二动态规划算法 (5) 1、最长公共子序列问题 (5) 2、最大子段和问题 (7) 3、实验小结 (8) 实验三贪心算法 (8) 1、多机调度问题 (8) 2、用贪心算法求解最小生成树 (10) 3、实验小结 (12) 实验四回溯算法和分支限界法 (12) 1、符号三角形问题 (12) 2、0—1背包问题 (14) 3、实验小结 (18) 实验五多种排序算法效率比较 1、算法：起泡排序、选择排序、插入排序、shell排序，归并排序、快速排序等 (19) 2、实验小结 (18) P art1：课程设计过程 设计选题--→题目分析---→系统设计--→系统实现--→结果分析---→撰写报告 P art2：课程设计撰写的主要规范 1.题目分析：主要阐述学生对题目的分析结果，包括题目描述、 分析得出的有关模型、相关定义及假设； 2.总体设计：系统的基本组成部分，各部分所完成的功能及相互 关系； 3.数据结构设计：主要功能模块所需的数据结构，集中在逻辑设 计上； 4.算法设计：在数据结构基础上，完成算法设计； 5.物理实现：主要有数据结构的物理存储，算法的物理实现，系 统相关的实现。具体在重要结果的截图，测试案例的结果数据，核心算法的实现结果等； 6.结果分析：对第五步的分析，包括定性分析和定量分析，正确 性分析，功能结构分析，复杂性分析等； 7.结论：学生需对自己的课程设计进行总结，给出评价，并写出 设计体会； 8.附录：带有注释的源代码，系统使用说明等； 9.参考文献：列出在撰写过程中所需要用到的参考文献。 目录 1实验主题 (1) 2实验目的 (1) 3实验性质 (1) 4实验考核方法 (1) 5实验报告提交日期与方式 (1) 6实验平台 (1) 7实验内容和要求 (1) 8实验指导 (2) 8.2 开启Hadoop所有守护进程 (2) 8.2 搭建Eclipse环境编程实现Wordcount程序 (3) 1.安装Eclipse (3) 2.配置Hadoop-Eclipse-Plugin (3) 3.在Eclipse 中操作HDFS 中的文件 (7) 4.在Eclipse 中创建MapReduce 项目 (8) 5.通过Eclipse 运行MapReduce (13) 6.在Eclipse 中运行MapReduce 程序会遇到的问题 (16) 1实验主题 1、搭建Hadoop、Eclipse编程环境 2、在Eclipse中操作HDFS 3、在Eclipse中运行Wordcount程序 4、参照Wordcount程序，自己编程实现数据去重程序 2实验目的 （1）理解Hadoop、Eclipse编程流程； （2）理解MapReduce架构，以及分布式编程思想； 3实验性质 实验上机内容，必做，作为课堂平时成绩。 4实验考核方法 提交上机实验报告，纸质版。 要求实验报告内容结构清晰、图文并茂。 同学之间实验报告不得相互抄袭。 5实验报告提交日期与方式 要求提交打印版，4月19日（第10周）之前交到软件学院412。 6实验平台 操作系统：Linux Hadoop版本：2.6.0或以上版本 JDK版本：1.6或以上版本 Java IDE：Eclipse 7实验内容和要求 （1）搭建Hadoop、Eclipse编程环境； （2）运行实验指导上提供的Wordcount程序； （3）在Eclipse上面查看HDFS文件目录； （4）在Eclipse上面查看Wordcount程序运行结果； （5）熟悉Hadoop、Eclipse编程流程及思想； 程序设计题，编程实现基于Hadoop的数据去重程序，具体要求如下： 把data1文件和data2文件中相同的数据删除，并输出没有重复的数据，自己动手实现，把代码贴到实验报告的附录里。 设计思路： 数据去重实例的最终目标是让原始数据中出现次数超过一次的数据在输出文件中只出现一次。具体就是Reduce的输入应该以数据作为Key，而对value-list则没有要求。当Reduce 接收到一个 维吉尼亚算法分析及应用 一．实验目的 通过应用维吉尼亚算法对数据进行加解密的操作，了解维吉尼亚的加解密的机制，加深对维吉尼亚的算法理解 二．试验环境 安装Windows操作系统的PC机，具有C语言编译环境 三．试验原理 加密过程很简单，就是给定密码字母X和明文字母Y，密文字母是位于X行和Y列的那个字母。这样就决定了加密一天消息与消息一样长的密钥字符串，通常，迷药字符串事是密钥的重复。 使用查表的方式多加密几次就能很轻易的总结出规律：将A-Z以0-25编号，那么加密过程就是，在代换表的第一行中找到消息字母，如W，然后向后移D次（即3次），所得的字母就是密文了。如果数到末位，那么下一次移位就是从头（即A）继续也就是说，可以将A-Z看成一个环，加密过程就是找到消息字母后，将指针往环的某个特定方向移位，次数就是密钥字母所代表的数字，这其实是一个模26的过程。 扩展一下，以上加密仅能对26个字母进行加密，而且不能区分大小写，但其实英文中除了字母外，还有标点符号，还有空格。如果考虑到大部分英文字符，那个维吉尼亚代换表将比较大，而且有点浪费空间，如果能将被加密的字符有N个如果把这N个字符建成一个环，那么加密过程即使模N的过程，即C(I)=K(I)+P(I)modN，其中，K，C，P分别代表的是密钥空间，密文空间，消息（明文）空间。 四．主要代码 #include 《算法分析与设计》作业参考答案 作业一 一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。 二、简答题： 1.算法需要满足哪些性质？简述之。 答：算法是若干指令的有穷序列，满足性质： （1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。 （3）确定性：组成算法的每条指令清晰、无歧义。 （4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答：分析分治法能解决的问题主要具有如下特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 答：将递归算法转化为非递归算法的方法主要有： （1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j] 《计算机算法设计与分析》实验指导书（第一版） 前言 计算机算法分析与设计是面向设计的，它是计算机科学的核心。无论是计算机系统、系统软件和解决计算机的各种应用问题都可归结为算法的设计。通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的算法描述：分治法、贪心法、动态规划、回溯法、分枝限界等算法，并掌握算法分析的方法，从而把学生的分析问题和解决问题能力提高到理论的高度。 前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。 开发环境不限，本书采用C/C++语言的集成开发环境等。 实验完成后书写实验报告，包含实验问题、基本思想、关键算法流程图、测试数据及运行结果（截图）、调试心得和源程序。 总实验学时为16学时。 目录 预备实验验证算法的方法 (4) 实验目的： (4) 实验课时： (4) 实验原理： (4) 实验题目： (6) 基本题： (6) 提高题： (6) 实验一递归与分治 (7) 实验目的： (7) 实验课时： (7) 实验原理： (7) 实验题目： (7) 基本题： (7) 提高题： (8) 思考问题： (8) 实验二动态规划算法 (9) 实验目的： (9) 实验课时： (9) 实验原理： (9) 实验题目： (9) 基本题： (9) 提高题： (10) 思考问题： (10) 实验三贪心选择算法 (11) 实验目的： (11) 实验课时： (11) 实验原理： (11) 实验题目： (11) 基本题： (11) 提高题： (12) 思考问题： (12) 实验四回溯算法 (13) 实验目的： (13) 实验课时： (13) 实验原理： (13) 实验题目： (14) 基本题： (14) 提高题： (14) 思考问题： (14) 《大数据分析方法与应用》课程教学大纲 课程代码：090542008 课程英文名称：Big Data Analysis: Methods and Applications 课程总学时：40 讲课：40 实验：0 上机：0 适用专业：应用统计学 大纲编写（修订）时间：2017.6 一、大纲使用说明 （一）课程的地位及教学目标 本课程是应用统计学专业的一门专业课，通过本课程的学习，可以使学生学会选用适当的方法和技术分析数据，领会大数据分析方法和应用，掌握复杂数据的分析与建模，使学生能够按照实证研究的规范和数据挖掘的步骤进行大数据研发，为就业与继续深造打下必要而有用的基础。 （二）知识、能力及技能方面的基本要求 1.基本知识：掌握数据挖掘流程、随机森林树的回归算法、基于预测强度的聚类方法、朴素贝叶斯分类、高维回归及变量选择、图模型等。 2.基本能力：要求能在真实案例中应用相应的方法。 3.基本技能：掌握复杂数据的分析与建模。 （三）实施说明 1. 本大纲主要依据应用统计学专业2017版教学计划、应用统计学专业专业建设和特色发展规划和沈阳理工大学编写本科教学大纲的有关规定并根据我校实际情况进行编写的。 2. 课程学时总体分配表中的章节序号在授课过程中可酌情调整顺序，课时分配仅供参考。打“*”号的章节可删去或选学。 3. 建议本课程采用课堂讲授、讨论相结合的方法开展教学，通过讨论等方式强化重点，通过分散难点，使学生循序渐进的掌握难点。 4．教学手段：建议采用多媒体等现代化手段开展教学。 （四）对先修课的要求 本课程的先修课程：应用多元统计分析。 （五）对习题课、实践环节的要求 通过案例讲解算法，鼓励学生演示分析思路和分析收获，使学生有机会诊断问题，并学会选用适当的方法和技术分析数据。 （六）课程考核方式 1．考核方式：考查 2．考核目标：在考核学生基础知识、基本技能，基本能力的基础上，重点考核学生的分析能力、解决实际问题能力。 3．成绩构成：本课程由平时成绩和结课报告的质量评定优、良、中、及格和不及格。 （七）参考书目: 《大数据分析：方法与应用》，王星编，清华大学出版社，2013. 二、中文摘要 《大数据分析方法与应用》是高等学校应用统计学专业的一门选修的专业课。本课程着重介绍了统计学习、数据挖掘和模式识别等领域的各种大数据分析方法。课程主要内容包括大数据分析概述、数据挖掘流程、随机森林树、基于预测强度的聚类方法、贝叶斯分类和因果学习、高 《算法分析与设计》 学习中心： 专业： 学号： 姓名： 作业练习二 一、名词解释 1、MST性质 2、子问题的重叠性质 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。 二、简答题 1、简述动态规划算法求解的基本要素。 答：动态规划算法求解的基本要素包括： 1)最优子结构是问题能用动态规划算法求解的前提； 2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。 答：备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。 3、贪心算法求解的问题主要具有哪些性质简述之。 答：贪心算法求解的问题一般具有二个重要的性质： 一是贪心选择性质，这是贪心算法可行的第一个基本要素； 另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。 最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。 实验一、归并排序及各种排序算法性能比较 一、实验实习目的及要求 了解归并排序等各种排序算法，并能独立在计算机上实现，同时并能够计算它们的时间复杂度，并用计算机来验证。 二、实验实习设备（环境）及要求（软硬件条件） 计算机eclipse软件，执行环境JavaSE-1.8. 三、实验实习项目、内容与步骤(注意是主要关键步骤，适当文字+代码+截图说明) 项目：对10 4 6 3 8 2 5 7进行从小到大排序，采用几种排序方法，并统计这几种方法的运行时间，与归并排序比较。 内容及步骤： (1)归并排序：将序列每次分成两组，再进行合并，直到递归完成； 1、递归调用mergeSort对数组排序 2、merge将两个有序数组合并为一个有序数组 3、主函数调用mergeSort对数组排序 4、统计时间 (2) 选择排序：每次选择一个当前最小的并和当前的相对的第一个元素交换，直到最后 只有一个元素时结束；也可选择当前最大的并与当前的相对的最后一个 元素交换，直到最后只有一个元素时结束。 1、数组长度为n，需要选择n-1次；每次选择完成后，将数组中的最大值与最后一 个元素互换，调用java.util包中Arrays类。 2、主函数调用ChooseSort对数组排序。 3、统计运行时间。 (3)插入排序：从第二个元素开始，每次插入一个到当前有序序列中，使得有序，当 所有的元素插入完毕时，就排好序了； 1、从第二个元素开始，与之前序列比较，插入到合适的位置。 2、主函数调用sort对数组排序。 3、统计运行时间 (4) 快速排序：每次选择一个中间元素，并进行交换，使得中间元素的左边比它小，右 边比它大，然后对左右两边进行递归； 1、选取一个基准位，从右边向左边看，找比基准位小的元素，再从左边向右边看， 找比基准位大的元素，若两者均存在则交换；若两者相遇，则相遇元素与基准位元素交换，然后递归排序左右半数组。 数据分析处理需求分类 1 事务型处理 在我们实际生活中,事务型数据处理需求非常常见,例如：淘宝网站交易系统、1２306网站火车票交易系统、超市ＰOＳ系统等都属于事务型数据处理系统。这类系统数据处理特点包括以下几点: 一就是事务处理型操作都就是细粒度操作,每次事务处理涉及数据量都很小。 二就是计算相对简单，一般只有少数几步操作组成，比如修改某行得某列; 三就是事务型处理操作涉及数据得增、删、改、查,对事务完整性与数据一致性要求非常高。 四就是事务性操作都就是实时交互式操作,至少能在几秒内执行完成； 五就是基于以上特点,索引就是支撑事务型处理一个非常重要得技术. 在数据量与并发交易量不大情况下,一般依托单机版关系型数据库,例如OＲＡＣLＥ、MＹSQL、SQＬSERVER,再加数据复制（DataGurａd、RＭAＮ、ＭｙSQＬ数据复制等)等高可用措施即可满足业务需求。 在数据量与并发交易量增加情况下，一般可以采用ORＡLＣＥRAC集群方式或者就是通过硬件升级（采用小型机、大型机等，如银行系统、运营商计费系统、证卷系统)来支撑. 事务型操作在淘宝、1230６等互联网企业中,由于数据量大、访问并发量高，必然采用分布式技术来应对,这样就带来了分布式事务处理问题，而分布式事务处理很难做到高效，因此一般采用根据业务应用特点来开发专用得系统来解决本问题。 ２数据统计分析 数据统计主要就是被各类企业通过分析自己得销售记录等企业日常得运营数据,以辅助企业管理层来进行运营决策。典型得使用场景有:周报表、月报表等固定时间提供给领导得各类统计报表;市场营销部门,通过各种维度组合进行统计分析,以制定相应得营销策略等． 数据统计分析特点包括以下几点: 一就是数据统计一般涉及大量数据得聚合运算，每次统计涉及数据量会比较大。二就是数据统计分析计算相对复杂，例如会涉及大量goｕpbｙ、子查询、嵌套查询、窗口函数、聚合函数、排序等；有些复杂统计可能需要编写ＳQＬ脚本才能实现． 三就是数据统计分析实时性相对没有事务型操作要求高。但除固定报表外,目前越来越多得用户希望能做做到交互式实时统计； 传统得数据统计分析主要采用基于ＭＰP并行数据库得数据仓库技术.主要采用维度模型,通过预计算等方法，把数据整理成适合统计分析得结构来实现高性能得数据统计分析，以支持可以通过下钻与上卷操作,实现各种维度组合以及各种粒度得统计分析。 另外目前在数据统计分析领域,为了满足交互式统计分析需求，基于内存计算得数据库仓库系统也成为一个发展趋势,例如SAP得HANA平台。 3 数据挖掘 数据挖掘主要就是根据商业目标，采用数据挖掘算法自动从海量数据中发现隐含在海量数据中得规律与知识。 Ex.1(p20)若将y ← uniform(0, 1) 改为y ← x, 则上述的算法估计的值是什么？解：若将y ← uniform(0, 1) 改为y ← x，此时有，则k++，即，此时k++，由于此时x ← uniform(0, 1)，所以k/n=，则此时4k/n=2。所以上述算法估计的值为2。Ex.2(p23) 在机器上用估计π值，给出不同的n值及精度。解：由ppt上p21可知，的大小，其中k为落入圆内的数目，n为总数，且π=，即需要计算4k/n。我们先令x ← un iform(0, 1)，y ← uniform(0, 1)。计算 的值，如果小于等于1，那么此时k++。最后计算4k/n的值即可估计此时的π值。代码的主要部分为： 执行结果为： 结果分析：随着N的取值不断地增加，得到的π值也就越来越精确。 Ex.3(p23) 设a, b, c和d是实数，且a ≤ b, c ≤ d, f:[a, b] → [c, d]是一个连续函数，写一概率算法计算积分： 注意，函数的参数是a, b, c, d, n和f, 其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。 解：的值为y=，y=0，x=a，x=b围成的面积。根据之前的例子我们可以知道 = k(b-a)d/n。其中k是落在函数y=，x=a，x=b以及y=0所包围区间内的个数。代码的主要部分为： 运行结果为： 结果分析： 随着N的取值不断地增加，得到的积分值越来越精确。 Ex4(p24). 设ε,δ是(0,1)之间的常数，证明：若I是的正确值，h是由HitorMiss算法返回的值，则当n ≥ I(1-I)/ε2δ时有： Prob[|h-I| < ε] ≥ 1 –δ 上述的意义告诉我们：Prob[|h-I| ≥ ε] ≤δ, 即：当n ≥ I(1-I)/ ε2δ时，算法的计算结果的绝对误差超过ε的概率不超过δ，因此我们根据给定ε和δ可以确定算法迭代的次数 () 解此问题时可用切比雪夫不等式，将I看作是数学期望。 证明：由切比雪夫不等式可知： P( | X - E(X) | < ε ) ≥ 1 - D(X) / ε2 由题目知，E(X)=I。且根据题意，我们可知，在HotorMiss算法中，若随机选取n个点，其中k个点在积分范围内，则。且k的分布为二项分布B(n，I)（在积分范围内或者不在 积分范围内），则。又因为k=x*n，所以D(X)=I(1-I)/n。再将E(X)和D(X)带入切比雪夫不等式中即可得到 Ex5(p36). 用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。解：由题知，集合的大小，通过计算新生成的集合中元素的个数来估计原集合的大小，代码的主体部分如下： 昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：算法设计与分析开课实验室：年月日 一、上机目的及内容 1.上机内容 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2.上机目的 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）证明哈夫曼树满足最优子结构性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档。 数据结构与算法: typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 程序流程图： 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 程序代码： #include 算法分析与设计作业及参考答案样本
算法分析与设计实验报告
《计算机算法设计与分析》习题及答案
北航数值分析大作业第一题幂法与反幂法
最新算法分析与设计作业(一)及参考答案讲课讲稿
计算机算法设计与分析
大数据分析技术与应用_实验2指导
维吉尼亚算法分析及应用
《算法分析与设计》作业参考答案
《算法分析与设计》实验指导书
《大数据分析方法与应用》教学大纲
算法分析与设计(线下作业二)
算法分析与设计实验报告
大数据处理技术的总结与分析
算法设计与分析
算法分析与设计 实验二 哈夫曼编码