中国科技大学算法导论_第二次实验报告
第二次实验报告红黑树
1.红黑树
1.1 需求分析
本实验要求实现红黑树各种操作如SEARCH ，PREDECESOR ，SUCCESSOR ，MINIMUM，MAXIMUM，INSERT，DELETE 等。
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途
是实现关联数组。它是在1972 年由Rudolf Bayer 发明的，他称之为"对称二叉B 树"，它现代的名字是在Leo J. Guibas 和Robert Sedgewick 于1978 年写的一篇论文中获得的。它是
复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强
制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
1. 每个结点或红或黑。
2. 根结点为黑色。
3. 每个叶结点(实际上就是NULL 指针)都是黑色的。
4. 如果一个结点是红色的,那么它的周边3 个节点都是黑色的。
5. 对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一
样。这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能
路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
要知道为什么这些特性确保了这个结果，注意到属性5 导致了路径不能有两个毗连的红
色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据属性4 所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本文中我们使用"nil 叶子" 或"空(null)叶子"。
1.2 算法设计
操作SEARCH,，PREDECESOR，SUCCESSOR，MINIMUM，MAXIMUM 与二查检索
树的对应操作几乎相同。这里只介绍旋转、插入、删除。
1.2.1 旋转
由于插入、删除操作对树作了修改，结果可能违反红黑树的五个性质。为保持这些性质，就要改变树中某些结点的颜色以及指针结构。指针结构的修改通过旋转来完成。
当在某个结点x 上做左旋时，假设它的有孩子y 不是nil[T]，左旋以x 与y 之间的链为“支轴”进行。它使y 成为该子树新的根，x 成为y 的左孩子，而y 的左孩子成为x 的孩子。右旋与左旋对称。左旋代码如下：
void RBLeftRotate(RBTree * T,RBTreeNode * x)
{
RBTreeNode * y = x->right;
x->right = y->left;
if(y->left != T->NIL)
y->left->parent = x;
y->parent = x->parent;
if(x->parent == T->NIL)
T->root = y;
else if(x->parent->left ==x)
x->parent->left = y;
else
x->parent->right =y;
y->left = x;
x->parent = y;
}
1.2.2 插入
向一颗含n 个结点的红黑树插入一个结点z 的操作可在O(lgn)时间完成。利用二叉查找树的Tree_Insert 过程，将z 插入树内，并将其着红色。为保证红黑树的性质，调用RB_INSERTT_FIXUP 来对结点重新着色并旋转。RB_INSERTT_FIXUP 代码如下：
void RBTreeInsertFixup(RBTree * T,RBTreeNode * z)
{
RBTreeNode * y;
if(z->parent == T->NIL)//z是根节点
{
z->color = BLACK;
return;
}
if(z->parent->color == BLACK)//这种情况下是平衡的
{
return;
}
//一直循环，直到z的父节点的颜色为黑色
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->left)//当z的父节点是z祖父节点的左孩子时
{
y = z->parent->parent->right;//y是z的叔叔
//case1:z的叔叔y 的颜色为红色
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->right)//case2:z的叔叔y 的颜色为黑色并且z是它父节点
的右孩子
{
z = z->parent;
RBLeftRotate(T,z);
}
//case3:z的叔叔y 的颜色为黑色并且z是它父节点的左孩子
z->parent->color =BLACK;
z->parent->parent->color = RED;
RBRightRotate(T,z->parent->parent);
}
}//当z的父节点是z祖父节点的右孩子时
else //如果z的父节点是其祖父节点的右孩子
{
y = z->parent->parent->left;//y是z的叔叔节点
if(y->color == RED)//case1：z的叔叔节点为红色，则z的父节点BLACK，祖父节点RED，叔叔节点BLACK均变色
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->left)//case2:z的叔叔y的颜色为黑色并且z是它父节点的
左孩子
{
z = z->parent;
RBRightRotate(T,z);
}
//case3:z的叔叔y的颜色为黑色并且z是它父节点的右孩子
z->parent->color = BLACK;
z->parent->parent->color = RED;
RBLeftRotate(T,z->parent->parent);
}
}
}
T->root->color = BLACK;
}
当调用RB_INSERTT_FIXUP(T，z)时，while 有三种情况：
Case 1)：z 的叔叔y 是红色
只有在p[z]和y 都是红色的时候才会执行case 1。既然p[p[z]]是黑色的，可以将p[z]和y 都着黑色，再将p[p[z]]着红色保持性质5，然后z=p[p[z]]来重复while 循环。
Case 2）：z 的叔叔y 是黑色，且z 的为p[z]的右孩子
Case 3）：z 的叔叔y 是黑色，且z 的为p[z]的左孩子
Case 2 与case 3 如上图。Case 2 中z 是p[z]的右孩子，利用左旋把case 2 转化为case 3，因为z 与p[z]都是红色的，左旋对结点黑高度和性质5 每影响。在case 3 下可以通过改颜色和旋转的方式到达平衡，并且不再出现红色警戒，因为无需往上遍历。首先我们将红父变成黑色，祖父变成红色，然后对祖父进行右旋转。这样我们可以看到，整颗树的黑高
- 4 -
不变，并且这颗树的左右子树也达到平衡。新的树根为黑色。
1.3 结果分析
根据每次从文件中读的数据，调用RB_Insert()。理论上红黑树结构应为下图，
由实验运行结果知，程序是正确的。
/*
* copyright@nciaebupt 转载请保留此标记
* 所有代码已经在linux g++ 下编译通过，直接拷贝运行即可如有问题欢迎指正* 红黑树（red-black tree）是许多“平衡的”查找树中的一种。
* 红黑树的性质:
* １、每个结点或是红的，或是黑的。
* ２、根结点是黑的。
* ３、每个叶结点（NIL）是黑的。
* ４、如果一个结点是红的，则它的两个儿子都是黑的。
* ５、对每个结点，从该结点到其子孙的所有路径上包含相同数目的黑结点。* 红黑树的结点比普通的二叉查找树的结点多了一个颜色属性。
*/
#include
#include
using namespace std;
//将RED,BLACK颜色值定义成枚举类型
enum RBCOLOR {RED,BLACK};
//定义红黑树节点的数据结构
struct RBTreeNode
{
int key;
RBCOLOR color;
RBTreeNode * left;
RBTreeNode * right;
RBTreeNode * parent;
};
//定义红黑树的数据结构
struct RBTree
{
RBTreeNode * root;
RBTreeNode * NIL;
};
void RBTreeInsertFixup(RBTree * T,RBTreeNode * z);
//实现红黑树的左旋操作
void RBLeftRotate(RBTree * T,RBTreeNode * x) {
RBTreeNode * y = x->right;
x->right = y->left;
if(y->left != T->NIL)
y->left->parent = x;
y->parent = x->parent;
if(x->parent == T->NIL)
T->root = y;
else if(x->parent->left ==x)
x->parent->left = y;
else
x->parent->right =y;
y->left = x;
x->parent = y;
}
//实现红黑树的右旋操作
void RBRightRotate(RBTree * T,RBTreeNode * x) {
RBTreeNode * y = x->left;
if(x->left == T->NIL)
return;
x->left = y->right;
if(y->right != T->NIL)
{
y->right->parent = x;
}
y->parent = x->parent;
if(x->parent == T->NIL)
T->root = y;
else
{
if(x->parent->left == x)
x->parent->left = y;
else
x->parent->right = y;
}
y->right = x;
x->parent = y;
}
//红黑树插入
void RBTreeInsert(RBTree * T,RBTreeNode * z) {
RBTreeNode * y = T->NIL;
RBTreeNode * x = T->root;
while(x != T->NIL)
{
y = x;
if(z->key <= x->key)
x = x->left;
else
x = x->right;
}
z->parent = y;
if(y == T->NIL)
T->root = z;
else
{
if(z->key <= y->key)
{
y->left = z;
}
else
{
y->right = z;
}
}
RBTreeInsertFixup(T,z);
}
//红黑树插入对节点重新着色
void RBTreeInsertFixup(RBTree * T,RBTreeNode * z)
{
RBTreeNode * y;
if(z->parent == T->NIL)//z是根节点
{
z->color = BLACK;
return;
}
if(z->parent->color == BLACK)//这种情况下是平衡的
{
return;
}
//一直循环，直到z的父节点的颜色为黑色
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->left)//当z的父节点是z祖父节点的左孩子时
{
y = z->parent->parent->right;//y是z的叔叔
//case1:z的叔叔y 的颜色为红色
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->right)//case2:z的叔叔y 的颜色为黑色并且z是它父节点的右孩子
{
z = z->parent;
RBLeftRotate(T,z);
}
//case3:z的叔叔y 的颜色为黑色并且z是它父节点的左孩子
z->parent->color =BLACK;
z->parent->parent->color = RED;
RBRightRotate(T,z->parent->parent);
}
}//当z的父节点是z祖父节点的右孩子时
else //如果z的父节点是其祖父节点的右孩子
{
y = z->parent->parent->left;//y是z的叔叔节点
if(y->color == RED)//case1：z的叔叔节点为红色，则z的父节点BLACK，祖父节点RED，叔叔节点BLACK均变色
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->left)//case2:z的叔叔y的颜色为黑色并且z是它父节点的左孩子
{
z = z->parent;
RBRightRotate(T,z);
}
//case3:z的叔叔y的颜色为黑色并且z是它父节点的右孩子
z->parent->color = BLACK;
z->parent->parent->color = RED;
RBLeftRotate(T,z->parent->parent);
}
}
}
T->root->color = BLACK;
}
//中序遍历红黑树
void InorderRBTreeWalk(RBTree * T,RBTreeNode * x)
{
if(x != T->NIL)
{
InorderRBTreeWalk(T,x->left);
cout<
cout<<" "< InorderRBTreeWalk(T,x->right); } } void preorderRBTreeWalk(RBTree * T,RBTreeNode * x) { if(x != T->NIL) { cout< cout<<" "< preorderRBTreeWalk(T,x->left); preorderRBTreeWalk(T,x->right); } } int main(int argc, char **argv) { //15,5,3,12,10,13,6,7,16,20,18,23 RBTree * T = new RBTree; T->NIL = new RBTreeNode; T->NIL->color = BLACK; T->NIL->key = 10000; T->NIL->left = NULL; T->NIL->parent = NULL; T->NIL->right = NULL; T->root = T->NIL; vector // vi.push_back(999); vi.push_back(15); vi.push_back(5); vi.push_back(3); // vi.push_back(1); vi.push_back(13); vi.push_back(6); vi.push_back(7); vi.push_back(70); vi.push_back(16); vi.push_back(20); vi.push_back(18); vi.push_back(23); //建立红黑树 cout<<"\n\ncreate the red-black tree:"< for(vector RBTreeNode * p = new RBTreeNode; p->color = RED; p->key = *it; p->left = T->NIL; p->parent = T->NIL; p->right = T->NIL; cout<<"Insert key : "< RBTreeInsert(T,p); } cout<<"---------------------------------"< //中序遍历红黑树 cout<<"the inOrder the red-black tree is :"< InorderRBTreeWalk(T,T->root); //先序遍历红黑树 cout<<"the preOrder the red-black tree is :"< preorderRBTreeWalk(T,T->root); cout<<"---------------------------------"< return 0; } 《中国科学技术大学学报》征稿须知（官方认证） 《中国科学技术大学学报》是在郭沫若、华罗庚和严济慈等一大批老一辈科学家直接关怀下于1965年在北京创刊的，先后有30位院士担任编委。由中国科学院主管，中国科学技术大学主办，为综合性自然科学核心学术期刊（月刊，国内外公开发行），主要刊登具有创新性、高水平的学术论文和研究成果以及由科学大家或知名教授撰写的反映学科前沿的综述，并且开辟专家论坛，就一些科学热点研究问题进行有益的讨论。 欢迎国内外学者投稿，中英文稿均可。 1 栏目 本刊设研究论文、研究快报、综述和论坛等栏目。 1.1 研究论文介绍某一课题高水平研究成果。来稿要求内容充实，推论严谨，数据可靠、完整，文字精炼，结论正确。可以发表系列论文。 1.2 研究突破简要、快速报道某一研究工作的创新性、高水平的阶段性成果和主要结论。要求方法从简、数据完整，结论明确，篇幅不超过3000字。发表研究快报后，深入研究的论文仍可在国外学术刊物或本刊上全文发表。 1.3 特约评述综述某一重要研究领域的代表性成果，评论研究现状，提出尚待解决的问题，并指明今后研究方向。一般约请科学大家或知名教授撰写，作者亦可向编辑部自荐。 1.4 专家论坛就科学研究热点问题提出解决问题的新思路，发表不同的见解或进行必要的有益讨论。 2 投稿要求和注意事项 2.1 正文书写顺序标题(一般不超过20个汉字)、作者姓名、作者单位，所在城市及邮政编码、中文摘要、关键词(3～8条)、中图分类号（数学稿还须提供AMS Subject Classification）、与中文相对应的英文标题、作者姓名（汉语拼音，姓前名后，姓全大写，名首字母大写）、作者单位译名、英文摘要、英文关键词、正文、参考文献。若为英文稿，题名不超过100个字符，书写顺序同上。 在文稿首页地脚处注明基金资助项目名称及项目号（将作为论文评审时参考的重要背景资料），并对第一作者（姓名，性别，出生年，学位，职称，目前主要从事的研究方向及E-mail）与通讯作者（姓名，学位（博士以上才注），职称（教授以上才注），E-mail及必要的联系电话）简要介绍。通讯作者是课题负责人或导师，要及时负责对读者的问题给予解答。 2.2 对摘要的要求摘要内容应包括有与论文同等量的主要信息，应说明研究目的、采用的方法、研究成果及结论四个部分。中英文摘要需对应。中文摘要约250个汉字，英文摘要约1500个字符。请参照EI，SCI要求，避免使用“This paper,in this paper（本文）”或“I（我）”等，用词要客观，尽量减少不必要的修饰。 2.3 对量、单位及符号的要求文中物理量、计量单位及符号的使用必须符合国际标准和国家标准（GB310093~GB3102-93）。正确书 中国科学技术大学 研究生学习培养过程要求 研究生院、校学位办 2011年4月 目录 关于博士学位标准修订的指导原则 (1) 中国科学技术大学硕士、博士学位授予实施细则 (4) 物理、天文一级学科研究生学习培养过程要求 (12) 关于博士学位标准修订的指导原则 第一条为进一步提高我校研究生的培养质量，提升我校博士教育的国际竞争力，学校研究决定对《中国科学技术大学硕士、博士学位授予实施细则》（校 学位字〔2009〕173号）中涉及博士学位标准——博士授予的资格、条 件与程序等进行修订。 第二条学位标准修订思路 （一）树立“质量优异、追求卓越”的价值与理念； （二）以学生为本，以博士生全面发展为目标； （三）“过程管理”与“出口把关”相结合； （四）培养全球视野，提升国际学术交流能力； （五）数量服从质量，学科差异服从总体质量要求； （六）体现我校博士培养学术标准的国际水平。 第三条校级学位标准为各学科学位标准的最低要求，各分学位委员会可根据自身情况制订高于校级标准的学位标准，但不得低于校级标准，各分 学位委员会所属的一级学科可根据学科特点制订高于分学位委员会标 准的学位标准。 第四条本次博士学位标准的修订为新增要求，原《中国科学技术大学硕士、博士学位授予实施细则》（校学位字〔2009〕173号）中与新要求不一致的，以此指导原则为准，其他要求仍继续实行。 第五条本次博士学位标准修订主要强调如下两项能力的培养与提高。 （一）创造性独立开展科研工作的能力 （二）国际学术交流能力 第六条各分学位委员会根据学科目前发展阶段的实际情况，制订出能够反映上述两项能力的客观的、可测量的、可评价的、国际化的学位标准。 第七条创造性独立开展科研工作的能力——《中华人民共和国学位条例》规定博士的学位标准为“在本门学科上掌握坚实宽广的基础理论和系统深入 的专门知识；具有独立从事科学研究工作的能力；在科学或专门技术上 关于做好2010年度普通全日制本科生转专业工作的通知 各院(系)，2010级本科各学生班： 根据《华中科技大学普通本科学生学籍管理细则》（校教[2010]52号）有关规定，2010年度本科生转专业工作定于本学期末进行，现将有关事项通知如下： 一、申请资格的限定 1.确有专长、兴趣或因生理疾病需要在其它专业学习的2010级本科生均可自愿申请； 2.已被确定为国防生或入学时单列录取标准的特殊专业（如护理学专业）的学生不得申请； 3．以美术科目考试入学的新生不得转入非美术科目的其它专业； 4．每个学生只能申请一个转入专业（包括中英班、中美班、中法班、中德班和中澳班所属的专业）。 二、限制转入专业 信息学科大类各专业及临床医学专业均不受理其它专业学生的转入申请（中英班、中美班、中法班、中德班和中澳班除外）。 三、报名时间、考试时间及考试地点 报名时间：通知发布之日起至2010年12月10日； 考试时间：2010年12月26日； 考试地点由教务处另行通知。 四、办理程序 1．学生到本院（系）教务科报名，填写《华中科技大学本科生转 专业申请表》（适用一年级本科生），并经分管教学院长（主任）签署同意转出意见；然后将申请表送交申请转入专业所在院（系）教务科，转入院（系）审核并由分管教学院长（主任）签署拟接收意见；各院（系）教务科于2010年12月13日将申请转入学生的申请表送交教务处学务指导科； 2.申请转入中英班、中美班、中德班和中澳班学生的申请表由国际教育学院统一上报，申请转入中法班学生的申请表由光电子科学与技术学院统一上报； 3.学生所在院（系）负责通知学生参加转专业课程考试的时间和地点； 4．转入院（系）根据学生的考试成绩和特长，确定接收学生名单； 5．学校教务处审核并报校领导批准。 五、其它注意事项 1.本科生转专业事关学生的权益,各院(系)应充分重视学生的个性发展和专业选择,务必将此项工作及相关政策传达到2010级每一位学生。同时，院（系）要根据本单位实际情况，确定转出与转入学生的适当数量（批准转出报名参加相关考试的学生比例不得超过该年级学生总数的20%），妥善做好各项工作； 2．学生应在充分了解各专业基本情况的基础上，根据自己的特长、兴趣提出转入专业申请，申请专业一旦得到批准，不得再转回原院（系 《大数据算法》实验教学大纲 大纲制定（修订）时间： 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）能够独立分析程序运行结果，分析算法性能。 五、实验内容和学时分配 一、实验目的 （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 中国科学技术大学学术委员会章程 第一章总则 第一条为实施科教兴国战略，落实科学发展观，努力把我校建成世界一流研究型大学，依据《中华人民共和国高等教育法》第四十二条和教育部有关规章，结合我校实际情况，特制定本章程。 第二条中国科学技术大学学术委员会（以下简称“校学术委员会”）是学校的学术审议、评议和咨询机构。 第三条校学术委员会遵循“学术优先、以人为本、协调发展、科学管理”的办学思路，坚持公平、公正、公开的原则，维护学校学术声誉，倡导学术自由，鼓励学术创新，弘扬科学精神，树立优良的学风，服务学校战略需求。 第二章组成 第四条校学术委员会由学术造诣高、学风端正、坚持原则的教授（或相应专业技术职务的专家）组成。成员由各院系和直属科研单位根据其正高级专业技术职务人数和学科分布按比例推荐，由校长工作会议讨论确定，校长聘任，校长可根据工作需要直接聘任不超过总数五分之一的委员。 第五条校学术委员会设主任1名，副主任若干名，秘书长1名，人选由校长工作会议提名，校学术委员会全体会议讨论通过，校长聘任。校学术委员会下设办公室，办公室挂靠科学技术处。 第六条校学术委员会可根据工作需要成立若干常设或临时性的评议组、评审组和专题组。 第七条每届校学术委员会委员任期与学校行政领导班子任期同步，可以连任，但连任总人数不超过上届总人数的三分之二。委员因故需要替换时，补缺人选由校学术委员会主任会议提出，报校长工作会议讨论确定，校长聘任。委员的撤换由校学术委员会主任会议提出，并经全体委员半数以上通过，报校长工作会议讨论确定。校学术委员会主任会议成员由主任、副主任和秘书长组成。 第八条学院、直属系及直属科研单位成立分学术委员会。分学术委员会主任、副主任和委员按一定的组织程序民主产生。分学术委员会参照本章程制定本单位学术委员会章程，并提出委员人选，报校学术委员会主任会议批准后执行。各类重点实验室应根据相应的管理办法成立学术委员会并制定章程。 第三章职责 第九条审议学科与专业的设置、学科和科学研究发展规划、院系调整和学校其他学术工作。 第十条评定并推荐申报各类优秀人才、创新团队、科研项目、科研基地和科研成果；评审学校各类科研基金支持的项目。 第十一条接受校长委托对有关学科建设、人才培养、学术研究、创新平台和队伍建设等重大事宜提供咨询意见。 第十二条承担学校学风维护和学术道德建设的有关工作，调查和评议学术纠纷和学术失范行为，调查结果交由学校有关部门处理。 课程设计报告 题目弹球小游戏 姓名方成 学号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）实现奖励机制及关卡机制 四、开发工具与平台 从中科大出发，转专业申请CS，2017我的申请小结（世毕盟学员） 基本背景 学校：中国科学技术大学 专业：统计学 GPA: 3.96 / 4.30 TOEFL: 109 GRE: 156 + 167 + 3.0 实习：三个月京东算法工程师实习 科研：美国八个月科研实习 最终去向：UIUC CS MS 1、前言 申请季已经结束，即将开始新的旅程。非常感谢家人对我毫无保留的支持，感谢挚友们对我的鼓励，感谢GGU的mentor Tony（Stanford CS PhD）和培训师明月姐一路上的帮助。这篇小小的文章是对自己近一年生活的一个总结，如果我的些许经历能带给后来人一点启发，那会是非常美妙的惊喜。 2、实习 & 初识GGU 在今年申请的时候我已经不是应届毕业生了。虽然本科期间一直有着出国留学的坚定信念，也早早结束了TOEFL和GRE的考试，但是大三期间，对于申请时专业的选择越来越感到迷茫——我本科专业是统计学，但是我对于机器学习的应用方向非常感兴趣，不知道是否应该申请统计学还是计算机科学的研究生。恍恍惚惚了大半年之后，我决定找机会去行业里面亲自看一看。很幸运地，我申请到了京东算法工程师岗位的实习机会，也算是积攒了一些CS方面的实战经验。 GGU的口碑一直很好，借着大四上学期在北京实习的机会，我特意去五道口拜访 了GGU ( 现在科大的同学们不用这么麻烦啦，GGU已经有了科大分部 )。龚老师以及各位培训师非常专业，也非常nice，给的建议很中肯。鉴于我之前的科研经历比较缺乏，GGU的老师建议我gap一年，努力申请国外的科研机会，为第二年的申请做好准备。其实我当时已经做好了gap一年的打算，但是没法下定决心。GGU对我的情况进行了非常透彻的分析，如果不是GGU负责任地鼓励我gap，我可能始终没法坚定地前行。 3、海外科研 从我接触到的很多申请者的情况来看，海外科研在申请过程中起的作用越来越大，几乎成为了每个人的标配。与此同时，从另一个角度来说，如果没有海外科研经历，那么在申请过程中就已经比别人落下了一大截。 我当时海外科研的申请最终有了两个备选offer，地理位置都是在美国，一个方向是经典的统计理论，另一个方向是机器学习的应用，GGU的培训老师非常热心地帮我向前辈打听两所学校和教授的特色，正是基于GGU搜集到的信息，我最终选择了进行机器学习方向的实习。从某种意义上说，那时候开始，我正式开始了转专业申请的道路。在京东和美帝实习过程中，我越来越发现自己真正的兴趣点在机器学习的应用领域，然而我最开始确定的申请方向是统计学。纠结许久，我最终于七月底向GGU申请更换了方向。实习过程中mentor作为CS领域的大拿，给了我很多科研方面的意见，获益良多。这里要感谢GGU灵活的制度以及mentor 的付出。 4、正式申请 养兵千日，用兵一时。经过漫长的准备，终于要迎来网申了。说“漫长的准备”一点不为过，因为从暑期开始，明月姐就开始督促我写出PS和CV的草稿，从夏天到冬天，PS和CV在明月姐、mentor和GGU外方老师的修改下，易稿数次，如果不是他们的辛勤付出，最终呈现出来的PS和CV不会读起来这么舒服。 网申结束之后是漫长的等待，这期间明月姐和mentor一直鼓励我，鼓励我套磁，鼓励我准备面试，在我心情低落的时候给予我信心。申请是一个非常磨练人的过程，我非常感谢GGU在这一路上的陪伴，这种陪伴在申请路上有温暖人心的力量。 结语 申请只是人生画布上浅浅的一笔，它已经结束，也终将随着时间的流逝慢慢褪去色彩。不断奋发前行，才是在人生这广阔画布上挥毫泼墨的正确方式。希望自己可以始终不忘初心。 重庆大学项目报告 项目题目：跳桩得珠宝问题 学院： 专业班级：计科 年级：2011级 姓名： 学号： 完成时间：2013 年 6 月7 日指导教师：陈波 重庆大学教务处制 项目报告正文 一.问题描述 有m排n列的柱桩，每一排的柱桩从左向右标号为1,2,…,n，且在每个柱桩上预先放好价值不一样的宝石。现在有位杂技演员从第一排的第1号柱桩开始跳跃，每次都必须跳到下一排的柱桩上，且每次跳跃最多只能向左或向右移动一个桩子。也就是说如果现在杂技演员站在第j号桩上，那么他可跳到下一排的第j号桩上，也可跳到下一排的第j-1 (if j>1)或者j+1 (if j 论文题目 University of Science and Technology of China A dissertation for doctor’s degree 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。 作者签名：___________ 签字日期：_______________ 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 □公开□保密（____年） 作者签名：_______________ 导师签名：_______________ 签字日期：_______________ 签字日期：_______________ 摘要 研究生学位论文是研究生在研究工作中所取得成果的集中反映，代表着研究生研究工作的水平，也是申请和授予相应学位的主要依据。 …… 关键词：学位论文…… ABSTRACT Graduate dissertation is a graduate student in research results of concentrated reflection, represents the level of the graduate research work, is also the main basis of application and corresponding degree granted. …… Key Words: dissertation …… 《算法导论》课程实验报告 （院）系数理系 _ _____ 专业 ______ _信息与计算科学________ ____ 班级信科1001班 学号_ 20 08 15__ 学生姓名刘俊伟_ 曹玮王舒斌 指导教师_ 阳卫锋 ______ _____ 《算法导论》实验指导书 实验目标 通过实验，使同学掌握并能熟练运用散列表、贪心算法、动态规划算法。 实验三计数排序 实验目的：掌握利用计数排序进行排序。 实验内容：对数组利用计数排序进行排序。 实验要求： 1）利用计数排序法。 2）记录每一步数组的中元素的变化 代码： import java.awt.BorderLayout; import java.awt.Button; import https://www.sodocs.net/doc/8e5778673.html,ponent; import java.awt.Frame; import https://www.sodocs.net/doc/8e5778673.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); 《数据库原理》实验报告书 班级: 学号: 姓名: 指导教师: 实验成绩: 中南林业科技大学涉外学院理工系 目录 数据库原理实验安排 (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语句完成建表操作并以截屏的方式将建表操作过程粘贴在下方表格中。 实验三：苯酚的紫外光谱绘制及定量测定 姓名：黄日权学号：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、绘制苯酚碱性溶液的标准工作曲线； 图一. 苯酚碱性溶液的标准工作曲线 《中国科学技术大学学报》征稿简则 《中国科学技术大学学报》是在郭沫若、华罗庚和严济慈等一大批老一辈科学家直接关怀下于1965年在北京创刊的，先后有30位院士担任编委。由中国科学院主管，中国科学技术大学主办，为综合性自然科学核心学术期刊（月刊，国内外公开发行），主要刊登具有创新性、高水平的学术论文和研究成果以及由科学大家或知名教授撰写的反映学科前沿的综述，并且开辟专家论坛，就一些科学热点研究问题进行有益的讨论。 欢迎国内外学者投稿，中英文稿均可。 1栏目 本刊设研究论文、研究快报、综述和论坛等栏目。 1.1 研究论文介绍某一课题高水平研究成果。来稿要求内容充实，推论严谨，数据可靠、完整，文字精炼，结论正确。可以发表系列论文。 1.2 研究突破简要、快速报道某一研究工作的创新性、高水平的阶段性成果和主要结论。要求方法从简、数据完整，结论明确，篇幅不超过3000字。发表研究快报后，深入研究的论文仍可在国外学术刊物或本刊上全文发表。 1.3 特约评述综述某一重要研究领域的代表性成果，评论研究现状，提出尚待解决的问题，并指明今后研究方向。一般约请科学大家或知名教授撰写，作者亦可向编辑部自荐。 1.4 专家论坛就科学研究热点问题提出解决问题的新思路，发表不同的见解或进行必要的有益讨论。 2 投稿要求和注意事项 2.1 正文书写顺序标题(一般不超过20个汉字)、作者姓名、作者单位，所在城市及邮政编码、中文摘要、关键词(3～8条)、中图分类号（数学稿还须提供AMS Subject Classification）、与中文相对应的英文标题、作者姓名（汉语拼音，姓前名后，姓全大写，名首字母大写）、作者单位译名、英文摘要、英文关键词、正文、参考文献。若为英文稿，题名不超过100个字符，书写顺序同上。 在文稿首页地脚处注明基金资助项目名称及项目号（将作为论文评审时参考的重要背景资料），并对第一作者（姓名，性别，出生年，学位，职称，目前主要从事的研究方向及E-mail）与通讯作者（姓名，学位（博士以上才注），职称（教授以上才注），E-mail及必要的联系电话）简要介绍。通讯作者是课题负责人或导师，要及时负责对读者的问题给予解答。 2.2 对摘要的要求摘要内容应包括有与论文同等量的主要信息，应说明研究目的、采用的方法、研究成果及结论四个部分。中英文摘要需对应。中文摘要约250个汉字，英文摘要约1500个字符。请参照EI，SCI要求，避免使用“This paper,in this paper（本文）”或“I （我）”等，用词要客观，尽量减少不必要的修饰。 2.3 对量、单位及符号的要求文中物理量、计量单位及符号的使用必须符合国际标准和国家标准（GB3100 93~GB3102-93）。正确书写易混淆的外文字母的文种、大小写、正斜体、黑白体及上下角标。 2.4 对图、照片、表的要求文中图要直观、简明、清晰。图中的文字、符号、纵横坐标必须写清，并与正文保持一致。 图版、照片必须图像清晰，层次分明，请提供矢量图或线条图，不接收扫描图；可根据作者需要印刷彩页。 大学项目报告 项目题目：跳桩得珠宝问题 学院： 专业班级：计科 年级：2011级 姓名： 学号： 完成时间：2013 年 6 月7 日指导教师：波 大学教务处制 项目报告正文 一.问题描述 有m排n列的柱桩，每一排的柱桩从左向右标号为1,2,…,n，且在每个柱桩上预先放好价值不一样的宝石。现在有位杂技演员从第一排的第1号柱桩开始跳跃，每次都必须跳到下一排的柱桩上，且每次跳跃最多只能向左或向右移动一个桩子。也就是说如果现在杂技演员站在第j号桩上，那么他可跳到下一排的第j号桩上，也可跳到下一排的第j-1 (if j>1)或者j+1 (if j 第二章算法入门 由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题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 中国科学技术大学 关于博士生培养工作的有关规定 为了以提高质量为中心积极稳妥地发展研究生教育，特别是博士生教育，逐步把我校建成重要的博士生培养基地，特制定《中国科学技术大学关于博士生培养工作的有关规定》，希望各博士点参照执行。 一、博士生培养目标 较好地掌握马克思主义的基本原理和邓小平理论；热爱祖国、遵纪守法、品德优良、学风严谨；具有追求真理和献身于科学事业的敬业精神和高尚的科学道德。 掌握本学科坚实宽广的基础理论和系统深入的专门知识；了解本专业范围内学科发展的现状和趋势；具有独立从事高水平科学研究的能力；能够在科学研究或专门技术上做出创造性的成果。 二、课程设置 1．根据国务院颁布的学位条例，博士生必须修完所规定的学位课程，并取得学分。 博士研究生的学位课程如下表所列： 马克思主义理论课 54学时 2学分课堂教学为主 英语 126学时2学分课堂教学 基础理论 40学时 2学分课堂讲授与研讨相结合 专业课 40学时 2学分课堂讲授与研讨相结合 硕博连读研究生的课程设置另行规定。 博士研究生应该至少修满11学分，即上述课程学习8学分，必修环节3学分：其中开题报告1学分，作学术报告1学分，参加学术报告1学分。 根据教育部1998年颁发的《关于修订研究生培养方案的指导意见》，博士生至少掌握一门外国语。能够熟练地阅读本专业的外文资料，具有一定的写作能力 和进行国际学术交流的能力。第一外语为英语的博士生是否必修第二外语，由博士点所在学位分委员会决定。第一外语为其他语种者，英语为必修课，且课内学时不 得少于144学时。 2．政治理论课和第一外语课作为博士生的学位课，考试成绩75分为合格。 3．博士研究生的基础理论课和专业课要注重综合性、前沿性和交叉性。内容应包括：加深和拓宽专业知识需要的基础理论和相应的现代实验技术；为进入学科前沿和研究课题需要阅读的学术专著和专题文献。 博士生的课程学习，一般采用在导师指导下阅读学术专著和专业文献为主，教学方法拟采用自学、讲课与研讨相结合。部分专业的博士生课程也可以以课堂讲授为主。 专业必修课的考试由学位分委员会指定三位或三位以上教授组成的考试委员会主持。考试成绩由考试委员会成员共同签字生效。 4．各博士学位授权点均应对本点博士生的知识结构提出要求，具体体现为本科阶段的主要基础理论课程和专业课程、硕士生阶段的 算法设计与分析 学 习 报 告 第一部分学习内容归纳 “计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述。”（参考文献：百度百科）《算法设计与分析》是一门面向设计，在计算机科学中处于核心地位的课程。这门课程主要讲授了在计算机应用中经常遇到的问题和求解的方法，分治法、动态规划法、随机算法等设计算法的基本原理、技巧和算法复杂性的分析，以及计算理论简介。 第一部分“概论和数学准备”在简单了解了算法的基本概念和复杂性、研究步骤等几个重要知识点后，着重学习了算法的数学基础，包括生成函数、差方方程的求解等，主要适用于求解算法的时间复杂性。 “任何可以用计算机求解的问题所需要的计算时间都与其规模有关：问题的规模越小，解题所需的计算时间往往也越短，从而也就比较容易处理。”（参考文献：《计算机算法设计与分析（第3版）》）而第二部分介绍的算法常用技术之首——分治法就运用了这样的思想。分治法的要领在于Divide（子问题的划分）-Conquer（子问题的求解）-Combine（子问题解的组合）。由于子问题和原问题是同类的，递归的思想在分治法中显得尤其重要，它们经常同时运用在算法设计中。这部分内容从Select（求第k小元）算法，寻找最近点对算法和快速傅立叶变换FFT等实际应用中深化对分治法思想的理解，同时也强调了平衡思想的重要性。 第三部分“动态规划”与分治法类似，同样是把问题层层分解成规模越来越小的同类型的子问题。但与分治法不同的是，分治法中的子问题通常是相互独立的，而动态规划法中的子问题很多都是重复的，因此通常采用递推的方法以避免重复计算。然而，也不是所有的情况下都采用递推法，当有大量的子问题无需求解时，更好的方式是采用动态规划法的变形——备忘录方法。通常需要用到动态规划法求解的问题都具有子问题的高度重复性和最优子结构性质两大特征，这也是我们分析问题和设计算法时的关键点。最长公共子序列LCS问题和最优二分搜索树就是从动态规划法的两个主要特征角度分析问题，进而设计出相应的解决算法的。而这部分内容中的另一个问题——流水作业调度，则告诉我们采用动态规划时偶尔也得不到高效的算法，我们要学会将已有的知识灵活运用，适当加工。 第四部分“集合算法”中首先介绍了一种分析算法复杂度的手法——平摊分析（Amortized Analysis）。与之前我们所接触的算法分析方法即逐一考虑执行每条指令所需的时间复杂度再进行累加的方法不同，平摊分析是对若干条指令从整体角度考虑其时间复杂度，通过这样的方法获得的时间复杂度更加贴近实际的情况。平摊分析的主要方法有聚集方法，会计方法和势能方法。聚集方法将指令的时间复杂度分类计算再相加；会计方法采用了耗费提前计算的思想；势能方法引入了势函数的概念，从每步操作的数据结构状态和势函数的关系角度分析得出操作的平摊代价。“集合算法”这一部分主要分析了Union（合并集合）和Find （给出元素所在集合名）这两种运算。从上学期的《数据结构》课程的学习中，我们就已经发现集合和树之间的关系是密不可分的，我们经常用树结构来表示集合。而2-3树是一种特殊的每个内结点都只有2个或3个儿子的树，广泛的应用于可实现Member（查找）、Insert（插入）、Delete（删除）操作的数据结构——字典，可实现Insert、Delete、Union和Min（查找最小叶结点）的数据结构——可并堆，可实现Insert、Delete、Find、Concatenate（保序合并）和Split《中国科学技术大学学报》征稿须知(官方认证)
《中国科学技术大学研究生学习培养过程要求》
华中科技大学 本科生转专业 通知
大数据算法实验教学大纲
动态规划解找零钱问题实验报告
中国科学技术大学学术委员会章程
Java弹球游戏实验报告—chen汇总
从中科大出发,转专业申请CS,2017我的申请小结
重庆大学算法导论跳桩得珠宝问题项目报告(包含报告和源代码)
中国科学技术大学博士学位论文模板
算法导论实验
数据库原理实验报告2012
实验报告
中国科学技术大学学报
重庆大学算法导论跳桩得珠宝问题项目报告(包含报告和源代码)
算法导论第二章答案
中国科学技术大学关于博士生培养工作的有关规定
算法导论学习报告