算法导论复习资料

算法导论复习资料

一、选择题：第一章的概念、术语。

二、考点分析：

1、复杂度的渐进表示，复杂度分析。

2、正确性证明。

考点：1）正确性分析（冒泡，归并，选择）；2）复杂度分析（渐进表示O，Ｑ，?，替换法证明，先猜想，然后给出递归方程）。

循环不变性的三个性质：

1）初始化：它在循环的第一轮迭代开始之前，应该是正确的；

2）保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确；

3）当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。

插入排序算法：

INSERTION-SORT(A)

1 for j ←

2 to length[A]

2 do key ←A[j]

3 ?Insert A[j] into the sorted sequence A[1，j - 1].

4 i ←j - 1

5 while i > 0 and A[i] > key

6 do A[i + 1] ←A[i]

7 i ←i - 1

8 A[i + 1] ←key

插入排序的正确性证明：课本11页。

归并排序算法：课本17页及19页。

归并排序的正确性分析：课本20页。

3、分治法（基本步骤，复杂度分析）。——许多问题都可以递归求解

考点：快速排序，归并排序，渐进排序，例如：12球里面有一个坏球，怎样用最少的次数找出来。（解：共有24种状态，至少称重3次可以找出不同的球）

不是考点：线性时间选择，最接近点对，斯特拉算法求解。

解：基本步骤：

一、分解：将原问题分解成一系列的子问题；

二、解决：递归地解各子问题。若子问题足够小，则直接求解；

三、合并：将子问题的结果合并成原问题的解。

复杂度分析：分分治算法中的递归式是基于基本模式中的三个步骤的，T(n)为一个规模为n的运行时间，得到递归式

T(n)=Q(1) n<=c

T(n)=aT(n/b)+D(n)+C(n) n>c

附加习题：请给出一个运行时间为Q(nlgn)的算法，使之能在给定的一个由n个整数构成的集合S 和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。

4、动态规划（最优子结构性质，自底向上填表计算最优解值（即最长公共子序列），导出最优解）。

考点：最优子结构性质，自底向上填表计算最优解值，导出最优解。

a）动态规划算法设计的4个步骤：1）描述最优解的结构；2）递归定义最优解的值；3）按自底向上的方式计算最优解的值；4）由计算出的结果构造一个最优解。

b）最优子结构遵循的共同模式：1）问题的一个解可以是做一个选择，做这种选择可能会

得到一个或多个有待解决的子问题；2）假设对一个给定的问题，已知的是一个可以导致最优解的选择，不必关心如何确定这个选择，尽管假定它是已知的；3）在已知这个选择后，要确定哪些子问题会随之发生，以及如何最好地描述所得到的子问题的空间；4）利用一种―剪切粘贴法‖，来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的。备注：A problem exhibits

optimal substructure if an optimal solution to the problem contains within it optimal solutions to

subproblems.

Whenever a problem exhibits optimal substucture it is a good clue that dynamic programming might apply.

c ）最长公共子序列的算法：这里以两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}为输入，注意课本211页的自底向上填表方法。

LCS-LENGTH(X, Y) 注：此程序运行时间为O （mn ），每个表项的计算时间为O （1） 1 m ← length[X]

2 n ← length[Y]

3 for i ← 1 to m

4 do c[i, 0] ← 0

5 for j ← 0 to n

6 do c[0, j] ← 0

7 for i ← 1 to m

8 do for j ← 1 to n

9

do if xi = yj 10

then c[i, j] ← c[i - 1, j - 1] + 1 11

b[i, j] ← ―=" 12

else if c[i - 1, j] ≥ c[i, j - 1] 13 then c[i, j] ← c[i - 1, j]

14 b[i, j] ← "↑"

15 else c[i, j] ← c[i, j - 1]

16 b[i, j] ← " ← "

17 return c and b

PRINT-LCS(b, X, i, j) 注：此程序运行时间为O （m+n ）

1 if i = 0 or j = 0

2 then return

3 if b[i, j] = "="

4 then PRINT-LCS(b, X, i - 1, j - 1)

5 print xi

6 elseif b[i, j] = "↑"

7 then PRINT-LCS(b, X, i - 1, j)

8 else PRINT-LCS(b, X, i, j - 1)

d ）矩阵链乘法的算法：参照课本上的矩阵链表得出矩阵相乘的最小算法。

}

],1[],[{min ],[1j k i j

k i p p p j k m k i m j i m -<≤+++=

MATRIX-CHAIN-ORDER(p) 每个表项的复杂度是O （n ），共有O （n^2）表项，则为O （n^3） 1 n ← length[p] - 1

2 for i ← 1 to n

3 do m[i, i] ← 0

4 for l ← 2 to n ?l is the chain length.

5 do for i ← 1 to n - l + 1

6 do j ← i + l - 1

7 m[i, j] ← ≦

8 for k ← i to j - 1

9

do q ← m[i, k] + m[k + 1, j] + pi-1 pkpj 10 if q < m[i, j]

11 then m[i, j] ← q

12 s[i, j] ← k

13 return m and s

PRINT-OPTIMAL-PARENS(s, i, j)

1 if i = j

2 then print "Ai "

3 else print "("

4 PRINT-OPTIMAL-PARENS(s, i, s[i, j])

5 PRINT-OPTIMAL-PARENS(s, s[i, j] + 1, j)

6 print ")"

e ）备忘录算法：1）程序结构采用自顶向上；2）保留了递归结构，开销较大；3）当所有的子问题都需要求解时，自底向上的方法效率较高，否则可以采用备忘录方法。

备忘录算法的代码可以参照课本207页。

f ）最优二叉查找树：1）一棵最优二叉查找树不一定是一棵整体高度最小的树，也不一定总是把有最大概率的关键字放在根部来构造一棵最优二叉查找树。

5、贪心法（最优子结构性质+贪心选择性质）。

考点：学会证明最优子结构性质和贪心选择性质的问题。

a ）活动选择问题：

?????≠++==<<φφij j

k i ij S if j k c k i c S if j i c }1],[],[{ 0],[max

注意课本上224页地贪婪法定理证明，这就是贪婪法的合理性证明。

RECURSIVE-ACTIVITY-SELECTOR(s, f, i, j)

1 m ← i + 1

2 while m < j and sm < fi ? Find the first activity in Sij.

3 do m ← m + 1

4 if m < j

5 then return {am} ∪RECURSIVE-ACTIVITY-SELECTOR(s, f, m, j)

6 else return

GREEDY-ACTIVITY-SELECTOR(s, f)

1 n ←length[s]

2 A ←{a1}

3 i ←1 2

4 for m ←2 to n

5 do if sm ≥fi

6 then A ←A ∪{am}

7 i ←m

8 return A

b）贪心算法遵循的步骤：1）决定问题的最优子结构；2）设计出一个递归解；3）证明在递归的任一阶段，最优选择之一总是贪心选择，那么，做贪心选择总是安全的；4）证明通过做贪心选择，所有的子问题（出一个以外）都为空；5）设计出一个实现贪心策略的递归算法；6）将递归算法转换成迭代算法。

c）根据贪心选择来构造最优子结构：1）将优化问题转化成这样一个问题，即先做出选择，再解决剩下的一个子问题；2）证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择的安全；3）说明在做贪心选择后，剩余的子问题具有这样的一个性质，即如果将子问题的最优解和我们所作的贪心选择联合起来，可以得出原问题的一个最优解。

d）贪心选择性质：证明定理16.1

e）最优子结构性质：课本229页。

6、搜索（回溯法、剪枝函数、最小成本优先）。

考点：回溯，剪枝函数，最小成本优先的问题；分支界限法，剪枝函数所具备的性质。

a）回溯法：

1）定义：回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为―回溯点‖。

2）回溯法解题的步骤：

a、针对所给的问题，定义问题的解空间；

b、确定易于搜索的解空间结构；

c、以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

2）回溯法解决的n后问题：在一个n * n的棋盘上放臵n个王后，使得n后彼此不受攻击。

3）回溯法解决0-1背包问题：

附：证明部分背包问题具有贪心选择性质。

课本练习题16.2-3：

c

剪枝函数：约束函数：剪去不满足约束函数的子树； 限界函数：剪去由限界函数表明不能得到最优解的子树。

n k x x x P x x x P k k <

,...,,(),...,,(21121

剪枝函数的必要条件：

典型例题：1）求不等式的整数解 5x 1+4x 2-x 3<=10, 1<=x j <=3, i =1,2,3

2）装载问题：

c）最小成本优先算法：

注：分支——限界的基本思想：

1回溯法的深度优先比较盲目

2广度优先代价太高

4能优先搜索那些最有希望得到解的路径

6深入分析问题，得到有用的启发信息

7利用启发信息构造成本函数

8最小成本优先的搜索策略

9结合剪枝函数

典型题型：重拍九宫问题。

7、最大流（概念，最大流-最小割定理，Edmonds-Karp算法）。

考点：最大流的相关概念，最大流——最小割定理，Edmonds-Karp算法，要求掌握Ford-Fulkerson 算法的相关内容。

1）流网络定义：有向图G = (V, E)，如果图G满足：

–存在源结点(source) s（s的入度为0）

–存在汇结点(sink) t（t的出度为0）

–任意结点v∈V，有s ~ v ~ t

–容量函数C：E →R+

称G为流网络。

流的定义：流网络G，若函数p：V X V→R+满足下述条件：

–容量限制：对任意(u,v) ∈E，有0<=p(u,v)<=c(u,v)

–守恒条件：对任意u ∈(V-{s,t})，有

则称p为G上的流。

注意课本399页的引理。

2）对源点顶点来说，离开它的正流要比进入它的正流更多；对汇点顶点来说，进入它的正流要比离开它的正流更多。

先证明如下：|f|=f（s，V）

=f（V，V）-f（V-s，V）

=f（V，V-s）

=f（V，t）+f（V，V-s-t）

=f（V，t）

3）Ford-Fulkerson方法：此方法依赖三中重要思想，a、残留网络；b、增广路径；c、割。这些是最大流最小割定理的精髓。（Ford-Fulkerson方法沿增广路径反复增加流，知道找出最大流为止；而最大流最小割定理告诉我们：一个流是最大流，当且仅当它的残留网络不包含增广路径。）

一、残留网络：在不超过容量c（u，v）的条件下，从u到v之间可以压入的额外网络流量，就是（u，v）残留容量，定义为c f（u，v）=c（u，v）-f（u，v）。注意课本401页的残留网络的例子。

残留网络G f本身也是一个流网络，其容量由c f给出，且|E f|<=2|E|。注意课本402页的引理

26.2。

二、增广路径：注意课本403页引理26.3和引理26.4。

三、流网络的割：注意403页的几个引理。

四、最大流最小割定理：几个相互等价的条件。

FORD-FULKERSON(G, s, t)

1 for each edge (u, v) ∈E[G]

2 do f[u, v] ←0

3 f[v, u] ←0

4 while there exists a path p from s to t in the residual network G f

5 do cf(p) ←min {cf(u, v) : (u, v) is in p}

6 for each edge (u, v) in p

7 do f[u, v] ←f[u, v] + cf(p)

8 f[v, u] ←-f[u, v]

FORD-FULKERSON的复杂性：FORD-FULKERSON过程的运行时间取决于如何决定第四行中的增广路径，选择不好，算法可能不会终止。假设容量是整数

?1~3行O(|E|)

?4~8循环执行O(|f*|)

?找增广路O(|E|)

?O(|E||f*|)

FORD-FULKERSON算法有其缺点，可以参照课本406页。

4）Edmonds-Karp算法：如果在第四行中用广度优先搜索来实现对增光路径p的计算。即如果增光路径是残留网络中从s到t的最短路径（其中每条边为单位距离，或权），则能够改进FORD-FULKERSON算法的界；称FORD-FULKERSON方法的这种实现为Edmonds-Karp算法。Edmonds-Karp算法的运行时间为O（V*E2）

注意课本407页关于Edmonds-Karp算法的一些证明。

8、NP完全问题（多项式时间规约）。

考点：多项式时间内的规约问题，掌握NP 完全问题的证明方法。

P类问题：是在多项式时间内可解的问题，即都是在O（n k）时间内求解的问题，此处k为某个常数，n是问题的输入规模。

NP类问题：是在多项式时间内?可验证?的问题即能够在问题输入规模的多项式时间内，验证该问题是正确的。

注意：P问题包含于NP问题。但P不一定是NP问题的真子集。

NPC问题：NP完全问题，即任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就成为NPC问题。换言之，如果这个问题解决了，那么所有的NP问题也都能解决了。若问题L满足

–L ∈NP, and

–L′≤P L for every L ′∈NP.

则问题L是NPC的，若L只满足条件2则称问题是NP-hard的。

注意：如果任何NP完全问题可以在多项式时间内解决，则NP中所有问题都有一个多项式时间的算法。

1）多项式时间内的规约：

–若问题2可以被多项式时间求解，则问题1也可被多项式时间求解；

–若问题1不能被多项式时间求解，则问题2也不能多项式时间求解；

–problem1 ≤p problem2表明：问题1的求解不?难?于问题2。

假定一个判定问题A和另外一个不同的判定问题B，在一个过程中，它能将A的任何势力a转换为B的、具有以下特征的势力b：

a、转化操作需要多项式时间；

b、两个实例的答案是相同的，即a的答案是?是?，当且仅当b的答案也是?是?，

称这样的过程为多项式时间的规约算法。可以参照课本599页的图。

a、给定问题A的一个实例a，利用多项式时间规约算法，将它转换为问题B的一个实例b。

b、在实例b上，运行B的多项式时间判定算法。

c、将b的答案用作a的答案。

可以将对问题A的求解?规约?为对问题B的求解。

注意：第一个NP完全问题就是电路可满足性问题。

2）NP完全性与可归约性：

课本609页引理34.3

3）电路可满足性问题：

引理：电路可满足性问题属于NP类、NP难度及NP完全的。

例题解析：

1、设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。（EX：有一个数字串：312，当N=3，K=1时会有以下两种分法：3*12=36、31*2=62，这时，符合题目要求的结果是：31*2=62。）

2、Olay教授是一家石油公司的顾问，这家公司正在计划建造一条由东向西的大型管道，它穿过一个有n口油井的油田。从每口井中都有一条喷油管道沿最短路径与主管道直接连接（或南或北）。给定各口井的x坐标和y坐标，应如何选择主管道的最优位置（使得各喷管长度总和最小）？证明最优位置可在线性时间内确定。

3、NPC证明：如集合的等划分问题，TSP问题，最小顶点覆盖问题。

一、证明：顶点覆盖问题是NP完全问题。

将3SAT变换到VC. 设U={u1,u2,...,un}, C={c1,c2,...,cm}是3SAT的实例. 如下构造图G, 分量设计法.

真值安排分量:

Ti=(Vi,Ei), 1≤i≤n, 其中Vi={ui,ūi}, Ei={{ui,ūi}}

任意覆盖必至少包含ui或ūi中的一个,否则不能覆盖边{ui或ūi}.

满足性检验分量:

Sj=(Vj’,Ej’), 1≤ j≤ m,

其中

Vj’={a1[j],a2[j],a3[j]}

Ej’={{a1[j],a2[j]},{a1[j],a3[j]},{a2[j],a3[j]}}

覆盖至少包含Vj’中的两个顶点,否则不能覆盖Ej’中的三角形

联络边:

沟通分量之间的关系

对于每个子句cj, 设cj = {xj,yj,zj}, 则

Ej’’={{a1[j],xj},{a2[j],yj},{a3[j],zj}}

G = (V,E)

V = (V1?V2?...?Vn)?(V1’?V2’?...?Vm’)

E = E1?E2?...?En)?(E1’?E2’?...?Em’)

?(E1’’?E2’’?...?Em’’)

K = n +2m

显然构造可在多项式时间完成

例如

U = {u1,u2,u3,u4},

C = {{u1,ū3,ū4},{ū1,u2,ū4}},

则G如下，K = 4 + 2×2 = 8

设V’是V中不超过K的顶点覆盖, 则V’中必包含Ti中的一个顶点和每个Ej’中的两个顶点, 至少要n+2m个顶点. 而K=n+2m, 故V’中一定只包含每个Ti中的一个顶点和每个Ej’中的两个顶点.

如下得到赋值

ui∈V’? t(ui)=T

ūi∈V’? t(ui)=F

Ej’’中的三条边有两条被Vj’?V’中的顶点覆盖, 第三条必被V’?Vi中的顶点覆盖. 这表示在Vi中的这个顶点对应的文字取真. 所以子句cj被满足. 从而C被满足.

设t: U→{T,F}是满足C的一组赋值. 若t(ui)=T, 则在Ti中取顶点ui, 否则取ūi. 因为t满足子句cj, 在Ej’’中的三条联络边中至少有一条被覆盖, 那么取Ej’’中的另两条边的端点作为V’中的端点即可.

二、证明：TSP（旅行商问题）问题是NP完全问题。

首先来说明TSP问题属于NP。给定该问题的一个实例，用回路中n个顶点组成的序列作为证书。验证算法检查该序列是否恰好包含每个顶点一次，并且对边的费用求和后，检查和是否至多为k。

为了证明TSP是NP难度的，先证明HAM-CYCLE<=P TSP。设G=（V，E）是HAM-CYCLE 额一个实例。构造TSP的实力如下，建立一个完全图G’=（V，E’），其中E’={（i，j）：i，j 属于V且i！=j}，定义费用函数为

c（i，j）={0，如果（i，j）属于E

{1，如果（i，j）不属于E

Notice：因为G是无向图，它没有自环路，因而对所有的顶点v属于V，都有c（v，v）=1，于是

就是TSP 的一个实例，它很容易在多项式时间内产生。

现在说明图G 中具有一个汉密尔顿回路，当且仅当图G ’中有一个费用至多为0的回路。假定图G 中有一个汉密尔顿回路h ，h 中的每条边度属于E ，因此在G ’中的费用为0。因此h 在G ’中的费用为0的回路。反之，假定图G ’中有一个费用h ‘至多为0的回路。由于E ’中边的费用只能是0或1，故回路h ’的费用就是0，且回路上每条边的费用必为0。故h ‘仅包含E 中的边。

三、证明：集合的等划分问题是NP 完全问题。

实例：有穷集A ，?a ∈A, s(a)∈Z+.

问：是否存在A ’?A ，使得 显然均分是NP 类问题。下面将3DM 变换到均分问题

设W,X,Y,M ? W ?X ?Y 是3DM 的实例，

其中|W| = |X| = |Y| = q ，

W = {w1,w2,… ,wq}

X = {x1,x2,… ,xq}

Y = {y1,y2,… ,yq}

M = {m1,m2,… ,mk}

构造A ，|A| = k +2

对应于每个mi = (wf(i),xg(i),yh(i)) 有ai.

s(ai)为二进制数，分成3q 段，每段有p = ?log(k+1)?位,共计3pq 位，每段对应一个W ?X ?Y 中的元素. Wf(i),xg(i),yh(i) 所代表的段的最右位为1，其它为0.

w1 w2 … wq x1 x2 … xq y1 y2 … yq

注：p ≥log(k+1)，2p ≥k+1，k ≤ 2p -1 ,

当 k 个1相加时不会产生段之间的进位

令

B 的段数与s(ai)一样，每段的最右位为1，其它为0

例如：

W={w1,w2},X={x1,x2},Y={y1,y2},

M={(w1,x2,y2),(w1,x2,y1),(w2,x1,y1)}

p=?log(3+1)?=2

元素a1,a2,a3分别对应

(w1,x2,y2),(w1,x2,y1),(w2,x1,y1)

s(a1) = 01 00 00 01 00 01 = 210 + 24 + 20

s(a2) = 01 00 00 01 01 00 = 210 + 24 + 22

s(a3) = 00 01 01 00 01 00 = 28 + 26 + 22

B = 01 01 01 01 01 01

子集A ’ = {ai:1≤i ≤k} 满足 当且仅当 M ’ = {mi: ai ∈A ’}是M 的匹配

A 的最后两个元素b1,b2

∑=∑-∈∈'')

()(A A a A a a s a s ))(())(2())(3(222)(i h q p i g q p i f q p i a s ---++=02)23()13(130222 (22)

2+++++=∑=---=p p q p q p q j pj B B

a s A a =∑∈')(-∑

==k k i i

B a s b s 1

1)(2)(

考虑包含b1的子集A ’, 必有

因此A ’-{b1}的元素对应的三元组构成M 的匹配 反之，若子集M ’构成M 的匹配，则

A ’ = {b1}?{ai: mi ∈M ’}

满足 证明题的考点：

1、正确性证明问题。

2、替换法证明问题。

3、贪心选择性质证明问题。

4、NP 完全问题的证明。

5、最大流问题的证明。

简单题的考点：

1、回溯法基本思想和步骤。

2、分治算法的基本方法和步骤。

3、搜索算法的基本方法和步骤。

4、动态规划问题的基本方法和步骤。

5、分支界限算法的基本方法和步骤。

∑=--∑=∑==-∈k i i k i i b A a B

B a s a s a s 11}{'))(2()(2)(1∑=∑=+-∑=∑-∈==∈'11

')

()(2))(2()(A A a k

i i k

i i A a a s a s B

B a s a s

大数据算法实验教学大纲

《大数据算法》实验教学大纲 大纲制定（修订）时间： 2017 年 11 月课程名称：《大数据算法》课程编码：0 课程类别：专业基础课课程性质：选修 适用专业：通信工程 课程总学时：40 实验（上机）计划学时： 8 开课单位：理学院 一、大纲编写依据 1.信息与计算科学2017-2020版教学计划； 2.信息与计算科学专业《大数据算法》理论教学大纲对实验环节的要求。 二、实验课程地位及相关课程的联系 1.《大数据算法》是信息与计算科学专业的一门专业方向课程；

2.本实验项目是《大数据算法》课程综合知识的运用； 3. 大数据不论在研究还是工程领域都是热点之一，算法是大数据管理与计算的核心主题，通过上机实验，不仅巩固学生在课堂上所学的知识，加深对大数据算法的理解，更重要的是通过实验题目，提高学生的动手能力，增强学生就业的竞争力； 4.本实验为后续的毕业设计有指导意义。 三、本课程实验目的和任务 1.理解大数据算法的基本理论，训练运用大数据思想对实际问题进行分析、设计、实践的基本技术，掌握科学的实验方法； 2.培养学生提炼、分析问题和独立解决问题的能力； 3.通过实验使学生能够正确使用一种大数据算法环境； 4.通过综合性、设计性实验训练，使学生初步掌握简单的概率算法、I/O有效算法、并行算法的设计方法； 5.培养正确记录实验数据和现象，正确分析算法性能的能力，以及正确书写实验报告的能力。 四、实验基本要求 1.实验项目的选定依据教学计划对学生实践能力培养的要求；

2.巩固和加深学生对大数据算法设计与分析方法的理解，提高学生结合运用所学知识解决问题的能力； 3.实验项目要求学生掌握大数据算法基本知识、MapReduce简单编程技术，并运用相关知识自行设计实验方案，完成解决一定问题的小型程序。 4.通过实验，要求学生做到： （1）能够预习实验，自行设计实验方案，并撰写实验报告； （2）学会一种大数据算法开发环境的使用，能利用该环境编制简单的外存有效的算法以及并行算法，验证课程中涉及的知识点，并独立设计算法解决某一实际问题； （3）能够独立分析程序运行结果，分析算法性能。 五、实验内容和学时分配

算法导论实验

《算法导论》课程实验报告 （院）系数理系 _ _____ 专业 ______ _信息与计算科学________ ____ 班级信科1001班 学号_ 20 08 15__ 学生姓名刘俊伟_ 曹玮王舒斌 指导教师_ 阳卫锋 ______ _____

《算法导论》实验指导书 实验目标 通过实验，使同学掌握并能熟练运用散列表、贪心算法、动态规划算法。 实验三计数排序 实验目的：掌握利用计数排序进行排序。 实验内容：对数组利用计数排序进行排序。 实验要求： 1）利用计数排序法。 2）记录每一步数组的中元素的变化 代码： import java.awt.BorderLayout; import java.awt.Button; import https://www.wendangku.net/doc/586206773.html,ponent; import java.awt.Frame; import https://www.wendangku.net/doc/586206773.html,bel; import java.awt.Panel; import java.awt.TextArea; import java.awt.TextField; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.geom.Area; import javax.swing.Box; import javax.swing.JFrame; class CountingSort extends Frame { public static void main(String[] args) { new CountingSort().lauchFrame(); } private void lauchFrame() { Frame f = new JFrame("计数排序"); f.setBounds(350, 150, 600, 300);

动态规划解找零钱问题实验报告

一、实验目的 （1）熟练掌握动态规划思想及教材中相关经典算法。 （2）掌握用动态规划解题的基本步骤，能够用动态规划解决一些问题。二、实验内容与实验步骤 （1）仔细阅读备选实验的题目，选择一个（可选多个）作为此次实验题目，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。 （2）可供选择的题目有以下2个： (i）找零钱问题（难度系数为3） ★问题描述 设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只 用硬币面值T[1],T[2],…,T[i]时，可找出钱数j的最少硬币个数记为 C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=∞。 ★编程任务 设计一个动态规划算法，对1≤j≤L，计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的 计算时间复杂性 ★数据输入 由文件input.txt提供输入数据。文件的第1行中有1个正整数n （n<=13），表示有n种硬币可选。接下来的一行是每种硬币的面值。由 用户输入待找钱数j。 ★结果输出 程序运行结束时，将计算出的所需最少硬币个数输出到文件output.txt中。 输入文件示例输出文件示例 input.txt output.txt 3 3 1 2 5 9

三、实验环境 操作系统 Windows 7 调试软件 VC++6.0 上机地点 综合楼211 四、问题分析 （1） 分析要解决的问题，给出你的思路，可以借助图表等辅助表达。 答：这个问题用动态规划来解，归结到动态规划上面就变成了无限背包问题（因为收银台的硬币默认是无穷的，但一种改进版本可以考察有限硬币的情况）。区别在于，现在我们需要求一个最少的硬币数而不是最大值。但是选择的情况也是相同的，即每次选择都可以选择任何一种硬币。 首先，找零钱问题具有最优子结构性质： 兑换零钱问题的最优子结构表述：对于任意需要找的钱数j ，一个利用T[n]中的n 个不同面值钱币进行兑换零钱的最佳方案为P(T(1),j)，P(T(2),j),...,P(T(n),j)，即此时的最少钱币个数 ∑==n 1j) P(T (k),),(k j n C ，则 P(T(2),j),...,P(T(n),j)一定是利用T[n]中n 个不同的面值钱币对钱数 j=j-P(T(1),j)* T(1)进行兑换零钱的最佳方案。 其次，找零钱问题具有重叠于问题性质： a)当n=1时，即只能用一种钱币兑换零钱，钱币的面值为T[0]，有 b)当n>1时， 若j>T[n],即第n 种钱币面值比所兑换零钱数小,因此有} 1])[,({),(m in 1+-=≤≤k T j n C j n C n k 。当k 为n)i (1k 0≤≤时，C(n,j)达到最小 值，有P(T(k0),j)=P(T(0k )，j-T(0k ))+1 若j=T[n]，即用n 种钱币兑换零钱，第n 种钱币面值与兑换零钱数j 相等，此时有C(n,j)=C(n,T[n])=1； { ] [,1] [,0])[,(),(n T i n T i n T i P j i P =≠= = 若j

算法导论 第三版 第21章 答案 英

Chapter21 Michelle Bodnar,Andrew Lohr April12,2016 Exercise21.1-1 EdgeP rocessed initial{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k} (d,i){a}{b}{c}{d,i}{e}{f}{g}{h}{j}{k} (f,k){a}{b}{c}{d,i}{e}{f,k}{g}{h}{j} (g,i){a}{b}{c}{d,i,g}{e}{f,k}{h}{j} (b,g){a}{b,d,i,g}{c}{e}{f,k}{h}{j} (a,h){a,h}{b,d,i,g}{c}{e}{f,k}{j} (i,j){a,h}{b,d,i,g,j}{c}{e}{f,k} (d,k){a,h}{b,d,i,g,j,f,k}{c}{e} (b,j){a,h}{b,d,i,g,j,f,k}{c}{e} (d,f){a,h}{b,d,i,g,j,f,k}{c}{e} (g,j){a,h}{b,d,i,g,j,f,k}{c}{e} (a,e){a,h,e}{b,d,i,g,j,f,k}{c} So,the connected that we are left with are{a,h,e},{b,d,i,g,j,f,k}, and{c}. Exercise21.1-2 First suppose that two vertices are in the same connected component.Then there exists a path of edges connecting them.If two vertices are connected by a single edge,then they are put into the same set when that edge is processed. At some point during the algorithm every edge of the path will be processed,so all vertices on the path will be in the same set,including the endpoints.Now suppose two vertices u and v wind up in the same set.Since every vertex starts o?in its own set,some sequence of edges in G must have resulted in eventually combining the sets containing u and v.From among these,there must be a path of edges from u to v,implying that u and v are in the same connected component. Exercise21.1-3 Find set is called twice on line4,this is run once per edge in the graph,so, we have that?nd set is run2|E|times.Since we start with|V|sets,at the end 1

实验报告

实验三：苯酚的紫外光谱绘制及定量测定 姓名：黄日权学号：20120010007 一、实验目的 1. 了解紫外可见分光光度计的基本原理； 2. 学习并掌握紫外可见分光光度计的基本操作； 3. 掌握紫外可见吸收光谱的绘制和定量测定方法。 二、实验原理 分子的紫外可见吸收光谱是由于分子中的某些基团吸收了紫外可见辐射光后，发生了电子能级跃迁而产生的吸收光谱。它是带状光谱，反映了分子中某些基团的信息。可以用标准光谱图再结合其它手段进行定性分析。 根据物质对紫外-可见光吸收的吸光度与物质含量符合Lambert-Beer（朗伯—比尔）定律：A=εbc，（A为吸光度，ε为摩尔吸光系数，b为液池厚度，c为溶液浓度），因此，可以对物质进行定量分析。 在紫外-可见吸收分光光度分析中，必须注意溶液的pH 值的影响。因为溶液的pH 值不但有可能影响被测物吸光强度，甚至还可能影响被测物的峰位形状和位置。酚类化合物就有这一现象，例如苯酚在溶液中存在如下电离平衡： 苯酚在紫外区有三个吸收峰，在酸性或中性溶液中，λmax 为196.3nm，210.4nm 和269.8nm;在碱性溶液中λmax 位移至207.1nm，234.8nm 和286.9nm。下图为0.021g/L 的苯酚分别在0.010mol/L 盐酸溶液与氢氧化钠溶液中的紫外吸收光谱。由图可知，在盐酸溶液与氢氧化钠溶液中，苯酚的紫外吸收光谱有很大差别，所以在用紫外可见吸收分光光度分析苯酚时应加缓冲溶液，本实验是通过加氢氧化钠强碱溶液来控制溶液pH 值的。

三、仪器和试剂 1、仪器：（1）UV-1700 型紫外可见分光光度计；（2）1.00cm石英比色皿2个；（3）50mL 容量瓶8 个；（4）5mL、10mL移液管各1 支；（5）100mL、250mL 烧杯各1 个；（6）吸耳球1 个。 2、试剂：（1）苯酚标准溶液: 100mg/L；（2）10% NaOH 溶液 四、实验操作 1、配置系列标准溶液：准确移取100mg/L 的苯酚标准溶液0.00（1 号）、2.00（2 号）、4.00（3 号）、6.00（4 号）、8.00（5 号）、10.00mL（6 号）分别置于50 ml 容量瓶中，各加10 滴10%的NaOH 溶液，并用蒸馏水稀释至刻度，摇匀。 2、绘制吸收曲线：用1cm 石英比色皿，以NaOH 空白溶液为参比，在200~330nm 范围内，测量系列标准溶液中的 3 号（或 4 号）的吸光度A，绘制吸收曲线，找出最大吸收波长λmax 。 3、绘制标准工作曲线：用1cm 石英比色皿，以NaOH 空白溶液为参比，在选定的最大吸收波长λmax 下分别测定标准系列样品的吸光度，绘制标准工作曲线。 4、测定未知溶液：取未知夜10.00mL 置于50.00mL 容量瓶中，加10 滴10%的NaOH 溶液，用蒸馏水稀释至刻度；以NaOH 空白溶液为参比，用1cm 的比色皿在最大吸收波长处测定吸光度A。 5、计算未知溶液的含量（mg/mL）。 6、配制0.1mg/mL 的苯酚水溶液，以空白溶液为参比，用1cm 石英比色皿测定其吸光 度A，绘制吸收曲线，比较其余步骤（2）所得吸收曲线的差别，并说明理由。 五、实验报告及要求 1、绘制苯酚碱性溶液的标准工作曲线； 图一. 苯酚碱性溶液的标准工作曲线

算法导论 第三版 第六章 答案 英

Chapter6 Michelle Bodnar,Andrew Lohr December31,2016 Exercise6.1-1 At least2h and at most2h+1?1.Can be seen because a complete binary tree of depth h?1hasΣh?1 i=02i=2h?1elements,and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive. Exercise6.1-2 Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these k leaves,which must have length m.It is clear from the way we de?ned m that m= lg n . Exercise6.1-3 If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtree Exercise6.1-4 The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5 Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1

Java弹球游戏实验报告—chen汇总

课程设计报告 题目弹球小游戏 姓名方成 学号20 专业java 指导教师陈华恩 2013年12 月30

目录 一、实验目的 (2) 二、需求分析 (2) 三、实验任务 (2) 1、设计 (3) 2、程序要求： (3) 3、选作题： (3) 四、开发工具与平台 (3) 五、设计思路 (3) 1、界面设计 (3) 2、逻辑设计 (3) 3、程序测试 (4) 六、实验总结 (5) 七、程序代码 (5) 八、参考文献 (11) 1.《疯狂java讲义》 (12) 2.《算法导论》 (12) 3.《java编程思想》 (12)

一、实验目的 1、熟练掌握java面向对象编程。 2、掌握Swing图形用户界面编程以及事件处理等，掌握java绘图技术。 3、掌握timer类的灵活使用 4、培养独立查找资料，并解决问题的能力。 二、需求分析 经典的碰撞球是一个的古老游戏，目的是在训练人的反应能力。只有通过把所有的砖块消除完，才能顺利的完成任务。游戏要求如下： 1、实现球速度的随机性 2、实现球碰撞到边缘或者砖块自动反弹 3、实现游戏可以随时暂停 4、实现游戏结束后能重新开始游戏 三、实验任务 1、设计 设计并编程实现弹球程序：用户能通过菜单或者按钮新增一小球，该小球将从随机的位置出现，并具有随机颜色，随机速度以及随机的运动方向，小球沿初始方向匀速运动，当碰到窗口边缘时，小球将依据受力原理改变运动方向（可简化考虑，受力只改变小球的运动方向，小球仍按照初始速度匀速运动，且不考虑小球之间的碰撞）。 2、程序要求： （1）具备相应界面，并通过事件编程，实现相应的菜单或者按钮功能。（2）使用timer，在程序窗口区域绘制小球，并以线程控制小球的移动，实现动画效果。 3、选作题： （1）实现奖励机制及关卡机制 四、开发工具与平台

大连理工大学软件学院算法导论第一次大作业源码

\documentclass{ctexart} \usepackage{amsmath} \usepackage{amssymb} \usepackage{fancyhdr} \begin{document} \pagestyle{fancy} \title{算法分析与设计第一次作业} \author{XXXX XXX\XXXXXX} \date{2013/9/11} \maketitle \noindent 3.1-2\ 证明： 证明$(n+a)^b=\Theta(n^b)$等价于证明存在$c_{1},c_{2},n_{0}>0$使得对于任意的 $n>n_{0}$,都有$0\leq c_{1}n^b \leq (n+a)^b \leq c_{2}n^b$成立。 $\because$ $n+a\leq n+|a|$，$\therefore$当$n\geq |a|$时，$n+a\leq 2n$。 又$\because$ $n+a\geq n-|a|$，$\therefore$当$|a|\leq \frac{1}{2}$时，$n+a \geq \frac{1}{2}n$。综上，当$n\geq 2|a|$时，$0\leq \frac{1}{2}n \leq (n+a) \leq 2n$。 $\therefore$ 对于$b>0$，有$0\leq (\frac{1}{2}n)^b \leq (n+a)^b \leq (2n)^b$ $\therefore$ 存在$c_{1} = (\frac{1}{2}n)^b$，$c_{2} = (2n)^b$，$n_{0}=2|a|$， 使得$0\leq c_{1}n^b \leq (n+a)^b \leq c_{2}n^b$成立。\ \ \ $\therefore$原命题得证。 \\ \noindent 3.1-3\ 解释：设运行时间为$F(n)$，则$F(n)\geq 0(n^2)$， $\therefore$ 若$F_{1}(n) = 0(n^2)$，则$F(n)\geq F_{1}(n)$， 又$\because$ $\forall$ n，$T(n)=0$时，$T(n)=0(n^2)$，且运行时间都大于0， $\therefore$对于所有的运行时间$F(n)$都有$F(n)\geq 0(n^2)$， $\therefore$这句话是没有意义的。 \\ \noindent

算法导论 第三版 第七章 答案 英

Chapter7 Michelle Bodnar,Andrew Lohr April12,2016 Exercise7.1-1 13199512874212611 13199512874212611 13199512874212611 91913512874212611 95131912874212611 95131912874212611 95819121374212611 95871213194212611 95874131912212611 95874131912212611 95874219122113611 95874261221131911 95874261121131912 Exercise7.1-2 If all elements in the array have the same value,PARTITION returns r.To make PARTITION return q= (p+r)/2 when all elements have the same value,modify line4of the algorithm to say this:if A[j]≤x and j(mod2)= (p+1)(mod2).This causes the algorithm to treat half of the instances of the same value to count as less than,and the other half to count as greater than. Exercise7.1-3 The for loop makes exactly r?p iterations,each of which takes at most constant time.The part outside the for loop takes at most constant time.Since r?p is the size of the subarray,PARTITION takes at most time proportional to the size of the subarray it is called on. Exercise7.1-4 To modify QUICKSORT to run in non-increasing order we need only modify line4of PARTITION,changing≤to≥. 1

MIT麻省理工学院 算法导论公开课Problem Set 1

Introduction to Algorithms September7,2005 Massachusetts Institute of Technology 6.046J/18.410J Professors Erik D.Demaine and Charles E.Leiserson Handout5

(a) (b) (c) (d)and(note the little-) (e)and Problem1-2.Recurrences Give asymptotic upper and lower bounds for in each of the following recurrences.Assume that is constant for.Make your bounds as tight as possible,and justify your answers. (a) (b) (c) (d)

Figure1:An example of a convex polygon represented by the array.is the vertex with the minimum-coordinate,and are ordered counterclockwise. (b)Give an algorithm to?nd the vertex with the maximum coordinate in time. (c)Give an algorithm to?nd the vertex with the maximum coordinate in time.

算法导论 第三版 第二章 答案 英

Chapter2 Michelle Bodnar,Andrew Lohr April12,2016 Exercise2.1-1 314159264158 314159264158 314159264158 263141594158 263141415958 263141415859 Exercise2.1-2 Algorithm1Non-increasing Insertion-Sort(A) 1:for j=2to A.length do 2:key=A[j] 3://Insert A[j]into the sorted sequence A[1..j?1]. 4:i=j?1 5:while i>0and A[i]

算法导论第二章答案

第二章算法入门 由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供个意见。 给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。 插入排序算法伪代码 INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ←A[j] 3 Insert A[j] into the sorted sequence A[1..j-1] 4 i ←j-1 5 while i > 0 and A[i] > key 6 do A[i+1]←A[i] 7 i ←i ? 1 8 A[i+1]←key C#对揑入排序算法的实现: public static void InsertionSort(T[] Input) where T:IComparable { T key; int i; for (int j = 1; j < Input.Length; j++) { key = Input[j]; i = j - 1; for (; i >= 0 && Input[i].CompareTo(key)>0;i-- ) Input[i + 1] = Input[i]; Input[i+1]=key; } } 揑入算法的设计使用的是增量（incremental）方法：在排好子数组A[1..j-1]后，将元素A[ j]揑入，形成排好序的子数组A[1..j] 这里需要注意的是由于大部分编程语言的数组都是从0开始算起，这个不伪代码认为的数组的数是第1个有所丌同，一般要注意有几个关键值要比伪代码的小1. 如果按照大部分计算机编程语言的思路，修改为： INSERTION-SORT(A) 1 for j ← 1 to length[A] 2 do key ←A[j] 3 i ←j-1

算法导论 第三版 第24章 答案 英

Chapter24 Michelle Bodnar,Andrew Lohr April12,2016 Exercise24.1-1 If we change our source to z and use the same ordering of edges to decide what to relax,the d values after successive iterations of relaxation are: s t x y z ∞∞∞∞0 2∞7∞0 25790 25690 24690 Theπvalues are: s t x y z NIL NIL NIL NIL NIL z NIL z NIL NIL z x z s NIL z x y s NIL z x y s NIL Now,if we change the weight of edge(z,x)to4and rerun with s as the source,we have that the d values after successive iterations of relaxation are: s t x y z 0∞∞∞∞ 06∞7∞ 06472 02472 0247?2 Theπvalues are: s t x y z NIL NIL NIL NIL NIL NIL s NIL s NIL NIL s y s t NIL x y s t NIL x y s t 1

Note that these values are exactly the same as in the worked example.The di?erence that changing this edge will cause is that there is now a negative weight cycle,which will be detected when it considers the edge(z,x)in the for loop on line5.Since x.d=4>?2+4=z.d+w(z,x),it will return false on line7. Exercise24.1-2 Suppose there is a path from s to v.Then there must be a shortest such path of lengthδ(s,v).It must have?nite length since it contains at most|V|?1 edges and each edge has?nite length.By Lemma24.2,v.d=δ(s,v)<∞upon termination.On the other hand,suppose v.d<∞when BELLMAN-FORD ter-minates.Recall that v.d is monotonically decreasing throughout the algorithm, and RELAX will update v.d only if u.d+w(u,v)

数据库原理实验报告2012

《数据库原理》实验报告书 班级: 学号: 姓名: 指导教师: 实验成绩: 中南林业科技大学涉外学院理工系

目录 数据库原理实验安排 (3) 实验一数据库和表的建立、数据操作 (4) 实验二 SQL语言的使用 (9) 实验三完整性、安全性实现 (16) 实验四数据库编程 (18) 附录一SQL Server的安装 (20)

数据库原理实验安排 一、实验目的 通过实验，使学生熟悉并掌握数据库的基本概念、基本原理、和基本技术；能够应用这些理论和技术设计合理的数据库；更重要的是通过教学活动，使学生能够把与数据库相关的先修后继知识融会贯通，初步具有开发完整可用的数据库系统的能力。 二、实验安排 本门课程共分4个实验，8学时 实验一数据库和表的建立、数据操作 2学时 实验二 SQL语言的使用2学时 实验三完整性、安全性实现 2学时 实验四数据库编程 2学时 三、实验考核 实验成绩通过实验报告及每次实验后的验机给出，每次实验结束后都必须写出实验报告。

实验一数据库和表的建立、数据操作 一、实验目的： 掌握使用SQL语言进行数据定义和数据操纵的方法。 二、实验要求： 建立一个数据库stumanage，建立三个关系表students，course，grade。向表中插入数据，然后对数据进行删除、修改等操作，对关系、数据库进行删除操作。 三、实验步骤： 1、在SQL Server中输入本机器的名字，选择“windows身份验证”。点击确定连接SQL Server数据库服务器。 2、新建查询分析器。 3、在查询分析器中输入SQL语句------建立数据库stumanage。然后单击上面的绿色三角形右箭头。下部的空白区显示该语句的运行情况。 4、选择数据库stumanage为当前数据库。 5、如下图建立表students： 列名数据类型允许空主键说明 (1) sno Char(8) 否是学号 (2) sname Varchar(20) 是否姓名 (3) sex Char(2) 是否性别 (4) dept Varchar(20) 是否所在系 如下图建立表：course 列名数据类型允许空主键说明 (1) cno Char(6) 否是课程号 (2) cname Varchar(20) 是否课程名 如下图建立表sc：（注：包括两个外键，sno和cno共同组成主键）列名数据类型允许空主键外键说明 (1) sno Char(8) 否是 students(sno) 学号 (2) cno Char(6) 否是 course(sno) 课程号 (3) grade int 否否否成绩 6、使用SQL语句完成建表操作并以截屏的方式将建表操作过程粘贴在下方表格中。

大数据算法实验教学大纲

大数据算法实验教学大 纲 -CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN

《大数据算法》实验教学大纲 大纲制定（修订）时间： 2017 年 11 月 课程名称：《大数据算法》课程编码：090141128 课程类别：专业基础课课程性质：选修 适用专业：通信工程 课程总学时：40 实验（上机）计划学时： 8 开课单位：理学院 一、大纲编写依据 1.信息与计算科学2017-2020版教学计划； 2.信息与计算科学专业《大数据算法》理论教学大纲对实验环节的要求。 二、实验课程地位及相关课程的联系 1.《大数据算法》是信息与计算科学专业的一门专业方向课程； 2.本实验项目是《大数据算法》课程综合知识的运用； 3. 大数据不论在研究还是工程领域都是热点之一，算法是大数据管理与计算的核心主题，通过上机实验，不仅巩固学生在课堂上所学的知识，加深对大数据算法的理解，更重要的是通过实验题目，提高学生的动手能力，增强学生就业的竞争力； 4.本实验为后续的毕业设计有指导意义。 三、本课程实验目的和任务 1.理解大数据算法的基本理论，训练运用大数据思想对实际问题进行分析、设计、实践的基本技术，掌握科学的实验方法； 2.培养学生提炼、分析问题和独立解决问题的能力； 3.通过实验使学生能够正确使用一种大数据算法环境； 4.通过综合性、设计性实验训练，使学生初步掌握简单的概率算法、I/O有效算法、并行算法的设计方法； 5.培养正确记录实验数据和现象，正确分析算法性能的能力，以及正确书写实验报告的能力。 四、实验基本要求 1.实验项目的选定依据教学计划对学生实践能力培养的要求； 2.巩固和加深学生对大数据算法设计与分析方法的理解，提高学生结合运用所学知识解决问题的能力； 3.实验项目要求学生掌握大数据算法基本知识、MapReduce简单编程技术，并运用相关知识自行设计实验方案，完成解决一定问题的小型程序。 4.通过实验，要求学生做到： （1）能够预习实验，自行设计实验方案，并撰写实验报告； （2）学会一种大数据算法开发环境的使用，能利用该环境编制简单的外存有效的算法以及并行算法，验证课程中涉及的知识点，并独立设计算法解决某一实际问题； （3）能够独立分析程序运行结果，分析算法性能。