实验小学教学管理系统的设计与实现——后台数据库系统的设计与实现.doc

1、苏州科技学院本科生毕业设计（论文） 摘 要制定一个学校的排课计划是一项非常耗时且相当辛苦的工作，而且它还得由有学校排课工作经验或者这方面知识的人才能做好。在一所高校时一个课程表的制定是一个难题，因为在有关课程表的问题上有很多的限制条件得考虑，还有大量的数据空间被挖掘，即便你的输入数据量并不是实际意义上的大批量。课程编排系统是一个学校不可缺少的部分,它的内容对于学校的决策者和管理者来说都至关重要,所以自动课程编排系统应该能够为用户提供充足的信息和快捷的查询手段。但一直以来人们使用传统人工的方式管理文件档案，这种管理方式存在着许多缺点,如:效率低、保密性差,另外时间一长,将产生大量的文件和数据,这

2、对于查找、更新和维护都带来了不少的困难。随着科学技术的不断提高,计算机科学日渐成熟,其强大的功能已为人们深刻认识,它已进入人类社会的各个领域并发挥着越来越重要的作用。关键字 排课；程序开发；数据库Experimental Primary School Teaching Management System Design and ImplementationDesign and Implementation of back-end Database SystemAbstractFormulates a school platoon class plan is an item consumes ex

3、tremely when also the quite laborious work, moreover it also must by have the school row of class work experience or this aspect knowledge talented person can complete. When a university a class schedule formulation is a difficult problem, because has the very many limiting condition in the related

4、class schedule question to result in the consideration, but also has the massive data space to excavate, even if your input data quantity is not in the practical significance mass.The curriculum arranges the system is a school essential part, Its content said regarding the school policy-maker and th

5、e superintendent all very important, Therefore the automatic curriculum arranges the system to be supposed to be able to provide the sufficient information and the quick inquiry method for the user. But the people have since always used the traditional artificial way management document file, this m

6、anagement way has many shortcomings, For example: The efficiency low, the secrecy is bad, Moreover the time one is long, Will produce the massive documents and the data, This regarding the search, the renewal and the maintenance has all brought many difficulties.Along with science and technology unc

7、easing enhancement, The computer science is mature day after day, Its formidable function had profoundly known for the people, t entered the human society each domain and is playing the more and more vital role.Keywords Course arrangement; Program development; DataBase VI目 录第一章 引言11.1 选题背景和意义11.2 国内

8、外研究现状21.3 本次设计所做的工作31.4 本文的组织结构3第二章 开发环境及技术介绍42.1 JSP简介42.2 Tomcat简介52.3 数据库设计技术介绍52.3.1 定义52.3.2 数据库设计方法简述62.3.3 设计步骤62.3.4 各级模式的形成过程8第三章 项目可行性分析93.1 技术可行性93.2 经济可行性93.3 操作可行性93.4 维护可行性10第四章 需求分析114.1 系统的基本功能114.2 排课的约束条件114.3 需求模型124.3.1 初使用列图124.3.2 最后用例图134.3.3 用例描述144.4 分析模型154.4.1 分析阶段类图154.4.

9、2 实体类关系图164.4.3 序列图/协作图创建174.5 设计模型194.5.1 组件图194.5.2 配置图19第五章 排课算法分析与设计215.1 背景与研究意义215.2 解决NP问题的几种算法及其比较225.2.1 动态规划225.2.2 贪心算法225.2.3 回溯法235.3 排课系统流程分析235.3.1 整理课程信息245.3.2 按等级分类245.3.3 获取可安排的教室245.3.4 排课245.3.5 生成课表245.4算法分析245.4.1 问题的描述245.4.2 排课约束条件255.5 算法设计25第六章 系统概要设计286.1 设计思想286.2 系统功能模块

10、划分296.3 数据库设计29第七章 详细设计307.1 登录模块设计307.2 主界面及课表生成设计307.2.1 班级管理设计307.2.2 班级课程处理设计317.2.3 课表生成部分设计327.2.4 报表输出功能设计337.2.5 系统调课功能设计347.3 数据库详细设计357.3.1 设计分析357.3.2 数据表设计377.4 主要界面实现407.4.1 登录页面407.4.2 教学任务信息管理页417.4.3 教师信息管理页417.4.4 班级信息管理页427.4.5 课程信息管理页427.4.6 专业教室信息管理页437.4.7 课时数信息管理页447.4.8 排课管理页4

11、47.4.9 总课表查询页457.4.10 教师课表查询页457.4.11 班级课表查询页467.4.12 调课页47第八章 测试报告488.1 测试方案488.2 测试项目488.3 主要测试用例488.4 测试进度518.5 测试方法528.6 测试结果分析528.6.1 测试的局限性528.6.2 评价测试结果的准则528.7 系统的优点及技术特征538.8 系统的不足及改进方案538.9 系统的运行与维护53结 论54致 谢56参 考 文 献57附录A 译文59附录A 外文原文70苏州科技学院本科生毕业设计（论文）第一章 引言1.1 选题背景和意义随着信息技术的飞速发展，各个行业的信息

12、化势在必行。科技的进步大大地提高了生产率。作为高校，如何才能提高办学效率，更好地完成教学任务，跟上社会发展步伐，这是一个摆在教学工作者面前的一个迫切的问题。应用信息化来改造传统的教学管理模式是一个重要途径。近几年来，随着各高校办公自动化工作的推进，教务管理自动化也被摆上了日程。在教务工作中占有很大比重的一项就是每学期的课程表排定工作。由于教工、教室和设备的相对紧张，如何进行合理地安排和分配，从而充分利用教学资源是我们不得不面对的问题。而人工进行排课不仅任务重，效率低，而且易出错，难于维护，想要排出一张各方面都满意的课表非常困难。并且随着高校规模的扩大手工排课的难度和工作量呈几何级数增长。在实际

13、的应用中，很多研究者都提出了各种解决排课问题的方法，由于排课问题的复杂性，还没有找到有效的算法能获得NP完全问题的最优解。因此，如何运用近似算法和新的软件技术来降低排课问题的计算复杂度，仍然是颇具挑战性的研究方向。排课管理系统是利用数据库管理系统开发的一种应用系统,其开发主要包括数据库的建立，充分满足正常的题库管理的前提下，提供了多角度的题库信息查询和题库信息分析报表，使学校管理人员可以随时掌握学校的排课情况，进一步指导学校的教学。真正实现了业务一体化，为学校全方位的信息化管理奠定了基础。传统的人工排课使用手工操作存在许多弊端，如重复劳动严重、效率低下、且不能达到资源的最优化配置等，将产生大量

14、的文件和数据，这对于查找、更新和维护都带来了不少的困难。最令人担心的问题就是出现教室资源冲突或教师资源冲突的情况，而且工作繁琐，工作量巨大,尤其是在给大学校园进行排课时出现的问题更多。当前高校教务管理所涉及到的信息资料数量大、类型多，还76可能带有大量的统计输出，同时学校规模的不断扩大和招生人数的逐年攀升导致传统的排棵手段已无法满足现代化管理的要求。在教学计划的不断完善和各高校校园网建立的大背景下，设计满足高校教务要求的排课系统显得十分必要。而据了解，排课管理是高校教务处重复性比较强且急需得到解决的工作， 且排课系统有安全性要求高、交互性强、处理数据量大等人工难以实现的特点。因此设计一个基于校

15、园网络的人工智能化且操作简便的排课系统是高校教务管理信息系统实现的首要条件，同时也是一大难点，因为排课管理要求综合考虑教师、课程、班级、教室、时间等诸方面的因素，统筹兼顾，使课表既符合教学规律，又能够充分利用现有资源使其最大限度地发挥作用。1.2 国内外研究现状早在20世纪50年代末，国外就有人开始研究课表编排问题。1963年，Gotlieb曾提出一个课表问题的数学模型，但由于排课问题易受实际问题的影响，求解结果也不理想。20世纪70年代，美国人S.Even等就证明了排课问题是一个NP完全问题，其算法的时间复杂度呈指数增长。S.Even的论证正式确立了排课问题的学术地位，把人们对排课问题的认识

16、提高到了理论高度。此外，有些文献试图从图论的角度来求解课表问题，但是图的染色体问题也是NP完全问题，只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题。在国内，在20世纪80年代初期，国内学者开始用从模拟手工排课，也有人工智能构建的专家系统等等，具有代表性的有：南京工学院的UTSS(A University Timetable Seheduling System)系统，大连理工大学的智能教学组织管理与课程调度系统等。这些系统大都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。但是这些课表编排系统往往依赖于各个学校的教学体制，不宜于进行大量推广。1.3 本次设计所做的工作

17、 本次毕业设计过程当中，本人主要负责实验小学教学管理系统的排课算法的分析与设计和后台数据库设计2大块内容。在下面的各章中将具体谈到本人所负责的各个环节的具体设计和实现过程。1.4 本文的组织结构本文对小学排课系统软件进行了原理和技术上的讨论，详细描述了该系统的设计思路和方法，在此基础上开发了可以实际使用的应用软件。本文包括内容如下:引言：描述了系统开发的背景和意义，简单介绍了系统的主要功能，并与传统的语音信箱进行了比较。开发环境：简要的讲述了本次系统中所采用的环境和技术。项目可行性：从4个方面论证了本次项目的可实施性。需求分析：利用面向对象的分析方法，建立各种环境下的用例模型，描绘出系统的功能

18、、性能和其它需求。系统设计：使用面向对象的设计方法，在需求分析确定的模型基础上，设计出软件的逻辑模型、软件各组成部分间的内在结构及实现方法。这一过程分为概要设计、数据库设计和详细设计三部分。系统实现：论述了系统各功能模块的实现方法。测试报告：对开发完成的软件进行测试分析。结论：总结本软件的特点，展望系统未来的发展方向。第二章 开发环境及技术介绍2.1 JSP简介JSP应用程序不同于其他语言开发的单一性程序。使用Jsp编程时，必须首先确定应用程序如何与用户交互，如鼠标单击，用户必须编写代码控制这些事件的响应方法。使用JSP开发数据库应用程序的一般步骤如下所示：（1） 建立数据库（2） 建立用户界

19、面（3） 编写代码（4） 调试运行（5） 编译应用程序（6） 发布应用程序界面设计:（1） 控件的位置（2） 界面元素的一致性（3） 保持界面的简明（4） 使用颜色和图像：增加视觉的感染力（5） 图像和图标：增加应用程序的视觉上的趣味（6） 选取字体JSP应用程序的结构： 由于JSP应用程序是基于对象的，所以应用程序的代码结构就是该程序在屏幕上物理表示的模型。根据定义，对象包含数据和代码。在屏幕上看到的窗体代表属性，这些属性定义了窗体的外观和内在特性14。2.2 Tomcat简介Tomcat 很受广大程序员的喜欢，因为它运行时占用的系统资源小，扩展性好，支持负载平衡与邮件服务等开发应用系统常用

20、的功能；而且它还在不断的 Tomcat 是一个小型的轻量级应用服务器，在本系统中当在一台机器上配置好Apache 服务器，可利用它响应对HTML 页面的访问请求。实际上Tomcat 部分是Apache 服务器的扩展，但它是独立运行的，所以当你运行tomcat 时，它实际上作为一个与Apache 独立的进程单独运行的。 当配置正确时，Apache 为HTML页面服务，而Tomcat 实际上运行JSP 页面和Servlet。另外，Tomcat具有处理HTML页面的功能，同时它还是一个Servlet和JSP容器，独立的Servlet容器是Tomcat的默认模式162.3 数据库设计技术介绍2.3.1

21、 定义数据库设计 (Database Design)是指根据用户的需求，在某一具体的数据库管理系统上，设计数据库的结构和建立数据库的过程。数据库系统需要操作系统的支持。 数据库设计是建立数据库及其应用系统的技术，是信息系统开发和建议中的核心技术。由于数据库应用系统的复杂性，为了支持相关程序运行，数据库设计就变得异常复杂，因此最佳设计不可能一蹴而就，而只能是一种“反复探寻，逐步求精”的过程，也就是规划和结构化数据库中的数据对象以及这些数据对象之间关系的过程。2.3.2 数据库设计方法简述1 手工试凑法设计质量与设计人员的经验和水平有直接关系缺乏科学理论和工程方法的支持，工程的质量难以保证数据库运

22、行一段时间后常常又不同程度地发现各种问题，增加了维护代价2 规范设计法基本思想：过程迭代和逐步求精典型方法：(1)新奥尔良（New Orleans）方法：将数据库设计分为四个阶段S.B.Yao方法：将数据库设计分为五个步骤I.R.Palmer方法：把数据库设计当成一步接一步的过程(2)计算机辅助设计ORACLE Designer 2000SYBASE PowerDesigner2.3.3 设计步骤1需求分析调查和分析用户的业务活动和数据的使用情况，弄清所用数据的种类、范围、数量以及它们在业务活动中交流的情况，确定用户对数据库系统的使用要求和各种约束条件等，形成用户需求规约。 2概念设计对用户要

23、求描述的现实世界(可能是一个工厂、一个商场或者一个学校等)，通过对其中诸处的分类、聚集和概括，建立抽象的概念数据模型。这个概念模型应反映现实世界各部门的信息结构、信息流动情况、信息间的互相制约关系以及各部门对信息储存、查询和加工的要求等。所建立的模型应避开数据库在计算机上的具体实现细节，用一种抽象的形式表示出来。以扩充的实体（E-R模型）联系模型方法为例，第一步先明确现实世界各部门所含的各种实体及其属性、实体间的联系以及对信息的制约条件等，从而给出各部门内所用信息的局部描述(在数据库中称为用户的局部视图)。第二步再将前面得到的多个用户的局部视图集成为一个全局视图，即用户要描述的现实世界的概念数

24、据模型。 3逻辑设计主要工作是将现实世界的概念数据模型设计成数据库的一种逻辑模式，即适应于某种特定数据库管理系统所支持的逻辑数据模式。与此同时，可能还需为各种数据处理应用领域产生相应的逻辑子模式。这一步设计的结果就是所谓“逻辑数据库”。4物理设计根据特定数据库管理系统所提供的多种存储结构和存取方法等依赖于具体计算机结构的各项物理设计措施，对具体的应用任务选定最合适的物理存储结构(包括文件类型、索引结构和数据的存放次序与位逻辑等)、存取方法和存取路径等。这一步设计的结果就是所谓“物理数据库”。 5验证设计在上述设计的基础上，收集数据并具体建立一个数据库，运行一些典型的应用任务来验证数据库设计的正

25、确性和合理性。一般，一个大型数据库的设计过程往往需要经过多次循环反复。当设计的某步发现问题时，可能就需要返回到前面去进行修改。因此，在做上述数据库设计时就应考虑到今后修改设计的可能性和方便性。 6运行与维护设计在数据库系统正式投入运行的过程中，必须不断地对其进行评调整与修改。 至今，数据库设计的很多工作仍需要人工来做，除了关系型数据库已有一套较完整的数据范式理论可用来部分地指导数据库设计之外，尚缺乏一套完善的数据库设计理论、方法和工具，以实现数据库设计的自动化或交互式的半自动化设计。所以数据库设计今后的研究发展方向是研究数据库设计理论，寻求能够更有效地表达语义关系的数据模型，为各阶段的设计提供

26、自动或半自动的设计工具和集成化的开发环境，使数据库的设计更加工程化、更加规范化和更加方便易行，使得在数据库的设计中充分体现软件工程的先进思想和方法。2.3.4 各级模式的形成过程1.需求分析阶段：综合各个用户的应用需求 2.概念设计阶段：形成独立于机器特点，独立于各个DBMS产品的概念模式(E-R图) 3.逻辑设计阶段：首先将E-R图转换成具体的数据库产品支持的数据模型，如关系模型，形成数据库逻辑模式；然后根据用户处理的要求、安全性的考虑，在基本表的基础上再建立必要的视图(View)，形成数据的外模式4.物理设计阶段：根据DBMS特点和处理的需要，进行物理存储安排，建立索引，形成数据库内模式。

27、第三章 项目可行性分析3.1 技术可行性该系统对软、硬件系统要求较低，所需硬件设备，市场上销售且价格较低，甚至可以使用原有的设备。软件上，操作系统采用Windows7或XP操作系统、MyEclipse作为前台开发工具，它具有的“编辑后继续运行”的特性，超越了旧的编辑编译测试模式。它还引入了面向对象的程序设计思想和“控件”概念，使得大量已经编好的JSP程序可以直接拿来使用。同时，JSP又是最容易学习与应用的程序语言之一。它的功能非常强大，已成为一种专业化的开发语言和环境。采用MySQL作为后台数据库平台的管理系统，它在电子商务、数据仓库和数据库解决方案等应用中起着核心作用，可为企业的数据管理提供

28、强大的支持，对数据库中的数据提供有效的管理，并采用有效的措施实现数据的完整性、数据的安全性以及数据的可靠易用性等等。这些软件在实验室排课及教学系统设计与实现开发中已被大量应用，技术上都比较成熟。因此在技术上是可行的。3.2 经济可行性当今学校内部没有完善的实验室排课系统设计与实现，管理水平差，学校课程不能得到合理分配，学生，教师管理档案问题重重。迫切需要提高现代化管理水平、管理质量和管理高校课程。实验室排课及教学系统设计与实现的初步现代化的开发和使用，能够大大提高学校管理者的工作效率，节省成本提高经济效益。它把从事人力资源管理的人员从繁重的手工操作中解脱出来，用更多精力从事创造性的管理活动和其

29、它重要的活动中去，从而达到节省人力、物力，财力的目标；它能使决策、计划和其它管理活动更加科学、精确、灵活。因此，开发一个专门针对实验室排课系统设计与实现，在经济上也是可行的。3.3 操作可行性本系统灵活方便，快捷迅速，适应处理多项数据。采用友好、直观的视窗界面，鼠标、键盘两种操作方式任意选择，方便快捷。界面统一规范，提示信息功能完整，稍一接触就可以上手进行所有操作。3.4 维护可行性在做工作流变更时应慎重考虑其必要性、可行性和对现有系统影响的风险。总的来说应把握的基本原则是对于已经完成的工作流实例不做改动，对于在变更点之前正在执行的工作流不做改动，而对于在变更点之后正在执行的工作流予以终止（如

30、果终止的代价较低）或者重新填充所涉及用户工作列表（如果终止的代价较高）。另外，必须考虑工作流引擎的实际情况，对工作流变更支持较好的工作流引擎可能已经为工作流变更做了充分的考虑，但大多数情况下需要开发人员编码解决。采用工作流驱动方案设计的系统在应对工作流变更时应考虑一下2 种情况：增加、删除新的局部工作流可能会影响已经实例化的全局工作流和新增局部工作流在全局工作流插入点前后（如果存在）的局部工作流。对于后一种情况应注意工作流之间的衔接，包括数据格式是否一致、流程链是否仍然连续（类似向链表中插入节点）。第四章 需求分析4.1 系统的基本功能 1 掌握学校所有的课程和教师的信息。包括每门课程的时间、

31、班级以及任课老师的姓名等。2 针对不同的人员授予不同的权限。提供灵活的浏览、查询功能。可以查看某个系、某个班级所有课程的信息。3 可以对一个或多个班级进入课程管理与排课表管理，可以不限次的生成该班级课程表。4 可以对课程进行变动管理。既可以手工排课，又可以实现自动排序功能。5 帮助系统维护可以实现：重新登录、打印设置（包括统计各种报表及打印等）、退出等操作。6 提供一种或多种课程表输出功能。7 实现功能全面化，由于每个学校或班级的每天课程数目或时间都不太一样，实现智能计算总课程数目和管理对应的时间段，并且根据每门课程的独立分布式来进行排列（例如：语文自动排列的分布方式可以是周一至周五，那么系统

32、就会自动将其平均分布在周一至周五这5天）。8用户管理：设置两个级别用户：管理员和普通用户（教师），管理员有权限操作系统中的所有数据，普通用户只能以执行查询，输出之类的功能，无法对系统进行实质性的操作，用户使用本系统之前必须先通过身份认证。4.2 排课的约束条件在我的排课系统，主要对不同类型课程进行等级划分，排列出课程的排课优先级别，通过优先次序对不同类型的课程使用不同的算法进行排课，能够非常方便地处理各种排课约束条件的限制。例如教师和教室冲突、班级冲突、教师上课时间和地点选择、分层次教学、单双周排课、一课多教师教学和课程连上等各种各样的约束。同时该系统还能够非常迅速地得到排课结果，例如排一千门

33、课只需几分钟时间等一系列问题。4.3 需求模型使用用例模型来表示需求阶段的系统模型，用例模型主要有用例图组成，从该子系统开始到子系统最终的发布，每一个思路整合其用例模型都不相同；随着思路整合的不断进行，用例模型也在不断地发生变化，由于篇幅所限，本文只给出第一次思路整合确定的用例模型和现今最后一次思路整合所确定的用例模型。通过需求分析，确定了排课管理的功能需求，其需求简要概括如下：1排课信息设置：包括教学科目信息，上课时间，科目和教师限制信息，班级排课信息，排课管理系统根据这些排课信息和限制信息对系统进行自动排课。2自动排课和手工排课：对于用户设定了排课信息之后，系统能够自动对课表进行安排，而且

34、能够手工对安排完的课表进行调整，在排课过过程当中，能够对不合理的排课结果给用户进行提示。3课表报表和课表查询，给出全校教师总课表，班级课表；在课表查询中，用户可以选择不同的教师、班级，系统根据用户的选择给出相应的课表。4.3.1 初使用列图 在项目开始阶段，需求不是非常清楚，但是，其需求的中心内容仍然是上面几点，在通过对需求的分析，我们确立了如下几个非常重要的用例：1 科目信息设置2 班级排课信息设置3 自动排课4 课表调整5 课表显示与打印上面所列出的用例即为排课管理系统的主要用例。根据这些主要用例，在项目的初始阶段，为排课管理系统确定了初始用例模型，描述了排课管理系统应该完成的功能，即从用

35、户的角度看，系统应该具有哪些功能。初始用例模型表示如下：图4.1 排课管理初始用例图上面所列出的用例模型，基本上描述了排课系统的主要的功能，将这些基本功能实现，就形成了一个简单的排课管理系统。在项目开发的第一次思路整合开发中，就是以上面确定的系统原型为基础的，这也确定了系统排课管理系统的初始架构。4.3.2 最后用例图通过几次思路整合，在新的需求的增加下和对系统的进一步理解，逐步完善了排课管理系统的用例模型，下面给出的用例图是当前排课系统的最新的用例模型：图4.2 排课管理用例图为方便显示，上面给出的排课管理用例图包括了排课管理子系统中的全部角色和用例。4.3.3 用例描述在建模时，必须给出每

36、个用例的说明，描述该用例所完成的功能，以及完成该用例功能的步骤。当然，对用例的描述也可以使用用例说明文档来表示。为了说明如何使用活动图来表示一个用例的行为，在此给出“自动排课”用例的活动图，如下所示：图4.3自动排课活动图4.4 分析模型在这个阶段，找出排课管理系统中涉及的主要的类，并且结合用例模型中的用例，将各个类与用例有机结合起来。对系统中的类，建立相应的类图来表示各个类之间的关系。而如何让用例与这些类进行结合，则需要建立相应的序列图/协作图来进行建模。4.4.1 分析阶段类图 在分析模型中的给出的类图，并不需要为每个类详细定义方法和属性，在这个阶段的类图，主要反映的是系统中应该有的类和各

37、个类之间的关系；当然，对于一些非常重要的方法和属性，特别是反映各个类之间的关系的方法和属性，在此阶段可以给出定义。在排课管理系统的分析模型中，通过对排课系统的分析和几次思路整合，找出了排课管理系统中涉及的类，并给出了如下的类图和各个类之间的关系：图4.4 排课管理类图(分析)上面类图中，将排课管理中的类分成三种，并构建了类图，这种表示方法能够清楚地表示各个类在系统中所处的位置，更加直观；当然，在实际建模中，也不一定要选择这种表示，开发人员可以根据自己项目的实际情况来选择相应的建模元素。4.4.2 实体类关系图在分析模型中，使用的类分为三类的，其图形的表示也比较简单；而在设计模型中，采用了UML

38、标准的类的表示图形，每个图被分为三个部分，分别表示类名字、属性栏和方法栏，在后面的设计阶段的排课管理类图中可以看到。 在上面的类图中，仅仅给出了三种类之间的关系，但是这样表示还是不够的。实体类之间也是有一定的关系的，对此，我们使用了另一个类图来表示各个实体类之间的关系，如下图： 图4.5 排课管理实体类关系类图4.4.3 序列图/协作图创建在这之前，所做的所有模型都是属于UML的静态建模机制中的；而现在所要用到的建模元素是属于UML的动态建模机制的。在此，给出了自动排课用例的序列图，如下图所示：图4.6 排课工作人员的序列图图4.7 查看课表时的时序图4.5 设计模型在设计阶段的工作，简单来说

39、，是根据分析模型，建立相应的设计模型；确切地说，是定义分析阶段所确定的每一个类，即定义每个类的方法和属性，并确定每个成员的可见性；可见性包括每个类成员是私有、保护、还是公有的。4.5.1 组件图 组件图描述了排课系统各个子系统之间的依赖关系。组成自动排课系统的页面包括：主页面，班级管理页面，教师管理页面，教室管理页面，课程管理页面，课表管理页面。图4.8 组件图4.5.2 配置图配置图主要是用来说明如何配置系统的软件和硬软。自动排课系统的应用服务器主要负责整个系统运行的总体协调工作,数据库则是负责数据管理。查询管理是用户可以用该页面对未安排的或已安排的进行快速的查看。教室管理是用来对教室的安排

40、。课程管理是对每个班级，教师所授课程的管理。教师管理是对是是否有课老师的管理。班级管理是每个班级的课程管理。4.9 配置图第五章 排课算法分析与设计5.1 背景与研究意义排课问题早在70年代就证明是一个NP完全问题，即算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。对于NP问题完全问题目前在 数学上是没有一个通用的算法能够很好地解决。然而很多NP完全问题目具有很重要的实际意义，例如。大家熟悉地路由算法就是很典型的一个NP完全问题，路由 要在从多的节点中找出最短路径完成信息的传递。既然都是NP完全问题，那么很多路由算法就可以运用到解决排课问题上，如Dijkstra算法、节点子树剪

41、 枝构造网络最短路径法等等。目前大家对NP 完全问题研究的主要思想是如何降低其计算复杂度。即利用一个近似算法来代替，力争使得解决问题的时间从指数增长化简到多项式增长。结合到课表问题就是建立 一个合适的现实简约模型，利用该简约模型能够大大降低算法的复杂度，便于程序实现，这是解决排课问题一个很多的思路。在高等院校中，培养学生的主要途径是教学。在教学活动中，有一系列管理工作，其中，教学计划的实施是一个重要的教学环节。每学期管理人员都要整理教 学计划，根据教学计划下达教学任务书，然后根据教学任务书编排课程表。在这些教学调度工作中，既有大量繁琐的数据整理工作，更有严谨思维的脑力劳动，还要 填写大量的表格

42、。因此工作非常繁重。加之，随着教学改革的进行及“211”工程的实施，新的教育体制对课表的编排提出了更高的要求。手工排课时，信息的上通下达是极其麻烦的，而采用计 算机排课，教学中的信息可以一目了然，对于优化学生的学习进程，评估每位教师对教学的贡献，领导合理决策等都具有重要的意义，必将会大大推进教学的良性循 环。5.2 解决NP问题的几种算法及其比较解决NP完全问题只能依靠近似算法，所以下面介绍几种常用算法的设计思想，包括动态规划、贪心算法、回溯法等。5.2.1 动态规划动态规划法是将求解的问题一层一层地分解成一级一级、规模逐步缩小的子问题，直到可以直接求出其解的子问题为止。分解成的所有子问题按层

43、次 关系构成一颗子问题树。树根是原问题。原问题的解依赖于子问题树中所有子问题的解。动态规划算法通常用于求一个问题在某种意义下的最优解。设计一个动态规 划算法，通常可按以下几个步骤进行：1. 分析最优解的性质，并刻划其结构特征。2. 递归的定义最优解。3. 以自底向上的方式计算出最优解。4. 根据计算最优解时得到的信息，构造一个最优解。步骤13是动态规划算法的基本步骤。在只需要求出最优解的情形，步骤4可以省去。若需要求出问题的一个最优解，则必须执行步骤4。此时，在步骤3中计算最优解时，通常需记录更多的信息，以便在步骤4中，根据所记录的信息，快速地构造出一个最优解。5.2.2 贪心算法当一个问题具有最优子结构性质时，我们会想到用动态规划法去解它，但有时会有更简单、更有效的算法，即贪心算法。顾名思义，贪心算法总是做出在当前 看来最好的选择。也就是说贪心算法并不是整体最优上加以考虑，他所作出的选择只是在某种意义上的局部最优的选择。虽然贪心算法不是对所有问题都能得到整体 最优解，但对范围相当广的许多问题它能产生整体最优解，如图的算法中单源最短路径问题，最小支撑树问题等。在一些情况下，即使贪心算法不能得到整体最优 解，但其最终结果却是最优