专业课程设计I题目-B

专业课程设计I 学生班级：B090402任课教师：黄海平专业课程：操作系统、微机原理与接口技术(含汇编语言)、Java语言程序设计、编译原理、计算机图形学、数据结构与算法课题考察形式：第一题为必做题+(在二、三、四、五、六、七题中)选做1题(选做规则：每题选择人数不能多于8人，不能少于4人)上机时间地点：第9-10周(2012.4.16-2012.4.26)，每周一周四下午13:4516:10，教五楼501室，不得缺席一、必做题：1、课题名称 教师对学生的项目评分进程的同步与互斥2、课题描述在一个班上有S个学生。每个学生都要做一个项目，每一个项目由K个老师一起评分。总共有M个老师。每个老师最多给N个项目评分。其中，S*K<=M*N。在项目结束后，老师们提供T分钟用来检查学生们的项目。检查每一个学生的项目需要用时D分钟。其中，T>D。每一个学生的项目由K个老师共同来检查。在T分钟的时间段内，学生可以在任何时间进入教室(random)，除了在最后的D分钟内。所有的老师一直保持工作状态直到他检查完N个项目或者是T分钟过去后。T分钟过去后，所有的老师和同学都必须离开教室。另外，在T分钟结束前的D分钟内(即在最后的D分钟内)，如果有任何老师或者是学生都处在没有任务的状态下，都必须离开教室，因为已经没有时间让他完成任务了(因为一个项目检查的时间是整整D分钟)。该课题主要考察操作系统中PV操作知识点，涉及到多进程管理和死锁的相关知识。3、具体过程当一个学生进入教室后，他立即开始找K个没有任务的老师(一次找一个老师，假如没有空闲的老师，则等到有老师为止)，找齐K个老师之后给老师检查，然后离开教室。刚开始每一个老师都是处于空闲状态直到他被学生找到，被学生找到后只能等待，直到学生找齐K个老师(在等待学生找其他老师的时间里，他是不能接受其他同学检查作业的请求的)，当学生找齐K个老师后，老师们执行完检查任务，然后重新变成空闲状态。每个老师在总共检查了N个学生的作业后，离开教室。注意，并不保证所有的学生都在T分钟的时间段内完成了检查，还要注意不能发生死锁问题。4、基本要求用一个程序来模拟上面描述的作业检查过程。每一个学生和每一个老师应该用不同的线程来完成。可以选用C、C+和Java作为开发语言，但是考虑到专业课程设计I的实验大纲，请尽可能使用Java语言。5、提高要求(1) 考虑到跨平台的特性，请尽量使用posix线程标准(采用该标准有额外的加分)；(2) 实现良好的图形用户界面；(3) 在程序演示过程中能清晰的展示多个学生线程和多个老师线程的同步和互斥流程。6、作答提示(1) 学生线程和老师线程一个学生线程执行下面的步骤：(1) 选择一个进入的时间(random()%(T-D)minutes ；(2) 进入教室；(3) 选择K个空闲的老师，若找不齐，则等待；(4) 找齐后，做D分钟的检查；(5) 检查完毕离开教室。一个老师线程执行下面的步骤：(1) 在教室中空闲；(2) 直到被一个学生选择后等待(所有K个老师聚集)；(3) 等待结束项目检查开始；(4) 做D分钟的项目检查； (1)(4)步骤重复N次(5) N次检查完毕或者T分钟时间到，离开教室。(2) 注意事项(1) 在剩余时间小于D时，一个已创建的学生线程只能执行第(5)步，不能再创建新的学生线程；(2) 在剩余时间小于D时，一个老师进程只能在执行(3)(4)步或者直接执行第(5)步； (3) 对于所有合理的S, M, K, N, T, D数值(这些数必须都是正整数并且满足条件：S*K<=M*N and T>D)，你的程序都能够运行成功；(4) 你的程序对所有的时间安排策略都必须运行成功。例如不管线程的相对速度，例如要把握好sleep的毫秒数；(5) 在每一个线程的生命周期内，每一步都要有一个合理的说明信息，来表明这个线程中包括哪个老师，哪个学生，进行到什么程度了；(6) 要特别注意防范死锁问题的发生。以上六点都是最后评分的要点。7、测试用例(注：仅供参考，不作为程序实现的标准格式)说明信息的格式提供如下：S=5 M=3 K=2 N=3 T=150 D=200 student 0: starts panicking0 student 1: starts panicking0 student 2: starts panicking0 student 3: starts panicking0 student 4: starts panicking0 marker 0: enters lab0 marker 1: enters lab0 marker 2: enters lab14 student 0: enters lab14 marker 0: grabbed by student 0 (job 0)14 marker 1: grabbed by student 0 (job 0)14 student 0: starts demo35 student 0: ends demo35 student 0: exits lab (finished)35 marker 1: finished with student 0 (job 0)35 marker 0: finished with student 0 (job 0)38 student 2: enters lab38 marker 2: grabbed by student 2 (job 2)38 marker 1: grabbed by student 2 (job 2)38 student 2: starts demo54 student 4: enters lab54 marker 0: grabbed by student 4 (job 4)59 student 2: ends demo59 student 2: exits lab (finished)59 marker 2: finished with student 2 (job 2)59 marker 2: grabbed by student 4 (job 4)59 marker 1: finished with student 2 (job 2)59 student 4: starts demo80 student 4: ends demo80 student 4: exits lab (finished)80 marker 2: finished with student 4 (job 4)80 marker 0: finished with student 4 (job 4)96 student 3: enters lab96 marker 1: grabbed by student 3 (job 3)96 marker 2: grabbed by student 3 (job 3)96 student 3: starts demo117 student 3: ends demo117 student 3: exits lab (finished)117 marker 1: finished with student 3 (job 3)117 marker 1: exits lab (finished 3 jobs)117 marker 2: finished with student 3 (job 3)117 marker 2: exits lab (finished 3 jobs)127 student 1: enters lab127 marker 0: grabbed by student 1 (job 1)131 student 1: exits lab (timeout, time<D)132 marker 0: exits lab (timeout)8、参考书目1 孙钟秀. 操作系统教程(第3版)M. 北京: 高等教育出版社, 2003.2 张孝祥. Java就业培训教程M. 北京: 清华大学出版社, 2003.二、选做题1：1、课题名称模拟小提琴演奏程序2、课题内容和要求利用汇编语言实现一个模拟小提琴演奏程序。在屏幕上显示一把简单的小提琴，同时设计一个简易界面，提供有候选演奏歌曲，根据选择来演奏指定的音乐或退出等的操作，演奏乐曲时，伴有小提琴的动态演奏效果。如按大写字母“A”，演奏乐曲A；按大写字母“B”，演奏乐曲B；按大写字母“C”，演奏乐曲C 按“K”(或者其他)键，退出。基本要求：(1) 设计一个模拟小提琴，其琴弦可以随着音乐声来回拉动；(2) 每人至少实现两首歌曲的演奏；(3) 在演奏音乐的时候能够检测外来的输入从而停止音乐播放；(4) 实物演示时要求讲出程序原理和设计思想；(5) 程序运行良好，界面清晰。提高要求：(1) 小提琴琴弦的拉动速度根据选定的音乐频率动态改变；(2) 模拟小提琴演奏时，手指的摆放位置，随着音符的不同，其位置动态改变。3、参考书目1 孙力娟等. 微型计算机原理与接口技术M. 北京: 清华大学出版社, 2008.2 徐建民等. 汇编语言程序设计M. 北京: 电子工业出版社, 2005.三、选做题2：1、课题名称汇编语言实现数学计算问题2、课题内容和要求利用汇编语言实现两个数学计算问题，分别是：(1) 两个矩阵相乘：假设矩阵A= B= 编程计算C=A*B(2) 采用递归子程序的方法，编程计算Fibonacci数列0, 1, 1, 2, ，前100项之和。Fibonacci函数FIB()定义如下：FIB(0)=0 FIB(1)=1 FIB(2)=1 FIB(n)=FIB(n-2)+FIB(n-1) n>2基本要求：(1) 计算结果正确；(2) 程序运行良好，演示清晰。提高要求：能实现图形化的显示。3、参考书目1 孙力娟等. 微型计算机原理与接口技术M. 北京: 清华大学出版社, 2008.2 徐建民等. 汇编语言程序设计M. 北京: 电子工业出版社, 2005.四、选做题3：1、课题名称Java语言实现一个嵌入网页执行的小Applet2、课题内容和要求实现一个有声音、图像和文字的小Applet嵌入网页中执行。基本要求：(1) 该Applet必须是个性化的，包含了你个人的信息(例如姓名、学号)，能体现个人的兴趣爱好等主题，与你自身主题无关的Applet一律认为是抄袭；(2) 该Applet能够实现丰富的图文素材，而不是单一的枯燥的简单例子；(3) 程序运行良好，界面清晰。提高要求：(1) 在Applet中实现个性化小游戏或者动画功能；(2) 封装成为JSP (Java Server Page)。3、参考书目1 王汝传. Java语言程序设计基础M. 成都: 成都科技大学出版社, 1998.2 张孝祥. Java就业培训教程M. 北京: 清华大学出版社, 2003.五、选做题4：1、课题名称图形动画制作2、课题内容和要求用图形函数设计动画，一个人在公路上奔跑，这时从屏幕右端开出一辆卡车，最终将人撞倒了。基本要求：(1) 编程实现该动画；(2) 实物演示时要求讲出程序原理；(3) 程序操作友好、界面清晰。提高要求：(1) 人和卡车的图形设计轮廓明晰，动画显示清楚、逼真；(2) 能够给动画赋予色彩，甚至实现三维效果。3、参考书目1 王汝传 黄海平 林巧民. 计算机图形学M. 北京: 人民邮电出版社, 2009.2 孙家广 编著. 计算机图形学M. 北京: 清华大学出版社, 2002.六、选做题5：1、课题名称词法分析程序的构造2、课题内容和要求选取语言，例如选取了C语言，选取其中一个子集，例如包含了部分关键字main、float、if、for等等，特殊符号( 、<、=、+等等，特殊定义的标识符变量以及部分常量等，采用编译原理词法分析中有穷自动机的思想构建出该语言子集的状态转换图，并编码实现。基本要求：(1) 将选取的语言子集编写一个简单程序，放在一个文本文件中； (2) 编程时采用C语言或者C+语言实现该词法分析程序；(3) 要将一个个单词区分清楚并归类(例如for属于关键字)。提高要求：(1) 能做出好的图形化界面，便于人机交互；(2) 能够实现实时的词法编译。3、参考书目1 王汝传. 编译技术原理及其实现方法. 成都: 成都科技大学出版社, 1998.2 吕映芝 等编著. 编译原理. 北京: 清华大学出版社, 1998.3 陈火旺 等编著. 程序设计语言编译原理. 北京: 国防工业出版社, 2000.4 王 雷 等编著. 编译原理课程设计. 北京: 机械工业出版社, 2004.七、选做题6：1、课题名称最短路径算法2、课题内容和要求该最短路径算法主要以南京市的道路交通为模板（具体见附录图1），简单实现任意两个地点之间最短路径查询（例如三牌楼新街口），该最短路径剔除了那些由于某些原因堵塞不通的路径。基本要求：(1) 编程实现，数据结构选用邻接矩阵或邻接表来实现；(2) 实物演示时要求讲出程序原理；(3) 程序操作友好、界面清晰。提高要求：(1) 有很好的图形界面便于人机交互，路径长度和道路编号明晰；(2) 高效先进的算法。3、参考书目1 陈慧南. 数据结构使用C+描述(第2版)(普通高等教育“十一五”国家级规划教材) M. 北京: 人民邮电出版社, 20082 殷人昆, 陶永雷等著. 数据结构(用面向对象方法与C+描述) M. 清华大学出版社, 2007.附 录：具体的需求分析见图1、表1和表2：山西路三牌楼紫金山中央门南邮仙林长江大桥莫愁湖珠江路鼓 楼江 宁南京西站草场门月牙湖四牌楼雨花台夫子庙新街口杨公井长途东站总统府(1#, 7)(10#, 5)(2#, 2)(24#, 3)(22#, 3)(20#, 4)(23#, 2)(15#, 3)(19#, 3)(21#, 2)(17#, 3)(16#, 7)(14#, 6)(7#, )(12#, 4)(13#, 7)(11#, 7)(8#, )(9#, 4)(5#, 3)(4#, 1)(3#, 5)(25#, 3)(26#, 4)(27#, 5)(6#, 3)(18#, 2)(28#, )图1 南京市道路交通图说明：虚线部分表明堵塞，(i#, j)中前者i标识路编号，后者j标识路径长度三牌楼山西路鼓楼草场门中央门南京西站长途东站南邮仙林紫金山珠江路月牙湖新街口莫愁湖总统府杨公井夫子庙雨花台江宁长江大桥四牌楼三牌楼0135273山西路10273鼓楼32034草场门50中央门20南京西站7054长途东站5074南邮仙林707紫金山34706珠江路3603月牙湖30新街口4033莫愁湖70总统府022杨公井32034夫子庙30雨花台405江宁50长江大桥40四牌楼3320表1 道路交通矩阵说明：标识没有直接路径到达或者堵塞三牌楼山西路鼓楼草场门中央门南京西站长途东站南邮仙林紫金山珠江路月牙湖新街口莫愁湖总统府杨公井夫子庙雨花台江宁长江大桥四牌楼三牌楼4#5#3#2#1#7#6#山西路4#18#16#17#鼓楼5#18#19#20#草场门3#中央门2#8#南京西站1#10#9#长途东站7#10#11#12#南邮仙林11#13#紫金山6#12#13#14#珠江路19#14#15#28#月牙湖15#新街口20#28#24#22#莫愁湖16#总统府23#21#杨公井24#23#25#26#夫子庙25#雨花台26#27#江宁27#长江大桥8#9#四牌楼17#22#21#表2 道路交通路编号矩阵说明：空格表示没有直接通路