演算法設計活動安排實驗

㈠ C語言程序問題——活動安排問題

題目出得不嚴密，題目要求是「計算安排的活動最多時會場使用時間」，但當「安排的活動最多」有多種安排方式，題目中卻沒說輸出這多種方式中的哪一種的會場使用時間。例如 ：當有3項活動要安排，開始時間和結束時間分別是1 2、3 5、4 5，這時可以安排第一項和第二項活動，也可以安排第一項和第三項活動，前者的會場使用時間是5，後者是4，這時是輸出4還是5，題目中沒用指出。先假設測試數據不會出現上述情況，則利用貪心演算法求解活動安排問題是一種最常用的方法：#include<stdio.h>
#include<stdlib.h>
struct activity
{
int start;
int end;
}act[8501];
int comp(const void *p, const void *q)
{
struct activity *a=(struct activity *)p;
struct activity *b=(struct activity *)q;
return a->end-b->end;
}
int main()
{
int i,k,res,e;
while(scanf("%d",&k)!=EOF)
{
for(i=0;i<k;i++) scanf("%d%d",&act[i].start,&act[i].end);
qsort(act,k,sizeof(act[0]),comp);
res=act[0].end-act[0].start+1;
e=act[0].end;
for(i=1;i<k;i++)
{
if(act[i].start>e)
{
res+=act[i].end-act[i].start+1;
e=act[i].end;
}
}
printf("%d\n",res);
}
return 0;
}

㈡ 活動安排問題，貪心演算法Greedyselector 卻總能求得整體的最優解，這個能用數學歸納法證明 求大俠指導

貪心演算法Greedyselector
第n + 1次select都比第 n 次更優
n 趨於 無限 的時候 總能得到最優解

㈢ 程序設計方法學實驗

動態規劃解0-1背包：
#include<iostream>
using namespace std;

//顯然定義為全局變數不好

const int item=3;//物品數量
const int max_wgt=10;//背包最大容量
int c[item+1][max_wgt+1];//從1…i…item物品中,背包剩餘空間為0<=j<=max_wgt的最大價值

int w[item+1]={0,3,4,5};//物品質量
int vl[item+1]={0,4,5,6}; //物品價值

int knapbag()
{
for (int i=0;i<=item;i++)//初始化
{
for (int j=0;j<=max_wgt;j++)
{
c[i][j]=0;
}
}
//c(i,j)=max{c(i-1,j), c(i-1,j-w[i])+vl(i)}
for (int i=1;i<=item;i++)
{
for (int j=1;j<=max_wgt;j++)
{
if (w[i]<=j)
{
if (vl[i]+c[i-1][j-w[i]]>c[i-1][j])
{
c[i][j]=vl[i]+c[i-1][j-w[i]];//選擇第i物品
}
else
c[i][j]=c[i-1][j];//不選擇第i個物品
}
else
c[i][j]=c[i-1][j];//剩餘容量不夠
}//endfor
}//endfor
return c[item][max_wgt];//返回最大值
}

int main()
{
cout<<knapbag()<<endl;
return 0;
}

void trackback()//算出是由哪幾個物品組成
{
int temp_wei=max_wgt;
int x[item+1]={0,0,0,0};
for (int i=item;i>0;i--)
{
if (c[i][temp_wei]==c[i-1][temp_wei])//最後一個肯定是最大價值的
{
x[i]=0;
}
else
{
x[i]=1;
temp_wei-=w[i];
}
}
for (int i=0;i<=item;i++)
{
if (x[i])
{
std::cout<<i<<",";
}
}
std::cout<<std::endl;
}
最長公共子序列：
最長公共子序列的定義是，一個數列z分別是已知數列的子序列（子序列不一定是連續序列，是在該序列中刪去若干元素後得到的序列），且是所有符合此條件序列中最長的，則z成為最長公共子序列lcs(Longest Common Subsequences)。有些地方則說公共子串就是要求連續的子序列，有些地方則不是，這里要注意區分。下面是完整實現代碼。

#include <iostream>
using namespace std;
void LCS_Length(char *x,char *y,int **b,int m,int n)
{
//c[i][j]表示x[i-1],y[j-1]之前公共子序列的長度,i表示x數組前進，j表示y數組前進
//不用c[i][j]表示x[i],y[j]之前公共子序列的長度是因為需要使用c[0][0]來表示沒有公共子序列，
//即c[0][0]恆等於0，因此c數組最大下標為c[m+1][n+1]
int **c;
c=new int*[m+1];
for( int i=0;i<m+1;i++)
c[i]=new int[n+1];

for(int i=0;i<m+1;i++)
c[i][0]=0;
for(int i=0;i<n+1;i++)
c[0][i]=0;

for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(x[i-1]==y[j-1])//找到一個公共「字元」
{
c[i][j]=c[i-1][j-1]+1;//公共子序列的長度在原來的基礎上加1
b[i][j]=0;//做一個輔助標志，表示要達到目前的長度，x，y數組均需「前進」一步
//即x[i-1]，y[j-1]都要作出貢獻
}
//當前字元不相同，且x數組後退一步（即c[i-1][j]）比y數組後退一步（即c[i][j-1]）
//所得到的公共子序列的長度要長，隱含的意思是當前最長公共子序列可以不需要x[i-1]
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];//當前最長公共子序列可以不需要x[i-1]
b[i][j]=-1;
}
//和上面分析類似
else
{
c[i][j]=c[i][j-1];//當前最長公共子序列可以不需要y[j-1]
b[i][j]=1;
}
}
}
for(int i=0;i<m+1;i++)
{
delete c[i];
c[i]=NULL;
}
delete []c;
c=NULL;
}

//列印結果
void Print_LCS(int **b,char *x,int i,int j)
{
if(i==0||j==0)
return ;
if(b[i][j]==0)
{
Print_LCS(b,x,i-1,j-1);
cout<<x[i-1];
}
else if(b[i][j]==-1)
Print_LCS(b,x,i-1,j);
else
Print_LCS(b,x,i,j-1);
}

int _tmain(int argc, _TCHAR* argv[])
{
char x[]="ADAB";
char y[]="ADCA";
int m=strlen(x);
int n=strlen(y);

int **b;
b=new int*[m+1];
for( int i=0;i<m+1;i++)
b[i]=new int[n+1];

LCS_Length(x,y,b,m,n);
Print_LCS(b,x,m,n);

for(int i=0;i<m+1;i++)
{
delete b[i];
b[i]=NULL;
}
delete []b;
b=NULL;

return 0;
}

A*演算法
1.啟發式搜索
廣度優先搜索和雙向廣度優先搜索都屬於盲目搜索，這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分龐大時，它們的效率實在太低，往往都是在搜索了大量無關的狀態結點後才碰到解答，甚至更本不能碰到解答。
搜索是一種試探性的查尋過程，為了減少搜索的盲目性引，增加試探的准確性，就要採用啟發式搜索了。所謂啟發式搜索就是在搜索中要對每一個搜索的位置進行評估，從中選擇最好、可能容易到達目標的位置，再從這個位置向前進行搜索，這樣就可以在搜索中省略大量無關的結點，提高了效率。
2.A*演算法
A*演算法是一種常用的啟發式搜索演算法。
在A*演算法中，一個結點位置的好壞用估價函數來對它進行評估。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值（也稱為最小耗費或最小代價），h'(n)是n到目標的最短路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以實際上使用的是下面的估價函數：
f(n) = g(n) + h(n)
其中g(n)是從初始結點到節點n的實際代價，h(n)是從結點n到目標結點的最佳路徑的估計代價。在這里主要是h(n)體現了搜索的啟發信息，因為g(n)是已知的。用f(n)作為f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。這樣必須滿足兩個條件：（1）g(n)>=g'(n)（大多數情況下都是滿足的，可以不用考慮），且f必須保持單調遞增。（2）h必須小於等於實際的從當前節點到達目標節點的最小耗費h(n)<=h'(n)。第二點特別的重要。可以證明應用這樣的估價函數是可以找到最短路徑的。
3.A*演算法的步驟
A*演算法基本上與廣度優先演算法相同，但是在擴展出一個結點後，要計算它的估價函數，並根據估價函數對待擴展的結點排序，從而保證每次擴展的結點都是估價函數最小的結點。
A*演算法的步驟如下：
1）建立一個隊列，計算初始結點的估價函數f，並將初始結點入隊，設置隊列頭和尾指針。
2）取出隊列頭（隊列頭指針所指）的結點，如果該結點是目標結點，則輸出路徑，程序結束。否則對結點進行擴展。
3）檢查擴展出的新結點是否與隊列中的結點重復，若與不能再擴展的結點重復（位於隊列頭指針之前），則將它拋棄；若新結點與待擴展的結點重復（位於隊列頭指針之後），則比較兩個結點的估價函數中g的大小，保留較小g值的結點。跳至第五步。
4）如果擴展出的新結點與隊列中的結點不重復，則按照它的估價函數f大小將它插入隊列中的頭結點後待擴展結點的適當位置，使它們按從小到大的順序排列，最後更新隊列尾指針。
5）如果隊列頭的結點還可以擴展，直接返回第二步。否則將隊列頭指針指向下一結點，再返回第二步。
4.八數碼問題的A*演算法的估價函數
估價函數中，主要是計算h，對於不同的問題，h有不同的含義。那麼在八數碼問題中，h的含意是各什麼？八數碼問題的一個狀態實際上是數字0~8的一個排列，用一個數組p[9]來存儲它，數組中每個元素的下標，就是該數在排列中的位置。例如，在一個狀態中，p[3]=7，則數字7的位置是3。如果目標狀態數字3的位置是8，那麼數字7對目標狀態的偏移距離就是3，因為它要移動3步才可以回到目標狀態的位置。
八數碼問題中，每個數字可以有9個不同的位置，因此，在任意狀態中的每個數字和目標狀態中同一數字的相對距離就有9*9種，可以先將這些相對距離算出來，用一個矩陣存儲，這樣只要知道兩個狀態中同一個數字的位置，就可查出它們的相對距離，也就是該數字的偏移距離：
0 1 2 3 4 5 6 7 8
0 0 1 2 1 2 3 2 3 4
1 1 0 1 2 1 2 3 2 3
2 2 1 0 3 2 1 4 3 2
3 1 2 3 0 1 2 1 2 3
4 2 1 2 1 0 1 2 1 2
5 3 2 1 2 1 0 3 2 1
6 2 3 4 1 2 3 0 1 2
7 3 2 3 2 1 2 1 0 1
8 4 3 2 3 2 1 2 1 0
例如在一個狀態中，數字8的位置是3，在另一狀態中位置是7，那麼從矩陣的3行7列可找到2，它就是8在兩個狀態中的偏移距離。
估價函數中的h就是全體數字偏移距離之和。
顯然，要計算兩個不同狀態中同一數字的偏移距離，需要知道該數字在每個狀態中的位置，這就要對數組p[9]進行掃描。由於狀態發生變化，個數字的位置也要變化，所以每次計算h都沿線掃描數組，以確定每個數字在數組中的位置。為了簡化計算，這里用一個數組存儲狀態中各個數字的位置，並讓它在狀態改變時隨著變化，這樣就不必在每次計算h時，再去掃描狀態數組。
例如，某個狀態中，數字5的位置是8，如果用數組r[9]存儲位置，那麼就有r[5]=8。
現在用數組r[9]存儲當前狀態的數字位置，而用s[9]存儲目標狀態的數字位置，那麼當前狀態數字i對目標狀態的偏移距離就是矩陣中r[i]行s[i]列對應的值。
5.A*演算法的類結構
A*演算法的類聲明如下：
class TAstar:public TEight
{
public:
TAstar(){} //構造函數
TAstar(char *fname); //帶參數構造函數
virtual void Search(); //A*搜索法
private:
int f,g,h; //估價函數
int r[Num]; //存儲狀態中各個數字位置的輔助數組
static int s[Num]; //存儲目標狀態中各個數字位置的輔助數組
static int e[]； //存儲各個數字相對距離的輔助數組
void Printl(TList<TAstar> L); //成員函數，輸出搜索路徑
int Expend(int i); //成員函數，A*演算法的狀態擴展函數
int Calcuf(); //成員函數，計算估價函數
void Sort(TList<TAstar>& L,int k); //成員函數，將新擴展結點按f從小到大
//順序插入待擴展結點隊列
int Repeat(TList<TAstar> &L); //成員函數，檢查結點是否重復
};

int TAstar::s[Num],TAstar::e[Num*Num];

TAstar::TAstar(char *fname):TEight(fname)
{
for(int i=0;i<Num;)
{
r[p[i]]=i; //存儲初始狀態個個數字的位置
s[q[i]]=i++; //存儲目標狀態個個數字的位置
}
ifstream fin;
fin.open(".\Eightd.txt",ios::in | ios::nocreate);//打開數據文件
if(!fin)
{
cout<<"不能打開數據文件!"<<endl;
return;
}
for(i=0;i<Num*Num;i++) //讀入各個數字相對距離值
fin>>e[i];
fin.close();
f=g=h=0; //估價函數初始值
}

void TAstar::Printl(TList<TAstar> L)
{
TAstar T=*this;
if(T.last==-1)
return;
else
{
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
}
}

int TAstar::Expend(int i)
{
if(Extend(i)) //結點可擴展
{
int temp=r[p[r[0]]]; //改變狀態後數字位置變化，存儲改變後的位置
r[p[r[0]]]=r[0];
r[0]=temp;
return 1;
}
return 0;
}

int TAstar::Calcuf()
{
h=0;
for(int i=0;i<Num;i++) //計算估價函數的h
h+=e[Num*r[i]+s[i]];
return ++g+h;
}

void TAstar::Sort(TList<TAstar>& L,int k)
{
int n=L.Getlen();
for(int i=k+1;i<n;i++)
{
TAstar T=L.GetData(i);
if(this->f<=T.f)
break;
}
L.Insert(*this,i);
}

int TAstar::Repeat(TList<TAstar> &L)
{
int n=L.Getlen();
for(int i=0;i<n;i++)
if(L.GetData(i)==*this)
break;
return i;
}

void TAstar::Search()
{
TAstar T=*this; //初始結點
T.f=T.Calcuf(); //初始結點的估價函數
TList<TAstar> L; //建立隊列
L.Append(T); //初始結點入隊
int head=0,tail=0; //隊列頭和尾指針
while(head<=tail) //隊列不空則循環
{
for(int i=0;i<4;i++) //空格可能移動方向
{
T=L.GetData(head); //去隊列頭結點
if(T.h==0) //是目標結點
{
T.Printl(L);//輸出搜索路徑
T.Print(); //輸出目標狀態
return; //結束
}
if(T.Expend(i)) //若結點可擴展
{
int k=T.Repeat(L); //返回與已擴展結點重復的序號 if(k<head) //如果是不能擴展的結點
continue; //丟棄
T.last=head; //不是不能擴展的結點，記錄父結點
T.f=T.Calcuf(); //計算f
if(k<=tail) //新結點與可擴展結點重復
{
TAstar Temp=L.GetData(k);
if(Temp.g>T.g) //比較兩結點g值
L.SetData(T,k); //保留g值小的
continue;
}
T.Sort(L,head) ; //新結點插入可擴展結點隊列 tail++; //隊列尾指針後移
}
}
head++; //一個結點不能再擴展，隊列頭指針指向下一結點
}
}

n皇後問題
#include <iostream.h>
#include <math.h>

void Queue(int n)
{
for (i=1; i<=n; i++) //初始化
x[i]=0;
k=1;
while (k>=1)
{
x[k]=x[k]+1; //在下一列放置第k個皇後
while (x[k]<=n && !Place(k))
x[k]=x[k]+1; //搜索下一列
if (x[k]<=n && k= =n) { //得到一個解，輸出
for (i=1; i<=n; i++)
cout<<x[i];
return;
}
else if (x[k]<=n && k<n)
k=k+1; //放置下一個皇後
else {
x[k]=0; //重置x[k]，回溯
k=k-1;
}
}
}

bool Place(int k) //考察皇後k放置在x[k]列是否發生沖突
{
for (i=1; i<k; i++)
if (x[k]= =x[i] | | abs(k-i)= =abs(x[k]-x[i]))
return false;
return true;
}

㈣ 貪心演算法之會場安排問題

三星演算法之間最好還是不要安排互相的問題，這樣不利於你們倆的關系的便有好。

㈤ 用哈夫曼樹演算法設計對文件文件的壓縮和解壓縮的實驗程序解析

樓主可以去看看最優二叉樹的編碼問題。
1、哈夫曼編碼
在數據通信中，需要將傳送的文字轉換成二進制的字元串，用0，1碼的不同排列來表示字元。例如，需傳送的報文為「AFTER DATA EAR ARE ART AREA」，這里用到的字元集為「A，E，R，T，F，D」，各字母出現的次數為{8，4，5，3，1，1}。現要求為這些字母設計編碼。要區別6個字母，最簡單的二進制編碼方式是等長編碼，固定採用3位二進制，可分別用000、001、010、011、100、101對「A，E，R，T，F，D」進行編碼發送，當對方接收報文時再按照三位一分進行解碼。顯然編碼的長度取決報文中不同字元的個數。若報文中可能出現26個不同字元，則固定編碼長度為5。然而，傳送報文時總是希望總長度盡可能短。在實際應用中，各個字元的出現頻度或使用次數是不相同的，如A、B、C的使用頻率遠遠高於X、Y、Z，自然會想到設計編碼時，讓使用頻率高的用短碼，使用頻率低的用長碼，以優化整個報文編碼。
為使不等長編碼為前綴編碼，可用字元集中的每個字元作為葉子結點生成一棵編碼二叉樹，為了獲得傳送報文的最短長度，可將每個字元的出現頻率作為字元結點的權值賦予該結點上，求出此樹的最小帶權路徑長度就等於求出了傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字元集中的所有字元作為葉子結點，由字元出現頻率作為其權值所產生的哈夫曼樹的問題。利用哈夫曼樹來設計二進制的前綴編碼，既滿足前綴編碼的條件，又保證報文編碼總長最短。
哈夫曼靜態編碼：它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--2^32-1，這已足夠表示大文件中字元出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。
哈夫曼動態編碼：動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。[3]
2、哈夫曼解碼
在通信中，若將字元用哈夫曼編碼形式發送出去，對方接收到編碼後，將編碼還原成字元的過程，稱為哈夫曼解碼。[4]

㈥ 演算法課程設計報告

題目中要求的功能進行敘述分析，並且設計解決此問題的數據存儲結構，（有些題目已經指定了數據存儲的，按照指定的設計），設計或敘述解決此問題的演算法，描述演算法建議使用流程圖，進行演算法分析指明關鍵語句的時間復雜度。
給出實現功能的一組或多組測試數據，程序調試後，將按照此測試數據進行測試的結果列出來 。
對有些題目提出演算法改進方案，比較不同演算法的優缺點。
如果程序不能正常運行，寫出實現此演算法中遇到的問題，和改進方法；
2 對每個題目要有相應的源程序（可以是一組源程序，即詳細設計部分）：
源程序要按照寫程序的規則來編寫。要結構清晰，重點函數的重點變數，重點功能部分要加上清晰的程序注釋。
程序能夠運行，要有基本的容錯功能。盡量避免出現操作錯誤時出現死循環；
3 最後提供的主程序可以象一個應用系統一樣有主窗口，通過主菜單和分級菜單調用課程設計中要求完成的各個功能模塊，調用後可以返回到主菜單，繼續選擇其他功能進行其他功能的選擇。最好有窗口展示部分。
4 課程設計報告：（保存在word 文檔中，文件名要求 按照"姓名-學號-課程設計報告"起名，如文件名為"張三-001-課程設計報告".doc ）按照課程設計的具體要求建立的功能模塊，每個模塊要求按照如下幾個內容認真完成；
其中包括:
a)需求分析：
在該部分中敘述，每個模塊的功能要求
b)概要設計
在此說明每個部分的演算法設計說明（可以是描述演算法的流程圖），每個程序中使用的存儲結構設計說明（如果指定存儲結構請寫出該存儲結構的定義。
c）詳細設計
各個演算法實現的源程序，對每個題目要有相應的源程序（可以是一組源程序，每個功能模塊採用不同的函數實現）
源程序要按照寫程序的規則來編寫。要結構清晰，重點函數的重點變數，重點功能部分要加上清晰的程序注釋。
d）調試分析
測試數據，測試輸出的結果，時間復雜度分析，和每個模塊設計和調試時存在問題的思考（問題是哪些？問題如何解決？），演算法的改進設想。
5. 課設總結： （保存在word 文檔中）總結可以包括 : 課程設計 過程的收獲、遇到問題、遇到問題解決問題過程的思考、程序調試能力的思考、對數據結構這門課程的思考、在課程設計過程中對C課程的認識等內容；
6.實驗報告的首頁請參考如下格式：

課程設計實驗
起止日期:20 -20 學年 學期
系別 班級 學號 姓名
實驗題目 □設計性 □綜合性
自我評價
教師評語 能夠實現實驗要求的功能 □全部 □部分演算法有新意 □有 □一般程序運行通過 □全部 □部分 演算法注釋說明 □完善 □僅有功能說明介面參數說明 □有 □無按期上交列印文檔資料及源程序 □所有 □部分綜合設計說明報告結構 □合理 □不合理用戶使用說明 □完整 □不全現場演示操作有準備 □有 □無問題解答流暢 □流暢 □不流暢獨立完成實驗 □能 □不能體現團隊合作精神。 □能夠 □不能
成績

這是張表格，過來時沒調整好，不過應該看得明白。我們是這樣寫的，你可以參考一下。

㈦ 數據結構與演算法實驗

計算機科學系

計算機科學與技術專業 培養具有良好綜合素質和開拓創新能力，系統掌握本專業的基本理論、基礎知識和基本技能與方法，具有實際應用和科學研究能力的計算機及其相關技術與產業領域的復合型應用技術人才。

主要課程：數學分析、高等代數、數理邏輯、集合論與圖論、計算機科學導論、程序設計基礎、數字電路與邏輯設計、計算機組成原理、數據結構與演算法、操作系統原理、匯編語言程序設計、資料庫系統原理、編譯原理、軟體工程導論、計算機網路、計算機體系結構、並行與分布式計算、計算機圖形學、信息安全技術、多媒體技術、Linux原理與應用等。專業課程還將安排相關的實驗（實習）、課程設計或社會實踐，以加強學生的實踐能力與開拓能力。高年級同學還可以選修本學院其它專業的相關課程。

網路工程專業 培養具有實際運用先進的工程化方法和工具從事網路規劃、設計、開發和維護等工作，具備工程項目的組織與管理能力的實用型、復合型網路工程技術與管理的高級人才。

主要課程：數學分析、高等代數、數理邏輯、集合論與圖論、計算機科學導論、程序設計基礎、數字電路與邏輯設計、計算機組成原理、數據結構與演算法、計算機網路、操作系統原理、計算機體系結構、計算機介面技術、通信原理、網路系統設計、密碼學與網路安全、無線通信與網路、Linux原理與應用等。專業課程還將安排相關的實驗（實習）、課程設計或社會實踐，以加強學生的實踐能力與開拓能力。高年級同學還可以選修本學院其它專業的相關課程。

信息安全專業 培養具有扎實的數理基礎，較好的外語和計算機技術運用能力，掌握信息安全的基本理論與技術、計算機與網路通信及其安全技術以及信息安全法律法規等方面的知識，能運用所學知識與技能去分析和解決相關的實際問題，具有較高的綜合業務素質、較強的創新與實踐能力，可以在政府、國防、金融、公安和商業等部門從事信息安全產品研發、信息系統安全分析與設計、信息安全技術咨詢與評估服務、信息安全教育、信息安全管理與執法等工作的高級專業人才。

主要課程：數學分析、數理邏輯、集合論與圖論、信息安全數學基礎、計算機組成原理、程序設計基礎、數據結構與演算法、資料庫系統原理、軟體工程導論、計算機介面技術、計算機網路、通信原理、資訊理論基礎、操作系統安全、Linux原理與應用、網路協議與驗證、移動計算、計算機密碼學、網路安全技術、計算機病毒、信息隱藏技術、電子商務技術、信息安全法律法規等。專業課程還將安排相關的實驗（實習）、課程設計或社會實踐，以加強學生的實踐能力與開拓能力。高年級同學還可以選修本學院其它專業的相關課程。

上述專業的畢業生適合在計算件軟硬體企業、網路公司、電信企業、金融、交通、銀行等各類企事業單位就職，從事計算機技術管理、計算機控制、軟體和信息安全產品的生產、開發、應用和維護工作，也可在政府管理部門、金融和經濟管理部門從事計算機應用、網路信息管理和維護工作，還可在高等學校和研究部門從事教學、科研工作。

電子與通信工程系

電子信息科學與技術專業 培養基礎扎實、知識面較寬、素質高、能力強，有一定創新能力、科學研究能力和解決實際問題的能力，適應21世紀社會和經濟發展的需要，能從事電子信息科學與技術領域的科學研究、教學與應用技術等工作的復合型人才。

畢業生具有堅實的數理基礎，掌握電子學與信息系統的基本理論和方法。熟悉電路與系統、電磁場與電磁波理論、微波與射頻技術、計算機網路以及通信和計算機應用等技術。具有較高的實驗能力和一定的分析和解決實際問題的能力；了解電子學與信息系統的新發展並具有一定的科學研究、應用研究、技術開發及教學等方面的能力。較為熟練地使用一種外國語閱讀專業書刊及外文資料。

學生畢業後適合在通訊、銀行、企業、機關等部門，從事電子技術和計算機技術管理、生產方面的開發應用，以及在高等學校和研究部門從事教學、科研工作。

主要課程：高等數學、概率論與數理統計、大學物理及實驗、高級程序設計、電路基礎理論、模擬電子技術及實驗、數字電路與邏輯設計及實驗、微型計算機原理及實驗、高頻電路、信號與系統、電磁場與電磁波、集成電路設計、資訊理論、微波技術與實驗、數字信號處理、計算機通信與網路、通信原理、EDA原理及應用、單片機原理及應用、數據結構與演算法、現代通信技術、資料庫系統原理等，學生還可選修學校及學院其他專業的相關課程。

自動化專業 自動化是以電子技術、計算機技術、檢測技術、通信技術和控制理論為基礎，研究自動控制系統的組成結構、控制規律及其應用的學科。該專業培養德、智、體全面發展，注重德、智、體、美、勞，具有健全的心理素質和健康的體格。基礎扎實、知識面寬、綜合素質高、實踐能力強，適應適應21世紀社會和經濟發展的需要，能從事自動化和計算機網路控制工程領域的先進技術研究、設計、應用開發及教學等方面的高級復合型人才。

畢業生應具有控制科學與工程學科扎實的基礎理論、基本技能和方法；具有對電子電氣電路、控制系統進行分析、設計和研究開發的能力；掌握信號自動檢測、數據處理的基礎知識與技能；掌握計算機與網路控制技術；有嚴謹的科學作風和創新能力；具有獨立進行科學研究、應用研究、分析和解決實際問題的能力。

學生畢業後適合在各類企業、國家政府部門、事業、通信、銀行、軍事等部門從事電子技術、計算機技術、通信技術及生產過程自動化方面的應用研究、產品開發及行政管理工作，以及在高等學校和研究等部門從事教學、科研及管理工作。

主要課程：高等數學、概率論與數理統計、工程數學、數值計算、高級程序設計、大學物理及實驗、電路基礎理論及實驗、模擬電子技術及實驗、數字電路與邏輯設計及實驗、電力電子技術、電機及拖動基礎、微型計算機原理及實驗、自動控制原理及實驗、信號與系統、現代控制理論、計算機控制技術及實驗、計算機通信與網路、數字信號處理、電氣與可編程控制器、過程式控制制工程、單片機原理及應用、自動測量技術、電力拖動自動控制系統、虛擬儀器技術、數據結構、操作系統、資料庫系統原理、科技信息檢索等，學生還可選修學校及學院其他專業的相關課程。

通信工程專業 培養基礎扎實、知識面較寬、綜合素質高、實踐能力強，適應21世紀社會和經濟發展的需要，系統掌握電路分析與信號處理理論、通信原理、網路理論、電磁場理論、傳輸原理、現代電信交換等專業基礎理論；掌握各類通信網、通信系統及其主要設備的構成原理、技術性能、設計、調試、運行維護和管理的基本知識；對國內外通信工程及相關學科的現狀和發展趨勢有一定的了解；有嚴謹的科學作風和創新能力；具有獨立對一般的通信系統和網路進行分析、設計和研究開發的能力。能從事現代通信工程和電信網路先進技術研究、設計、開發及教學等方面的高級復合型人才。

學生畢業後適合在電信企業、郵電管理部門、銀行、交通等部門從事通信、電子技術和計算機應用等方面的管理和技術開發工作，也可以在高等學校和研究部門從事教學和科研工作。

主要課程：高等數學、概率論與數理統計、高級程序設計、大學物理及實驗、電路基礎理論、模擬電子技術及實驗、數字電路與邏輯設計及實驗、微型計算機原理及實驗、高頻電路、信號與系統、電磁場與電磁波、微波技術實驗、通信原理、計算機網路、數字信號處理、資訊理論、操作系統、資料庫系統原理、數字通信系統及實驗、無線通信原理、現代電信交換、光纖通信、數字圖象處理、數據結構、單片機原理及應用、計算機視覺等。學生還可選修該學院其他專業的相關課程。

謝謝

㈧ 請高手進來解答一下這道演算法設計與分析的題目，謝謝了！！

設有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si<fi。如果選擇了活動i，則它在半開時間區間[si,fi)內佔用資源。若區間[si,fi)與區間[sj,fj)不相交，則稱活動i與活動j是相容的。也就是說，當si≥fj或sj≥fi時，活動i與活動j相容。

在下面所給出的解活動安排問題的貪心演算法greedySelector:

publicstaticintgreedySelector(int[]s,int[]f,booleana[])

{

intn=s.length-1;

a[1]=true;

intj=1;

intcount=1;

for(inti=2;i<=n;i++){

if(s[i]>=f[j]){

a[i]=true;

j=i;

count++;

}

elsea[i]=false;

}

returncount;

}

由於輸入的活動以其完成時間的非減序排列，所以演算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該演算法的貪心選擇的意義是使剩餘的可安排時間段極大化，以便安排盡可能多的相容活動。

演算法greedySelector的效率極高。當輸入的活動已按結束時間的非減序排列，演算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。

例：設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下：

i 1 2 3 4 5 6 7 8 9 10 11

S[i] 1 3 0 5 3 5 6 8 8 2 12

f[i] 4 5 6 7 8 9 10 11 12 13 14