|
《组合网络理论》教学大纲
(
2003
年02月09日
--
07月02日)
本课程大纲以《Topological
Structure and Analysis of Interconnection Networks》（Junming
Xu，Kluwer Academic Publishers，2001）为依据。按学校教学日历表安排，本学期授课时间72课时，法定假日（5月1日）和因故（5月15日）停课各一次，期中考试2课时，总结复习4课时，实际授课时间共62个课时。课堂教学以概念和理论为主，介绍组合网络的基本问题、方法和理论。课后安排少量必作习题，课堂未涉及的部分均为自学内容。通过此课程的学习，了解和掌握组合网络的基本概念、理论和方法，学会将网络问题转化为图论问题，提高发现问题和解决问题的能力,着手介入研究工作。为确保达到这个目的，课余预习、复习思考和自学时间应不少于课堂教学时间的2倍。请关注有关通知。
1).
2.18（星期二）:
开课，导引，课程意义，国内外理论研究和应用进展，最主要的参考书和参考杂志。课程要求和注意事项。
2).
2.20（星期四）:
内容是第一章。掌握网络拓扑结构与图的关系，了解度量网络拓扑结构性能的图论参数和图论概念和参数的网络意义。复习将在本课程用到的基本图论概念和结果。本章分两次课，主要是课后复习，重点是新概念。
3).
2.25（星期二）: 内容是第一章（续）。平均距离，子图嵌入，路由选择，容错性与连通度。网络设计原则。
4).
2.27（星期四）:
内容是2.1(节分1.5次课完成)，线图方法，基本性质和一些著名网络拓扑的设计。重点掌握线图连通度和直径的结论，Euler性和Hamilton性之间的关系，多重线图的概念、性质和论证方法。
5).
3.04（星期二）:
内容是2.1.6和2.2.1节（2.2节分2.5次课完成）。无向线图的边连通度和点可迁图。
6).
3.06（星期四）:
内容是2.2.2 - 2.2.4节。边可迁图，图的原子和点可迁图的连通度。重点掌握边可迁与点可迁之间的关系，图的原子结构性质，可迁图连通度的基本结果。
7).
3.11（星期二）:
内容是2.2（续）。Cayley方法，基本性质和一些著名网络拓扑的设计。重点掌握Cayley图的概念的基本性质，Cayly图的原子和连通度基本结果及其论证方法。
8).
3.13（星期四）:
内容是2.3节（分2次课完成）中2.3.1-2.3.4小节。笛卡儿乘积方法，基本性质和一些著名网络拓扑的设计。重点掌握笛卡儿乘积基本性质、连通度和直径及其论证方法。
9).
3.18（星期二）:
内容是2.3节（续）。重点掌握可迁图和Cayley图的笛卡儿乘积性质,一些著名的网络。
10).
3.20（星期四）:
内容是2.4节，网络拓扑设计的一个基本问题－（d, k）问题。重点了解无向图和有向图的(d,
k) Moore界及其相关的论证方法。
11).
3.25（星期二）:
内容是3.1，超立方体网络。重点掌握超两个等价定义、基本性质、连通度、直径、路长、2叉数的嵌入及其论证方法，几种广义超立方体网络的定义及其基本性质。分两次课完成。
12).
3.27（星期四）:
内容是3.1节（续）。
13).
4.01（星期二）:
内容是3.2节，De Bruijn网络。重点掌握三个等价定义、基本性质、连通度、直径、路长及其论证方法。分两次课完成。
14).
4.03（星期四）:
内容是3.2节（续）。
15).
4.08（星期二）:
内容是3.3，Kautz网络。重点掌握超三个等价定义、基本性质、连通度、直径、路长及其论证方法。
16).
4.10（星期四）:
内容是3.4节，重点是双环网络的设计中的问题和几何方法。
17).
4.15（星期二）:
内容是4.1节，网络中路由选择。重点掌握度量路由选择优劣的两个参数：点转发指数和边转发指数和它们的基本结果及其论证方法。分2次课完成。
18).
4.17（星期四）: 内容是4.1（续）。重点掌握度量容错网络中路由选择优劣的一个参数：路由延迟，和它们的基本结果及其论证方法。
19).
4.22（星期二）:
内容是4.2.1节，网络中的边添加问题。重点掌握路中添加边问题的网络背景、基本结果和论证方法。
20).
4.24（星期四）:
内容是4.2.2节，网络中的边减少问题。边容错直径，确定边容错直径的两个参数f(t,k)和g(t,k)，它们的基本结果和它们与边增加问题之间的关系。
21).
4.29（星期二）:
内容是4.2.3节,点容错直径问题。
22).
5.01（星期四）:
内容是4.3节，并行系统网络中Menger型问题。重点掌握有界路长、Menger数、有界连通度和Rabin数概念的网络背景和基本结果及其论证方法。分3次课完成。
23).
5.06（星期二）:
内容是4.3节（续）。
24).
5.08（星期四）:
内容是4.3节（续）。
25).
5.13（星期二）:
内容是4.4节，网络宽直径。重点掌握宽直径的概念、网络背景和基本结果及其论证方法。的分3次课完成。
26).
5.15（星期四）:
内容是4.4节（续）。
27).
5.20（星期二）:
内容是4.4节（续）。
28).
5.22（星期四）:
内容是4.5节，并行系统网络中(l, w)独立数和(l, w)控制数。重点掌握其概念、网络背景和基本结果及其论证方法。
29).
5.27（星期二）:
内容是4.5节（续）。
30).
5.29（星期四）:
内容是4.6节，网络的限制连通度。重点掌握其概念、网络背景和点可迁图基本结果及其论证方法。分3次课完成。
31).
6.03（星期二）:
内容是4.6节（续）。
32).
6.05（星期四）:
内容是4.6节（续）。期终总结。布置期终复习和考试事宜。
期终考试时间：06月25日（星期三）下午2:30--4:30；地点：数学楼419教室（如有变化，将另行通知）。
成绩分配：平时作业和期中考试占25％；期终考试占70％，另外5％是指出讲义中错误（其具体政策见通知）。
|
