信息工程学院博士考试大纲
数据结构与算法分析
参考书目：
（1）《数据结构----用C语言描述》唐策善 李龙澎 黄刘生 编著，
高等教育出版社；
（2）《数据结构》 严蔚敏 吴伟民 编著， 清华大学出版社；
（3）《算法设计和分析》 朱洪编著，上海科学技术文献出版社。
考试要求：
1、能熟练运用C语言及或类PASCAL语言描述算法； 0----10％
2、熟练掌握常用数据结构（线性表、栈和队列、串、多维数组和广义表、树、图等）的逻辑结构、存储结构及在其上的基本运算的实现算法；0—20%
3、能结合实际问题，选择较好的数据结构，给出问题求解算法的实现思想及算法描述； 0----20%
4、对一般问题，能综合运用算法设计技术，给出其解算问题的有效算法；
0----20％
5、能熟练运用算法分析技术（方法），对其算法的时间复杂度（空间复杂度）进行分析、给出较准确的分析结果； 0----30％
6、能用非形式化（或形式化）的语言，对算法的正确性、最优性给出论证或说明； 0----20％
7、对求解问题的不同算法，能洞察其各算法的优缺点，提出改进意见，给出“改进算法”的实现思想及算法描述；
8、对给定的问题，能判断它是否在有效时间（空间）内是可解的；
0—10％
9、了解NP类问题及“难”的（NP-完全的）问题，并能给出近似求解这些问题的算法思想； 0----10％
10、对“算法设计与分析”研究领域的新技术、新方法有所了解和思考。
0----10％
操作系统结构分析
专业名称：计算机软件与理论
参考书目：
《UNIX高级教程—系统技术内幕》 作者：（美）Uresh Vahalia著
聊鸿斌 曲广之 王元鹏 等译 清华大学出版社 1999
《操作系统精髓与设计原理》
作者：William Stallings 清华大学出版社 1999
《Linux内核源代码分析》 作者：（美）Scott Maxwell
冯锐 邢飞 刘隆国 陆丽娜 译 机械工业出版社 2000
《Linux操作系统结构分析》
作者：郭玉东
西安电子科技大学出版社 2001
考试内容：
一、 操作系统概述，包括操作系统发展的历史、演变的动力、未来的趋势等。0--5分。
二、 硬件体系结构，如Intel体系结构的基本知识，包括段、页、描述符表、中断等。0--5分。
三、 引导与初始化，包括OS的引导过程，操作系统初始化时所做的主要工作。0--10分。
四、 中断、时钟、系统调用，包括中断的处理机制、时钟的处理机制、系统调用的处理机制等。5--15分。
五、 内存管理，包括系统对物理内存、内核内存、虚拟内存的管理。10--20分。
六、 进程管理，包括进程、线程、调度、同步、互斥、死锁等。10--25分。
七、 进程间通信，包括信号、管道、共享内存、消息队列、信号灯等常用的进程间的通信机制。10--20分。
八、 文件系统，包括虚拟文件系统、磁盘文件系统、分布式文件系统等。10--20分。
九、 设备驱动，包括字符设备驱动程序、块设备驱动程序、网络设备驱动程序等。10--20分。
十、 关闭与重启，操作系统关闭的过程。0--10分。
十一、安全，操作系统安全的隐患、漏洞及其对策。5--15分。
十二、其它操作系统技术，如微内核、实时、嵌入式、SMP、集群等。5--20分。
考试要求：
本课程主要考察考生对操作系统了解的广度和深度。要考察的内容包括：
一、 操作系统概述
1、 操作系统发展的历史。了解
2、 操作系统演变的动力。了解
3、 操作系统未来的趋势。了解
二、 硬件体系结构（以Intel体系结构为主）
1、 段、段描述符、各种门的描述符、描述符表。掌握
2、 页目录、页表。掌握
3、 中断处理。掌握
4、 指令系统、汇编语言。掌握
三、 引导与初始化
1、 操作系统的引导过程。了解
2、 操作系统的初始化过程。了解
3、 第一个用户进程的建立。掌握
四、 中断、时钟、系统调用
1、 操作系统中的中断处理机制。掌握
2、 时钟的作用以及各种定时器的工作机制。了解
3、 系统调用的实现机制，在用户空间和内核空间之间交换数据的方法，在用户程序和内核代码之间切换控制的方法。掌握
五、 内存管理
1、 物理内存的分配与回收机制。掌握
2、 内核内存管理器的作用及实现机制。掌握
3、 虚拟内存的工作原理，包括虚拟内存的建立、缺页处理、换出换入、文件映射以及虚拟内存的撤消等。掌握
六、 进程管理
1、 进程控制结构。掌握
2、 进程的创建、执行映像的装入、进程的撤消。掌握
3、 进程的调度。掌握
4、 进程的同步与互斥。掌握
5、 进程的死锁与饥饿。掌握
6、 内核线程、用户线程、轻量级进程及其关系。掌握
七、 进程间通信
1、 信号机制，包括信号处理程序的注册、信号的产生、信号的处理等。掌握
2、 管道的实现机制。了解
3、 SVR的IPC机制，包括共享内存、消息队列、信号灯等。掌握
八、 文件系统
1、 虚拟文件系统的作用，它与底层文件系统及其它输入输出系统的关系，虚拟文件系统提供的缓存机制。掌握
2、 磁盘文件系统的结构、组织、磁盘调度策略等。掌握
3、 分布式文件系统。了解
九、 设备驱动
1、 设备驱动程序的结构、组成，它和内核的接口。掌握
2、 字符设备驱动程序。掌握
3、 块设备驱动程序，包括缓存、RAID等。掌握
4、 网络设备驱动程序。了解
十、 关闭与重启
1、 操作系统的关闭过程。掌握
2、 操作系统的重启过程。了解
十一、安全
1、 操作系统安全的隐患、漏洞。掌握
2、 操作系统安全的评价标准。掌握
3、 增加操作系统安全性的主要措施。了解
十二、其它操作系统技术
1、 微内核。掌握
2、 实时操作系统。了解
3、 嵌入式操作系统。了解
4、 SMP。了解
5、 集群技术。了解
说明：
信息工程学院硕士研究生的《操作系统结构分析》课程主要讨论的是Linux操作系统。
计算机网络
专业：计算机软件与理论
参考书目：
《计算机网络》 作者：（美）Andrew S. Tanenbaum 著
熊桂喜 王小虎译 李学农 审
出版社：清华大学
《用TCP/IP进行网际互连》第一卷（第3版）
作者：（美）DOUGLAS E.COMER 著
林摇 等译 谢希仁 校
出版社：电子工业
《计算机网络》（第2版）
作者：谢希仁
出版社：电子工业
《虚拟专用网的创建与实现》
作者： Casey Wilson, Peter Doak著
钟鸣，魏允韬等译
出版社：机械工业
《IPSEC新一代因特网安全标准》
作者：Naganand Doraswamy等著 出版社：机械工业
考试内容：
一、 计算机网络概述：计算机网络发展的历史，网络硬件，网路软件，参考模型，网络实例，数据通信实例，网络标准化。
占5到10分
二、 物理层：数据通信理论基础，传输介质，无线传输，电话系统，窄带ISDN,宽带ISDN和ATM,蜂窝无线通信，通信卫星。
占5到10分
三、 数据链路层：数据链路设计问题，差错检测和校正，基本数据链路协议，滑动窗口协议，协议描述和验证，数据链路层示例。
占10到25分
四、 介质访问子层：信道分配，多路访问协议，局域网和广域网的IEEE802标准，网桥，高速LAN,卫星网。
占5到20分
五、 网络层：网络层设计的有关问题，路由选择算法，拥塞控制算法，网络互联，因特网上的网络层，ATM网络中的网络层。
占10到25分
六、 传输层：传输服务，传输协议的要素，一个简单的传输协议，因特网传输（TCP/UDP）,性能问题。
占10到25分
七、 应用层：DNS(域名系统)，SNMP（简单网络协议），电子函件，USENET新闻，万维网，多媒体。
占5到20分
八、 网络安全及计算机网络若干热门课题
网络安全概念，IPsec安全标准，虚拟专用网技术，三网融合，IP电话， WAP。
占10到20分
考试要求：
本课程主要考察考生对计算机网络了解、掌握的广度和深度。考查的内容主要包括：
一、 计算机网络概述
1、 计算机网络发展的历史。了解
2、 网络硬件。掌握
3、 网络软件。掌握
4、 参考模型。掌握
5、 网络实例。领会
6、 数据通信实例。领会
7、 网络标准化。领会
二、 物理层
1、 数据通信理论基础。掌握
2、 传输介质。了解
3、 无线传输。掌握
4、 电话系统。了解
5、 窄带ISDN。领会
6、 宽带ISDN和ATM。领会
7、 蜂窝无线通信。了解
8、 通信卫星。了解
三、 数据链路层
1、 数据链路设计问题。掌握
2、 差错检测和校正。了解
3、 基本数据链路协议。掌握
4、 滑动窗口协议。掌握
5、 协议描述和验证。了解
6、 数据链路层示例。领会
四、 介质访问子层
1、信道分配。掌握
2、多路访问协议。掌握
3、局域网和广域网的IEEE802标准。领会
4、网桥。掌握
5、高速LAN。领会
6、卫星网。了解
五、 网络层
1、网络层设计的有关问题。掌握
2、路由选择算法。掌握
3、拥塞控制算法。掌握
4、网络互联。掌握
5、因特网上的网络层。掌握
6、ATM网络中的网络层。了解
六、 传输层
1、传输服务。掌握
2、传输协议的要素。掌握
3、一个简单的传输协议。领会
4、因特网传输协议（TCP/UDP）。掌握
5、性能问题。了解
七、 应用层
1、DNS(域名系统)。掌握
2、SNMP（简单网络协议）。领会
3、电子函件。领会
4、USENET新闻。了解
5、万维网。领会
6、多媒体。了解
八、 网络安全及计算机网络若干热门课题
1、网络安全概念。掌握
2、IPsec安全标准。领会
3、虚拟专用网技术。领会
4、三网融合。领会
5、IP电话。领会
6、无线应用协议WAP。了解
矩阵理论
类型：博士研究生
专业：通信与信息系统、军事通信学、军事情报学
参考书目：
1、《矩阵分析引论》 罗家洪 编
2、《矩阵论》（第二版） 程云鹏主编 西北工业大学出版社
考试内容：
１、线性空间与线性变换 (在试卷中占20%)
２、内积空间 (在试卷中占20%)
３、矩阵的标准形与矩阵分解 (在试卷中占30%)
４、矩阵函数 (在试卷中占15%)
５、特征值估计与广义逆矩阵 (在试卷中占15%)
考试要求：
１、线性空间与线性变换
深刻理解并熟练掌握线性空间、基变换与坐标变换、线性空间的同构以及线性变换的概念和方法；深刻理解并熟练掌握子空间与维数定理、线性变换的矩阵表示和不变子空间等概念和结论以及它们所涉及到的基本方法。
２、内积空间
深刻理解并熟练掌握内积空间和酉空间的定义和性质，熟悉正交基及子空间的正交关系、内积空间的同构、正交变换和正规矩阵的概念和方法；深刻理解并熟练掌握厄米特二次型的概念及其相关方法。
３、矩阵的标准形与矩阵分解
深刻理解并熟练掌握矩阵的相似对角形、约当标准形、哈密顿－凯莱定理以及矩阵的最小多项式等基本概念和基本结论以及它们所涉及到的基本方法，理解并掌握多项式矩阵的相关概念以及以及矩阵的ＱＲ－分解和奇异值分解。
４、矩阵函数
理解并熟练掌握向量范数、矩阵范数、向量和矩阵的极限、矩阵幂级数、矩阵函数、矩阵的微分与积分等基本概念和它们所涉及到的基本方法，了解常用矩阵函数的性质及其在微分方程组中的应用。
５、特征值估计与广义逆矩阵
掌握特征值界的估计和谱半径估计的基本方法，理解广义逆矩阵的概念并掌握它在解线性方程组中的应用。
代 数 学
专业: 密码学
参考书目
1. 《Algebra》(Second Edition), Serge Lang, 出版社：Addison-Wesley Publishing Company, 1984
2. 《Algebra》, Thomas W. Hungerford, 出版社：Springer-Verlag, 1974
考试内容:
一、范畴初步 (8%)
1. 范畴与函子的基本概念
2. 积(product)与上积(coproduct)
二、模论 (25%)
1. Hom函子的正合性质
2. 模的直积与直和
3. 自由模
4. 向量空间及其对偶空间
5. 模同态交换图(如Snake Lemma和Short Five Lemma)
6. 投射模与内射模
7. 模的张量积
8. 模范畴中的正向极限与反向极限
三、交换代数初步 (25%)
1. Noether模与Noether环的基本概念
2. Hilbert基本定理，
3. 子模和理想的准素分解
4. Nakayama引理及其应用
5. 分次环与分次模，
6. Dedekind整环。
7. 局部化理论初步
四、域的代数扩张 (22%)
1. 有限扩张与代数扩张
2. 分裂域与正规扩张
3. 可分扩张与纯不可分扩张
五、Galois理论 (20%)
1. Galois扩张与Galois理论基本定理
2. 单位根、分圆多项式与分圆扩张
3. 迹与范
4. 方程的根式解
注: 考虑到交叉和综合题型, 上述分数比例仅作参考。
考试要求:
一、范畴初步
理解范畴与函子的基本概念, 理解积与上积是普通直积与直和概念的推广
二、模论
熟练掌握和运用Hom函子的正合性质和模同态交换图。深刻理解模的直积、直和、自由模、模的张量积。掌握向量空间与其对偶空间之间的关系。理解并掌握投射模与内射模的基本概念和基本性质。了解模范畴中的正向极限与反向极限的基本概念及其构造
三、交换代数初步 (25%)
深刻理解Noether模与Noether环的基本概念和多个等价条件。熟练掌握Hilbert基本定理内容和证明思想。熟悉和掌握Noether环和Noether模的准素分解性质。熟练掌握Nakayama引理及其应用。了解分次环与分次模的基本概念和基本性质。熟练掌握Dedekind整环的特性和若干等价条件了解局部化理论的基本思想。
四、域的代数扩张 (22%)
熟练掌握并深刻理解有限扩张、代数扩张、分裂域、正规扩张和可分扩张的基本概念、基本性质和相互之间的关系。了解纯不可分扩张的概念。
五、Galois理论 (20%)
熟练掌握并深刻理解Galois扩张的基本概念与基本理论。熟练掌握单位根、分圆多项式与分圆扩张的概念及其应用。掌握域扩张中的迹函数与范函数。熟练掌握方程的根式解原理及与Galois理论之间的关系.
概率论基础
类型: 博士研究生
专业: 密码学
参考书目:
1、《概率论与数理统计》，中山大学数学力学系《概率论与数理统计》编写小组编，高等教育出版社1992。
2、《测度与概率基础》，中山大学《测度与概率基础》编写小组编，广东科技出版社，1981。
3、《概率论基础》，严士健等，科学出版社，1982。
考试内容：
一、概率论（50%）
1、随机事件和概率（10%）
2、随机变量及其分布函数（10%）
3、随机变量的数字特征及其特征函数（15%）
4、极限理论（15%）
二、概率论基础（测度论基础）（50%）
1、 几类常用的集族和测度（10%）
2、 可测空间与可测函数（10%）
3、 测度空间与积分（10%）
4、 可测函数列的几种收敛性（10%）
5、 可测变换（10%）
考试要求：
一、概率论
1、随机事件和概率
熟练掌握随机事件、条件概率、事件独立性等基本概念。在深刻理解古典概率、统计概率与几何概率的直观意义的前提下，了解概率公理化定义的客观背景。在熟练掌握事件的关系和运算、概率的性质与运算法则基础上，能较熟练地应用条件概率、乘法公式、全概率公式、贝叶斯公式及事件的独立性解决应用问题。
2、随机变量及其分布函数
熟练掌握离散型随机变量与分布列、连续型随机变量与分布密度的定义，分布密度与分布函数的性质，深刻理解相互独立随机变量的概念，熟练掌握二项分布、泊松分布、指数分布及正态分布等重要分布。较熟练掌握多维随机变量及其分布的性质、边沿分布、随机变量和与商的分布，理解条件分布，了解x2—分布、t—分布、F—分布三种重要分布的推导，熟练掌握求随机变量的线性变换与平方变换的分布的方法。
3、随机变量的数字特征及其特征函数
熟练掌握离散型随机变量与连续型随机变量的数学期望和方差的定义及性质，能较熟练地求出具体问题的期望和方差。深刻理解随机变量的矩、多维随机变量的数字特征、协方差和相关系数，并掌握相应的计算技巧，理解条件数学期望的定义及性质。熟练掌握特征函数的定义及性质，特征函数与矩的关系、相互独立随机变量和的特征函数的性质，深刻理解反演公式及唯一性定理，多维随机变量数字特征的性质，并对母函数有一定了解。
4、极限理论
熟练掌握大数定律、依分布收敛的充分必要条件与中心极限定理，深刻理解依概率收敛与以概率1收敛的关系，理解强大数定律并了解三种收敛性之间的关系。
二、概率论基础（测度论基础）
1、几类常用的集族和测度
熟练掌握半环、环、代数、s-代数、测度的概念，掌握单调族、p族、l族的定义和它们之间的相互关系。掌握半环上有限测度的定义及性质，了解测度从半环扩张到s-代数的方法，了解测度的完备化和有限可加测度成为完全可加测度的条件。掌握一维勒贝格测度及勒贝格—司帝阶测度和n维勒贝格测度及勒贝格—司帝阶测度的定义。
2、可测空间与可测函数
熟练掌握可测空间与可测函数的定义，可测函数的性质。
3、测度空间与积分
熟练掌握测度空间及其上的积分的定义，积分的性质，不定积分和勒贝格—司帝阶积分的定义及性质。
4、可测函数列的几种收敛性
熟练掌握可测函数列的几乎处处收敛、几乎一致收敛、依测度收敛和平均收敛等几种收敛性的定义和相互关系。了解Lp函数空间的定义，掌握一致可积的充要条件。
5、可测变换
熟练掌握变换和可测变换的定义、性质及相关应用。
随机过程与排队论
类型：博士研究生
专业：通信与信息系统、军事通信学、军事情报学
参考书目：
1、《随机过程》 刘次华，华中理工大学出版社2000年1月
2、《运筹学随机模型》 严颖等，中国人民大学出版社1995年6月
3、《随机过程及其应用》 陆大金，清华大学出版社1986年
考试内容：
1、随机过程的一般概念 10%
2、泊松过程 20%
3、马尔可夫链（MC） 20%
4、马尔可夫过程（MP） 20%
5、平稳随机过程 15%
6、排队过程 15%
考试要求：
一、随机过程的一般概念
1、随机过程的定义，有限维分布函数库
2、随机过程的数字特征
3、平稳性、严平稳与宽平稳
4、随机过程的分类
5、两个随机过程的联合分布及数字特征
二、泊松过程
1、泊松过程的三个等价定义
2、泊松过程的基本性质
3、到达时刻的分布与条件分布
三、马尔可夫链（MC）
1、MC的定义、转移概率函数，时齐性
2、C-K方程
3、状态分类
4、状态空间的分类
5、转移概率的极限分布平稳分布
四、马尔可夫过程（MP）
1、时间连续的马尔可夫链
2、柯尔莫哥洛夫微分方程
3、生灭过程
五、平稳随机过程
1、平稳过程的谱密度
2、联合平稳过程的互谱密度
3、遍历性与抽样定理
4、线性时不变系统
六、排队过程
1、排队模型的描述与记号
2、M/M/1模型
3、M/M/n模型
4、M/G/1模型
5、简单排队网络
数字信号处理
专业： 通信与信息系统、军事通信学、军事情报学
参考书目： 《数字信号处理》，A.V 奥本海默和R.W 谢弗，科学出版社
考试要求：
1．傅氏变换 0-35分
熟练掌握离散时间信号的序列傅氏变换
熟练掌握基-
熟练掌握离散时间信号的线性卷积、周期卷积和循环卷积的定义、性质、相互关系和计算。
2. 数字滤波器 0-25分
熟练掌握离散时间系统线性、非时变、因果和稳定的概念，
熟练掌握巴特沃思滤波器的设计、模拟低通和高通滤波器的设计、
3. 离散随机信号处理 0-20分
熟练掌握狭义平稳随机序列、广义平稳随机序列、相关序列、协方差序列、功率谱密度和白噪声序列的概念，
熟练掌握
4. 同态信号处理 0-20分
熟练掌握模拟非周期、模拟周期、数字非周期信号希尔伯特变换的定义和性质，最小相位系统、最大相位系统、全通系统的定义和性质，序列傅氏变换的希尔伯特变换关系以及数字希尔伯特变换器的设计。
熟练掌握广义叠加原理的概念，卷积同态特征系统的分析和计算，复倒谱的概念和计算。
通信理论
参考书目：
《通信原理》 樊昌信等编，第四版，国防工业出版社，1995年10月
考试大纲：
一、信息论基础
1．信源、信息量和信息熵、信源编码定理；
2．信道、信道容量、信道编码定理。
二、调制基础理论—模拟调制
3．AM、DSB、VSB、SSB；FM。
4．FDM
5．各种调制的性能分析。
三、传输波形的脉冲形成技术
1．码间干扰及无码间干扰的条件（Nyqiust 第一定理）和传输特性
2．受控码间干扰的部分响应技术
3．眼图与均衡技术
四、模拟信号的数字化
1．取样、量化、编码的原理
2．PCM、DPCM、ADPCM
3．DM、ADM
4．TDM
五、数字调制
1．ASK（M-PAM：多进制脉冲幅度调制）、FSK（M-FSK）、PSK（BPSK、DPSK、M-PSK）、连续相位调制CPM（MSK、GMSK）
2．各种调制的能量（功率）效率与频谱效率及其性能
3．最佳接收准则
4．相关接收和匹配滤波器接收
六、信道编码
1．ARQ与CRC
2．线性分组码：循环码、BCH码、RS码
3．卷积码及Viterbi 译码
七、扩频调制与伪随机码
1．扩频调制的概念
2．直接序列扩频
3．跳频扩频
4．扩频码：正交码及PN码（重点是m序列）
八、同步
1．载波同步及其载波相位误差对解调性能的影响
2．位（符号）同步及其误差对性能的影响
九、现代无线通信的最新技术动态
组合数学
参考书目：
１．组合数学基础 李乔 高等教育出版社
２．组合论 （上册） 柯召、魏万迪 科学出版社
３．组合数学 邵嘉裕 同济大学出版社
考试内容：
一、基本计数问题 （25%）
二、母函数与递归关系 （20%）
三、两个基本原理 （15%）
四、反演公式 （20%）
五、（0，1）—矩阵 （20%）
考试要求：
熟练掌握组合数学分析问题和解决问题的方法和技巧，能综合运用组合方法解决问题
一、基本记数问题
1、列、组合及组合恒等式
2、第一、第二类Ｓtirling数
3、Catalan数
4、正整数的分拆
5、分配问题
熟练掌握基本组合计数方法，熟练掌握证明组合恒等式的基本方法；熟悉第一、第二类Ｓtirling数和Catalan数的定义和各种表述形式及相关性质；熟练掌握正整数分拆的基本方法，能用诸如Ｆerrers图、母函数、递归关系等对分拆数进行计数；能对各种分配问题进行计数。
二、母函数与递归关系
1、函数和指数型母函数的性质
2、函数和指数型母函数在计数问题中的应用
3、归关系的建立和解法
4、用母函数解递归关系
5、差分
熟练掌握母函数和指数型母函数的性质及母函数与计数问题的内在联系，能利用母函数和指数型母函数对计数问题进行计数；熟练掌握建立递归关系的方法及解递归关系的常用解法；熟悉差分（或差分方程）的性质及其应用。
三、两个基本原理
1、鸽笼原理
2、容斥原理
熟练掌握鸽笼原理和容斥原理及其应用
四、反演公式
1、经典反演公式
2、偏序集上的反演公式
3、偏序集上的Möbius函数
4、数列的反演公式
熟练掌握经典反演公式和偏序集上的反演公式，熟练掌握偏序集上关联代数中函数（如Zeta函数、Möbius函数等）的性质；会求特殊偏序集上的Möbius函数，熟悉反演公式的应用。
五、（0，1）—矩阵
1、项秩与线秩
2、相异代表系、Hall定理
3、积和式
4、集系的关联矩阵
熟练掌握（０，１）－矩阵的性质，能用（０，１）－矩阵处理相关的组合模型，解决相应的组合问题。