<4D F736F F D20CDBCC2DBD3EBCDF8C2E7D3C5BBAF2DC1F5B1F2C5A9C7ECC7D92E646F6378>

Size: px

Start display at page:

Download "<4D F736F F D20CDBCC2DBD3EBCDF8C2E7D3C5BBAF2DC1F5B1F2C5A9C7ECC7D92E646F6378>"

葵复董
5 years ago
Views:

1 中国海洋大学本科生课程大纲课程名称图论与网络优化 Graph Theory and Network Optimization 课程代码课程属性专业知识课时 / 学分 3/ 课程性质专业选修实践学时责任教师农庆琴刘彬方奇志课外学时 64 (3 ) 一课程介绍 1. 课程描述 : 课程性质主要内容图论与网络优化以图和网络为研究对象, 通过对事物间的联系相互影响进行网络建模, 对网络结构以及建立在网络结构上行为决策进行研究本课程主要介绍图论与网络优化的基本概念重要理论和算法以及理论的应用, 主要包括以下三部分内容 : 1) 图的概念与结构 : 树连通度 Euler 环游与 Hamilton 圈匹配独立集与团平面图染色等 ; ) 网络优化算法 : 最小支撑树最短路中国邮递员最大网络流与最小费用最大流等 ; 3) 复杂网络及社会网络研究简介通过本课程学习, 学生能够掌握图论与网络优化的基本概念理论方法及优化算法, 具备应用所学理论和算法解决相关实际问题的能力. 设计思路 : 课程开设依据课程内容 ( 或项目 ) 选择标准内容编排顺序本课程是为学习运筹学基础后的高年级学生开设的, 引导学生认识图论与网络科学在现代科学技术发展中的基础性和其中所蕴含的深刻数学思想, 理解数学定理 ( 理论 ) 和算法之间的关系以及算法设计的重要性, 了解图论与网络科学前沿研究领域课程内容选取了图论中一些重要的概念与经典理论若干经典的网络优化问题及算法, 并对相关研究前沿进行专题介绍图论部分的内容 :1) 图的基本概念 ( 包括路圈树连通等 );)Euler 环游和 Hamilton 圈, 其中 Euler 环游起源于哥尼斯堡七桥问题, 是图论和拓扑学的起源 ; 3) 基于图的边集或者点集进行划分的若干概念理论及证明方法 ( 匹配与覆盖独立集与团染色等 );4) 平面图的判定 Euler 公式和著名的四色猜想等网络优化理论与算法的内容建立在相应图论内容基础上, 包括几个经典网络优化问题的理论算法及应用案例 :1) 最小支撑树问题 ;) 图搜索与最短路问题 ;3)Euler - 1 -

2 环游与中国邮递员问题 ;4) 最优指派问题 ;5) 最大网络流与最小费用流问题等这两部分内容将结合穿插在一起进行讲授学习, 将图的结构刻画与优化算法设计有机地结合起来, 强调基于图与网络的结构刻画出发进行算法设计研究前沿专题部分 : 通过最新研究论文介绍复杂网络及社会网络研究热点 3. 与其他课程的关系 ( 先修并行和后置课程 ): 先修课程 : 高等代数 I 空间解析几何数学实验 I 运筹学基础等; 并行课程 : 结构化程序设计最优化方法等博弈论基础 ; 后置课程 : 计算复杂性理论等本课程与运筹学基础博弈论基础计算复杂性理论最优化方法等课程构成完整的运筹学系列课程群, 内容和要求各有侧重联系密切二课程目标 ( 知识能力素质一体化设计 ) 本课程目标是让学生通过对图与网络的理论与算法的学习, 理解刻画结构性的抽象数学理论与算法设计之间的关系和完美结合, 认识图与网络研究方法在科技和现代社会各领域的广泛应用, 提升解决实际问题的能力到课程结束时, 学生应能 : (1) 掌握图与网络的基本概念重要的图论定理及证明方法 ( 技巧 ); () 掌握经典的网络优化问题的算法 ( 理论基础基本思想算法过程 ); (3) 通过建立图或网络优化模型合理选择相关理论和算法解决问题的方法, 能够利用数学软件 (Matlab Lingo Excel 表等 ) 进行算法的实现 ; (4) 通过小组合作, 对实际问题开展图与网络建模与算法研究三学习期望 ( 课程要求 : 主动学习有效学习学习指导 ) 要完成所有的课程任务, 学生必须 : (1) 按时上课, 上课认真听讲, 积极参与课堂讨论随堂练习和测试本课程将包含较多的随堂练习讨论小组作业展示等课堂活动, 课堂表现和出勤率是成绩考核的组成部分 () 按时完成常规练习作业这些作业要求学生按书面形式提交, 只有按时提交作业, 才能掌握课程所要求的内容延期提交作业需要提前得到任课教师的许可 (3) 完成教师布置的一定量的阅读文献和背景资料案例分析理论探讨和算法软件应用等作业, 其中大部分内容要求以小组合作形式完成这些作业能加深对课程内容的理解促进同学间的相互学习并能引导对某些问题和理论的更深入探讨 - -

3 四教材与主要参考书 1. 教材 : [1] Graph theory with applications, J.A. Bondy and U.S.R. Murty, The Macmillan Press Ltd, New York, 1976.( 中译本 : 图论及其应用, 科学出版社,1984) [] 运筹学 ( 第 4 版 ), 运筹学教材编写组, 清华大学出版社, 主要参考书 : [1] 图论与网络流理论, 高随祥, 高等教育出版社, [] Introduction to Graph Theory (Second Edition), Douglas B. West, Prentice Hall, 001.( 中译本 : 图论导引, 李建中骆吉周译, 机械工业出版社,006) 五进度安排序号专题主题计划课时主要内容概述实验实践 ( 课下 ) 内容 1 绪论图与网络基本概念 3 树 4 5 Euler 环游和 Hamilton 圈匹配独立集覆盖集团 6 染色图论与网络优化简介什么是图网络?(Graph, Network) 1 图论与网络优化历史发展前沿 1 连通性? 最短路 (SP)? 什么是树 (Tree)? 最小支撑树 (MCST)? Euler 环游? 中国邮递员问题 (CPP)? Hamilton 圈? 如何判别? 匹配和覆盖? (Matching & Covering) 独立集与团? (Independent Set & Clique) 图的染色? (Coloring) 无向图有向图的基本定义图与网络的代数表示与计算机输入图的连通度边连通度块的概念与基本性质图的搜索与连通性判定算法最短路问题 Dijkstra 算法和 Floyd 算法树的定义与基本性质割边割点 1 最小支撑树问题和贪心算法 Euler 环游 Euler 图中国邮递员问题与奇偶点算法 Hamilton 圈 Hamilton 图基本性质 3 匹配覆盖的概念和基本性质, 匹配与覆盖关系, 二部图最优匹配算法 ( 最优指派 ) 1 独立集团的概念和基本性质边染色点染色的概念和基本结论搜集 : 1. 图论故事 ( 包括但不限于 : 历史 / 人物 / 应用 ). 可以用图与网络进行建模的实际问题 ( 包括工件排序问题 ) 用数学软件求解最短路问题 1.MCST 其他算法 ;. 用计算机实现 MCST 的求解旅行售货员问题 (TSP) 与 Hamilton 圈问题的关系 TSP 的动态规划算法 1. 从 0-1 线性规划角度理解匹配与覆盖之间的关系 ;. 用计算机求解最优指派问题各种时间表问题的建模与求解方

4 时间表问题? (Time Table) 1 时间表问题建模与算法法 7 平面图平面图? (Planar Graph) 平面图的判定定理 Euler 公式, 五色定理证明了解四色猜想搜集 : 四色定理的理论与应用进展 8 网络流最大流问题? (Max Flow) 最小费用流? (Min-cost Flow) 4 基本概念 ( 流割 ) 及基本性质, 最大流最小割定理 Ford-Fulkerson 算法最小费用流的算法 1. Ford-Fulkerson 算法的改进 ;. 用计算机求解最大流问题 3. 应用案例 9 研究前沿复杂网络与社会网络 4 最新研究成果研究前沿介绍五成绩评定 ( 过程考核综合评价 ) ( 一 ) 考核方式 A :A. 闭卷考试 B. 开卷考试 C. 论文 D. 考查 E. 其他 ( 二 ) 成绩综合评分体系 : 课后常规书面作业 15% 随堂练习随堂测试出勤率 15% 小组作业附加作业 0% 期末考试 50% 总计 100% 附 : 考核项目的评分标准 1) 作业的评分标准作业的评分标准 1. 严格按照作业要求并及时完成, 基本概念清晰, 解决问题的方案正确合理, 能提出不同的解决问题方案. 基本按照作业要求并及时完成, 基本概念基本清晰, 解决问题的方案基本正确基本合理 3. 不能按照作业要求, 未及时完成, 基本概念不清晰, 解决问题的方案基本不正确基本不合理 4. 不能按照作业要求, 未及时完成, 基本概念不清晰, 不能制定正确和合理解决问题的方案得分分分分 0-30 分 - 4 -

5 ) 课堂讨论及平时表现评分标准课堂讨论平常表现评分标准 1. 资料的查阅知识熟练运用, 积极参与讨论能阐明自己的观点和想法, 能与其他同学合作交流, 共同解决问题. 基本做到资料的查阅知识的运用, 能参与讨论能阐明自己的观点和想法, 能与其他其他同学合作交流, 共同解决问题 3. 做到一些资料的查阅和知识的运用, 参与讨论一般不能阐明自己的观点和想法, 与其他同学合作交流, 共同解决问题的能力态度一般 4. 不能做到资料的查阅和知识的运用, 不积极参与讨论, 不能与其他同学合作交流, 共同解决问题得分分分分 0-30 分七学术诚信学习成果不能造假, 如考试作弊盗取他人学习成果一份报告用于不同的课程等, 均属造假行为他人的想法说法和意见如不注明出处按盗用论处本课程如有发现上述不良行为, 将按学校有关规定取消本课程的学习成绩八大纲审核教学院长 : 院学术委员会签章 : - 5 -

<4D F736F F D20CAFDBEDDBFE22DD5C5C1D9BDDC2E646F63>

<4D F736F F D20CAFDBEDDBFE22DD5C5C1D9BDDC2E646F63> 中国海洋大学本科生课程大纲课程名称数据库 Database 课程代码 075322201227 课程属性专业知识课时 / 学分 64/3 课程性质选修实践学时 32 责任教师张临杰课外学时 64(32 2) 课程属性 : 公共基础 / 通识教育 / 学科基础 / 专业知识 / 工作技能, 课程性质 : 必修选修一课程介绍 1. 课程描述 : 本课程是信息与计算科学与数学与应用数学专业的选修课