【转载】一位计算机系研究生的心路历程
时光荏苒，回眸一看，不觉在安大计算机已经过了一学期的研究生生活了.大多数作为计算机学院的研究生，一个很大的误区就是计算机专业毕业出来的研究生都得找编程、写算法方面的工作，于是读研的大部分时间就耗在如何通过增加项目实践经验来充实自己的研究生阶段生活。而以这种作为读研模式的研究生注定了出来找工作很可能还是和一些比较优秀的本科毕业生竞争抢饭碗，most importantly，这不是正确的读研模式。读研究生出来必须能具备本科生所不具备的能力素质和科研修养，要不然研究生学费就白交了，钱是小事，关键是读研所耗费的青春就白白浪费了…多宝贵的3年！很可惜，安大计算机学院大多数实验中心效仿的是这种读研机制…😦
但关键是看个人，如果自己对某个研究方向感兴趣的话可以自己独立钻研，把计算机专业看做一门科学而不是纯粹的工程实践诚然是一个重大的观念性的转折。
下面我引用一篇牛人对攻读计算机专业研究生的一些看法：
如果你有实际开发工作经验，感觉自己的水平和实力进入了一个高原期，迫切需要从理论上提高，那么计算机学院是唯一选择。因为计算机学院才能让你在理论上更上一层楼。软件学院从教学计划上就没有把你往这方面带。当然 ...
到了哈佛，你就知道
到了哈佛，你才知道真正的精英并不是天才，都是要付出更多努力的人。
日前，两张美国哈佛大学图书馆凌晨4点多学生仍在学习的照片，在网上迅速传播。照片显示：凌晨4点的哈佛大学图书馆里，灯火通明，座无虚席……图片配文这样写道：哈佛是一种象征。人到底有怎样的发挥潜力？人的意志，人的才情，人的理想，为什么在哈佛能兑现？哈佛的学生餐厅，很难听到说话的声音，每个学生端着比萨可乐坐下后，往往边吃边看书或是边做笔记。我就没见过哪个学生光吃不读的，更没见过哪个学生边吃边闲聊的。感觉哈佛，餐厅不过是一个可以吃东西的图书馆，是哈佛正宗100个图书馆之外的另类图书馆。哈佛的医院，同样的宁静，同样的不管有多少在候诊的人也无一人说话，无一人不在阅读或记录。医院仍是图书馆的延伸。于是，哈佛产生的诺贝尔奖得主有33位。哈佛产生的美国总统有7位。
哈佛校园里，不见华丽服饰，不见浓妆异彩，更不见晃里晃荡，只有匆匆的脚步，坚实地写下人生的篇章。哈佛不是神话，哈佛只是一个证明，人的意志，精神，抱负，理想的证明。
央视《世界著名大学》制片人谢娟曾带摄制组到哈佛大学采访。她告诉人们：我们到哈佛大学时，是半夜2点，可让我们惊讶的是，整 ...
散列表
table th:nth-of-type(1){
width: 10%;
}
table th:nth-of-type(2){
width: 6%;
;
}
table th:nth-of-type(3){
width: 6%;
}
table th:nth-of-type(4){
width: 6%;
}
table th:nth-of-type(5){
width: 6%;
}
table th:nth-of-type(6){
width: 5%;
}
table th:nth-of-type(7){
width: 5%;
}
table th:nth-of-type(8){
width: 5%;
}
table th:nth-of-type(9){
width: 5%;
}
table th:nth-of-type(10){
width: 5%;
}
table th:nth-of-type(11){
width: 5%;
}
table th:nth-of-type(12){
width: 5%;
}
table th:nth-of-type(13){
width: 5%;
...
继续
一位音乐系的学生走进练习室。在钢琴上，摆着一份全新的乐谱。
“超高难度 …… ”他翻动着乐谱，喃喃自语，感觉自己对弹奏钢琴的信心似乎跌到了谷底，消靡殆尽。
已经三个月了！自从跟了这位新的指导教授后，不知道，为什么教授要以这种方式整人。
勉强打起精神。他开始用十指奋战、奋战、奋战 …… 琴音盖住了练习室外教授走来的脚步声。
指导教授是个极有名的钢琴大师。授课第一天，他给自己的新学生一份乐谱。“试试看吧！”他说。乐谱难度颇高，学生弹得生涩僵滞，错误百出。“还不熟，回去好好练习！”教授在下课时，如此叮嘱学生。
学生练了一个星期，第二周上课时正准备让教授验收，没想到教授又给了他一份难度更高的乐谱，“试试看吧！”上星期的课，教授提也没提。学生再次挣扎于更高难度的技巧挑战。
第三周。更难的乐谱又出现了。同样的情形持续着，学生每次在课堂上都被一份新的乐谱所困扰，然后把它带回去练习，接着再回到课堂上，重新面临两倍难度的乐谱，却怎么样都追不上进度，一点也没有因为上周的练习而驾轻就熟的感觉，学生感到越来越不安，沮丧和气馁。
教授走进练习室。学生再也忍不住了。它必须向钢琴大师提出这三个月来何以不断折磨自己的 ...
表排序、桶排序、基数排序
table th:nth-of-type(1){
width: 10%;
}
table th:nth-of-type(2){
width: 10%;
;
}
table th:nth-of-type(3){
width: 10%;
}
table th:nth-of-type(4){
width: 10%;
}
table th:nth-of-type(5){
width: 10%;
}
table th:nth-of-type(6){
width: 10%;
}
table th:nth-of-type(7){
width: 10%;
}
table th:nth-of-type(8){
width: 10%;
}
table th:nth-of-type(9){
width: 10%;
}
表排序
表排序(间接排序)
当每一个待排序的元素都非常大，一本书，一部电影等，移动元素的代价比较大
选择不移动元素而移动指向他们的下标
定义一个数组作为“表”(table)
例：table(以插入排序为例)
A
[0]
[1]
[2]
[3]
[4]
[5]
[6]
...
堆排序、归并排序
堆排序
堆排序伪代码描述：(自底向上建堆)
建立最大堆，将最大的元素存在数组末尾)
void Heap_Sort(ElementType A[],int N)
{
for(i=N/2-1;i>=0;i--) //BuildHeap
PercDown(A,i,N);
for(i=N-1;i>0;i--) //DeleteMax(取出最大元素并在0-i之间构建最大堆)
Swap(&A[0],&A[i])
PercDown(A,0,i);
}
将较大的元素放到最后，然后将前面的元素重新建立最小堆
注意，在常规的堆中第0个元素应该存放哨兵，但是对某个数组进行排序时数组可能并没有存放哨兵，此时
对于下标为i的元素，其左、右孩子的下标分别为：2i+1, 2i+2
定理：堆排序处理N个不同元素的随机排列的平均比较次数是2N ...
希尔排序、快速排序
希尔排序
希尔排序(by Donald Shell)：基于插入排序，利用插入排序的简单，同时每次交换相隔较远的元素，使得每次消去不止一个逆序对
定义增量序列元素 D(M)>D(M-1)>…>D(1)=1
对每个D(k)进行“D(k)-间隔”排序(k=M,M-1,…,1)
“D(k)-间隔”有序的序列，在执行“D(k-1)-间隔”排序后，仍然是“D(k)-间隔”有序的
例：[81,94,11,96,12,35,17,95,28,58,41,75,15][81,94,11,96,12,35,17,95,28,58,41,75,15][81,94,11,96,12,35,17,95,28,58,41,75,15]
5-间隔–分为5组
[81,35,41][81,35,41][81,35,41],[94,17,75][94,17,75][94,17,75],[11,95,15][11,95,15][11,95,15],[96,28][96,28][96,28],[12,58][12,58][12,58]
[35,41,81][35,41,81][35,41,81 ...
简单排序
排序
前提：void X_Sort(ElementType A[],int N)
本文及后续章节希尔排序、快速排序、堆排序、归并排序、表排序、桶排序、基数排序中在介绍排序算法时，函数头都有统一的范式为X_Sort
大多数情况下，为简单期间，讨论排序的情况默认是从小到大的整数排序(任何一种数据结构，只要可以比较都可以采用排序算法)
N是正整数
只讨论基于比较的排序(>,=,<的情况均有定义)
只讨论内部排序(内存空间足够大，所有数据都可以一次性导入内存中，排序在内存中一次性完成)
稳定性：任意两个相等的数据，排序前后的相对位置不发生改变
没有一种排序是在任何情况下都表现最好的
冒泡排序
冒泡排序伪代码描述
void Bubble_Sort(ElementType A[],int N)
{
for(P=N-1;P>=0;P--){
flag=0;
for(i=0;i<P;i++){ //一趟冒泡 ...
AOV、AOE网络与拓扑排序
AOV(Activity On Vertex)网络
顶点表示活动，边表示活动之间的优先关系
拓扑排序
拓扑序：如果图中从v到w有一条有向路径，则v一定排在W之前，满足此条件的顶点序列成为一个拓扑序
获得一个拓扑序的过程就是拓扑排序
AOV如果有合理的拓扑序，则必定是有向无环图(Directed Acyclic Graph, DAG)
v必须在w开始之前结束
拓扑排序算法伪代码描述：
void TopSort()
{
for(cnt=0;cnt<nv;cnt++)
{
v=为输出的入度为0的顶点; //O(v)
if(这样的v不存在) //如果外循环还没结束就已经找不到入度为0的顶点，则说明剩下的顶点中没有入度为0的顶点，存在回路
{
ERROR("图中有回路");
break;
}
输出v，或者记 ...
最小生成树问题
最小生成树问题
什么是最小生成树(Minimum Spanning Tree, MST)？
是一棵树
连通，无回路
|V|个顶点一定有|V|-1条边
向生成树中任加一条边都一定构成回路
是生成树
包含图的全部顶点
它的|V|-1条边都包含在图中
边的权重和最小
推论：最小生成树存在<->图连通
最小生成树问题中的贪心算法策略
什么是"贪"
每一步都要最好的
什么是"好"
选择权重最小的边
需要的约束
只能用图里有的边
只能正好用掉|v|-1条边
不能有回路
Prim算法——让一棵小树长大(归并点)
类似于Dijkstra算法，只需将访问的结点按顺序收录进入最小生成树MST即可
Prim算法伪代码描述：
void Prim()
{
MST={S};
while(1)
{
V=未收录顶点中dist最小者;
if(这样的v不存在)break;
将v收录进M ...
