计算机科学导论实验四:系统(“淝水之战”)
实验报告
1408班 第4组
小组成员:房子祺、何慧卉、李永明、吴崇祎、王温博
实验目的
1、理解系统的模块化,抽象化概念,能够使用多种模块完成一个独立抽象系统的构建,完成指定目标;
2、理解分布式系统与独立系统的关系,尝试约定一种协议保证分布式系统的容错性。
第一阶段构建部队子系统
对系统构建要求进行分析,构建出唯一正确的系统结构:
关于操作类型的说明:对于各个模块,只能进行拖动和连线操作;其中属性只能被拖入模块当中。对于模块的内部逻辑,则通过点击模块进行设置。
对模块化的理解:外部简略,内部实现。将不同各项功能模块化,可以使整个系统显得结构清楚,使系统的构建更为清晰、简单。
构建成功效果图:
第二阶段进行分布式战役
分析题目:胜利条件(分布式系统的容错性)
一致性条件:所有忠臣将军作出相同的决策。
有效性条件:少数忠臣将军应服从多数忠臣将军的状态进行决策,数量相同时进行任意决策。
终止性条件:所有忠臣将军都做出了决策。
当忠臣部队中为就绪状态的数量为2时,只需保证忠臣的决策一致:
方法1. 约定一致做出攻击决策;(算法1)
方法2. 加入奸臣的状态。若有不少于2名忠臣看到他的状态为就绪,则认为他的状态为就绪(指向他的箭头至少有2个绿色),否则认为他的状态是等待。若全体就绪人数达到3人,则攻击。(算法2、3)
关键:让4名忠臣对战场情况得出不错误且一致的认识(不必识别出奸臣)(算法3)
进行调研:是否存在保证忠臣胜利的算法?
经过调研,发现与之相似的问题——拜占庭将军问题(Byzantine failures)。已证明此问题中,如果有m 个叛国将军,将军总数不少于3m+1 个时,存在算法能使口头消息传递达到一致,满足胜利条件。
与“淝水之战”的不同之处:不要求有效性条件
淝水之战中有1个奸臣,共5名将军,5≥3×1+1=4,故一定存在保证忠臣胜利的算法。
我们的探究过程
为了设计出保证忠臣胜利的算法,需思考下述问题:奸臣有哪些操作可能导致忠臣做出错误决策?
忠臣在看到的情况为(3,2)时,比较容易出现决策错误。
忠臣状态为(3,1)时,奸臣可有如下操作,使:
我们将可能出现的情况画图(图一)列出,进行分析,寻找可以作为区分两种情况依据的图形特征。
观察发现,(3,1)与(2,2)的特征性差别在于,(3,1)的情况下,一定会有1位忠臣看到的是(4,1)的情况,并已做出决策。因此想到算法1第三步中,把此人自身的状态与他发出的箭头合起来看的方法。
图 1
设计算法
列举所有可能出现的情况
算法1(方法1)
新的一天开始。
第一步:
广播自身状态。忠臣如实,奸臣任意。
以下情况下,忠臣做出决策:
若看到就绪人数≥4,攻击;
若看到就绪人数≤2 拒绝;
若看到就绪人数=3,且有不少于2人已做出决策,攻击;
若看到就绪人数=2,且有不少于2人已做出决策,拒绝。
安全度过一天或进入第二步。
第二步:
广播自己看到的其余4人的状态。忠臣如实,奸臣任意。
若看到某人被指2红2绿,或指错自己的状态,可断定此人为奸臣。
此时若忠臣就绪人数≥2,则攻击;若忠臣就绪人数=1,则拒绝。
若已有不少于2人做出决策,可断定此时忠臣状态为(3,1)。
此时若5名将领中就绪人数≥3,攻击;若5名将领中就绪人数≤2,拒绝。
安全度过一天或进入第三步。
第三步:
对其余4人逐个进行如下分析:
把此人自身的状态与他发出的箭头合起来看,若存在一人的视角中总体情况为4红1绿,可断定此时忠臣中只有1人就绪,决策拒绝。(此时必定至少有1人已做出决策)否则,决策攻击。
安全度过一天,进入下一天。
算法2 矛盾数辨奸臣(方法2)
一、无矛盾图
在这种情况下中至少可以确定奸臣在所有人眼里的颜色相同,那么五个人的自身状态在所有人的图里就是共同点,直接通过五人状态确定策略即可。
二、矛盾图
1、辨奸臣
定义状态数组(x1,x2,x3,x4,x5)x1,x2,x3,x4,x5∈{0,1}
(1)、x1=x2=x3=x4=x5 忠奸不分
(2)、x1=x2=x3=x4≠x5:“单异色元”
(3)、x1≠x2=x3:奸臣!
关于(1)、(2)
若五个元素均为情况(1),则该图为无矛盾图
若五个元素中存在情况(3),则奸臣已定
若五个元素中不存在情况(3)且存在情况(2),则——
单异色元的讨论
产生:奸臣误导:箭头末端是奸臣
奸臣污蔑:箭头首端是奸臣
结论:单异色元的产生都与奸臣有关
3个或以上单异色元
根据抽屉原理,单异色元只分两类,至少有两个单异色元同属奸臣误导或奸臣污蔑,那么同时被矛盾箭头指向或发出两个矛盾箭头的即为奸臣。
2个或以下单异色元
α.2个单异色元
矛盾不重叠:同上可确认奸臣身份
矛盾重叠:同色矛盾:两者完全等价,假设一个是奸臣即可
异色矛盾:同时去掉这两个元素,依照剩下三人决策
β.1个单异色元:按照大多数人的意见修正自己的图并依据5人颜色决
策即可。
2、决策
根据1的论述,除无矛盾图、?α异色矛盾重叠图以及?β图以外,我们可以准确判断奸臣身份。进而进入决策阶段。
确定奸臣的身份主要目的是保证决策一致性。在所有人的图中,当奸臣已知时,忠臣的自我声称以及忠臣对奸臣的指认是非常重要的共享信息,是所有人图的共同点,通过这些信息决策自然可以保证决策一致性。
因此我们约定:
(1)依照指向奸臣的箭头颜色多者决定奸臣颜色,若两红两绿则视为奸臣未声明。
(2)在就奸臣颜色达成共识以后,按照五人颜色作出决策,若奸臣属于未声明状态,忠臣两红两绿则约定攻击。
注:
1、我们的算法中假设奸臣足够聪明,操作速度超神,不会因为操作过慢而暴露身份。
2、所有忠臣约定公布全部信息,如果奸臣不公布全部信息,那么观察自己的图中被一个四人双向完全图孤立在外的那个就是奸臣。
算法3
通过之前的探究,理解到问题的关键:
让4名忠臣对战场情况得出不错误且一致的认识(不必识别出奸臣)。
在忠臣都如实广播的前提下,指向忠臣的4个箭头中有3个是忠臣发出,必定是此人真实的状态。而指向奸臣的4个箭头的颜色情况在所有忠臣的视角中都是相同的,可保证一致性。
因此只需:
广播自身状态,广播看到的其余4人的状态,如果指向某人的箭头中有不少于2个是绿色,则认为此人的状态是就绪;否则认为此人的状态是等待。若5人中就绪的较多,则发动攻击;否则,拒绝攻击。
思考:第一阶段与第二阶段的联系
第一阶段的设置与第二阶段有着密不可分的联系。
下表列出了在第一阶段构建部队子系统的设置在第二阶段中的作用:
第二篇:计算机导论课程教学大纲
《计算机导论》课程教学大纲
适用于计算机科学与技术(普本、应本)专业
教学学时:50~60学时
一、课程概况
《计算机导论》是计算机科学与技术专业本科生的一门先导基础课程。主要讲述计算机科学的特点,历史渊源,发展变化,知识组织结构和分类体系。通过对本课程的学习,使学生了解计算机科学与技术领域的基本知识、基本理论和基本技术方法,为将后学习《操作系统》、《程序设计》、《数据结构》等课程打下基础。
二、教学基本要求
1、了解计算机科学的基本概念和基本知识
2、了解计算机的基本结构与工作原理
3、了解高级语言与程序设计技术
4、了解计算机系统软件与应用软件
5、了解计算机网络与通信
6、了解新一代计算机体系结构与软件方法学
7、了解数据管理的进展
三、教学内容及要求
(一)、计算机系统的基础知识
主要内容:计算机的发展历史,计算机的基本组成及工作原理,理解数制与编码,数制运算,逻辑代数及逻辑电路;
重点:数制与编码;
难点:计算机的基本组成及工作原理;
基本要求:了解计算机的发展历史,了解计算机的基本组成及工作原理,理解数制与编码,掌握数制运算,了解逻辑代数及逻辑电路;
(二)、计算机系统的硬件
主要内容:中央处理器(CPU)及结构,半导体储器的工作原理及结构,辅助存储器的种类,输入/输出系统,计算机的整机结构,计算机的系统结构。
重点:中央处理器、存储器、计算机的系统结构
难点:计算机的系统结构、存储器
基本要求:了解中央处理器(CPU)及结构,了解半导体储器的工作原理及结构,了解辅助存储器的种类,了解输入/输出系统,了解计算机的整机结构,了解计算机的系统结构。
(三)计算机系统的软件
主要内容:计算机软件的功能、分类,程序设计语言的分类和功能,数据结构的基本概念,程序编译的基本原理,操作系统的功能,软件开发的基本流程
重点:程序设计语言分类、操作系统的功能
难点:操作系统的功能
基本要求:了解计算机软件的功能、分类,了解程序设计语言的分类和功能,了解数据结构的基本概念,了解程序编译的基本原理,理解操作系统的功能,了解软件开发的基本流程
(四)计算机系统的应用
主要内容:计算机网络的功能及应用,数据库系统的应用,虚拟现实的原理,人工智能与专家系统的基本原理及应用,计算机控制系统与管控一体化系统的工作原理及应用,计算机信息安全的重要性。
重点:计算机网络的功能及应用、数据库系统的应用
难点:数据库系统的应用
基本要求:了解计算机网络的功能及应用,了解数据库系统的应用,了解虚拟现实的原理,了解人工智能与专家系统的基本原理及应用,了解计算机控制系统与管控一体化系统的工作原理及应用,理解计算机信息安全的重要性。
(五)Windows2000操作系统介绍
主要内容: Windows 20## 的基本操作,Windows 2000的文件管理方法, Windows 2000的系统设置及管理, Windows 2000的网络配置, Windows 20## 的帮助系统及使用
重点:Windows 20## 的基本操作、Windows 2000的文件管理方法
难点:Windows 2000的系统设置及管理
基本要求:掌握Windows 20## 的基本操作,掌握Windows 2000的文件管理方法,了解Windows 2000的系统设置及管理,了解Windows 2000的网络配置,掌握Windows 20## 的帮助系统及使用
(六)办公自动化软件的使用
主要内容: Microsoft Word的使用, Microsoft Excel的使用, Microsoft PowerPoint的使用
重点:Microsoft Word的使用、Microsoft Excel的使用
难点:Microsoft Word的使用、Microsoft Excel的使用
基本要求:掌握Microsoft Word的使用,掌握Microsoft Excel的使用,掌握Microsoft PowerPoint的使用
(七)计算机技术新进展
主要内容:计算机硬件技术的发展现状,计算机软件开发技术的发展现状,计算机应用技术的发展现状
重点:计算机软件开发技术的发展现状;
难点:
基本要求:了解计算机硬件技术的发展现状,了解计算机软件开发技术的发展现状,了解计算机应用技术的发展现状
四、学时分配表
五、实验
(一)目的:
通过上机实际操作,使学生掌握Windows操作技能,并能熟练使用Microsoft Office系列软件进行文档的编排,为以后编写实验报告、设计论文和从事办公自动化工作打下基础,巩固老师课堂讲授的知识和技巧。
(二)要求
本课程安排8学时上机实验,主要是培养学生使用微机的能力,因此要求实验室应具备Microsoft Windows 2000及以上版本, Microsoft Windows Office 2000或以上版本软件环境。
实验一:Windows基本操作
熟悉一种中文输入发,熟练英文输入,养成良好的输入习惯和指法。
实验二:Microsoft Word使用
掌握文档格式的编排,文档模板的使用,表格的制作和使用,理解文档视图的概念,了解文档格式管理和对象插入方法。
实验三:Microsoft Excel使用
掌握电子表格的制作方法,常用函数的使用,图表的制作方法,对象的插入。理解图表格式及编辑,了解数据导入、导出方法。
实验四:Microsoft Powerpoint使用
掌握幻灯片的制作方法、版式、对象的使用,动画及其他效果的使用。
实验五:Internet使用
掌握利用Internet进行信息检索和浏览技术、收发电子邮件技术。
(三)项目及学时分配表
*学生在能够熟练使用Office的情况下,可以安排一次Internet使用实践,让学生熟悉IE,收发E-Mail等操作。
五、推荐教材、参考资料
1、王玉龙主编《计算机导论(第2版)》,电子工业出版社,2005
2、赵致琢主编<<计算机科学导论>>,科学出版社,1997
六、执行大纲说明
执笔人:杨治明
审核人:王成敏