软件工程课程设计

1 28 题题 目 目 高校课表编排子系统高校课表编排子系统 学学 院院 信息工程学院信息工程学院 专专 业业 计算机科学与技术计算机科学与技术 指指 导导 教教 师师 白白 娟娟 2014 年 1 月 3 日 2 28 摘要 教学工作是高校的中心工作 而课表是高校日常教学活动运行的指挥调度表 是高校能否进行正常教学的关键 因此科学的 合理的课表在高校的重要性 毋庸置疑 高校教务管理是一向复杂而繁重的工作 课表编排作为其中腰组 成部分是长期困扰学校教务管理工作的大问题 计算机排课无疑是必然优势 课表编排是一个涉及多因素约束的 多目标的 结构复杂的典型的组合优化 问题 并且已经被证明为一个 NP 完全类 是典型的组合优化的问题 其问 题求解的时间复杂度呈指数函数增长 每个学校在排课表时考虑的因素千差 万别 各种约束条件也不尽相同 但是它所涉及的主要实体却具有相对稳定 性 关键字 NP 完全类 约束满足 课表编排 课程设置 3 28 4 28 目录 目录 4 第一章 需求分析说明 5 1 1 编写目的 5 1 2 问题定义 5 1 3 可行性分析 5 1 4 任务描述 5 1 5 目标 5 1 6 运行环境 6 1 7 功能需求 6 1 7 1 功能描述 6 1 7 2 排课约束 6 1 7 3 操作规程 7 第二章 概要设计说明 8 2 1 数据描述与数据库设计 8 2 2 数据表 8 2 2 1E R 图 9 2 2 2 数据流图部分 9 2 3 运行需求 10 2 3 1 硬件 10 2 3 2 软件 10 第三章 详细设计说明 11 3 1 模块的具体算法 11 3 1 1 登陆模块 11 3 1 2 管理员模块 11 数据库中各表的物理结构 15 第四章 编码 测试 17 4 1 登录模块 17 4 1 1 管理员模块 18 4 1 2 教师模块 20 4 2 测试方案设计 21 测试结果分析 22 第五章 用户使用说明书 23 第六章 实验总结 26 第七章 参考文献 28 5 28 第一章 需求分析说明 1 1 编写目的 供设计人员 开发人员参考 为明确软件需求 安排项目规划进度 组织软件开发与测试 撰写本文档 1 2 问题定义 随着社会的发展 我们越来越接近自动化的时代 随着高校学生的日益增多 学校 制度的日趋完善 我们的排课也不需要人工操作了 慢慢的交给系统自动完成 为了给 操作人员提供更简便的操作 排课系统必须不断完善以满足需求 根据工作人员的实际 需要 高校课表排课系统主要应包括以下几个方面 1 任课教师只具有查询个人课程信息和教室信息以及修改密码的功能 2 管理员除了具有查询功能之外 还有设定排课约束 完成排课的功能 1 3 可行性分析 排课管理系统是一个教育单位不可缺少的部分 它的内容对于学校的决策者和管理者 来说都至关重要 所以排课管理系统应该能够为用户提供充足的信息和快捷的查询手段 对于一个课表编排子系统来说 基础表的设置是很重要的基础性问题 而基础表的设 置仅仅是一个数量级问题 查询的时间复杂度是一个线性复杂度 O n 或平方复杂度 O n2 在此基础上 较为困难的部分是排课 由于排课问题已被证明为 NP 问题 找到最优 解的时间复杂度为指数级 故采用优化的方式是必需的 对排课来说 各个学校都有着 不太相同的排列方法 有每天的课节数 允许课程连排数 时间段等等 而这些方法转 换为计算机语言时 往往会因为各类限制而造成死循环或者程序速度缓慢 因为排课系 统要适应大部分学校使用 所以这里提供的一些要求是需要满足大部分人的 经过详细的分析与计算之后 小组成员一致认为 在一定程度的随机化算法 退火 贪心变形算法 类贪心算法 下 排课的时间复杂度可以减小到多项式级别 达到 O n3 甚至更低 故该系统是可行的 1 4 任务描述 1 5 目标 随着时代的发展 高校扩招的趋势正在加大 与此同时 高校教务管理是一项复 6 28 杂繁重的工作 课表编排是一项繁重的工程 计算机排课已经成为必然趋势 软件的目的是设计出一套易于使用与维护的排课子系统 能够完成课程管理 课程编排 教师 学生 课程基本信息维护等功能 软件需要较大的通用性 能够适应多学年的排 课 以及一个专业多个学期的排课 同时 能够对于各种信息进行查询 1 6 运行环境 1 操作系统 Microsoft Windows 7 Ultimate Microsoft Windows XP Professiona 2 支持环境 NET Framework 4 0 3 数据库 Microsoft SQL Server 2005 1 7 功能需求 1 7 1 功能描述 作为一个课表编排子系统 应当在完成排课任务之外 进行一部分相应的查询与管理功 能 经过小组成员分析 列出主要功能如下 1 机构设置 建立系 系内部门 专业 班级等信息 2 课程信息 建立全校开设的课程并录入相关信息 3 教师信息 建立教师的基本信息 4 教室信息 建立可用教室的信息 类型等 包括教学楼 教室 5 教学任务 录入教学任务 包括生成上课班级 6 课表编排 建立排课约束 预排课 自动排课 手动调整课表 冲突检测恢复 上述功能不仅应包括新增 还应包括查询与维护 1 7 2 排课约束 1 基本约束 a 同一时间一个教室不能够上两门课 b 同一时间一个教师不能上两门课 c 同一时间一个班级不能上两门课 2 优先顺序 经小组讨论分析 考虑优先顺序问题 将优先顺序分类 再按照优先顺序设计算 法排课 1 7 3 操作规程 7 28 1 对于新建立的数据库 需要设定各基本信息 包括院系 职称 职位 课程类别 教室类别等 2 设立基本信息后 建立教学资源信息 包括教师 教室 楼房等 3 建立学籍信息 包括学生 班级 4 建立教学计划 决定每个专业在学期间的课程 5 安排教学任务 根据教学计划排定本学年学期的教学任务 包括对该学期每个专 业的每一门课程指定上课班级和上课老师 生成教学任务 6 排课 包括预排课 自动生成上课记录 手动调整 冲突分析检测步骤 此步需 要经过反复执行 STD 图如下 录入基本信息 录入教学资源 录入学籍 制定教学计划 安排教学任务 排课 学年结束 图 1 5 3 系统操作流程图 8 28 第二章 概要设计说明 2 1 数据描述与数据库设计 2 2 数据表 登录表 用户名 密码 身份 教师信息表 工号 姓名 性别 出身年月 职称 联系电话 课程信息表 课程号 课程名 是否选修课 课时 学分 考试形式 是否安排 开始 周次 教室信息表 教室号 容量 是否多媒体 班级课程表 班级号 课程号 任务号 教师任务书 任务号 工号 课程号 所教专业 周数 人数 要求 是否多媒体 选课表 教室号 星期 时间段 任务号 占用情况 其中 加下划线的为关键码 9 28 2 2 1E R 图 2 2 2 数据流图部分 数据流图说明 系统的流程为 管理员和教师通过登录表进入该系统 管理员查询 设置排课约束 以及排课等职能 排课使选课表 课程信息表数据发生变化 根据分析 可得系统顶层 数据流图 将顶层数据流图进行分解 可知教师登录后有查询课程安排 修改密码的功 能 这样得出了系统的数据流图 数据流图 教师任务书授课教师信息表 登录 登录表 安排 选课表 安排 教室信息表 教授 课程信息表 讲课 班级课程表 N 1 1N 1 1 1 N 1 1 N N 管理员 系统管理排课 教 师查 询 D1登录表 D2排课表 D3课程信息表 D7班级课程表 D6教师任务书 D4教师信息表 D5教室信息表 10 28 2 3 运行需求 2 3 1 硬件 a x86 架构 CPU b 512MB 以上内存 c 1 7KB 硬盘空间 2 3 2 软件 a 操作系统 Microsoft Windows 7 Ultimate Microsoft Windows XP Professional b 数据库系统 Microsoft SQL Server 2005 c 运行时环境 NET Framework 4 0 11 28 第三章 详细设计说明 3 1 模块的具体算法 3 1 1 登陆模块 该模块涉及到 2 个登录身份 教师 管理员 教师和管理员 需要用用户名和密码和身份进行验证才能登录 登录要有自己的身份识别 是教师还是管理员 可以先判断出用户是以什么身份登录的 若未选择身份就进行查询 则提示出错 程序流程图如下 3 1 2 管理员模块 管理员添加排课约束条件 进行排课 其中休息日时间不能和选修课时间冲突 同时两 节选修课的时间同样也不能发生冲突 程序流程图如下 1 给所有课程分开始周数 开 始 身份为 管理员 Y N 根据用户名和 密码查询记录 reader read 跳转 Form2 name 管理员 Y N 跳出提示信息 根据用户名和 密码查询记录 reader read 跳转 Form2 name 教师 Y N 开 始 查询教师任务书 所有记录 Fill ds i 0 12 28 2 选修课排课 foreac h 要求 0 require 0 require 接收查询的要 求 require 0 开始周数 require 入 库 周数 16 YN N N Y Y 开始周数 1 入 库 周数 8 N Y 开始周数 1 入 库 i 2 0 开始周数 1 入库 开始周数 9 入库 Y N 结 束 开 始 查询未安排的选修课 foreach i 0 13 28 3 其他课程排课 查询该课程的任务号 人数 是否多媒体 任务 号 i 2 0 上课时间为选修 课约束的第一节 上课时间为选修 课约束的第二节 YN select 符合条件的教室 random 教 室 更新选课表 课程信息 表 结 束 开 始 创建时间链表 h 查询课程号 人数 按照人数降序排列 count 0 Y N row 0 课程的所有任务 排课完成 foreach 每周课时 课时 周 数 每周课时 6 排除矛盾分派教 室并入库的函数 每周课时 4 Y N Y 14 28 排除矛盾的函数 第二节链表 p 指向 星期三 第一节 排除矛盾分派教 室并入库的函数 第三节链表 p 指向 星期四 第一节 排除矛盾分派教 室并入库的函数 N 排除矛盾分派教 室并入库的函数 排除矛盾分派教 室并入库的函数 排除矛盾分派教 室并入库的函数 第二节链表 p 指向 星期三 第一节 结 束 开 始 该工号该时段选修 课表的记录 Fill ds count 0 YN 该班级该时段选修 课表的记录 Fill ds count 0 该时段符合条件的 教室记录 Fill ds N Y 15 28 数据库中各表的物理结构 1 登录表 2 教师信息表 3 教室信息表 4 课程信息表 下一时间段 count 0 N Y 随机入库 结 束 16 28 5 班级课程表 6 教师任务书 7 选课表 17 28 第四章 编码 测试 4 1 登录模块 if comboBox1 Text 管理员 string sql select 密码 from 登录表 where 用户名 name and 身份 管理员 SqlCommand cmd new SqlCommand sql conn SqlDataReader reader cmd ExecuteReader if reader Read if reader 密码 ToString Trim textBox2 Text Form2 f2 new Form2 f2 GetName name 管理员 this Hide f2 Show else MessageBox Show 用户名错误或密码错误 请核对 else MessageBox Show 用户名错误 请核对 if comboBox1 Text 教师 string sql select 密码 from 登录表 where 用户名 name and 身份 教师 SqlCommand cmd new SqlCommand sql conn SqlDataReader reader cmd ExecuteReader if reader Read if reader 密码 ToString Trim textBox2 Text Form2 f2 new Form2 f2 GetName name 教师 this Hide f2 Show 18 28 else MessageBox Show 用户名错误或密码错误 请核对 else MessageBox Show 用户名错误 请核对 4 1 1 管理员模块 排课 void MatchStartWeek 给任务课程分前 8 和后 8 根据周数和要求 string commString SqlCommand cmd new SqlCommand commString conn cmd CommandText select 课程号 周数 要求 from 教师任务书 SqlDataReader reader cmd ExecuteReader if reader Read reader Close 可以不使用 reader 直接 ds Tables 0 Rows Count 0 就可以了 SqlDataAdapter da new SqlDataAdapter cmd CommandText conn DataSet ds new DataSet da Fill ds mytable for int i 0 i ds Tables 0 Rows Count i int i 0 foreach DataRow Row in ds Tables 0 Rows cource num Row 课程号 ToString Trim week num Convert ToInt32 Row 周数 ToString Trim if Row 要求 ToString Trim require 0 else require Convert ToInt32 Row 要求 ToString Trim if require 0 19 28 cmd CommandText update 课程信息表 set 开始周次 require where 课程号 cource num cmd ExecuteNonQuery else if week num 16 cmd CommandText update 课程信息表 set 开始周次 1 where 课程号 cource num cmd ExecuteNonQuery else if week num 8 if i 2 0 cmd CommandText update 课程信息表 set 开始周次 1 where 课程号 cource num cmd ExecuteNonQuery else cmd CommandText update 课程信息表 set 开始周次 9 where 课程号 cource num else cmd CommandText update 课程信息表 set 开始周次 1 where 课程号 cource num cmd ExecuteNonQuery i MessageBox Show 开始周数已分配 else MessageBox Show 教师任务书为空 约定无课时间安排 选修课时间安排 用变量接受 每次排课时间上排除掉 20 28 排课结束 4 1 2 教师模块 private void button5 Click object sender EventArgs e SqlConnect string sql1 SqlCommand cmd1 new SqlCommand sql1 conn cmd1 CommandText select from 选课表 SqlDataReader reader11 cmd1 ExecuteReader if reader11 Read if radioButton1 Checked true SqlConnect string num textBox1 Text string sql SqlCommand cmd new SqlCommand sql conn if id 教师 cmd CommandText select from 教师信息表 where 工号 num 只有一条 SqlDataReader reader cmd ExecuteReader if reader Read name N reader 姓名 ToString Trim else reader Close else cmd CommandText select from 教师信息表 where 工号 num 只有一条 SqlDataReader reader cmd ExecuteReader if reader Read name N reader 姓名 ToString Trim 21 28 else MessageBox Show 该职工号不存在 请核对 reader Close SqlDataAdapter adapter new SqlDataAdapter select from 教师任务书 where 工号 num conn 确定这位老师所有任务号 DataSet ds new DataSet adapter Fill ds mytable if ds Tables 0 Rows Count 0 for int i 0 i ds Tables 0 Rows Count i 对一个任务号 进行 一系列查询 课程信息查询 cource num ds Tables 0 Rows i 课程号 ToString Trim week num Convert ToInt32 ds Tables 0 Rows i 周数 ToString Trim string pross ds Tables 0 Rows i 所教专业 ToString Trim cmd CommandText select from 课程信息表 where 课程号 cource num SqlDataReader reader1 cmd ExecuteReader if reader1 Read course name reader1 课程名 ToString Trim teststyle reader1 考试形式 ToString Trim score reader1 学分 ToString Trim totalhour reader1 课时 ToString Trim startweek reader1 开始周次 ToString Trim int startweeks Convert ToInt32 startweek ToString Trim int endweeks startweeks week num 1 string endweek endweeks ToString Trim weeks startweek endweek else reader1 Close 该老师 该任务号 该课程的排课时间 地点 22 28 4 2 测试方案设计 测试方式 测试方式 黑盒测试 白盒测试 原因 原因 由于白盒测试需要进行某种路径覆盖 而无论是逻辑覆盖还是路径覆盖 都由于 数据量过大而无法设计测试用例 故前期只采用白盒测试 部分 后期均采用黑盒测试 且测试数据来自前期的数据 由于基本模块在单元测试时全都通过 而且接口均为标准化接口 而较大的模块只是 调用该接口 故只需在接口进行测试 即可保证数据的正确性 测试结果 测试结果 测试结果分析 大部分的测试都较为平稳 主要原因在于大部分的工作都由数据库来做 而数据 库的查询一般情况下是安全的 而由于使用了 SQL Server 的性能分析器后 查询性能一般 较高 23 28 第五章 用户使用说明书 1 首先将 VS 和数据库相连接 然后在 VS 中打开项目 点击调试程序 出现主界面 2 选择相应的身份 输入用户名和密码进入到系统中 在此以管理员为例 输入用户名 和密码后 进入选择界面 3 首先 进行初步排课 选择某个下午作为休息日 再选择进行排选修课的时间 24 28 4 初步排课完成后 就可以进行相应的查询了 因为是管理员登录 可以查询每个老师 的课表和每个教室的课表 5 输入对应的教职工号和教室号可以查询到相应的课表信息 25 28 由于时间紧迫 调课模块和修改密码模块仅仅完成了界面 还未实现其功能 26 28 第六章 实验总结 实验前期 由于该实验的前期部分的过程最为困难 教务系统较为庞大 即使是 子系统 也很难做的很完善 由于排课需要根据教学任务进行 而教学任务牵涉到课程 班级 教师等多种信息 而课程 班级等实体又有各自的属性 并且彼此相连 在查询 时就会变得非常复杂 故一个良好的数据库体系结构设计是非常重要的 数据库的建立 中 遇到了如下的问题 外键的基表必须是主键而非主属性 故无论是用 B 作基表还是 用 A 作基表 主键都大于 1 个 而外键只有 1 个 故列不匹配 而一对一的实现不符合 外键的定义 故被数据库否决 在咨询了两位老师之后 小组成员进行了讨论 大家一 致认为没有合适的解决方案 故解决的办法是不设此外键 而是采用程序控制的方式让 这两个表建立联系 并在开发文档中标明 在这一部分测试较为用心 编码阶段由于表比较多 排课设计的条件比较多 查看了大量的关于排课的算法 最终决定用贪心算法 当一个问题具有最优子结构性质时 我们会想到用动态规划法去 解它 但有时会有更简单 更有效的算法 即贪心算法 顾名思义 贪心算法总是做出 在当前看来最好的选择 也就是说贪心算法并不是整体最优上加以考虑 他所作出的选 择只是在某种意义上的局部最优的选择 虽然贪心算法不是对所有问题都能得到整体最 优解 但对范围相当广的许多问题它能产生整体最优解 如图的算法中单源最短路径问 题 最小支撑树问题等 在一些情况下 即使贪心算法不能得到整体最优解 但其最终 结果却是最优解的很好的近似解 在贪心算法中较为有名的算法是 Dijkstra 算法 它作 为路由算法用来寻求两个节点间的最短路径 Dijkstra 算