课程数据分析的Markov链模型

论文摘要

自二十世纪五十年代,时间表问题（Timetabling Problem）成为一个备受关注的研究课题。1963年,Gotlieb提出了第一个课程时间表（课表）问题的数学模型,将课表问题描述成一个组合优化模型。到1975年Even等人证明了课表问题属于NP-完全问题（NP-Complete Problem）,因此很难寻求一个有效的整体优化算法。而后对于课表问题的研究,人们更多关注于它的有效近似算法。经典课表问题是预先根据各种需求安排课程,学生在排好的课程表上选择课程。针对大学排课表这个多因素优化决策问题,分组优化决策是一种行之有效的算法策略。分组策略,可以将课程按优先等级逐次分组,每组再采用组合优化方法进行求解。通常认为课程的规模是优先等级的决定性因素。实行学分制,需要在自由选课的模式下允许学生在一定的范围内选择课程,这就使得课程的关联关系更趋复杂。本文将课程的关联关系描述为一个Markov链,从而提出了课程优先度（CourseRank）的概念。通过对清华大学20012002,20022003年度学生选课数据的分析和计算,结果表明课程的规模仍然是重要的因素,但并不完全是决定性的。本文对课程数据的分析和挖掘,为进一步优化时间表问题的算法,打下了坚实的基础。

论文目录

• 第1章 引言
• 1.1 时间表问题概述
• 1.2 原有的排课系统介绍
• 1.3 课程数据分析的需求
• 1.4 本文结构
• 第2章 Timetabling 问题简介
• 2.1 School Timetabling 问题
• 2.2 Course Timetabling 问题
• 2.3 Examination Timetabling 问题
• 2.4 Course Timetabling 问题的分组优化决策算法
• 2.4.1 问题描述
• 2.4.2 分组优化决策算法
• 2.4.3 研究课题
• 第3章 CourseRank 的数学模型
• 3.1 Google PageRank
• 3.1.1 PageRank 的基本概念
• 3.1.2 PageRank 的随机冲浪模型
• 3.2 自由选课的Markov 链模型
• 3.3 CourseRank 的计算
• 第4章 实例计算
• 4.1 清华大学选课数据分析
• 4.1.1 算法描述
• 4.1.2 数据存储
• 4.1.3 算法的时间复杂度
• 4.2 计算结果与分析
• 4.2.1 2001～2002 年度本科生选课数据分析
• 4.2.2 2002～2003 年度本科生选课数据分析
• 4.2.3 计算结果分析
• 结论
• 参考文献
• 致谢与声明
• 附录A
• 个人简历、在学期间发表的学术论文与研究成果