（计算机软件与理论专业论文）排课系统的研究与实现.pdf

摘要 摘要 随着信息技术的不断发展和普及，使教育面临新的课题和挑战。课程安排和 管理是高等学校教务活动中非常重要的工作之一，是保证教学秩序正常进行的前 提和基础。在高校招生规模扩大、教学资源严重不足、办学形式多样化的今天， 排课过程涉及面广、约束条件多，人工排课已经无法完成，借助计算机软件辅助 排课是当前各高校普遍采用的手段。如何才能得到一个高效快速的排课系统是高 校教务管理人员梦寐以求的事。然而，在实际项目的研发中，由于排课问题是一 个n p 完全问题，开发出符合要求的排课系统是一件难事。结合本人在成都大学教 务处工作过的实际，针对我校现行排课系统存在的问题，通过阅读、研究一些排 课方面的文献资料，本文认为通过改进排课策略和局部排课方法，能够增强排课 系统的实用性。 贪心算法是从问题的某一个初始解出发，通过一系列的贪心选择一一当前状 态下的最优选择，逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算 法中的某一步不能再继续前进时，算法停止。在贪心算法( g r e e d ym e t h o d ) 中采用 逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策( 在一定的标 准下) 。 结合我校实际，本文对我校排课系统作了详细分析与研究，并利用贪心算法 对系统作了具体实现，其主要工作如下： 1 、对目前流行的软件开发技术作了详细介绍，并在本系统中得到充分运用。 2 、根据我校排课系统的需求，进行了排课相关资源的规划及对贪心算法的研 究与分析。 3 、根据需求分析和排课算法的设计，对系统的数据库结构、系统模块及系统 安全进行了详细分析和设计。 4 、介绍了n e t 的开发技术，以及分布式应用程序在n e t 架构下的设计与实 现。重点研究了本排课系统在n e t 架构上的设计与实现。 关键字：排课系统，贪心算法，n e t 架构 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n ta n dp o p u l a r i z a t i o no ft h ei n f o r m a t i o nt e c h n o l o g y , e d u c a t i o n i sf a c e dw i mn e wi s s u e sa n dc h a l l e n g e s c o u r s ea r r a n g e m e n ta n dm a n a g e m e n ti so n eo f t h em o s ti m p o r t a n tt a s k so fe d u c a t i o n a la d m i n i s t r a t i o ni nc o l l e g e so ru n i v e r s i t i e s ，a s w e l la st h e p r e c o n d i t i o n a n db a s ew h i c hw i l le n s u r e t e a c h i n ga r r a n g e m e n ti n o r d e r n o w a d a y s ，b e c a u s eo fas e r i o u ss h o r t a g eo ft e a c h i n gr e s o u r c e s ，e x p a n s i o no f e n r o l l m e n to fs t u d e n t si nc o l l e g e so ru n i v e r s i t i e sa n dv a r i e t yo fs c h o o lf o r m s ，c o u r s e a r r a n g e m e n tp r o c e s si n v o l v e sb r o a d l ya n d t h e r ea r em a n yr e s t r i c t e dc o n d i t i o n s ，i nw h i c h c o n d i t i o n ，i ti sav e r yp o p u l a rw a yi n e a c hc o l l e g e so ru n i v e r s i t i e st oa s s i s tc o u r s e a r r a n g e m e n tb yd i n to fc o m p u t e rs o f t w a r e ，o t h e r w i s ew ec a n n o tc o m p l e t e i tb ym a n u a l w o r k t h e r e f o r e ，e d u c a t i o n a la d m i n i s t r a t i o ni nc o l l e g e so ru n i v e r s i t i e se a r n e s t l yl o n gf o r a ne f f i c i e n tc o u r s ea r r a n g e m e n ts y s t e m h o w e v e r ，i nt h ea c t u a lr e s e a r c h i n gp r o j e c t ， a r r a n g i n gc o u r s ei san pp r o b l e m w h i c hi sd i f f i c u l tt od e v e l o pag o o da r r a n g i n gc o u r s e s y s t e mt om e e tt h er e q u i r e m e n t so fu s e r s a c c o r d i n g t om ye x p e r i e n c ei na d m i n i s t r a t i o n o f f i c eo fc h e n g d uu n i v e r s i t y ，a n di nr e s p o n s et ot h ep r o b l e mo ft h ec u r r e n tc o u r s e s c h e d u l i n gs y s t e mi n0 1 1 1 u n i v e r s i t y , t h i st h e s i sc o n s i d e r st h a ti tc a no p t i m i z et h ec o u r s e a r r a n g i n gs y s t e mb yi m p r o v i n gt h ea r r a n g e m e n tt a c t i c sa n dm e t h o d s ，t h r o u g hr e a d i n g a n ds t u d y i n gs o m ed a t a si nt h i sf i e l d g r e e d ya r i t h m e t i cg e t sg o i n gf r o ma ni n i t i a ls o l u t i o nt op r o b l e m ，t h r o u g ha s e r i e s o fg r e e d i n gc h o s e nw h i c hi sb e s tc h o s e na tc u r r e n t l ys t a t u s ， a n di tg e t st h ea i ms t e pb y s t e p ，h o p et og e tt h eb e t t e rs o l u t i o na sp o s s i b l ea u si tc a n w h e n i tr e a c h e sas t e pc a nn o t r e s u m p t i o n ，t h ea r i t h m e t i cw i l ls t o p g r e e d ya r i t h m e t i cw a n t t og e tt l l eb e s ts o l u t i o ns t e p b ys t e p ，a te v e r ys t e p ，i t w i l lm a k ead e c i s i o nt h a ts e e mt ob e s t a c c o r d i n gt om y s c h o o l sr e a l i t y ，t h i st h e s i ss t a r t sw i t ht h eb a s i ct h e o r yo fg r e e d y a l g o r i t h m s i th a sb e e nc a r e f u l l ya n a l y s i sa n d r e s e a r c h e do u rs c h o o lc o u r s ea r r a n g e m e n t a n du s e dg r e e d ya l g o r i t h m st oh a v er e a l i z e dc o u r s ea r r a n g e m e n ts y s t e m t h ef o l l o w i n g p a s s a g ea r em o s t l y w o r ka b o u tt h i sp a p e r 1 、p o p u l a rs o f t w a r ed e v e l o p m e n tt e c h n o l o g yw a ss y s t e m a t i c a l l yi n t r o d u c e da n d s u f f i c i e n t l yu s e di nt h i ss y s t e m a b s t r a c t 2 、a l l o c a t e dc l a s ss c h e d u l i n gr e l a t e dr e s o u r c e ，a n a l y z e da n dd e s i g n e dg r e e d y m e t h o do ft h es y s t e m ，b a s e do nt h es p e c i f i cn e e do fo u rs c h o o l s sc o u r s ea r r a n g e m e n t s y s t e m 3 、a c c o r d i n gt ot h en e e da n a l y s i sa n dt h ed e s i g no fc l a s ss c h e d u l i n ga l g o r i t h m ， w ea n a l y s i s e da n dd e s i g n e dd e t a i l e d l yt h ed a t a s t r u c t u r e 、s y s t e mm o d u l ea n ds a f e t yo f t h es y s t e m 4 、i ti n t r o d u c e dt h e d e v e l o p m e n tt e c h n i q u eo f n e ta n dt h ed e s i g na n d a c c o m p l i s h m e n to fd i s t r i b u t i v ea p p l i c a t i o ni n n e tf r a m e w o r k i tm a i n l yr e s e a r c h e dt h e d e s i g na n da c c o m p l i s h m e n to fa l g o r i t h mo fa r r a n g e m e n to fc u r r i c u l u mi n n e t f r a m e w o r k k e y w o r d s ：c o u r s ea r r a n g e m e n ts y s t e m ，g r e e d ym e t h o d ，n e tf r a m e w o r k i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 和7 年月易日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：彭耄荤导师签名：善雠 日期：即年钥3 e l 第一章序言 1 1 论文研究背景及意义 第一章序言 课程表是一个学校日常教学工作和其他各项活动的指挥调度表。它不仅是学 生和教师上课的依据，而且对学校其他工作的统一安排也有直接影响。利用计算 机辅助手段编排课表，是教学管理走向科学化、现代化的重要标志之一。 随着计算机在教学工作中的普及应用，各级各类学校教务管理部门均在尝试 用计算机代替劳动强度大、工作效率低的手工排课工作。然而排课问题与运筹学 中研究的一个问题时间表问题( t i m et a b l ep r o b l e m s ，简记t t p ) 密切相关， 并被公认是n p 难解问题。由于排课问题本身的复杂性和难解性，一直没有得到完 全有效的解决。 随着对排课问题研究的逐步深入，市场上已出现一些商业排课系统，例如： 南京工学院的u t s s 系统、清华大学的t i s e r 系统、正达排课软件、德凯排课软件 智能排课系统等。但这些软件的课表的编排依赖于各个学校的教学约束条件，其 通用性、灵活性和方便性均有待进一步提高。 2 0 0 6 年成都教育学院、成都幼儿师范学校、成都卫生学校并入成都大学，学 校招生规模也逐年扩大。目前成都大学教务管理部门使用的排课软件也存在教学 区域教学楼不能合理安排，智能化排课程度低，大量课表需要手工调整，不能很 大程度上满足教师个性化排课要求等等问题。 为了提高我校教务管理部门的信息化水平与工作效率，减轻教务管理部门工 作人员的劳动强度，科学合理地调度师资与教室资源，安排出符合教学计划和广 大师生要求的课表，作者参与了我校排课软件系统的研究开发。 1 2 排课系统现状分析 随着高等教育的发展，教学资源和学生之间的供需缺口越来越大，需要合理 安排课程和教室资源，达到教学资源的充分利用，引发众多高校、科研机构、软 件公司及个人对排课问题从理论与实践两个方面进行了大量的研究与开发工作， 涌现出了很多专业排课系统。 电子科技大学硕士学位论文 各个学校的课程设置和专业及学校的要求密切相关，随着教学计划的不同， 上课的时间顺序有很大的差异，课程表的编排需要了解教学计划、教师、教室、 学生自然班的情况。找到课程、上课时间、上课地点、教师和其他资源综合的一 个最优解是一个非常复杂的问题，因此，课程表问题是一个多因素的优化决策问 题，最终的目标是为每学期的每门课程安排恰当的上课时间和地点，从而保证学 校整个教学工作的顺利进行。 在1 9 6 2 年，g o t l i e b 提出一个课表问题的数学模型，此后人们对课表问题的 算法、解的存在性等问题作了很多探索，但大多数文献中用到的数学模型都是 g o t l i e b 的数学模型的简化或补充【m 】。 近4 0 年来，人们对课表问题的计算机解法做了许多尝试。有些文献试图从图 论的角度来求解排课表的问题，但是图的染色问题也是n p 完全问题，只有在极为 简单的情况下才可以将课表编排转化为二部图匹配问题，这样的数学模型与实际 相差太远，所以对于大多数学校的课表编排问题来说没有实用价值【4 匍。 进入九十年代以后，国外对课表问题的研究仍然十分活跃。比较有代表性的 有印度的v a s t a p u r 大学管理学院的a r a b i n d a t r i p a t h y 、加拿大m o n t r e a l 大学的 j e a na u b i n 和j a c q u e sf e r l a n d 等【删。目前，解决课表问题的方法有：模拟手工 排课法，图论方法，拉格朗日法，二次分配法等多种方法【6 母】。国外的研究表明， 解决大规模课表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划 的思想将问题分解，是一个有望得到成功的办法。 在国内，对课表问题的研究开始于8 0 年代初期、具有代表性的有：南京工学 院的u t s s ( au n i v e r s i t yt i m e t a b l es c h e d u li n gs y s t e m ) 系统，清华大学的t i s e r ( t i m e t a b l es c h e d u l e ) 系统，大连理工大学的智能教学组织管理与课程调度等。 这些系统大多数都是模拟手工排课过程，以“班”为单位，运用启发式函数来进 行编排的。但是这些系统课表编排往往比较依赖于各个学校的教学约束条件，不 宜进行大量推广【1 0 - 1 2 1 。 总而言之，从这些排课软件的实际使用的情况来看，其方便性、实用性和通 用性还不尽如人意。由于国内各高校教学模式和资源的不同、约束也存在很大的 差异，所以到现在为止还没有一款适合所有学校的通用的排课软件。就成都大学 来说，也曾经购买过几个排课软件，但都存在这样或那样的问题，不能很大程度 上满足教师个性化排课要求。所以研究高效、灵活的符合我校实际情况的排课系 2 第一章序言 统是具有现实意义的。 1 3 作者主要工作 随着成都大学四校合并以及招生规模的逐年扩大，原有的教务管理系统不能 很好地满足我校教务管理工作。而排课管理系统是教务管理的一个很重要的模块， 本人参与本课题的研究，主要工作如下： 1 、对排课系统进行需求分析及算法设计。 2 、对排课系统数据库进行详细设计 3 、系统架构的实现。 1 4 论文组织结构 本论文首先对我校排课系统进行了需求分析和算法设计，然后在n e t 架构模 式下进行设计与实现，以下是论文的主要内容。 第一章：序言 介绍了本课题的研究背景、意义及该课题国内外研究的现状，同时介绍了作 者的主要工作及论文组织结构的安排。 第二章：系统相关技术 首先对系统采用的相关技术和开发工具进行了介绍。然后再简要介绍了系统 建模工具u m l 。 第三章：成都大学排课系统分析 根据成都大学排课系统的需求，进行了排课相关资源的规划及排课算法设计 和系统安全设计。 第四章：成都大学排课系统设计与实现 本章介绍了数据库设计步骤，需求分析，系统功能模块组成和各功能模块的 设计，最后介绍了系统在n e t 架构上的设计与实现。 第五章：系统测试 3 电子科技大学硕士学位论文 本章介绍了系统的测试方法、过程及系统的运行结果。 第六章：总结与展望 本章对系统从需求分析到算法设计及实现进行总结，同时也指出本论文存在 的不足和需要继续完善的地方。 4 第二章系统相关技术 第二章系统相关技术 本章首先对系统采用的相关技术和开发工具进行了介绍，然后简要介绍了算 法设计和u m l 建模工具。 2 1 微软网络开发平台简介 1 、n e t 开发平台概述 n e t 是建立在开放体系结构基础之上的w e b 应用程序的开发平台，它的策略 是将互联网本身看作新一代操作系统的基础，对互联网和操作系统的设计思想进 行合理的延伸。x m l 是i n t e r n e t 环境中跨平台的依赖于内容的技术，是处理分布 式结构信息的选择工具。x m l 是年轻的m e t a 语言，不仅满足了w e b 开发者的需要， 而且适合于任何对出版业感兴趣的人。它让网站之间相互协作，提供一系列互动 式的新型网络服务。 n e t 开发平台包括以下内容1 3 】： n e tf r a m e w o r k ( 框架) ，包括：公共语言运行库( c l r ，c o m m o nl a n g u a g e r u n t i m e ) ，它处于框架的底层，是框架的基础；基础类库，它提供了一个面向对 象的、层次化的、可扩展的统一编程接口。 n e t 开发工具，包括：v i s u a ls t u d i o n e ti n t e g r a t e dd e v e l o p m e n t e n v i r o n m e n t ，用来开发和测试应用程序；n e t 编程语言用来创建运行在c l r 下并 且使用类库的应用程序，如：c # 、j # 等。 a s p n e t 是一个取代以前的a c t i v es e r v e rp a g e s 的特殊类库，用来创建动态 的w e b 内容和w e b 服务器应用程序，这些都将采用诸如h t m l 、x m l 和s i m p l eo b j e c t a c c e s sp r o t o c o l ( s o a p ) 等i n t e r n e t 协议。n e t 开发平台的组成如图2 - 1 所示。 2 、n e t 框架【1 3 】 n e t 框架是n e t 的基础结构，它提供了构建和执行应用程序及x m lw e b s e r v i c e 的基础平台。所有的应用程序，无论是w i n d o w s 应用程序、w e b 应用程序 还是x m lw e bs e r v i c e ，都可以使用一套通用的工具和代码来开发，并且易于互相 5 电子科技大学硕士学位论文 集成。 6 第二章系统相关技术 价也大大降低。 m i c r o s o f t n e t 对于最终用户来说意义重大，因为它将使计算机的功能越来越 强大，操作也越来越简单。对开发人员来说，n e t 它不但可以改变开发人员开发 应用程序的方式，而且还可以使得开发人员能创建出各种全新的应用程序。总之， m i c r o s o f t n e t 将把计算和通信带入一个丰富、合作和互动的环境中，远胜过今天 的单向网络。作为第一个全面利用计算与通信技术的平台，m i c r o s o f t n e t 无疑是 当今计算机技术通向计算时代的一个十分重要的里程碑。 2 2 网络编程语言 现在流行的网络编程语言主要有a s p ，j s p 和p h p ，下面对它们作一些简单的 介绍和比较【1 3 15 1 。 a s p 是a c t i v es e r v e rp a g e s 的缩写，是微软公司推出的w e b 应用程序开发技 术的一个服务器的脚本环境。a s p 它本身并不是一种脚本语言和开发工具，而只是 一种技术框架。利用a s p 提供的服务器端脚本环境，在服务器端，可以结合h t m l 、 a s p 指令和对象以及a c t i v e x 元件建立交互的、动态的、高性能的w e b 服务器应用 程序。 1 、a s p 有如下几个特点：( 1 ) 可在服务器端直接执行，因为它容易编写且无 须c o m p i l e 编译。( 2 ) 由于a s p 源文件为纯文本文件，所以普通的文本编辑器， 如w i n d o w s 的记事本，就可以编写a s p 程序。( 3 ) 与浏览器无关( b r o w s e r i n d e p e n d e n c e ) ，a s p 所使用的脚本v b s c r i p t 、j s c r i p t 均在w e b 服务端执行，用户 端的浏览器不需要能够执行这些脚本语言。同时也正是因为a s p 的源程序，不会 被传到客户浏览器，因而可以避免所写的源程序被他人剽窃，程序的安全性也得 到了一定提高。( 4 ) a s p 不仅可以使用v bs c r i p t 或j s c r i p t 语言来设计，而且它 还可以采用p l u g i n 的方式，使用第三方提供的其它脚本语言等。因此，a s p 能 与任何a c t i v e xs c r i p t i n g 语言兼容。( 5 ) a c t i v e x 服务器组件具有无限可扩充性。 a c t i v e x 可以使用v i s u a lb a s i c 、j a v a 、v i s u a lc + + 、c o b o l 等程序设计语言来 实现【乃j 。 2 、p h p ( p e r s o n a lh o m ep a g e s ) 是一种在服务器端运行的、h t m l 文档中嵌入 的脚本语言。它借鉴c 语言、j a v a 语言和p e r l 语言的语法，同时具有自己独特的语 法，可以快速运行于多种平台上。与其他中间件技术相比，p h p 具有扩展性好、开 7 电子科技大学硕士学位论文 发代码快、安全性好、代码执行速度快、可移植性好等优点。p h p 最强大和最重要 的特征就是它几乎支持现在所有的数据库，如：o r a c l e 、s y b a s e 、m y s q l 、o d b c 等常见数据库。由于p h p 采用源代码公开方式，程序员可以为它不断加入新的东西， 形成庞大的函数库，以实现更多的功能，所以p h p 具有很好的开放性和可扩展性。 为了实现面向对象编程，p h p 还提供了类和对象，包括对象重载和引用技术等。p h p 还具有多种功能，包括图像处理、编码与解码、压缩文件处理、x m l 解析、支持 h t t p 的身份认证、c o o k i e 、p o p 3 、s n m p 等。 3 、j s p ( j a y & s e r v e rp a g e s ) 是由s u n 公司推出的一种基于j a v a 语言的动 态网页技术。它是在服务器端应用的一种脚本，所以它拥有对服务器端资源的访 问权限。它在传统的h t m l 页面中加入了j a v a 程序片段和j s p 标记构成，因此它 可以将页面表示层和业务逻辑层进行分离。j s p 不仅可以访问可重用的组件，如 s e r v l e t 、j a v a b e a n 和基于j a v a 的w e b 应用程序，而且它还支持在w e b 页面中直 接嵌入j a v a 代码。对于j s p 文件的访问可以有两种方法：浏览器发送j s p 文件请 求、发送至s e r v l e t 的请求。 a s p 和j s p 都属于面向w e b 服务器的技术，它们都是在服务器端执行的，客户 端浏览器都不需要安装任何附加的软件。但是它们也存在着最明显的区别：j s p 的 动态部分用j a v a 编写，而不是用v b s c r i p t 或其它m i c r o s o f t 语言编写，而a s p 则是使用v b s c r i p t 之类的脚本语言，因此j s p 相对于a s p 具有更强大和易用的功 能。 h p h 和j s p 都具有很好的可移植性，基本上可以在所有的平台上执行。h p h 几 乎支持现在所有的数据库，但是h p h 没有像j s p 和a s p 那样对组件的支持功能， 其扩展性较差。目前，由于j s p 是一种新技术，所以在国内应用较少，而h p h 和 a s p 在国内应用较为广泛。综合上面对a s p 、j s p 和p h p 的介绍和比较，由于我们 的开发人员对a s p 比较熟悉并且a s p 也满足我们所开发系统的需要，所以，在此 我们选择a s p 作为系统的开发工具。 2 3s q ls e r v e r2 0 0 0 及s q l 语言简介 1 、s q ls e r v e r2 0 0 0 简介1 6 】 s q ls e r v e r 是由m i c r o s o f t 公司开发和推广的关系数据库管理系统( d b m s ) ， 它具有强大的数据管理功能，提供了丰富的管理工具支持数据的完整性管理、安 第二章系统相关技术 全性管理和作业管理。s o ls e r v e r 具有分布式数据库和数据仓库功能，能进行分 布式事务处理和联机分析处理，支持客户机服务器结构。s q ls e r v e r 支持标准的 a n s is q l ，还把标准s q l 扩展成为更为实用的t r a n s a c t - s q l 。另外，s q ls e r v e r 还具有强大的网络功能，可以接收电子邮件和发布w e b 页面。 s q ls e r v e r2 0 0 0 是一套完整的数据库和分析产品，它除了具有扩展性、可靠 性、易于安装、部署和使用数据仓库等功能外，它还包含许多新特性，这些特性 使其成为针对电子商务、数据仓库和在线商务解决方案的卓越的数据库平台。 总之，s q ls e r v e r 是目前广为使用的数据库管理系统，它具有较强的可靠性、 质量性和易用性，而且其价格较低，性能完全能够满足系统的需要。综合考虑我 们选择了s q ls e r v e r2 0 0 0 作为后台数据库工具。 2 、s q l 语言简介【1 6 】 s q l ( s t r u c t u r e dq u e r yl a n g u a g e ) 是一种功能强大的“结构化查询语言 ，目 前所有关系型数据库管理系统都以s q l 作为核心，包括在j a v a 、v c + + 、v b 、d e l p h i 程序设计语言中也都可使用s q l ，是一种真正跨平台跨产品的语言。按照a n s i ( 美 国国家标准协会) 的规定，s q l 被确定为关系型数据库管理系统的标准语言。s q l 语言简洁明了、方便实用、功能齐全，备受广大用户的欢迎。 s q l 语言功能主要包括以下四个方面： ( 1 ) 数据定义语言d d l ( d a t ad e f i n i t i o nl a n g u a g e ) ：它包括三部分功能：定 义基本表、定义视图和定义索引。其中定义基本表又包括创建表、修改表和删除 表。它主要包括c r e a t e ，a l t e r 和d r o p 三条命令。 ( 2 ) 数据查询语言d q l ( d a t aq u e r yl a n g u a g e ) ：用于查询数据，它的主要命 令是s e l e c t 。 ( 3 ) 数据控制语言d c l ( d a t ac o n t r o ll a n g u a g e ) ：用于控制用户对数据表的 访问权限。它主要包括g r a n t 和r e v o k e 命令。 ( 4 ) 数据操纵语言d m l ( d a t am a n i p u l a t i o nl a n g u a g e ) ：用于修改数据，比 如插入、修改或删除数据。它主要包括以下几个语句： i n s e r t ：向数据库中增加数据。 u p d a t e ：对数据库中的数据进行修改。 9 电子科技大学硕士学位论文 d e l e t e ：删除数据库中的数据。 s q l 集数据查询、数据操纵、数据定义和数据控制功能于一身，充分体现了关 系数据语言的优越性，是一种功能强大、通用性好又简单易学的语言。s o l 语言的 主要特点如下： ( 1 ) 高度非过程化 用s q l 进行数据操作，用户只需要指出“干什么 ，而不需要指出“怎么干 因此用户不必了解文件的存取路径，数据的存取和s q l 语句的操作过程由系统自 动完成。 ( 2 ) 面向集合的操作方式 s q l 采用集合操作方式，不仅查询的结果可以是元组的集合，而且一次更新操 作的对象也可以是元组的集合。 ( 3 ) 语言简洁、易学易用 虽然s q l 语言的功能非常强大，但是它的语法简单，语言简洁，只有少量的 关键字，所以学习起来很容易。 2 4 基于浏览器服务器的体系研究 浏览器服务器( b s ：b r o w s e r s e r v e r ) 结构即浏览器和服务器结构。它是随 着i n t e r n e t 技术的兴起，对c s 模式应用的扩展。在这种结构下，用户工作界面 是通过i e 浏览器来实现的。b s 结构是一种全新的软件体系结构，它利用不断成 熟和普及的浏览器技术结合浏览器的多种脚本语言，用通用浏览器实现原来需要 复杂专用软件才能实现的强大功能，大大节约了系统开发成本。 b s 结构具有如下优点： 1 、具有分布性特点，可以随时随地进行查询、浏览等业务处理。 2 、业务扩展简单方便，通过增加网页即可增加服务器功能。 3 、维护简单方便，只需改变网页，即可实现所有用户的同步更新。 4 、开发简单，共享性强。 在成都大学排课系统软件开发过程中，系统采用微软的n e t 技术实现系统的 l o 第二章系统相关技术 b s 架构。 2 5 算法设计简介 算法不仅是计算机科学的一个分支，它更是计算机科学的核心。在第一台计 算机诞生之前，国内外就有人开始了算法的研究，也产生了很多有效的算法，例 如：欧几里德算法。随着计算机技术的飞速发展，越来越多的计算机爱好者加入 到算法研究的行列，很多过去无法处理的问题也在新的算法的研究下得以轻松解 决。算法研究的领域十分广泛，无论从事计算机的理论还是实际应用研究，都与 算法有着千丝万缕的联系。下面我们给出“算法 的概念描述。 算法是一系列解决问题的清晰指令， 可以在有限时间内获得相应的输出结果。 也就是说，对于符合要求的数据输入， 如果一个算法有缺陷，或不适合于某个 问题，执行这个算法将不会解决这个问题。对于同一个任务，若用不同的算法来 完成，则可能会花费不同的时间、空间或者效率。当然，对于一个算法的优劣， 我们可以用空间复杂度和时间复杂度来衡量它。 一般情况下，一个算法具有以下五个基本特征： l 、有穷性：一个算法在执行有穷步之后必须结束。 2 、确定性：算法中每条指令必须有确切的含义，读者理解时不会产生二义性。 3 、可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次 来实现的。 4 、输入：有零个或多个外部量作为算法的输入。 5 、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没 有输出的算法是毫无意义的。 算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过 程。当面临某个问题时，需要找到用计算机解决这个问题的方法和步骤，算法就 是对解决这个问题的方法和步骤的描述。在算法的表示中它具有以下的性质： 1 、目的性：算法有明确的目的，能完成赋予它的功能。 2 、分步性：算法为完成其复杂的功能，由一系列计算机可执行的步骤组成。 3 、有序性：算法的步骤是有序的，不可随意改变算法步骤的执行顺序。 电子科技大学硕士学位论文 4 、有限性：算法是有限的指令序列，所包含步骤也应是有限的。 5 、操作性：有意义的算法总是对某些对象进行操作，使其改变状态，完成其 相应的功能。 算法设计技术是用算法解题的一般性方法，用于解决不同计算领域的多种问 题。在算法设计过程中我们还应该注意以下几个问题： 1 、正确性( c o r r e c t n e s s ) ：说一个算法是正确的，是指对于一切合法的输入 数据，该算法经过有限时间( 算法意义上的有限) 的执行都能产生正确( 或者说 满足规格说明要求) 的结果。一切合法的输入数据都能得出满足要求的结果；典 型、苛刻的几组输入数据也能够得出满足要求的结果。为了保证算法的正确性， 我们在设计算法时力争严谨、考虑周全，在可能的情况下，分析论证算法设计的 合理性，最后在算法实现后，依靠大量的测试，以保证算法的正确性。 2 、可读性( r e a d a b i l i t y ) ：一个好的算法应该是易于理解的，晦涩难读的算 法容易隐藏较多错误而难以调试。 3 、健壮性( r u b u s t n e s s ) ：算法的异常情况。处理出错的方法是返回一个表 示错误或错误性质的值，以便在更高的抽象层次上进行处理。 4 、高效率与低存储量需求：效率指的是算法执行时间，存储量指的是算法执 行过程中所需的最大存储空间，这两者都与问题的规模有关。 算法设计的基本方法通常有结构化方法和面向对象方法。在本系统的算法设 计中我们采用面向对象的方法来加以设计。结构化方法总的指导思想是自顶向下、 逐步求精。它的基本原则是功能的分解与模块化。所谓“自项向下”是将现实世 界的问题经抽象转化为逻辑空间或求解空间的问题。是将复杂且大的问题划分为 较小问题，找出问题的关键和重点，然后抽象、概括地描述问题。所谓“逐步求 精”是将复杂问题经抽象化处理变为相对比较简单的问题。经若干步精化处理， 最后细化到用“三种基本结构 及基本操作去描述算法。结构化算法设计具有符 合人类解决复杂问题的普遍规律的优点。它用先全局后局部、先整体后细节、先 抽象后具体的逐步求精过程开发出的算法有清晰的层次结构。 重用是面向对象的一个重要优点。最大特点是能够大幅度的提高软件项目的 成功率，减少日后的维护费用，提高软件的可移植性和可靠性。面向对象算法设 计方法的过程包括以下步骤： 1 2 第二章系统相关技术 1 、在给定的抽象层次上识别类和对象。 2 、识别这些对象和类的语义。 3 、识别类和对象之间的关系。 4 、实现类和对象。 2 6 系统模型工具研究 模型是用某种工具对同类或其它工具的表达方式，它抓住事物最重要的方面 而简化或忽略其它方面。各个领域中都有用到模型，在计算机领域中主要用建模 语言来表达，如u m l 等。 统一建模语言( u n i f i e dm o d e l i n gl a n g u a g e ，u m l ) 是一种用于对软件密集 型系统的制品进行可视化、详述、构造和文档化的图形语言。它是由b o o c h 、 j a c o b s o n 和r u m b a u g h 三位面向对象方法专家提出来的，是一种定义良好、易于表 达、功能强大且普遍适用的建模语言，它的出现是面向对象技术发展的重要成果。 我们借助u m l 软件模型，可以正确理解系统需求，从而对系统进行恰当的分析和 设计，这样就可以使软件的扩展性和易维护性得到较大提高。 下面介绍标准建模语言u m l 的内容，作为一种建模语言，u m l 的定义包括u m l 语义和u m l 表示法两个部分。 1 、u m l 语义：描述基于u m l 的精确元模型定义。元模型为u m l 的所有元素在 语法和语义上提供了简单、一致、通用的定义性说明，使开发者能在语义上取得一 致，消除了因人而异的最佳表达方法所造成的影响。此外u m l 还支持对元模型的扩 展定义。 2 、u m l 表示法：定义u m l 符号的表示法，为开发者或开发工具使用这些图形符 号和文本语法为系统建模提供了标准。这些图形符号和文字所表达的是应用级的 模型，在语义上它是u m l 元模型的实例。 标准建模语言u 地的内容可以由下列五类图来定义： 第一类是用例图，从用户角度描述系统功能，并指出各功能的操作者。它包含 用例，系统，角色三种模型元素。系统：是用例模型的一个组成部分，代表一部机 器或者一个商务活动，而不是真正实现的软件系统。角色：是与系统交互的人或事， 1 3 电子科技大学硕士学位论文 是一个群体概念；角色是启动用例的前提条件，可以分为主要角色和次要角色，或 者主动角色和被动角色。用例：是一个完整的功能，是动作( a c t i o n ) 步骤的集合，用 例总是由角色初始化，为角色提供值，并具有完整性。用例与角色之间是关联关系。 第二类是静态图( s t a t i cd i a g r a m ) ，包括类图、对象图和包图。其中类图描述 系统中类的静态结构，它不仅可以定义系统中的类，而且还可以表示类之间的联 系。类图主要用于描述系统的静态结构。对象图是类图的一个实例，它描述了系统 在某一个具体的时间点上所包含的对象以及各对象之间的关系。包图由包或类组 成，表示包与包、包与类之间的关系，包图用于描述系统的分层结构。 第三类是行为图( b e h a v i o rd i a g r a m ) ，描述系统的动态模型和对象之间的交互 关系。包括状态图和活动图。其中状态图描述类的对象所有可能的状态以及事件 发生时状态的转移条件。通常，状态图是对类图的补充。而活动图用来描述满足用 例要求所要进行的活动以及活动间的约束关系，有利于识别并行活动。 第四类是交互图( i n t e r a c t i v ed i a g r a m ) ，描述对象间的交互关系，包括顺序 图和合作图。其中顺序图用来描述对象之间的交互顺序，它强调对象之间消息发 送的顺序。合作图描述对象之间的合作关系，它侧重于说明哪些对象之间有消息传 递。顺序图和合作图之间可以相互转化。 第五类是实现图( i m p l e m e n t a t i o nd i a g r a m ) 。包括构件图和部署图。其中构 件图描述代码部件的物理结构及各部件之间的依赖关系。部署图定义了系统中硬 件的物理体系结构，用来描述实际的物理设备以及它们之间的连接关系。 目前使用的建模工具主要有r a t i o n a lr o s e ，m i c r o s o f to f f i c ev i s i o ， p o w e r d e s i g n e r 和t o g e t h e r 等。r a t i o n a lr o s e 易于使用，同时提供对c + + 、j a v a 、 v i s u a lb a s i c 等多种语言的支持。m i c r o s o f to f f i c ev i s i o 它可以帮助用户交流 创意、信息和系统并将其可视化。v i s i o