算法设计活动安排实验

㈠ 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