计算机科学概论第1版英文版提纲.doc

Computer Science OutlineYang Zhao-Huaqiao University-International School-Echonomics-Chapter 1:Data storage 数据存储1.1 Bits and their storageBits and Bit Patterns位与位模式1.Bit: Binary Digit (0 or 1)2.Bit Patterns:are used to represent information.-Numbers-Text characters-Images-Sound-And others1.1.1 Boolean Operation布尔运算(George Boolean)1.Boolean Operation: An operation that manipulates one or more true/false values2.Specific operations：-AND-OR-XOR (exclusive or) 异或-NOT1.1.2 Gates and Flip-Flops门和触发器1.Gate: A device that computes a Boolean operation-Often implemented 应用as (small) electronic circuits 电路-Provide the building blocks from which computers are constructed 为构造计算机提供基础条件-VLSI (Very Large Scale Integration) 超大规模集成电路（A pictorial representation of AND, OR, XOR, and NOT gates as well as their input and output values）2.Flip-flop: A circuit built from gates that can store one bit.One input line is used to set its stored value to 1One input line is used to set its stored value to 0While both input lines are 0, the most recently stored value is preserved（A simple flip-flop circuit） （Setting the output of flip-flop to 1）1.1.3 Hexadecimal Notation1.Hexadecimal notation: A shorthand notation for long bit patternsDivides a pattern into groups of four bits eachRepresents each group by a single symbolExample: 10100011 becomes A3简便算法：例如：1011（二位制计数法）变为十六位制计数法表示 只需1*20+1*21+0*22+1*23=11B 例如：0011（二位制计数法）变为十六位制计数法表示 只需1*20+1*21+0*22+0*23=31.2Main Memory主储存器（就是平时说的内存）1.2.1 Memory organization1.Cell(储存单元): A unit of main memory (typically 8 bits位 which is one byte字节)2.Most significant bit: the bit at the left (high-order) end of the conceptual row of bits in a memory cell3.Least significant bit: the bit at the right (low-order) end of the conceptual row of bits in a memory cell（The organization of a byte-size memory cell）4.Address: A “name” that uniquely identifies one cell in the computers main memoryThe names are actually numbers.These numbers are assigned consecutively starting at zero.Numbering the cells in this manner associates an order with the memory cells.（Memory cells arranged by address)Memory Terminology5.Random Access Memory (RAM): Memory in which individual cells can be easily accessed in any order6.Dynamic Memory (DRAM): RAM composed of volatile memory（在此处可以简单理解为RAM包括DRAM； DRAM表示动态的RAM）1.2.2 Measuring Memory Capacity存储器容量的度量Kilobyte: bytes = 1024 bytesExample: 3 KB = 3 times1024 bytesMegabyte: bytes = 1,048,576 bytesExample: 3 MB = 3 times 1,048,576 bytesGigabyte: bytes = 1,073,741,824 bytesExample: 3 GB = 3 times 1,073,741,824 bytes1.3Mass Storage 海量存储器（就是平时说的硬盘）On-line versus off-line-on-line means that the device or information is connected and readily available to the machine without human intervention.-off-line means that human intervention is required before the device or information can be accessed by the machine-perhaps because the device must be turned on ,or the medium holding the information must be insert into some machine.Compared with main memoryTypically larger than main memory容量大Typically less volatile than main memory更稳定Typically slower than main memory速度慢Mass Storage Systems-Magnetic SystemsDiskTape-Optical SystemsCDDVD-Flash TechnologyFlash DrivesSecure Digital (SD) Memory Card1.3.1Magnetic System 磁学系统1. Magnetic disk(Hard disk)architecture-track磁道-cylinder柱面-sector扇区-ZBRFormatting格式化Seek time寻道时间Rotation delay(Latency time)旋转延迟/等待时间Access time存取时间=Seek time+Rotation delayTransfer rate传输速率92. Magnetic tapetape reel带盘 Take-up reel卷盘1.3.2 Optical Systems光学系统Compact disk(CD) 600MB700MB only 1 track-CD-DA (Compact disk-digital audio)-CD-ROM-VCDDigital Versatile Disk (DVD)-Blue Ray蓝光技术-Multiple Layers多层Blu-ray Disks(BDs)1.3.3 Flash Drives 闪存驱动器No Mechanical MotionFlash-Total Electronic-Not suitable for main memory-Hard DriveSD SDHC SDXC1.3.4 File Storage and Retrieval文件存储及检索File: A unit of data stored in mass storage systemFields and keyfields字段和键字段Field:example:Name/sexKey field:example:student numberPhysical record versus Logical recordBuffer缓冲区: A memory area used for the temporary storage of data (usually as a step in transferring the data)1.4 Representing Information as Bit Pattern位模式的表示1.4.1 Representing Text文本的表示1.Each character (letter, punctuation, etc.) is assigned a unique bit pattern.2.ASCII: Uses patterns of 7-bits to represent most symbols used in written English text3.ISO developed a number of 8 bit extensions to ASCII, each designed to accommodate a major language group 4.Unicode: Uses patterns of 16-bits to represent the major symbols used in languages world wide5. Text file文本文件6. Text editor 文本编辑器（简单文本文件）7. Word processor字处理程序（如微软word产生的较复杂的文件）1.4.2Representing Numeric ValuesBinary notation二进制记数法: Uses bits to represent a number in base twoLimitations of computer representations of numeric values-Overflow超值: occurs when a value is too big to be represented-Truncation截断: occurs when a value cannot be represented accurately1.4.3Representing ImagesBit map techniques-Pixel: short for “picture element”像素 3bytes=24bits-Bit map位图 （像素的集合就是位图）-RGB-Luminance and chrominance光和色-Scaling problemVector techniques矢量技术-Scalable缩放-TrueType and PostScript-CAD (computer-aided design)计算机辅助设计1.4.4 Representing SoundSampling techniques振幅采样方法-Used for high quality recordings：44.1KHZ-Records actual audioMIDI乐器数字化接口-Used in music synthesizers合成器-Records “musical score”乐谱12 31 12 31 34 5记录乐谱而不是音乐本身Computation 1 minute music-Stereo立体声-44.1 KHz/s-16 bit一个样本（）-60 （一分钟）* 2（双声道） * 44.1 * 1000 * 16/8（2bytes） 10 MB-MP3: 101 1（有压缩的能力）1.5The Binary System二进制系统The traditional decimal system is based on powers of ten.The Binary system is based on powers of two.1.5.1Binary Notation 二进制记数法二进制与十进制的转换二进制转十进制十进制转二进制Example:1.5.2Binary Addition二进制加法 法则： Example：1.5.3 Fractions in Binary 二进制中的小数Ridix point（小数点）Chapter 2:Data Manipulation数据操控2.1 Computer ArchitectureCentral Processing Unit (CPU) or processor:the circuitry in a computer that control the manipulation of data is that.MotherboardMID(Mobile Internet Device)Microprocessors微处理器2.1.1 CPU BasicsA CPU consists of three parts:-Arithmetic/Logic unit -算 versus -Control unit -协调-Registers unit寄存器单元 -CPU内部数据临时存储 General-purpose register 通用寄存器 Special-purpose register 专用寄存器Bus 总线2.1.2 Stored Program ConceptA program can be encoded as bit patterns and stored in main memory. From there, the CPU can then extract the instructions and execute them. In turn, the program to be executed can be altered easily.-Not see the forest for the trees-Such ruts may still exist in CS(computer science)-New insights may open door to New Things2.2 Machine LanguageMachine instruction: An instruction (or command) encoded as a bit pattern recognizable by the CPUMachine language: The set of all instructions recognized by a machine2.2.1The Instruction Repertoire指令系统Machine Language PhilosophiesReduced Instruction Set Computing (RISC)-Few, simple, efficient, and fast instructions-Examples: PowerPC from Apple/IBM/Motorola and ARMComplex Instruction Set Computing (CISC)-Many, convenient, and powerful instructions-Example: IntelMachine Instruction Types1.Data Transfer: copy data from one location to another-LOAD/STORE-I/O instructions与外界设备传输的指令2.Arithmetic/Logic: use existing bit patterns to compute a new bit patterns-SHIFT/ROTATE3.Control: direct the execution of the program: -STOP/JUMP-unconditional jump/conditional jump2.2.2 An illustrative Machine Language 一种演示用的机器语言Parts of a Machine Instruction-Op-code操作码: Specifies which operation to execute 说运算方式1C-Operand操作数字段: Gives more detailed information about the operation 详细的运算信息Interpretation of operand varies depending on op-code2.3 Program Execution程序执行Controlled by two special-purpose registers -Program counter: address of next instruction-Instruction register: current instructionMachine Cycle-Fetch取指-Decode译码-Execute执行2.3.1 An example of Program Execution这个图其实应该是动态的，如果静态的看这两个图就是错误的，所以千万不要被这个图混淆，下面我将写出做题的技巧：例：Program counter：A0 Program counter：A2 Program counter：A4Instruction regiser:156C Instruction regiser:156C Instruction regiser:166D永远记住Program counter记的是下一个待执行指令的地址2.3.2 Programs versus DataAll Binary strings in memoryBAD ?NO-Programs can modify itself, the same as data. machine learning-Write programs to solve problemsChapter 3:Operating Systems操作系统Functions of Operating SystemsOversee operation of computerStore and retrieve filesSchedule programs for executionCoordinate the execution of programsExamples-Windows / Linux-Unix: Mac OX-Phone: iOS / Android3.1 The History of Operating Systems1.Batch processing批处理-Job作业/job queue作业队列/JCL作业控制语言2.Interactive processing交互式处理-Requires real-time processing3.Time-sharing分时/Multitasking多任务-Implemented by Multiprogramming多道程序设计4.Multiprocessor machines多处理器机器-Load Balancing负载平衡 动态将任务分配给各个处理器-scaling 均分 把大任务划分若干子任务与可用处理器相适应5.Embeded system嵌入式系统（手持设备 特定任务设备）3.2 Operating System Architecture3.2.1 A software Survey 软件概述Types of Software-Application softwarePerforms specific tasks for users-System softwareProvides infrastructure for application softwareConsists of operating system and utility software实用软件 用户界面 内核3.2.2 Components组件of Operating System User Interface: Communicates with users-Text based (Shell)-Graphical user interface (GUI)Kernel内核: Performs basic required functions-File manager文件管理程序Directory目录 (or Folder): A user-created bundle of files and other directories (subdirectories)Directory Path: A sequence of directories within directoriesdirectory path 目录路径 EX:yz/homework/151118-Device drivers 设备驱动程序-Memory manager 内存管理程序Allocates space in main memoryMay create the illusion 错觉that the machine has more memory than it actually does (virtual memory) by playing a “shell game” in which blocks of data (pages) are shifted back and forth between main memory and mass storagepaging 页面调度 内存管理程序在内存与海量存储器之间来回切换程序和数据page 页面 这块数据区被分数据区被分成大小一致的存储单元virtual memory 虚拟内存-Scheduler调度程序-dispatcher分派程序3.2.3 Getting it Started 系统启动Boot loader引导程序: Program in ROM (example of firmware)-ROM只读存储器-Run by the CPU when power is turned on-Transfers operating system from mass storage to main memory-Executes jump to operating system-Firmware updateBooting（启动计算机）在主储存器中有一部分作为ROM 开机时执行Boot Loader启动操作系统的整个过程3.3 Coordinating the Machines Activities3.3.1 The concept of a Process进程Process: The activity of executing a programProcess State进程状态: Current status of the activity-Program counter程序计数器-General purpose registers通用寄存器-Related portion of main memory3.3.2 Process Administration管理Scheduler调度程序: Adds new processes to the process table and removes completed processes from the process table在进程表中增加进程 移除已经完成的进程-process table 进程表Ready能够继续执行就处于就绪 / Waiting因外部事件中断 / RunningDispatcher分派程序: Controls the allocation of time slices to the processes in the process tableThe end of a time slice is signaled by an interrupt.确保调度的的进程能实际执行-multiprogramming多道程序设计time slice时间片process switch进程切换（context switch上下文切换）-interrupt中断信号 指示时间片结束 记录位置-interrupt handler 中断处理系统Chapter 4: Networking and the Internet4.1 Network Fundamentals4.1.1 Network Classifications3 types of classificationsScope按范围分-Local area network (LAN)局域网 楼-Metropolitan area (MAN)城域网 大型局域网 校-Wide area network (WAN)广域网 城市、世界Ownership按所有权分-Closed network封闭式（Proprietary network专用网络） Versus- Open network 开放式InternetTopology (configuration)拓扑学配置-Bus (Ethernet)总线拓扑hub集线器-Star (Wireless networks with central Access Point)星型拓扑AP中央计算机（access point接入点） 4.1.2 Protocols 协议CSMA/CD-Used in Ethernet-Silent bus provides right to introduce new message一边监测一边发 CSMA/CA-Used in WiFi-Hidden terminal problem隐藏终端问题（距离、障碍）先监测后发4.1.3 Connecting NetworksRepeater:中继器 Extends a network 原始两条总线传输Bridge:网桥Connects two compatible networks 检查报文的目的地址 同端传输不打扰另一端Switch:交换机Connects several compatible networks 多连接的网桥Router:路由器Connects two incompatible networks resulting in a network of networks called an internet 连接异构网络forwarding table转发表 包含了根据目的地地址消息应该发送的方向这种路由信息Gateway：网关 一个网络与互联网连接的“点”4.1.4 Methods of Process CommunicationInterprocesss communication进程间通信-Client/server（客户机/服务器模型）One server, many clientsServer must execute continuously不断地Client initiates启动 communicationEx：print server ; file serverPeer-to-peer (P2P)对等-Two processes communicating as equals-Peer processes can be short-lived短暂的对等执行持续运作、临时执行Ex:instant messaging;play competitive interactive gamespol4.1.5 Distributed Systems分布式系统Systems with parts that run on different computersCluster Computing集群计算-High-availability高可用性-Load-balancing 负载平衡Grid Computing网格计算-Loosely coupled耦合度不高Cloud Computing-Like electricity services就像是供电4.2 The InternetThe Internet: An internet that spans 跨越the world-Original goal was to develop a means of connecting networks that would not be disrupted by local disasters.-Today it has shifted from an academic research project to a commercial undertaking.4.2.1 Internet ArchitectureInternet Service Provider (ISP) 因特网提供商-Tier-1 ISP 第一层ISP -通信行业大公司-Tier-2 ISP 第二层ISP -区域性 通信公司 集中提供因特网通信基础设施，或说成是因特网的核心Access ISP/Intranet:因特网接入服务提供商/内联网Provides connectivity to the InternetEnd system/Host:终端系统/主机The technology by which End systems connect to access ISPs -Traditional telephone line (dial up access)拨号连接-Modem,modulator/ demodulator 调制解调器DSL 数字用户线路(digital subscriber line)低频用于传统电话 高频用于数字数据传输-Cable/satellite system电缆/卫星系统-Wireless 无线WiFi technologyHot spot 热点4.2.2 Internet AddressingIP address: pattern of 32(IPv4) or 128 bits(为了提供更多的地址IPv6)often represented in dotted decimal notation点分十进制计数法-ICANN(Internet Corporation for Assigned Name&Numbers)因特网名称与数字地址分配机构-dotted decimal notation 点分十进制计数法Ex:33Mnemonic address:助记名称地址（Addresses in bitten-pattern form are rarely conducive to human consumption）-Domain 域 -Registar 注册商Assigned by ICANN -Domain names 域名 DomainEx：-Top-Level Domains(TLDs)顶级域名Ex：com/edu/gov/org/museum/info/netCountry-code TLDs 国家代码顶级域名（two-letter TLDs）Ex：au 澳大利亚 ca加拿大-Subdomain 子域Ex： 计算机 子域名 域名 顶级域名-Domain name system (DNS)域名系统Name servers域名服务器 助记地址转换成IP地址DNS lookup域名系统查找 使用域名系统进行解析的过程-Internet Corporation for Assigned Names & Numbers (ICANN)Allocates IP addresses to ISPs who then assign those addresses within their regions.Oversees the registration of domains and domain names.4.2.3 Internet Applications1.Electronic Mail (email)-Domain mail server 邮件服务器collects incoming mail and transmits outing mail-Mail server delivers collected incoming mail to clients via POP3 or IMAP2.File Transfer Protocol (FTP)-anonymous FTP 匿名FTP3.Telnet and Secure Shell (SSH)远程登录与SSH-Telnet 远程登录 获取对应用和工具的访问权限-Not safe-SSH 安全shell 提供加密以及验证4.Voice Over IP (VoIP)语音通信-Soft phone VoIP VoIP软电话 通过P2P软件两个或多个PC共享一个电话 硬件只需扬声器及麦克风-analog telephone adapter 模拟电话适配器 传统电话连接到某个因特网接入服务提供商提供的电话服务上-embedded VoIP phone 嵌入式VoIP电话 手持设备连接TCP/IP 铜线换为基于以太网的 VoIP-Smartphone VoIP technology 4G网络完全基于IP网络，4G电话本质上只是全球因特网上的另一台主机。5.Internet Radio 因特网广播-Streaming audio音频流 因特网传送而不是无线电-N-unicast 多点传播 负担放于因特网邻居-Multicast多路广播 通过路由器4.3 World Wide Web 万维网Hypertext &Hyperlink-A term that originally referred to text documents that contains links,called hyperlinks,to other documents.-Today,hypertext has been expanded to encompass images,audio,and video,and because of this expanded scope it is sometimes referred to as hypermedia（超媒体）World Wide Web ：The web that has evolved on the Internet spans the entire globe and is known as the World Wide Web（WWW、W3、Web）Web page:the hypertext document on world wide webWeb site:A collection of closely related Web pages 4.3.1 Web Implementation实现Software packages that allow users to access hypertext on the Internet fall into one of two categories:-packages that play the role of clients 客户端-packages that play the role of serversBrowser/Web browser浏览器（the client packages）Web server万维网服务器（the server packages）-the server package resides on a computer containing hypertext documents to be accessed-Its task is to provide access to the documents under its control as requested by clients.Browser gets documents from Web serverHypertext documents&HTTP-Hypertext documents are normally transferred between browsers and Web servers using a protocol known as the Hypertext Transfer Protocol (HTTP)URLs (Uniform Resource Locator)统一资源定位符Documents identified by URLs超文本协议 主机助记符 目录路径 文档名4.3.2 HTML超文本标记语言Tag&HTMLHypertext documents contains a special symbols ,called tags（标签）,that describe how