《运算机导论温习提纲》由会员分享，可在线阅读，更多相关《运算机导论温习提纲（31页珍藏版）》请在金锄头文库上搜索。
1、运养机导论温习纲要2010/6/2108:52第1章结论一、第一台运算机；二、运算机进展的五个阶段；第一代（1945T957）:电子管运算机（VacuumTubes）第二代（19581963）：晶体管运算机（Transistor）第三代（19641969）：小规模巢成电蹈运算机IntcgraicdCircuits第四代（19707990）:以微处置器（Microprocessors）为标志的大规模/超大规模集成电路（LSI/VLSI）运算机（Large-scaleIntegratedCircuits）第五代（1991目前）：以互联网（Internet）为标志的信息系统3、计算学科的概念计算学科
2、是对描述和变换信息的算法进程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。4、计算学科的根本问题计算学科的根本司题是：什么能被（有效地）自动进行。计算学科所有分支领域的根本任务就是进行计算，其实质就是字符串的变换。五、计算学科的5个分支学科运算机科学（ComputerSciuncu,筒称CS）信息系统（InformationSystem,简称IS）软件工程（SoftwareEngineering,简称SE）运算机工程（ComputerEngineering,筒称CE）信息技术（InformationTechnology,简称IT）六、学科知识体运算机科学知识体由以下3个层次组成
3、：（1）最高层是分支领域（area）,它代表一个特定的学科子领域。（2）分支领域之下又分为更小的知识单元（unit）,它代表该领域中的主题模块。（3）知识单元又被细分为众多的知识点（topic）,这些知识点组成了知识体结构的最底层。7、运算机科学二维概念矩阵三个过程主领域抽象理论设计离散结构(DiscreteStructures)程序设“.基础(ProgrammingFundamentals)算法和复杂性(Algorithms&Complexity)计算机结构与组织(Architecture&Organization)操作系统(OperatingSystems)网络计算(NetworkComp
4、uting)程序设计语言(ProgrammingLanguages)人-机交互(Human-ComputerInteraction)图形学与可视计算(Graphics&VisualComputing)智能系统(IntelligentSystems)信息管理(InformationManagement)软件工程(SoftwareEngineering)社会和职业问题(Social&ProfessionalIssues)科学计算(ComputationalScience)运算机科学二维概念矩阵是学科概念的认知模型。“纵向”关系，即运算机科学的研究领域。这些内容包含在学科3个进程中，并将学科各分支领
5、域结合成一个完整的体系，而不是互不相关的领域。“横向”关系，即抽象、理论和设计3个进程的关系，是概念矩阵中最为重要的内容。它反映的是，人们在计算领域的熟悉规律，即是从感性熟悉（抽象）到理性熟悉（理论），再由理性熟悉（理论）回到实践（设计）的进程。“横向”关系还包含着学科中的大体问题。抽象、理论和设计3个进程（1）理论源于数学。应用数学家们以为科学的进展都是成立在数学基础之上。它的研究内容表此刻两个方面：一方而是成立完整的理论体系，另一方而是在现有理论的指导下，成立具体问题的数学模型，从而实现对客观世界的理性熟悉。（2）抽象源于现实世界。抽象建模是自然科学的根本。（3）设计源于工程。设计是工程的
6、根本。八、摩尔定律和“贝尔定律”在体系结构方面，有所谓“摩尔定律（MooresLaw）和“贝尔定律（BellsLaw）。前者判定微处置器的速度会每18个月提升一倍，而后者则以为若是维持计算能力不变，微处置器的价钱和体枳每18个月缩减一倍。第2章计算学科的大体问题什么是科学问题？科学问题是指一按时期的科学熟悉主体，在已完成的科学知识和科学实践的基础上，提出的需要解决且有可能解决的问题。它包括必然的求解目标和应答域，但尚无肯定的答案。罗素悖论罗素悖论的表现形式：在对结果的观察中同时包括了观察者自身的行为，就会出现悖论。也就是说，理性无法回答关于自身的问题。希尔伯特纲领希尔伯特在数学基础的研究中提出
7、了一个假想：将每一门数学的分支形式化，组成形式系统或形式理论，并在以此为对象的元理论即元数学中，证明每一个形式系统的相容性，从而导出全数数学的相容性。他企图寻觅通用的形式逻辑系统，在该系统中，能够机械地判定任何给定命题的真伪，即该系统是完备的。任何系统的完备和一致性，能够由系统本身取得证明。希尔伯特这一假想，就是所谓的“希尔伯特纲领工库尔特哥德尔（K.Godel）提出的关于形式系统的“不完备性定理中指出：形式系统不能穷尽全数数学命题，任何形式系统中都存在着该系统所不能判定其真伪的命题。没有一种公理系统能够导出数论中所有的真实命题，除非这种系统本身就有悖论。“哥德尔第必然理“，即哥德尔的“不完备
8、性定理一个形式系统，若是是一致的（=相容的=无矛盾的），那么，就必然存在一个命题，那个命题在该系统中不能被证明，也不能被否证。换一种说法，那个命题在该系统中不能被证明，它的反命题在该系统中也不能被证明。“哥德尔第二定理“，即：任何一个被以为是一致的系统，它的一致性是不能在系统内部取得证明的。因此：形式系统是不完备的哥尼斯堡七桥问题欧拉回路欧拉给出了哥尼斯堡七桥问题的证明，还用数学方式给出了三条判定规则（判定每座桥恰好走过一次，不必然回到原点，即对欧拉路径的判定）：（1）若是通奇数座桥的地方不止两个，知足要求的线路是找不到的。（2）若是只有两个地方通奇数座桥，能够从这两个地方之一动身，找到所要求
9、的线路。（3）若是没有一个地方是通奇数座桥的，则无论从哪里动身，所要求的线路都能实现。按照第3点，能够得出，任连续通图存在欧拉回路的充分必要条件是所有极点均有偶数度。哈密尔顿回路问题：在某个图G中，能不能找到如此的路径，即从一点动身不重复地走过所有的结点，最后又回到原起点。那个问题也被称作周游世界问题。“哈密尔顿回路问题”与“欧拉回路问题”的不同点“哈密尔顿回路问题”是访问每一个结点一次，而“欧拉回路问题”是访问每条边一次。对图G是不是存在“欧拉回路”前而已给出充分必要条件，而对图G是不是存在“哈密尔顿回路”至今仍未找到知足该问题的充分必要条件。计算问题能够分为可计算问题与不可计算问题。可计算
10、问题：存在可解的算法。不可计算问题：不存在可解的算法。梵天塔问题说明了：理论上能够计算的问题，实际上并非必然能行，这属于算法复杂性方面的研究内容。算法复杂性中的难解性问题、P类问题和NP类问题算法复杂性包括算法的空间和时刻两方面的复杂性问题。在计算复杂性理论中，将所有能够在多项式时刻内求解的问题称为P类问题，而将所有在多项式时刻内能够验证的问题称为NP类问题。证比求易算法在运算机科学中，一般以为求解一个问题往往比较困难，但验证一个问题就比较简单。顺序算法和并行算法当将一个问题分解到多个处置器上解决时，由于算法中不可避免地存在必需串行执行的操作，从而大大地限制了并行运算机系统的加速能力。阿达尔定
11、律(参看书本)一个不可计算问题：停机问题停机问题(HaltingProblem)是1936年图灵在其著名论文论可计算数及其在判定问题上的应用中提出，并用形式化方式给予证明的一个不可计算问题。停机问题引出了一个悖论一当一个程序无穷循环时才会停机,而且当它停机时才会无穷循环。什么是形式化方式：引入表达形式结构的符号语言,用符号与符号之间的联系表达命题或推理的形式结构。找零问题、背包问题与贪婪算法一类能够用启发式的贪婪算法来处置的典型问题。1 .找零问题2 .背包问题“哲学家共餐”问题与运算机资源管理运算机的资源分软件资源和硬件资源。硬件的资源主要指CPU、存储器和输入和输出设备等；软件资源则是指存
12、储在存储设备里面的各类文件。在运算机中，操作系统负责对运算机软硬资源进行控制和管理，要使运算机系统中的软硬件资源取得高效的利用，就会碰到由于资源共享而产生的问题。“哲学家共餐”问题哲学家进餐问题在运算机科学中所反映的问题实际上是程序并发执行时进程同步的问题：为了提高系统的处置能力和机械的利用率，并发程序被普遍地利用，因此必需完全解决并发进程中的死锁和饥饿问题。并行处置并行计算时的完整性和同步性出现了问题。生产者一消费者问题一个生产者和一个消费者和一个硬件资源。所谓消费者是指利用某一软硬件资源时的进程,而生产者是指提供（或释放）某一软硬件资源时的进程。一个重要的概念，即信号灯，它借用了火车信号系
13、统中的信号灯来表示进程之间的互斥。生产者一消费者问题例如：大型数据库的共享、联网的售票系统、火车（航班）进出管理系统“两军问题”与运算机网络运算机网络的概念运算机网络是将分散在不同地理位置上的，具有独建功能的多台运算机系统、各类终端设备、外部设备及其它附属设备，通过通信设备和通信线路连接起来，在网络协议和网络操作系统的管理和控制下，实现数据通信、资源共享和散布处置的系统。运算机网络进展的四个阶段运算机网络的进展，大致经历了四个阶段：1 .远程终端联机阶段2 .运算机网络阶段3 .网络互连阶段4 .信息高速公路（互联网）阶段运算机网络的功能资源共享、信息传输、提高系统的靠得住性、散布处置，系统便
14、于扩充。运算机网络的分类1 .按照组成运算机网络的地理范围大小的不同，可分为广域网（WAN）、城域网（MAN）和局域网（LAN）三种。2 .按网络的利用范围划分，可将运算机网络分为公用网和专用网。运算机网络的组成运算机网络由运算机通过通信线路互连而成，用户通过终端访问网络。从组成网络的设备或系统功能看，运算机网络由通信子网和资源子网组成。运算机网络的拓扑结构局域网中，组成网络服务器、工作站（又称节点）等设备通过电缆在物理上互连的几何构形,称为网络的拓扑结构。信道信道是指信号的传输通道，可分为物理信道和逻辑信道。其中，物理信道是指用来传递信号的一条物理通道，由传输介质和相关设备组成。依照传输方式
15、分，信道可分为两类：点到点信道和广播信道。按利用的传输介质不同，信道可分为有线信道和无线信道。有线信道能够是架空明线、同轴电缆、光钎电缆及微波导管等信道。无线信道能够是微波信道、短波信道等。信道所能传送信号的频率宽度(即可传送信号的最高频率和最低频率之差)称为信道的带宽。网络协议运算机网络为了进行网络中的数据互换而成立的规则、标准或约定称为网络协议。网络协议规定了有关功能部件在通信进程中的操作，规定了传输数据的格式和有关的同步问题。网络的标准化组织为运算机网络制定标准的组织主要有三个：国际标准化组织ISO国际电子电器工程师协会IEEE(3)ARPA(AdvancedResearchProjectsAgency)参照运算机系统多层体系结构的原理，网络系统的通信结构也采用分层结构的方式。开放性系统互连(OSI)的参考模型传输介质局域网协议的标准IEEE802局域网的标准是由IEEE802
