10.证明：G中最大团的size为a当且仅当Gm里最大团的size是ma
解：
（1）必要性
由定义可知，Gm是不同G中任意两顶点连线以及G中原有边形成的图，不妨设G 中的两个图分别标记为p和q，p中的每一个点与q中的一个点都有边相连，所以假如G中的一个最大团的size为a，以此类推，p与q组合形成G2最大团的size为2a，同理，Gm最大团的size为ma
（2）充分性
对于充分性，即对图中的顶点的删除，每删除一个G最大团中的顶点，G最大团的size都减一，以此类推，显然有Gm最大团的size为ma。
11.证明：当最优调度在任何机器上至多包含2个作业时，LPT也是最优的
解：
不妨设n=2m，若n<2m，则令Jn+1,…,J2m的时间均为0，将其加入I，不妨设
P1≥P2≥…≥P2m.
设最优调度使得每台机器恰有2个作业：Ji和Jj，则必有i≤m,j>m。否则若某最优调度O，有i,j≤m，则定有某台机器上有Js和Jt，使得s,t>m
因为Pi,Pj≥Ps,Pt，交换Pj和Pt，则Pi+Pt≤Pi+Pj，Ps+Pj≤Pi+Pj
交换后的调度O’的最迟完成时间只可能减少，故O’也是最优调度。
对于i,j>m时，因为Pi,Pj≤Ps,Pt，交换Pj和Pt，则Pi+Pt≤Ps+Pt，Ps+Pt≤Ps+Pt，所以必有最优调度使J I,…,Jm分别分配到M1,…,Mm上，当将J m+1,…,J2m分配到M台机器上时，LPT是将长时间的作业分配到轻负载上，必与该最优调度结果相同。
中国科学技术大学模式识别试题 （2012年春季学期） 姓名：学号：成绩： 一、填空与选择填空（本题答案写在此试卷上，30分） 1、模式识别系统的基本构成单元包括：、 和。 2、统计模式识别中描述模式的方法一般使用；句法模式识别中模式描述方法一般 有、、。 3、聚类分析算法属于；判别域代数界面方程法属于。 （1）无监督分类 (2)有监督分类（3）统计模式识别方法（4）句法模式识别方法 4、若描述模式的特征量为0-1二值特征量，则一般采用进行相似性度量。 （1）距离测度（2）模糊测度（3）相似测度（4）匹配测度 5、下列函数可以作为聚类分析中的准则函数的有。 （1） (4) 6、Fisher线性判别函数的求解过程是将N维特征矢量投影在中进行。 （1）二维空间（2）一维空间（3）N-1维空间 7、下列判别域界面方程法中只适用于线性可分情况的算法有；线性可分、不可分都适用的 有。 （1）感知器算法（2）H-K算法（3）积累位势函数法 8、下列四元组中满足文法定义的有。 （1）({A, B}, {0, 1}, {A→01, A→ 0A1 , A→ 1A0 , B→BA , B→ 0}, A) （2）({A}, {0, 1}, {A→0, A→ 0A}, A) （3）({S}, {a, b}, {S → 00S, S → 11S, S → 00, S → 11}, S) （4）({A}, {0, 1}, {A→01, A→ 0A1, A→ 1A0}, A) 二、(15分)简答及证明题 （1）影响聚类结果的主要因素有那些？ （2）证明马氏距离是平移不变的、非奇异线性变换不变的。 （3）画出对样本集 ω1：{(0,0,0)T, (1,0,0)T, (1,0,1)T, (1,1,0)T,} PDF 文件使用 "pdfFactory Pro" 试用版本创建https://www.doczj.com/doc/4211181605.html,
《面向对象编程技术》试卷 注：1）请将答案写在答题纸上，写在试卷上不算分。答题纸在试卷的最后页。 2）交卷时,试卷和答题纸一起交。 一、单选题 (每小题1.5分，共30分) 1. C++中，以下有关构造函数的叙述不正确的是 ______ 。 A. 构造函数名必须和类名一致 B. 构造函数在定义对象时自动执行 C. 构造函数无任何函数类型 D. 在一个类中构造函数有且仅有一个 2．以下叙述不正确的是 ______ 。 A. 在类的定义中，通常是成员变量描述对象的属性；用成员函数描述对象的行为 B. 类的一个成员只能具有一种访问控制属性 C. 构造函数和析构函数是特殊的成员函数，因此不允许重载 D. 通过对象只能访问类的公有成员 3. 以下关于虚函数的叙述不正确的是 ______ 。 A. 虚函数属于成员函数 B. 虚函数不允许说明成静态的 C. 凡是虚函数必须用virtual说明 D. 虚函数可以被继承 4. cout是I0流库预定义的______ 。 A．类 B. 对象 C. 包含文件 D. 常量 5．面向对象程序设计中的数据隐藏指的是______ 。 A．输入数据必须输入保密口令 B．数据经过加密处理 C. 对象内部数据结构上建有防火墙D．对象内部数据结构的不可访问性6．拷贝（复制）构造函数的作用是______ 。 A．进行数据类型的转换 B．用对象调用成员函数 C．用对象初始化对象D．用一般类型的数据初始化对象 7. 下列不是描述类的成员函数的是______ 。 A.构造函数 B.析构函数 C.友元函数 D.拷贝构造函数 8. 如果类A被说明成类B的友元，则______ 。 A. 类A的成员即类B的成员 B. 类B的成员即类A的成员 C. 类A的成员函数不得访问类B的成员 D. 类B不一定是类A的友元 9. 对于任何一个类，析构函数最多有______ 个。 A. 0 B. 1 C. 2 D. n 10. 下列特性中，C与C++共有的是______ 。 A.继承 B.封装 C.多态性 D.函数定义不能嵌套 11. 在公有继承的情况下，基类公有和保护成员在派生类中的访问权限______ 。 A. 受限制 B. 保持不变 C. 受保护 D. 不受保护 12. 通过______ 调用虚函数时，采用动态束定。 A. 对象指针 B. 对象名 C. 成员名限定 D. 派生类名 13. C++ 类体系中，不能被派生类继承的有______ 。 A. 成员转换函数 B. 构造函数 C. 虚函数 D. 静态成员函数 14. 假定 ab 为一个类，则执行 ab x；语句时将自动调用该类的______ 。 A. 有参构造函数 B. 无参构造函数 C. 拷贝构造函数 D. 赋值构造函数 15. 静态成员函数不能说明为______ 。 A. 整型函数 B. 浮点函数 C. 虚函数 D. 字符型函数 16. 在 C++ 中，数据封装要解决的问题是______ 。 A. 数据规范化排列 B. 数据高速转换 C. 避免数据丢失 D. 保证数据完整性
一、概念题： （1）排序算法时间复杂度： 排序算法最好最坏平均 插入O(n)O(n2)O(n2) 归并O(nlogn)O(nlogn)O(nlogn) 快排O(nlogn)O(n2)O(nlogn)排序算法空间复杂度： 1、所有简单排序和堆排序都是0(1) 2、快速排序为0(logn)，要为递归程序执行过程栈所需的辅助空间 3、归并排序和基数排序所需辅助空间最多，为O(n) （2）渐近记号 1、渐近确界：Θ(g(n))={f(n):存在正常数c1和c2和n0，使对所有的n>= n0，都有0<=c1g(n)<=f(n)<=c2g(n)}。大Θ记号给出函数的渐进确界。 2、渐近下界：Ω(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=cg(n)<=f(n)}。大Ω记号给出函数的渐进下界。 3、渐近上界：O(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=f(n)<=cg(n)}。大O记号给出函数的渐进上界。 （3）二叉查找树： 执行基本操作的时间与树的高度成正比。搜索、插入、删除的复杂度等于树高，期望O(lgn)，最坏O(n)（数列有序，树退化成线性表） （4）红黑树： 1、时间复杂度： 基本动态集合操作：O(log n)，n是树中元素的数目。 2、性质： 1)节点是红色或黑色。 2)根节点是黑色。 3)每个叶节点（NIL节点）是黑色的。 4)如果一个结点是红的，则它的两个儿子都是黑的（不能有两个连续 红结点） 5)从任一节点到其子孙结点的所有路径都包含相同数目的黑色节点。 3、相关概念，定理： 1）黑高度：从某个结点出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度，bh(x)。红黑树的黑高度定义为其根节点的黑高度。 2）一颗有n个内结点的红黑树的高度至多为2lg(n+1)。(用2-3-4树理解) 3）在一颗黑高度为K的红黑树中，总结点数最多有22k+1-1，此时内结点
一、给定关系 R(A,B) 和 S(B,C) ，将下面的关系代数表达式转换为相应的SQL语句： π (attribute-list) [ (condition) [ R ? S ] ] 二、Megatron 747 磁盘具有以下特性： 1）有8个盘面和8192个柱面 2）盘面直径为英寸，内圈直径为英寸 3）每磁道平均有256个扇区，每个扇区512字节 4）每个磁道10％被用于间隙 5）磁盘转速为 7200 RPM 6）磁头启动到停止需要1ms，每移动500个柱面另加1ms 回答下列有关Megatron 747的问题（要求写出式子并且计算出结果，精确到小数点后两位）： 1）磁盘容量是多少GB 2）如果一个块是8KB，那么一个块的传输时间是多少ms 3）平均寻道时间是多少ms 4）平均旋转等待时间是多少ms 三、下面是一个数据库系统开始运行后的undo/redo日志记录，该数据库系统支持simple checkpoint （1）（2）（3） 1)
211大学介绍 (2014-03-21 18:37:56) 转载▼ 我国 211大学 第一档 （财经类）：中央财经大学、上海财经大学、对外经济贸易大学、西南财经大学、中南财经政法大学 （专属类）：北京外国语大学、上海外国语大学、中国政法大学、中国传媒大学、中央音乐学院、北京体育大学 （理工类）：北京邮电大学、华北电力大学、北京交通大学、北京科技大学、南京航空航天大学、西安电子科技大学、华东理工大学、南京理工大学 第二档 （理工类）：西南交通大学、哈尔滨工程大学、武汉理工大学、北京化工大学、北京工业大学、河海大学、大连海事大学 （综合类）：上海大学、暨南大学、苏州大学 （医药类）：天津医科大学、北京中医药大学、中国药科大学 第三档 （综合类）：郑州大学、福州大学、安徽大学、南昌大学、西北大学 （理工类）：东华大学、长安大学、江南大学、合肥工业大学、河北工业大学、太原理工大学 （师范类）：华中师范大学、华南师范大学、西南大学、东北师范大学、陕西师范大学、南京师范大学、湖南师范大学 （专属类）：中国石油大学、中国地质大学、中国矿业大学 第四档 （边远类）：云南大学、贵州大学、广西大学、海南大学、辽宁大学、内蒙古大学
（边远类）：宁夏大学、青海大学、新疆大学、西藏大学、延边大学、石河子大学 （农林类）：北京林业大学、华中农业大学、南京农业大学、东北农业大学、东北林业大学、四川农业大学 下面对211大学的分档进行一下简单的说明 一、排名依据 主要依据是2011年所有大学在全国31个省市的理科平均录取分的平均值的排名。 二、最热门的211 在一档211大学中，最热门的几所大学为中央财经大学、上海财经大学、对外经济贸易大学、北京外国语大学、北京邮电大学这五所。他们的录取分数排在前20名，和二档的985大学可以一争天下。 二档985中只有同济大学、南开大学、北京航空航天大学、西安交通大学可以和他们抗衡。 连著名的中山大学、武汉大学、厦门大学、天津大学，哈尔滨工业大学、华中科技大学，东南大学这些老牌的二档985的分数都没有他们高。可见这五所211大学是何等的热门。 三、一档211财经类 1、中央财经大学 号称我国银行家的摇篮，在金融街的校友资源全国第一，主要是政治定位，需要一所高水平的财经类院校在北京首都。中央财经大学最好的专业是金融学院的金融、金融工程、国际金融。 2、上海财经大学 上海财经大学是全国最著名的财经类大学，全国财经院校综合实力前五，经济学实力全国前十。加上地处上海这个金融大都市、全国金融中心，上海财大的未来将更加辉煌。最好的学院是会计学院、金融学院、商学院、经济学院、国际工商管理学院。 会计学院是第一大王牌大院。国际会计班包括ACCA、CGA、美国会计师。 国际会计班的CGA和ACCA比较好，美国会计证书很难考。非国际会计班包括会计学、注册会计师、财务管理。
Pattern Recognition Lecture0 Introduction Feb. 19th, 2009
?任课教师 –唐珂ketang@https://www.doczj.com/doc/4211181605.html,; –电话：3600754 ?助教 –林民龙sunnyboy@https://www.doczj.com/doc/4211181605.html, ?课程主页 https://www.doczj.com/doc/4211181605.html,/~sunnyboy/pr/
主要内容 ?0.1 课程内容介绍 –课程内容、特点和授课方式 –教材和主要参考书目 ?0.2 课程要求 –考核和评分要求 ?0.3 模式识别导论 –什么是模式识别? –为什么需要模式识别? –模式识别在计算机科学中的地位 –模式识别系统框架 –模式识别研究领域的重要科学问题
0.1 课程内容介绍 ?课程内容： –模式识别系统模型和基本知识； –模式识别算法：贝叶斯方法、判别分析、神经网络、决策树、聚类算法等； –特征分析方法：特征选择、特征提取； –模式识别理论及系统评估方法。 ?课程特点： –介绍各种模式识别方法 –学习结束后，应能大致了解本领域的研究现状，并会用基本的模式识别方法解决自己科研中的相关问题。?学习方式： –课程讲授、平时作业和课堂讨论相结合
0.1 教材和主要参考书目 ?教材： ?Richard.O.Duda, P.E.Hart, D.G.Stork； 《模式分类》，机械工业出版社，2005年。 ?主要参考书目： – A. R. Webb, Statistical Pattern Recognition. John Wiley & Sons, London, (2002). –T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, 2001. –边肇祺，张学工；《模式识别》，清华大学出版社，2004年
1.ipv4 的替代方案； 2.单链表原地逆向转置； 3.折半查找算法 4.简述操作系统中系统调用过程； 5.在数据库中什么是关系，它和普通二维表啥区别； 6.什么是原子操作； 7.路由协议有哪些； 8.进程的三种状态，以及之间转换的过程； 9.快速排序的基本过程； 10.什么叫视图？视图在数据库的第几层； 11.二叉树的搜索； 12.什么叫冲突？解决冲突的办法都有哪些； 13.java 与 C++区别； 14.深度、广度搜索的过程； 15.迪杰斯克拉算法的过程； 16.关系模式和关系； 17.数据链路停发协议，就是流量控制； 18.虚拟存储器及相关算法；段存储器； 19.进程线程树图； 20.传输等待协议； 21.堆栈排序及其与快速排序的不同； 22.386 的保护模式是什么； 23.页表； 24.ER图； 25.关系范式 26.链表查询某个元素，平均时间复杂度是多少； 27.路由协议有哪些； 28.网络服务质量包括哪些方面； 29.并发控制是为了保证事务的？； 30.什么是 DMA； 31.两个时钟不同步的设备怎么通信； 32.操作系统的调度算法有哪些； 33.单链表的原地逆置算法 34.数据库的两级模式以及它们的关系和作用（貌似是这样） 35.操作系统的进程调度算法有哪些，并介绍其中两种 36.计算机的一条指令有几个机器周期，为什么 37.原子操作， pv 操作的要点和注意事项 38.内核、芯片（记不清了） 39.DMA控制器的组成和工作原理 40.简述最短路径的迪杰斯特拉算法 41.什么是 P 操作与 V 操作。 42.一个深度为 N的满二叉树有多少个结点。 43.实现一个队列的方法 44.折半查找调节与时间复杂度
中科大考博辅导班：2019中科大软件学院考博难度解析及经验分享中国科学院大学2019年博士研究生招生统一实行网上报名。报考者须符合《中国科学院大学2019年招收攻读博士学位研究生简章》规定的报考条件。考生在报考前请联系所报考的研究所(指招收博士生的中科院各研究院、所、中心、园、台、站)或校部相关院系，了解具体的报考规定。 下面是启道考博辅导班整理的关于中国科学技术大学软件学院考博相关内容。 一、院系简介 中国科学技术大学是中国科学院直属的唯一院校，是一所以前沿科学和高新技术为主、科技人文与科技管理兼备的综合性全国名校，为国家教育重点建设的9所世界知名高水平研究型大学之一，在国际上享有较高的声誉。学校力争在2018年建校60周年前后，把学校建设成为“规模适度、质量优异、结构合理、特色鲜明”的世界知名的高水平研究型大学。目前，校本部共有10个学院、25个系和少年班，43个本科专业；一级学科博士学位授权点17个，国家重点学科19个，二级学科博士学位授权点89个，二级学科硕士学位授权点105个，有工商管理（MBA）、公共管理（MPA）和工程硕士3个专业硕士学位授权点；17个博士后流动站，45个博士后流动站专业，具备培养学士、硕士、博士的完整教育体系。其严谨务实的学风、创新探索的精神、高水平级的成果、国际化办学的追求，都使得这所年轻的研究型大学受到国际社会越来越强的关注 二、招生信息 中国科学技术大学软件学院博士招生专业有1个： 085271电子与信息 研究方向：不区分研究方向 三、报考条件 （1）中华人民共和国公民；拥护中国共产党的领导，愿意为祖国社会主义现代化建设服务；品德良好，遵纪守法，学风端正，无任何考试作弊、学术剽窃及其它违法违纪行为； （2）身体健康状况符合我校规定的体检要求，心理正常； （3）申请者原则上应来自国内重点院校或所在高校学习专业为重点学科； （4）专业基础好、科研能力强，在某一领域或某些方面有特殊学术专长及突出学术成果； （5）对学术研究有浓厚的兴趣，有较强的创新意识、创新能力和专业能力；
专业代码及名称培养单位代码招生类专业代码及名称培养单位代码招生类别 070121★数学物理001 硕，博3 623 数学分析《数学分析教程》常庚哲中国科大出版社数学分析：极限、连续、微分、积分的概念及性质 4 802 线性代数与解析几何《线性代数》李炯生中国科大出版社《空间解析几何简明教程》吴光磊高等教育出版社线性代数：行列式，矩阵，线性空间线性映射与线性变换，二次型与内积；解析几何：向量代数，平面与直线，常见曲面 070201理论物理004 硕、博 3 62 4 普通物理A 中国科大、北大或其他高校物理系普通物理教材力学、电磁学、原子物理 4 811 量子力学《量子力学》第一卷曾谨言科学出版社第三版量子力学的概念和基本原理、波函数和波动方程，一维定态问题、力学量算符与表象变换，对称性及守恒定律、中心力场、粒子在电磁场中的运动、定态微扰论、量子越迁 070202粒子物理与原子核物理004 硕、博 3 62 4 普通物理A 中国科大、北大或其他高校物理系普通物理教材力学、电磁学、原子物理 4 811 量子力学《量子力学》第一卷曾谨言科学出版社第三版量子力学的概念和基本原理、波函数和波动方程，一维定态问题、力学量算符与表象变换，对称性及守恒定律、中心力场、粒子在电磁场中的运动、定态微扰论、量子越迁 070203原子与分子物理004 硕、博 234 硕、博 3 62 4 普通物理A 中国科大、北大或其他高校物理系普通物理教材力学、电磁学、原子物理 4 83 5 原子物理与量子力学《近代物理学》徐克尊高等教育出版社《原子物理学》杨福家高等教育出版社第三版《原子物理学》褚圣麟高等教育出版社《量子力学导论》曾谨言高等教育出版社原子结构和光谱、分子结构和光谱、量子力学概论 070204等离子体物理004 硕、博 4 808 电动力学A 《电动力学》郭硕鸿高等教育出版社第二版电磁现象的普遍规律，静电场和静磁场，电磁波的传播，电磁波的辐射（包括低速和高速运动带电粒子的辐射），狭义相对论 4 872 等离子体物理导论《等离子体物理导论》F. F. Chen科学出版社1980《等离子体物理原理》马腾才胡希伟陈银华中国科大出版社1988 单粒子理论、等离子体平衡、等离子体波动、等离子体不稳定性 070205凝聚态物理002 博 203 硕 3 62 4 普通物理A 中国科大、北大或其他高校物理系普通物理教材力学、电磁学、原子物
2015年 7.在异步环上，一个O(n^2)的leader选举算法按顺时针单向发送消息，假设只有最大的标识符节点可以当选为leader,则当环上标识符次序为_________时该算法发送的消息数量最多。 A 0,1, … , n-1 随机 b逆时针 n-1,n-2,…,0 C 顺时序 0,1，…, n-1 d 顺时针 n-1,n-2,…,0 8.设正整数d1,d2,…,dn是n个结点的标识符集合，x = min(d1,d2,…,dn),y = max(d1,d2,…,dn)，则同步环上非均匀的leader选举算法的时间复杂性是_______ A O(n) b O(xn) c (yn) d O(nlogn) 9.在下述因素中，已知有3个阻碍分布式系统了解系统全局状态，与全局状态无关的是____ A 非及时的通信b 相对性影响c中断d算法的正确性 10. 下述说法错误的是___ A 异步系统中的消息延迟是不确定的 B 分布式算法的消息复杂性是指在所有合法的执行上发送消息总数的最大值 C 在一个异步算法中，如果不存在错误，则算法的执行只取决于初始配置 D 分补水系统终止是指系统中所有结点处于终止状态，且没有消息在传输 二．简要回答下述问题（55分） 1 构造一个16节点的环，使其高度对称，并给出所有序等价的连续片段。 2 已知事件e1,e2,e3和e4的向量时戳分别为（2,3,0,0），（1,2,0,0），（0,0,1,1），（3,6,4,2），请找出所有因果关系的事件对。
3若将消息复杂度为O(nlgn)的异步环选举算法（在阶段1向节点的2邻居发送Prob消息）修改为只向其中一个方向发送Prob消息，请问修改后算法的消息复杂度是多少？如何对其做进一步的修改使得消息复杂度仍然为O(nlgn)。 4.对于一个优化问题π，最佳可达性能比为Rmin(π)（定义如下）分别为何值时，问题π易于近似和难于近似？ 5 装箱问题是将n件物品放入尽可能少的若干个容量为1的箱子中。不妨设实例I中，物品item，（i<= j <=n ,n = 6）的大小依次为：0.4，0.3，0.6，0.7，08，0.2，请分别给出实例I 的最优解和采用首次适应（first fit）策略得到的近似解的值OPT(I)和A(I)，并给出解得构造，以及近似比Rff(I)。 6. 说明为什么用MST启发解△TSP时，其近似比是2。 三算法题（25分） 1.设一个同步匿名的单向环有n个结点，每个结点均知道n，每个节点的初始均状态相同， 每个结点上的程序相同且开始于同一时刻。 （1）请问是否存在一个确定的算法选出一个leader？简述理由。 （2）试设计一个概率的leader选举算法。 （3）请问你设计的概率算法属于哪一类算法？
模式识别miniproject 实验报告 报告人：李南云 学号：SA16173027 日期：2016.12.23
数据分析 在此简要的说明一下数据情况，给定数据集分为train和test 两个data文件， train.data是11列8285行，意味着有8285个样本，矩阵的最后一列是该列所对应的样本类别。根据统计，train数据前466个样本均为1类，而后7819个样本均为-1类，所以该分类器为二分类问题。MATLAB中用importdata（）读取数据，并将样本和其所属类别分开来，样本为trnset，所属类别为trnclass，train数据用于训练分类器。 Test.data是11列2072行，同样也意味着有2072个样本，最后一列为该列所对应样本类别，test数据前117为1类，后1955个数据为-1类。同样读取数据后，分为tstset和tstclass两个矩阵，前者代表2072个样本，后者代表所对应样本的类别，我们需要将train所训练好的分类器应用在tstset样本上，输出分类结果tstclass1，将其与tstclass相比较，计算每个类别的正确率和总的正确率。 算法介绍 本次实验采用了SVM（support vector machines）分类模型，由于数据线性不可分而且在实际问题中数据也大都线性不可分，所以本次试验采取的线性不可分SVM方法，即将数据向高维空间映射，使其变得线性可分。 本实验选取的二分类算法，SVC_C。
下面先以线性分类器为例，来引入SVM算法的一些概念和处理流程，如图1所示，假设C1和C2是需要区分的类别，而在二维平面中它们的样本如图，中间的一条直线就是一个线性分类函数，由图中可以看出，这个线性分类函数可以完全的将两类样本区分开来，我们就称这样的数据是线性可分的，否则则为线性不可分，本实验中所采用的数据在二维空间里分布如图2和图3所示（红色标注分类为1的样本，蓝色标注为分类为-1的样本），明显线性不可分。 图1
第一次实验报告 1、实验任务 根据下面的需求描述，使用Sybase Power Designer设计相应的数据库概念模型，并转换成Oracle或MS SQL Server上的物理数据库结构： 某银行准备开发一个银行业务管理系统，通过调查，得到以下的主要需求： 银行有多个支行。各个支行位于某个城市，每个支行有唯一的名字。银行要监控每个支行的资产。银行的客户通过其身份证号来标识。银行存储每个客户的姓名及其居住的街道和城市。客户可以有帐户，并且可以贷款。客户可能和某个银行员工发生联系，该员工是此客户的贷款负责人或银行帐户负责人。银行员工也通过身份证号来标识。员工分为部门经理和普通员工，每个部门经理都负责领导其所在部门的员工，并且每个员工只允许在一个部门内工作。每个支行的管理机构存储每个员工的姓名、电话号码、家庭地址及其经理的身份证号。银行还需知道每个员工开始工作的日期，由此日期可以推知员工的雇佣期。银行提供两类帐户——储蓄帐户和支票帐户。帐户可以由2个或2个以上客户所共有，一个客户也可有两个或两个以上的帐户。每个帐户被赋以唯一的帐户号。银行记录每个帐户的余额、开户的支行以及每个帐户所有者访问该帐户的最近日期。另外，每个储蓄帐户有其利率，且每个支票帐户有其透支额。每笔贷款由某个分支机构发放，能被一个或多个客户所共有。每笔贷款用唯一的贷款号标识。银行需要知道每笔贷款所贷金额以及逐次支付的情况（银行将贷款分几次付给客户）。虽然贷款号不能唯一标识银行所有为贷款所付的款项，但可以唯一标识为某贷款所付的款项。对每次的付款需要记录日期和金额。
2、实验过程 （1）确定实体和属性 由上面的需求描述我们可以很容易得出以下几个实体: ●员工（身份证号，姓名，电话号码，家庭地址，开始工作日 期） ●存储账户（账户号，余额，利率） ●支票账户（账户号，余额，透支额） ●客户（身份证号，姓名，街道，城市） ●支行（支行名称，城市，资产） ●贷款（贷款号，总额） ●支付（日期，金额） 图1 PS: 1、在此ER图中我没有设计账户类，然后派生出存储账户和支票账户，因为在客户的需求中，只有两种账户类型，除了支票账户类型就是存储账户类型，没有所谓的“一般的账户”，所以就不
算法分析 一、单选(11*3) 1、下列描述正确的是_______ A、概率算法的期望执行时间是指反复解同一输入实例所花的平均执行时间 B、概率算法的期望执行时间是指所有输入实例上所花的平均执行时间 C、概率算法的平均期望时间是指算法执行时间的上界 D、概率算法的最坏期望时间是指算法执行时间的上界 2、当问题只有一个正确的解，不存在近似解时，某概率算法总是给出一个未必正确的 解，但是随着调用该算法次数的增加，可将错误的概率控制在任意给定的范围，该算法属于_______ A、数字概率算法 B、Las Vegas算法 C、Monte Carlo 算法 D、Sherwood算法 3、Las Vegas算法的一般形式是_______ Obstinate(x){ Repeat LV(x,y,success) Until success; Return y } 设p(x)是LV成功的概率，s(x)和e(x)分别是LV成功和失败的期望时间，t(x)是算 法obstinate得到一个正确解的期望时间，则t(x)的表达式应该是_______ A、t(x)=s(x)+e(x)(1-p(x))/p(x) B、t(x)=p(x)t(x)+(1-p(x))(e(x)+t(x)) C、t(x)=p(x)s(x)+(1-p(x))(e(x)+s(x)) D、t(x)=p(x)s(x)+(1-p(x))(t(x)+s(x)) 4、若一个一致的、p-正确的MC算法是有偏的，则p至少应该满足_______ A、p<0 B、p>0 C、p>=1/2 D、p>1/2 5、若A是一个偏真的MC算法，则下列陈述正确的是_______ A、只有A返回true时解正确 B、A以较大的概率返回true C、A返回true时解必正确，A返回false时解必错误 D、A返回true时解必正确，A返回false时有可能产生错误的解。 6、用Las Vegas算法求解某问题，已知obstinate(x)找到正确的解的期望时间是288。其 中LV成功的概率为p(x)=0.2，成功时的期望s(x)是8，则失败的期望时间e(x) 是_ _____ A、70 B、102 C、210 D、280 7、一个MC算法是一致的、3/5-正确的，偏y0的，若要求出错概率不超过ε，则重复 调用MC至少为_______ A、 B、
美国CS(Computer science)专业的主要分支（世毕盟留学） 1. Artificial Intelligence 人工智能 人工智能做为当前计算机科学专业下最热门,最有发展前景研究方向,因此所招收的国际学生多具备很强的学术背景,在该方面有着非常突出表现的人才.MASTER 招收的并不多,主要是PHD的学生居多. 由于这个方向更多的强调数据表述及算法方面的知识,所以当申请目标定位在这个方面的时候可以整理一下自己在这些方面的背景,看看对于这个方面的理解是否很深度.如果不够深入的话需要及时进行相关的学习! 2. Bioinformatics 生物信息学 对于这个方向的选择大家一定要谨慎,首先这个专业对于学生背景的选择很特殊,有的时候需要计算机背景的学生,有的时候需要生物学背景的学生,所以除非大家在这两个方面都具备非常强的实力,可以放手一拼,否则不如考虑申请纯CS的其他专业,申请这个方向需主要具备数学、信息学、统计、计算机科学、化学和生化方面的知识!或者综合知识,一般来说本科生很难达到这种要求! 设置在计算机科学下的生物信息学历年中国学生的招生录取情况都不好,网上也有很多相关的评论,因为美国本土学生的青睐,因此这个方向招收的国际学生非常少,而且一般被录取的国际学生出了有出色的硬件条件同时也具备很强的研究经历.而且一般研究生毕业被录取的几率相对更大一些.这个方向做为一个交叉学科,申请者多数具备计算机和生物学的双层背景.因此也提升了申请的难度!
3. Computer Architectures/Hardware Systems and De sign/VLSI 这个方向主要从事计算机硬件芯片,例如CPU的结构设计,内部结构逻辑门的电子开关,了解VLSI的同学应该知道这个方面的研究深度和难度,申请者必须具备很强的逻辑电路基础知识. 这三个方向的申请因为其就业环境的影响,申请热度下降的非常快,因为更偏向于理论性的研究因此申请的难度也很大,并且奖学金情况也不乐观! 4. Human-Computer Interaction/Graphics/Visualization 如果你打算申请这个方向,那么你需要掌握计算机制图,计算机成像的一些基本工具及其原理,但这通常往往不足以满足录取的要求,因为这种应用性极强的方向更多的强调经验,你是否从事过相关的工作,所以本科的客户要谨慎选择! 人机交互技术的申请热度随着这个在业界的关注度提升而渐渐升温,但该方向对于申请者的背景要求同样很高,多数录取者也是具备研究生学位.因此对于本科毕业的学生来讲申请这个方向的难度也是相当大的! 5. Computing Computing is the systematic study of algorithmic processes that describe and transform information: their theory, analysis, design, efficiency, implementation, and application. The fundamental question underlying all the computing is 'What can be (efficiently) automated? 该方的申请一直是不温不火的局面,由于这个方向偏基础所以大多数申请者考虑到今后就业的问题而放弃了他,也因为这个方向的资金相对较少,所以不被大多数人所关注,只是本科从事该方向学习的学生是申请这个方向的主流.历年AD出一些,OFFER相对较少! 6. Multimedia; Networking 这两个方面大家都很熟悉了,我就不做太多的说明了,其实选择这两个方面需要注意的并不是专业基础,而是选择学校的层次,尽量避免竞争吧! 多媒体技术与网络技术这两研究方向越来越多的出现在EE,ECE专业下,不过计算机背景的学生在申请这两个方向的时候仍然具有相当不错的竞争力!多媒体技术与EE专业下信号处理方向有着非常紧密的联系越来越多的美国学校将相关的研究放在信号处理方向下边.网络技术这个方面也有很多的设置在EE下边,以致于很多CS的同学为了这个专业转向EE或者ECE下边的通信与网络专业.国际上竞争比较激烈的方向之一!
自动化专业排名 更新学习 自动化专业排名首先谈谈顶尖牛校。: 毫无疑问，清华一支独秀，上交紧随其后，这在圈内是人所共识的。清华自动化的特点是研究领域广度深，在拥有传统优势，控制理论与控制工程方面极负盛誉,在新兴的信息学科交叉领域——模式识别与智能系统方面以明显优势领先于国内同行。之所以会取得如此骄人成绩，归功于该校强大的工科整体实力。事实上自动化系的许多科研项目都是在与计算机系、电子工程系紧密合作下开展的。清华最具国际竞争力的智能技术与系统国家重点实验室就挂靠这
三个系。自动化系负责智能信息处理的相关研究。另外，清华的cImS国家工程研究中心更是该系的金字招牌。因此，无论国家投入，自身实力，国际声誉，发展前景上看，清华自动化在中国的霸主地位短期内不会动摇。 上交是传统的工科牛校，自动化系又是该校工科中的重点方向。虽然它规模不大，但却发展均衡，锋芒毕露，极具实力。在自动控制和模式识别方面均有牛人如席裕庚、施鹏飞等主持。这两个领域曾入选国家重点学科，获此殊荣的仅清华、上交两家，其实力可见一斑。另外，该系在cImS、机器人装配方面也大有作为。 接下来可以谈谈第二档牛校——浙大与东南。浙大自动化发展很不均衡，几乎朝着工业自动化一边倒。在这方面，既有国家重点实验室与国家工程中心，也有以孙优贤院士为首的一群牛人撑腰，在国内将同行们甩开了一大截。可惜其他领域乏善可陈，如不加强新兴方
向的研究投入，很难获得较高的国际声誉。毕竟，工业自动化只是自动化的一个经典分支，并且在国际学术界受重视度十分有限。 东南大学自动化有着与浙大相似的学科构成，也是偏于工程控制。该系于这方面的历史浸淫颇深，全凭多年来打下的深厚功底运作到现在。老一辈院士钱钟韩、冯纯伯为其在国内赢得了很高地位。现在的人才梯度建设也不错，有田玉平、郭雷等。cImS更是国内独领风骚(北京第一机床厂cImS工程：该校是工程唯一的技术依托单位，由本建设项目中的三个二级学科与“计算机应用”学科联合攻关，最终完成的该工程获得美国制造工程师协会颁发的“工业领先奖”。这是该组织第一次授予非美国企业的国际性大奖。)，不过近年来在势力强大的弱电学科影响下，有着偏弱电的倾向，目前在重点发展检测技术与自动化装置、模式识别与智能系统两个二级学科。如果学科领域再有所拓展的话，应
算法实验报告 快速排序 1. 问题描述： 实现对数组的普通快速排序与随机快速排序 (1)实现上述两个算法 (2)统计算法的运行时间 (3)分析性能差异，作出总结 2. 算法原理： 2.1快速排序 快速排序是对冒泡排序的一种改进。它的基本思想是：选取一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准元素小，另外一部分的所有数据都要比基准元素大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 设要排序的数组是A[0]……A[N-1]，首先选取一个数据（普通快速排序选择的是最后一个元素, 随机快速排序是随机选择一个元素）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。 一趟快速排序的算法是： 1）设置两个变量i、j，排序开始的时候：i=0，j=N-1； 2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]； 3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]赋给A[i]； 4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]赋给A[j]； 5）重复第3、4步，直到i=j；(3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i，j指针位置不变。另外，i==j这
一过程一定正好是i+或j-完成的时候，此时令循环结束）。 2.2随机快速排序 快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个或者最后一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。 3. 实验数据 本实验采用对80,000个随机数据进行十次排序，并取出平均值。分别用普通快速排序和随机快速排序对数据排序。用毫秒作为运行计数单位，观测两种算法所用的时间的不同。 4. 实验截图 如下图所示的时间，普通快速排序所用的平均时间为181毫秒，而随机化版本的快速排序所用时间仅仅为119毫秒。 5. 结果分析 5.1 时间分析 从实验截图得到的结果来看，随机化版本的快速排序所用时间比普通快速排序所用的平均时间少。 快速排序的平均时间复杂度为O(nlogn)，最坏时间时间可达到O(n^2)，最坏情况是当要排序的数列基本有序的时候。根据快速排序的工作原理我们知道，
中科大考博辅导班：2019中科大信息科学与技术学院考博难度解析 及经验分享 中国科学院大学2019年博士研究生招生统一实行网上报名。报考者须符合《中国科学院大学2019年招收攻读博士学位研究生简章》规定的报考条件。考生在报考前请联系所报考的研究所(指招收博士生的中科院各研究院、所、中心、园、台、站)或校部相关院系，了解具体的报考规定。 下面是启道考博辅导班整理的关于中国科学技术大学信息科学与技术学院考博相关内容。 一、院系简介 为迎接信息科学技术的迅猛发展和知识经济时代的到来，适应国家经济、国防建设和社会发展的需要，中国科学技术大学于1999年6月成立信息科学技术学院（以下简称“信息学院”），学院由电子工程与信息科学系、自动化系、电子科学与技术系、国家示范性微电子学院、网络空间安全学院、信息与计算机实验教学中心、信息科学实验中心等单位组成。 学院拥有1个语音及语言信息处理国家工程实验室、1个类脑智能技术及应用国家工程实验室、1个未来网络国家基础设施和7个省部级重点实验室，即：多媒体计算与通信教育部—微软重点实验室、中国科学院电磁空间信息重点实验室、中国科学院空间信息处理与应用系统技术重点实验室（电子学研究所、中国科学技术大学共建）、中国科学院无线光电通信重点实验室、网络传播系统与控制安徽省重点实验室、无线网络通信安徽省重点实验室、未来网络安徽省重点实验室。此外，学院还拥有中国科大—中国通服、教育部—微软重点实验室两个国家级工程实践教育中心。 目前，信息学院已设置电子信息工程/通信工程、自动化、电子科学与技术、信息安全、生物医学工程、人工智能等6个本科专业，拥有信息与通信工程、电子科学与技术、控制科学与工程、生物医学工程、网络空间安全等5个一级学科博士硕士学位授权点，拥有电子与信息工程博士学位授权点和电子与通信工程、集成电路工程、控制工程、生物医学工程等4个专业硕士学位授权点，以及13个二级学科和3个博士后流动站 二、招生信息 中国科学技术大学信息科学与技术学院博士招生专业有4个： 081000信息与通信工程
考研究生调剂到了中科大软件学院，现在看来是一件让我觉得十分幸运的事情。中科大的学习气氛非常的浓，课程的内容也十分有新意，虽然有新意，但是又都是很基础的内容，让我收获很大，很多课程给我带来了很大的启发。直到过年时候，才腾出时间来写上一篇总结，记录我这一学期的生活和学习。我一直是一个地地道道的北方人，生在北京，长在北京，却跑到哈尔滨读了四年书。哈工大学习负担不轻，假期也很短，一直没有时间到处玩玩，再加上自己比较懒，大学期间也就去了趟长春。这次考到了中科大苏州研究院，心中对于南方的风土人情很是期待，内心中也不乏有些忐忑。 开学前，我直接跑到了南京玩了一周，玩的十分痛快，题外话暂且不提，然后从南京坐高铁到了苏州。中科大苏州研究院地处独墅湖高教园区，正巧高铁有工业园区一站，我就在工业园区站下了车。人生地不熟找不到合适的公交，直接拦下一辆出租车奔着学校这边就来了。苏州的出租车司机素质感觉比较高，礼让行人等做的都很不错，开车也很规矩。出租车司机还很健谈，就像北京的老师傅一样，听说我是来上学的，给我说了很多苏州的情况。我是提前一天前来报道的，物业态度很不好，不过好在顺利办理了入住手续，搬进了宿舍。宿舍两人寝，上床下桌，屋子不小，但是什么都没有，不过比较干净，我开学前几天都在置备东西。苏州的空气很好，略显湿润但却不潮湿，气温跟北京差不多，略高3℃左右，我很适应。住宿的地方离学校不近，走路30分钟左右，不过每天都有班车。中科大开的课程都很有意思，很多课程我遗憾的没有抢到，不过幸好没有全抢到我喜欢的课程，不然估计得累到爆。曾经我很不理解哈佛的学生为什么一学期只有8门课程还累得要死，知道我来到了号称不要命的来科大的中科大，才彻底理解了原因。中科大的课很有意思，难度也颇高，想要学好，就要付出150%的努力，而且基本上我学的所有的课都需要这种程度的努力。 下面说说我都上了些什么课，都有什么好玩的内容。英语免修过关考试侥幸水过，让我能够选一些其他我感兴趣的课程。一开始我选的是实用算法设计一课，第一节课时，老师负责任的指出此课程针对于没有算法基础的同学，恰巧此时算法分析与设计一课有一个空位，我就改选了算法分析与设计。实用算法设计一课使用的是《程序员实用算法》一书，说实在的，里面的例子都是经过精心编写的算法，非常优美，很多细节处理的十分精妙，可惜我还是更喜欢算法分析与设计一课。算法分析与设计使用的教材是经典的《算法导论》一书，整个课程跳过了一些简单的章节，但是覆盖到了算法导论中的大部分章节(不含第七部分和第八部分)。这课说实在的，超赞啊!我本科学的算法课用的是《算法概论》一书，比较偏重于算法设计，《算法导论》则是设计与分析并重。自己看《算法导论》的时候真心看不进去，这门课程一口气跟下来觉得并不吃力，而且有一种融会贯通的感觉。发现很多的时候，一个算法的时间复杂度暗示了其设计思想。上这门课的感觉还是很多问题都似曾相识，比如说经典的八皇后问题，这些问题以前在遇到的时候都是采用一些固定的策略来进行处理，并不知道为什么要采用这样的策略。这门课程让我认识到了三类基本问题：组合计数、组合优化、组合设计，每一类问题都有很多数学工具来对其进行分析和解决。顺便说一下，书中对于如何构造GF(pk)讲解的实在是让人有点稀里糊涂的，恰巧我另一门课程密码学及其应用中讲到了这些内容，让我在这点上没有稀里糊涂的跳过去。随机过程是一门神奇的课，说实在的，我一直都挺怕概率论的，我觉得概率论十分的违反直觉，很多时候得出的答案都令我十分费解，也不能够肯定是否正确。这有助于我们抛弃一些不必要的tricks，在关键的时候进行优化。(这也是CSAPP所需要达到的一个目标之一) 说完这两门课程，不妨看看上面提到过的密码学及其应用一课。在上这门课程以前，我一直认为密码学领域主要是一些数学问题，程序员需要关注的内容很少;上了这门课程后，我发现，所有的程序员都应该学习一下密码学的基本知识，走出密码学的误区。在这门课程上，我了解了，即便是有了安全的加密方式，如果使用不当的话，仍然可能会泄密或收到被攻击者伪装成正常消息而受到欺骗，非对称加密并不比对称加密更安全，反而，非对称加密方式由于加密速度较慢，使用范围会受到限制。有些不