北航计算机研究生课程 算法设计与分析 Assignment_1

计算机学院计算机科学与技术（0812）博士研究生培养方案一、适用学科计算机科学与技术（0812）二、培养目标1．坚持党的基本路线，热爱祖国，遵纪守法，品行端正，诚实守信，身心健康，具有良好的科研道德和敬业精神。

2．在计算机科学与技术方面具有坚实宽广的理论基础和系统深入的专门知识，全面了解学科发展动向；具有独立从事科学研究的能力；具有良好的综合素质；能够独立地、创造性地从事科学研究工作，或具有主持较大型科研、技术开发项目，或解决经济、社会发展问题的能力；至少能熟练运用一门外国语撰写科技论文和进行国际学术交流。

3．在科学或专门技术上做出创造性的成果。

三、培养方向按计算机科学与技术一级学科统一招生，按计算机系统结构、计算机软件与理论、计算机应用技术、计算机网络与信息安全等培养博士研究生。

学科培养方向包括：1.计算机系统结构：具体研究方向包括高性能计算机体系结构、嵌入式与容错计算技术、网络体系结构、分布式计算机系统、计算机存储技术、并行计算技术、分布式计算技术、新概念计算技术等；2.计算机软件与理论：具体研究方向计算复杂性理论、计算系统建模理论、算法理论、智能计算理论、程序的形式化理论与编程模型、程序变换方法与技术、新型程序设计方法、可计算性理论、海量信息的理论与方法、软件中间件技术等；3.计算机应用技术：具体研究方向数据库应用技术、多媒体技术、数字图像及音视频处理、虚拟现实技术与系统、计算机视觉、模式识别、计算机仿真技术、嵌入式系统应用、物联网应用、云计算应用、服务计算、社会计算、大规模计算机应用工程化等；4.计算机网络与信息安全：具体研究方向计算机网络理论、网络传输技术、网络管理技术、网络计算技术、计算机网络应用技术、计算机安全技术、软件安全技术、网络安全技术、信息对抗技术、内容安全技术、行为安全技术、信息隐藏与检测以及可信计算技术等。

四、培养模式及学习年限本学科博士研究生主要按一级学科培养，鼓励开展国际联合培养，实行导师或联合导师负责制，负责制订研究生个人培养计划、指导科学研究和学位论文。

一：判断题1、一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。

（对）2、NP完全问题比其他所有NP问题都要难。

（错）3、回溯法用深度优先法或广度优先法搜索状态空间树。

（错，仅深度优先）4、在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。

（错）5、P类和NP类问题的关系用P⊂NP来表示是错误的。

（错）6、若近似算法A求解某极小化问题一实例的解为Sa，且已知该问题的最优解为Sa/3，则该近似算法的性能比为3。

（错）7、通常来说，算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。

（对）8、若P2多项式时间转化为(polynomial transforms to)P1，则P2至少与P1一样难。

（错）9、快速排序算法的平均时间复杂度是O(nlogn)，使用随机化快速排序算法可以将平均时间复杂度降得更低。

（错）10、基于比较的寻找数组A[1,…,n]中最大元素的问题下届是Ω(n/3)。

（错）11、O(f(n))+O(g(n))=O(min{f(n),g(n)})（错）12、若f(n)=Ω(g(n))，g(n)=Ω(h(n))，则f(n)=Ω(h(n))（对）13、若f(n)=O(g(n))，则g(n)=Ω(f(n))（对）14、贪婪技术所做的每一步选择所产生的部分解，不一定是可行性的。

（错）15、LasVegas算法只要给出解就是正确的。

（对）16、一个完全多项式近似方案是一个近似方案{Aε}，其中每一个算法Aε在输入实例I的规模的多项式时间内运行。

（错）二：简答1、二叉查找树属于减治策略的三个变种中的哪一个的应用？什么情况下二叉查找树表现出最差的效率？此时的查找和插入算法的复杂性如何？答：减治策略有3个主要的变种，包括减常量、减常数因子和减可变规模。

(1) 二叉查找树属于减可变规模变种的应用。

(2) 当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度等于n，此时二叉查找树表现出最差的效率，(3) 查找和插入算法的时间效率都属于Θ(n)。

一、解：设第k月的需求量为Nk(k=1,2,3,4)状态变量Xk：第k月初的库存量，X1=X5=0，0≤Xk≤Nk+…+N4决策变量Uk：第k月的生产量，max{0，Nk-Xk}≤Uk≤min{6，Nk+…+N4 - Xk}状态转移方程：X k+1 = Uk + Xk – Nk第k月的成本Vk = 0.5*(Xk - Nk) Uk=03 + Uk + 0.5*(Uk + Xk - Nk) Uk≠0设F k(Xk)是由第k月初的库存量Xk开始到第4月份结束这段时间的最优成本则F k(Xk) = min{Vk + F k+1(X k+1)} 1≤k≤4= min{ 3 + Uk + 0.5*(Uk + Xk - Nk) + F k+1(Uk + Xk - Nk) } Uk≠0min{ 0.5*(Xk - Nk) + F k+1(Xk - Nk) } Uk=0 F5(X5)=0四个月内的最优成本为F1(X1)=F1(0)详细计算步骤如下：（1）k=4时4（2）k=3时（3）k=2时（4）k=1时由以上计算可得，4个月的总最优成本为F1(0) = 20.5(千元)二、解：1、变量设定阶段k：已遍历过k个结点，k=1,2…6,7。

K=1表示刚从V1出发，k=7表示已回到起点V1状态变量Xk=(i，Sk)：已遍历k个结点，当前位于i结点，还未遍历的结点集合为Sk。

则X1=(1，{2,3,4,5,6})，X6=(i，Φ)，X7=(1，Φ)决策变量Uk=(i，j)：已遍历k个结点，当前位于i结点，下一个结点选择j。

状态转移方程：X k+1 = T(Xk，Uk) = (j，Sk-{j})第k阶段的指标函数Vk = D[i,j]。

最优指标函数Fk(Xk) = Fk(i，Sk)：已遍历k个结点，当前从i结点出发，访问Sk中的结点一次且仅一次，最后返回起点V1的最短距离。

则Fk(i，Sk) = min{ D[i,j] + F k+1(j，Sk-{j}) } 1≤k≤6F7(X7) = F7(1，Φ) = 02、分析：（1）k=6时，F6(i，Φ) = min{D[i,1] + F7(X7)} = D[i,1] i=2,3,4,5,63、伪代码和时间复杂度为方便计算，结点编号改为0到5.(1)用一张二维表格F[][]表示F(i,Sk)，行数是n，列数是2n-1。

数值分析大作业一、算法设计方案1、矩阵初始化矩阵[]501501⨯=ij a A 的下半带宽r=2,上半带宽s=2，设置矩阵[][]5011++s r C ，在矩阵C 中检索矩阵A 中的带内元素ij a 的方法是：j s j i ij c a ,1++-=。

这样所需要的存储单元数大大减少，从而极大提高了运算效率。

2、利用幂法求出5011λλ，幂法迭代格式：0111111nk k k k kk T k k k u R y u u Ay y u ηηβ------⎧∈⎪⎪=⎪=⎨⎪=⎪⎪=⎩非零向量 当1210/-≤-k k βββ时，迭代终止。

首先对于矩阵A 利用幂法迭代求出一个λ，然后求出矩阵B ，其中I A B λ-=(I 为单位矩阵），对矩阵B 进行幂法迭代，求出λ'，之后令λλλ+'=''，比较的大小与λλ''，大者为501λ，小者为1λ。

3、利用反幂法求出ik s λλ,反幂法迭代格式：0111111nk k k k kk T k k k u R y u Au y y u ηηβ------⎧∈⎪⎪=⎪=⎨⎪=⎪⎪=⎩非零向量 当1210/-≤-k k βββ时，迭代终止，1s k λβ=。

每迭代一次都要求解一次线性方程组1-=k k y Au ，求解过程为：（1）作分解LU A =对于n k ,...,2,1=执行[][]s k n r k k k i c c c c c n s k k k j c cc c k s ks k t k s k r i t t s t i k s k i k s k i js j t k s j r k t t s t k j s j k j s j k <+++=-=++=-=+++----=++-++-++-++----=++-++-++-∑∑);,min(,...,2,1/)(:),min(,...,1,:,1,11),,1max(,1,1,1,11),,1max(,1,1,1（2）求解y Ux b Ly ==,（数组b 先是存放原方程组右端向量，后来存放中间向量y))1,...,2,1(/)(:/:),...,3,2(:,1),min(1.1.11),1max(,1--=-===-=+++-++-+--=++-∑∑n n i c x c b x c b x n i b c b b i s t n s i i t t s t i i i ns n n ti r i t t s t i i i使用反幂法，直接可以求得矩阵按模最小的特征值s λ。

2006-2007学年第二学期《计算机算法设计与分析》试题院系：软件学院专业：软件工程年级：2004级一.简答题（共10分）略二.计算题(35分)1. (6 分)对下列各组函数f(n)和g(n),确定f(n)=O(g(n))或f(n)= Q(g(n))或f(n)=8 (g(n))。

(1)f(n)=3n, g(n)=2n2(2)f(n)=log n + 5, g(n)=log n(3)f(n)=log n, g(n尸J n咨：(1)f(n) = Q(g(n)) (2 分)(2)f(n) = 9(g(n)) (2 分)(3)f(n) = O(g(n)) (2 分)2. (8分)采用动态规划策略，计算a= {5,-37-4,-5,9,-2,10,-3,2}的最大子段和, 并给出这个最大子段和的起始下标和终止下标。

[设数组a中的元素下标从1开始。

]要求给出过程。

答：b[1]=5;b[2]=max{b[1]+a[2] , a[2]}=max{2,-3}=2b[3]=max{b[2]+a[3] , a[3]}=max{9,7}=9b[4]=max{b[3]+a[4] , a[4]}=max{5,-4}=5b[5]=max{b[4]+a[5] , a[5]}=max{0,-5}=0b[6]=max{b[5]+a[6] , a[6]}=max{9,9}=9b[7]=max{b[6]+a[7] , a[7]}=max{7,-2}=7b[8]=max{b[7]+a[8] , a[8]}=max{17,10}=17b[9]=max{b[8]+a[9] , a[9]}=max{14,-3}=14b[10]=max{b[9]+a[10] , a[10]}=max{16,2}=16(上述每两行1分，共5分)最大子段和为17 (1分)(若数组下标从1开始)起始下标：6 (1分)，终止下标：8 (1分)(若数组下标从0开始)起始下标：5 ( 0.5分)，终止下标：7 (0.5分)3 .（11分）设有3件工作分配给3个人，将工作i分配给第j个人所花的费用为C ij,现将为每一个人都分配1件不同的工作，并使总费用达到最小。

用分支定界算法求以下问题：某公司于乙城市的销售点急需一批成品，该公司成品生产基地在甲城市。

甲城市与乙城市之间共有n 座城市，互相以公路连通。

甲城市、乙城市以及其它各城市之间的公路连通情况及每段公路的长度由矩阵M1 给出。

每段公路均由地方政府收取不同额度的养路费等费用，具体数额由矩阵M2 给出。

请给出在需付养路费总额不超过1500 的情况下，该公司货车运送其产品从甲城市到乙城市的最短运送路线。

具体数据参见文件：m1.txt: 各城市之间的公路连通情况及每段公路的长度矩阵(有向图); 甲城市为城市Num.1，乙城市为城市Num.50。

m2.txt: 每段公路收取的费用矩阵（非对称）。

思想：利用Floyd算法的基本方法求解。

程序实现流程说明：1.将m1.txt和m2.txt的数据读入两个50×50的数组。

2.用Floyd算法求出所有点对之间的最短路径长度和最小费用。

3.建立一个堆栈，初始化该堆栈。

4.取出栈顶的结点，检查它的相邻的所有结点，确定下一个当前最优路径上的结点，被扩展的结点依次加入堆栈中。

在检查的过程中，如果发现超出最短路径长度或者最小费用，则进行”剪枝”，然后回溯。

5.找到一个解后，保存改解，然后重复步骤4。

6.重复步骤4、5，直到堆栈为空，当前保存的解即为最优解。

时间复杂度分析：Floyd算法的时间复杂度为3O N，N为所有城市的个数。

()该算法的时间复杂度等于DFS的时间复杂度，即O(N+E)。

其中，E为所有城市构成的有向连通图的边的总数。

但是因为采用了剪枝，会使实际运行情况的比较次数远小于E。

求解结果：算法所得结果:甲乙之间最短路线长度是:464最短路线收取的费用是:1448最短路径是:1 3 8 11 15 21 23 26 32 37 39 45 47 50C源代码（注意把m1.txt与m2.txt放到与源代码相同的目录下，下面代码可直接复制运行）：#include<stdlib.h>#include<stdio.h>#include<time.h>#include<string.h>#define N 50#define MAX 52void input(int a[N][N],int b[N][N]);void Floyd(int d[N][N]);void fenzhi(int m1[N][N],int m2[N][N],int mindist[N][N],int mincost[N][N]);int visited[N],bestPath[N];void main(){clock_t start,finish;double duration;int i,j,mindist[N][N],mincost[N][N],m1[N][N],m2[N][N]; /* m1[N][N]和m2[N][N]分别代表题目所给的距离矩阵和代价矩阵*/// int visited[N],bestPath[N];FILE *fp,*fw;// system("cls");time_t ttime;time(&ttime);printf("%s",ctime(&ttime));start=clock();for(i=0;i<N;i++){visited[i]=0;bestPath[i]=0;}fp=fopen("m1.txt","r"); /* 把文件中的距离矩阵m1读入数组mindist[N][N] */if(fp==NULL){printf("can not open file\n");return;}for(i=0;i<N;i++)for(j=0;j<N;j++)fscanf(fp,"%d",&mindist[i][j]);fclose(fp); /* 距离矩阵m1读入完毕*/fp=fopen("m2.txt","r"); /* 把文件中的代价矩阵m2读入数组mincost[N][N] */if(fp==NULL){printf("can not open file\n");return;}for(i=0;i<N;i++)for(j=0;j<N;j++)fscanf(fp,"%d",&mincost[i][j]);fclose(fp); /* 代价矩阵m2读入完毕*/input(m1,mindist); /* mindist[N][N]赋值给m1[N][N]，m1[N][N]代表题目中的距离矩阵*/input(m2,mincost); /* mincost[N][N]赋值给m2[N][N]，m2[N][N]代表题目中的代价矩阵*/for(i=0;i<N;i++) /* 把矩阵mindist[i][i]和mincost[i][i]的对角元素分别初始化，表明城市到自身不连通，代价为0 */{mindist[i][i]=9999;mincost[i][i]=0;}Floyd(mindist); /* 用弗洛伊德算法求任意两城市之间的最短距离，结果存储在数组mindist[N][N]中*//*fw=fopen("1.txt","w");for(i=0;i<N;i++){for(j=0;j<N;j++)fprintf(fw,"%4d ",mindist[i][j]);fprintf(fw,"\n");}fclose(fw);// getchar();//*/Floyd(mincost); /* 用弗洛伊德算法求任意两城市之间的最小代价，结果存储在数组mincost[N][N]中*//*fw=fopen("2.txt","w");for(i=0;i<N;i++){for(j=0;j<N;j++)fprintf(fw,"%4d ",mincost[i][j]);fprintf(fw,"\n");}fclose(fw);// getchar();//*/fenzhi(m1,m2,mindist,mincost); /* 调用分支定界的实现函数，寻找出所有的可行路径并依次输出*/finish=clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;printf( "%f seconds\n", duration );//*/}void Floyd(int d[N][N]) /* 弗洛伊德算法的实现函数*/{int v,w,u,i;for(u=0;u<N;u++){for(v=0;v<N;v++){for(w=0;w<N;w++)if(d[v][u]+d[u][w]<d[v][w]){//printf("v,w,u,d[v][u],d[u][w],d[v][w] %d %d %d %d %d %d",v+1,w+1,u+1,d[v][u],d[u][w],d[v][ w]);getchar();d[v][w]=d[v][u]+d[u][w];}}}}void input(int a[N][N],int b[N][N]) /* 把矩阵b赋值给矩阵a */{int i,j;for(i=0;i<N;i++)for(j=0;j<N;j++)a[i][j]=b[i][j];}void fenzhi(int m1[N][N],int m2[N][N],int mindist[N][N],int mincost[N][N]){int stack[MAX],depth=0,next,i,j; /* 定义栈，depth表示栈顶指针；next指向每次遍历时当前所处城市的上一个已经遍历的城市*/int bestLength,shortestDist,minimumCost,distBound=9999,costBound=9999;int cur,currentDist=0,currentCost=0; /* cur指向当前所处城市，currentDist和currentCost分别表示从甲城市到当前所处城市的最短距离和最小代价，currentDist和currentCost初值为0表示从甲城市出发开始深度优先搜索*/stack[depth]=0; /* 对栈进行初始化*/stack[depth+1]=0;visited[0]=1; /* visited[0]=1用来标识从甲城市开始出发进行遍历，甲城市已被访问*/while(depth>=0) /* 表示遍历开始和结束条件，开始时从甲城市出发，栈空，depth=0；结束时遍历完毕，所有节点均被出栈，故栈也为空，depth=0 *//* 整个while（）循环体用来实现从当前的城市中寻找一个邻近的城市*/{cur=stack[depth]; /* 取栈顶节点赋值给cur，表示当前访问到第cur号城市*/ next=stack[depth+1]; /* next指向当前所处城市的上一个已经遍历的城市*/for(i=next+1;i<N;i++) /* 试探当前所处城市的每一个相邻城市*/{if((currentCost+mincost[cur][N-1]>costBound)||(currentDist+mindist[cur][N-1]>=distBound)){ /* 所试探的城市满足剪枝条件，进行剪枝*///printf("here1 %d %d %d %d %d %d %d\n",cur,currentCost,mincost[cur][49],costBound,curre ntDist,mindist[cur][49],distBound); getchar();//printf("%d %d %d %d %d %d",cur,i,m1[cur][i],currentCost,mincost[cur][49],costBound); getchar();continue;}if(m1[cur][i]==9999) continue; /* 所试探的城市不连通*/if(visited[i]==1) continue; /* 所试探的城市已被访问*/if(i<N) break; /* 所试探的城市满足访问条件，找到新的可行城市，终止for循环*/ }if(i==N) /* 判断for循环是否是由于搜索完所有城市而终止的，如果是（i==N），进行回溯*/{// printf("here");getchar();depth--;currentDist-=m1[stack[depth]][stack[depth+1]];currentCost-=m2[stack[depth]][stack[depth+1]];visited[stack[depth+1]]=0;}else /* i!=N,表示for循环的终止是由于寻找到了当前城市的一个可行的邻近城市*/{//printf("%d %d %d %d %d %d\n",cur,i,m1[stack[depth]][i],m2[stack[depth]][i],currentCost,curre ntDist);//getchar();currentDist+=m1[stack[depth]][i]; /* 把从当前所处城市到所找到的可行城市的距离加入currentDist */currentCost+=m2[stack[depth]][i]; /* 把从当前所处城市到所找到的可行城市的代价加入currentCost */depth++; /* 所找到的可行城市进栈*/stack[depth]=i; /* 更新栈顶指针，指向所找到的可行城市*/stack[depth+1]=0;visited[i]=1; /* 修改所找到的城市的访问标志*/if(i==N-1) /* i==N-1表示访问到了乙城市，完成了所有城市的一次搜索，找到一条通路*/{// printf("here\n");for(j=0;j<=depth;j++) /* 保存当前找到的通路所经过的所有节点*/ bestPath[j]=stack[j];bestLength=depth; /* 保存当前找到的通路所经过的所有节点的节点数*/shortestDist=currentDist; /* 保存当前找到的通路的距离之和*/minimumCost=currentCost; /* 保存当前找到的通路的代价之和*///costBound=currentCost;distBound=currentDist; /* 更新剪枝的路径边界，如果以后所找到的通路路径之和大于目前通路的路径之和，就剪枝*/if(minimumCost>1500) continue; /* 如果当前找到的通路的代价之和大于1500，则放弃这条通路*/printf("最短路径:%3d,路径代价:%3d,所经历的节点数目:%3d,所经历的节点如下:\n",shortestDist,minimumCost,bestLength+1); /* 输出找到的通路的结果*/bestPath[bestLength]=49;for(i=0;i<=bestLength;i++) /* 输出所找到的通路所经过的具体的节点*/ printf("%3d ",bestPath[i]+1);(完整word版)北航研究生算法设计与分析Assignment_2 printf("\n");depth--; /* 连续弹出栈顶的两个值，进行回溯，开始寻找新的可行的通路*/currentDist-=m1[stack[depth]][stack[depth+1]];currentCost-=m2[stack[depth]][stack[depth+1]];visited[stack[depth+1]]=0;depth--;currentDist-=m1[stack[depth]][stack[depth+1]];currentCost-=m2[stack[depth]][stack[depth+1]];visited[stack[depth+1]]=0;// getchar();}}}}。

算法设计与分析_北京航空航天大学中国大学mooc课后章节答案期末考试题库2023年1.对如下所示连通无向图【图片】，其最小生成树的权重为【图片】参考答案:232.对如下所示有向图，从【图片】点开始进行深度优先搜索（DFS），搜索时按照字典序遍历某一节点的相邻节点。

在得到的深度优先搜索树中，包含如下哪些类别的边（多选）【图片】参考答案:树边_前向边_后向边_横向边3.在0-1背包问题中，若背包容量为20,5个物品的体积分别为【图片】，价格分别为【图片】。

则该背包能容纳物品的最大总价格为____参考答案:254.设计动态规划算法的一般步骤为____参考答案:问题结构分析→递推关系建立→自底向上计算→最优方案追踪5.给定两个序列分别为“algorithm”和“glorhythm”。

则以下分别为两序列的最长公共子序列和最长公共子串的选项是____参考答案:gorthm thm6.在最长公共子串问题的递推式中，【图片】表示____参考答案:和中以和结尾的最长公共子串的长度7.在支持插入、删除、替换三种操作的最小编辑距离问题中，用【图片】数组来记录编辑方案。

则【图片】数组中的"L","U","LU"分别代表哪种操作___参考答案:插入删除替换/空操作8.字符串“algorithm”到字符串“altruistic”的最小编辑距离为___参考答案:69.数组【图片】中的逆序对个数为____参考答案:510.在上题中，均不在搜索树中的边有哪些____（多选）参考答案:_11.在扇形图(Fan Graph)【图片】中，其邻接表和结构如下第一张图所示。

从顶点【图片】开始进行广度优先搜索（BFS），搜索时按照邻接表顺序遍历某一节点的相邻节点。

得到搜索树如下第二张图，该搜索树并未画全，应从虚线中选择____补全。

（多选）【图片】【图片】参考答案:①_②12.同上题，在扇形图(Fan Graph)【图片】中，其邻接表和结构如下图所示。

研究生计算机科学教案：算法分析与设计1. 导言本教案旨在提供给研究生计算机科学专业的学生一门关于算法分析与设计的课程。

在计算机科学领域中，算法是解决问题的有效方法和步骤。

通过本课程的学习，学生将能够深入了解常见的算法分析技术和设计策略，并掌握如何选择合适的数据结构来实现高效的算法。

此外，本课程还将涵盖一些经典问题和相应的解决方案，以及在实际应用中如何应用这些经典算法。

2. 学习目标•理解基本的算法概念和术语•掌握常见的算法分析技术，如时间复杂度、空间复杂度等•熟练掌握常见的排序和搜索算法•理解动态规划、贪心算法、回溯等设计策略•学会通过递归构建和分析复杂的数据结构和算法•能够应用所学知识解决实际问题3. 教学内容安排第一周：导论及基本概念•算法概述和定义•算法分析的基本概念：时间复杂度和空间复杂度•渐进符号表示法第二周：排序算法•冒泡排序、插入排序、选择排序•快速排序、归并排序、堆排序•排序算法的比较和选择第三周：搜索算法•顺序搜索与二分搜索•深度优先搜索（DFS）和广度优先搜索（BFS）•A*搜索算法第四周：动态规划•基本概念和原理•背包问题和最长公共子序列问题•动态规划解决方案的设计与实现第五周：贪心算法•基本概念和原理•最小生成树问题和背包问题的贪心算法解决方案第六周：回溯算法•基本概念和原理•八皇后问题及其回溯解决方案•迷宫求解问题及其回溯解决方案第七周：递归算法与数据结构•递归思想与应用场景•递归构建和操作链表、二叉树等数据结构•分治策略及其应用第八周：经典算法问题•0/1背包问题•旅行商问题•最短路径问题4. 教学方法与评估方式本课程将采用理论讲授与实践结合的教学方法。

理论讲授部分将以教师演讲、示例分析和交互式讨论等方式进行。

实践部分将通过编程练习、算法案例分析等形式进行，学生需要在课后完成相关的作业和项目，并提交实验报告。

评估方式将包括课堂参与度、作业成绩、项目成果以及期末考试。

5. 参考资料•Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009)."Introduction to Algorithms." MIT Press.•Dasgupta, S., Papadimitriou, C.H., and Vazirani, U.V. (2008)."Algorithms." McGraw-Hill Education.以上是本课程《研究生计算机科学教案：算法分析与设计》的大纲内容。

北航计算机考研教材
北航计算机考研教材主要包括以下内容：
1. 《计算机网络》：介绍计算机网络基本概念、通信原理、网络协议、网络安全等内容。

2. 《操作系统》：涵盖操作系统的原理、进程与线程管理、存储管理、文件系统、设备管理等主题。

3. 《数据结构与算法分析》：讲解数据结构基本概念、线性表、树、图等数据结构以及基本的算法分析方法。

4. 《数据库系统原理》：介绍数据库系统的基本概念、数据库设计、关系数据模型、SQL语言等。

5. 《计算机组成原理》：涵盖计算机体系结构、指令系统、指令执行过程、存储器层次结构、I/O系统等内容。

6. 《软件工程》：讲解软件开发过程、需求分析与设计、软件测试、软件维护等软件工程的基本理论和方法。

此外，还可以参考一些经典的考研教材，如《计算机科学与技术考研指南》、《计算机考研数学》、《计算机考研英语》等。

请注意，以上仅为参考教材，具体以北航计算机硕士考研招生要求和考试大纲为准。

一、请安排投资计划，使总的利润最大。

写出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步 骤及结果。

解：设k 表示前k 个项目；状态变量为k x ，表示能投资到前k 个项目中的金额为k x ；决策变量为}0|{ , k k k k k k x u u D D u ≤≤=∈，表示将k u 的金额投入到第k 个项目中；状态转移方程为k k k u x x +=+1，表示能投资到前k+1个项目的金额等于能投资到前k 个项目的金额，加上投资到第k+1个项目的金额；指标函数为)(P k k x ，表示将k x 投入到前k 个项目中所能获得的最大利润；设)(A k k x 为向第k 个项目投资k x 金额所能获得的利润。

则递推关系式为：⎪⎩⎪⎨⎧+-====-∈)}(A )({P max )(P 00 , 0)(P 1k k k k k D u kk k k k u u x x x k x k k 或① 当k=0或0=k x 时，总利润一定为0③ 当k=2时，8万元只投资第一、第二个项目，有若将0万投资第一个项目，8万投资第二个项目，利润为0+75=75若将1万投资第一个项目，7万投资第二个项目，利润为5+74=79 若将2万投资第一个项目，6万投资第二个项目，利润为15+73=88 若将3万投资第一个项目，5万投资第二个项目，利润为40+70=110 若将4万投资第一个项目，4万投资第二个项目，利润为80+60=140 若将5万投资第一个项目，3万投资第二个项目，利润为90+40=130 若将6万投资第一个项目，2万投资第二个项目，利润为95+15=110 若将7万投资第一个项目，1万投资第二个项目，利润为98+5=103 若将8万投资第一个项目，0万投资第二个项目，利润为100+0=100此时将4万元投资第一个项目，将剩余4万元投资第二个项目可获得最大利润140万元 同时计算出将2x 万元投资到前两个项目的获利情况如下表：④ 当k=3时，8万元同时投资第一、第二、第三个项目，有 若将0万投资前两个项目，8万投资第三个项目，利润为0+53=53若将1万投资前两个项目，7万投资第三个项目，利润为5+52=57若将2万投资前两个项目，6万投资第三个项目，利润为15+51=66若将3万投资前两个项目，5万投资第三个项目，利润为40+50=90若将4万投资前两个项目，4万投资第三个项目，利润为80+45=125若将5万投资前两个项目，3万投资第三个项目，利润为90+40=130若将6万投资前两个项目，2万投资第三个项目，利润为95+26=121若将7万投资前两个项目，1万投资第三个项目，利润为120+4=124若将8万投资前两个项目，0万投资第三个项目，利润为140+0=140此时将4万元投资第一个项目，将剩余4万元投资第二个项目，第三个项目投资0元，可获得最大利润140万元。