计算概论：计算机文化、程序设计.doc

计计 算算 概概 论论 计算机文化、计算机文化、程序设计程序设计Introduction to Computing: Computer Culture, and Programming闫宏飞 陈翀 编著by Hongfei Yan and Chong Chen2010/9/23内内 容容 简简 介介本书主要是汇编各书和参考资料汇编各书和参考资料而成，比较系统地介绍了计算机文化，和程序设计。通过这两部分有机的结合（前者占 1/3，后者占 2/3） ，即理论与实践结合，使学生理解和掌握有关计算机和信息技术的基本概念和基本原理，对计算机学科有全局性的认识；学会使用计算机进行信息处理，熟练掌握 C+语言编程技术，为后续相关课程的学习打好基础。本书层次分明，由浅入深，具有学习和实用双重意义。本书可作为高等院校各专业一、二年级学生的教学参考书和技术资料，对广大从事计算机相关研究和应用开发的科技人员也有很大的参考价值。i前前 言言计算概论是普通高校面向理工科低年级学生开设的计算机基础教育课。课程前 1/3 部分为计算机文化，后 2/3 部分为程序设计。任教此课两年来，发现没有合适的教材，因此根据授课经验，汇编各书和汇编各书和参考资料参考资料，编成此书。编者2009 年 1 月于北大燕园ii目目 录录前言前言第第 1 1 章章 引论引论.11.1 计算机科学 .21.2 摩尔定律 .31.3 SCOPE OF PROBLEMS.5上篇上篇 计算机文化计算机文化.8第第 2 2 章章 计算机系统计算机系统.92.1 COMPUTER INTRODUCTION.92.1.1 TURING MODEL .102.1.2 VON NEUMANN MODEL .152.1.3 Computer components .172.1.4 History.182.1.5 Practice set .212.2 计算机系统漫游 .222.1.1 Information is Bits + Context.242.1.2 Programs Are Translated by Other Programs into Different Forms.262.1.3 It Pays to Understand How Compilation SystemsWork.282.1.4 Processors Read and Interpret Instructions Stored in Memory.302.1.5 Caches Matter.362.1.6 Storage Devices Form a Hierarchy.372.1.7 The Operating System Manages the Hardware.382.1.8 Systems Communicate With Other Systems Using Networks .452.1.9 The Next Step.472.1.10 Summary.47第第 3 3 章章 数据和数的表示数据和数的表示.503.1 数据的表示 .503.2 数的表示 .54iii第第 4 4 章章 程序设计语言和开发环境程序设计语言和开发环境.584.1 程序设计语言 .584.2 开发环境 .68下篇下篇 程序设计程序设计.74第第 5 5 章章 C+基础基础.755.1 GETTING STARTED.755.2 FUNDAMENTAL TYPES.795.3 ARITHMETIC OPERATOR.815.4 CONTROL STRUCTURES.83第第 6 6 章章 数组和结构数组和结构.946.1 数组 .946.1.1 Initializing arrays .956.1.2 Accessing the values of an array.966.1.3 Multidimensional arrays.976.2 结构 .1056.2.1 Data structures.1056.2.2 Pointers to structures.1096.2.3 Nesting structures.112Quiz : Structures.113第第 7 7 章章 C+标准库标准库.1147.1 C LANGUAGE LIBRARY.1157.2 INPUT/OUTPUT STREAM LIBRARY.1167.3 STRING LIBRARY.1177.4 STL: STANDARD TEMPLATE LIBRARY.117第第 8 8 章章 函数和递归函数和递归.1208.1 FUNCTIONS WITH NO TYPE. THE USE OF VOID. .1258.2 ARGUMENTS PASSED BY VALUE AND BY REFERENCE.1278.3 DEFAULT VALUES IN PARAMETERS.1298.4 OVERLOADED FUNCTIONS.1308.5 INLINE FUNCTIONS.1328.6 RECURSIVITY.1328.7 DECLARING FUNCTIONS.136iv第第 9 9 章章 指针和引用指针和引用.1399.1 POINTERS.1399.1.1 Reference operator ( World Community Grid, an effort to create the world's largest public computing grid to tackle scientific research projects that benefit humanity, run and funded by IBM; SETIhome, which is focused on analyzing radio-telescope data to find evidence of intelligent signals from space, hosted by the Space Sciences Laboratory at the University of California, Berkeley (the Berkeley Open Infrastructure for Network Computing (BOINC), was originally developed to support this project); LHChome, which is used to help design and tune the Large Hadron Collider, hosted by CERN in Geneva; and distributed.net, which is focused on finding optimal Golomb rulers and breaking various cryptographic ciphers.http:/folding.stanford.edu/English/Main http:/zh.wikipedia.org/wiki/Foldinghome 第 1 章 引论 6 http:/www.stanford.edu/group/pandegroup/images/FAH-May2008.png http:/www.equn.com/folding/ Foldinghome 是如何工作的呢？Foldinghome 是一个研究研究蛋白质折叠，误折，聚合及由此引起的相关疾病的分布式计算工程。使用联网式的计算方式和大量的分布式计算能力来模拟蛋白质折叠的过程，并指引我们近期对由折叠引起的疾病的一系列研究。图 1-3 Foldinghome第 1 章 引论 7 图 1-4 Shrek © Dreamworks Animation, rendering multiple frames of high-quality animationHappy Feet © Kingdom Feature Productions; Lord of the Rings © New Line Cinema 图 1-5 Simulating several hundred or thousand charactersIndexing the web (Google)Google（www.google.com）是一个搜索引擎，由两个斯坦福大学博士生Larry Page 与 Sergey Brin 于 1998 年 9 月发明，Google Inc. 于 1999 年创立。Google 网页搜索技术是来源于信息检索技术。Google 的“网页快照”功能，能从Google 服务器里直接取出缓存的网页。Simulating an Internet-sized network for networking experiments (PlanetLab)http:/www.planet-lab.org/ PlanetLab is a global research network that supports the development of new network services. Since the beginning of 2003, more than 1,000 researchers at top academic institutions and industrial research labs have used PlanetLab to develop new technologies for distributed storage, network mapping, peer-to-peer systems, distributed hash tables, and query processing. PlanetLab currently consists of 1128 nodes at 511 sites. Speeding up content delivery (Akamai)美国 Akamai 是国际上最大的 CDN 服务商,它巨大的网络分发能力在峰值时可达到 15Gbps。Akamai 公司是为数不多的旨在消除 Internet 瓶颈和提高下载速度的几家新公司之一,是一个致力于网络交通提速的“内容发布”公司，是波士顿高技术区最卓越的新兴企业之一。Akamai 公司向全球企业 提供发送互联网内容，汇流媒体和应用程序的服务(目前，该公司为 15 个国家的企业管理着 8000第 1 章 引论 8 多台服务器)。1998 年，丹尼尔.L 和麻省理工学院的一 些研究人员一起创立了这家公司,他在麻省理工学院的硕士论文构成了 Akamai 公司最初的“自由流”（Freeflow）技术的核心。 9 上篇上篇 计算机文化计算机文化上篇的主要目的是向读者介绍有关计算机和信息技术的基本概念和基本原理，使读者能够对计算机学科有全局性的认识。第 2 章 计算机系统 10 第 2 章 计算机系统2.1 Computer Introduction本节大部分内容取自下面这本书的第一章。等号线之间内容是我加的。Foundations of Computer Science,2e,by Behrouz Forouzan and Firouz Mosharraf, Cengage Learning Business Press, December 5, 2007http:/www.cengage.co.uk/forouzan/ http:/www.amazon.com/Foundations-Computer-Science-Behrouz-Forouzan/dp/1844807002/ref=si3_rdr_bb_product The phrase computer science has a very broad meaning today. However, in this book, we define the phrase as “issues related to the computer“. This introductory chapter first tries to find out what a computer is, then investigates other issues directly related to computers. We look first at the Turing model as a mathematical and philosophical definition of computation. We then show how today's computers are based on the von Neumann model. The chapter ends with a brief history of this culture-changing device.the computer.Objectives After studying this chapter, the students should be able to:Define the Turing model of a computer.Define the von Neumann model of a computer.Describe the three components of a computer: hardware, data, and software.List topics related to computer hardware.List topics related to data.List topics related to software.Discuss some social and ethical issues related to the use of computers.Give a short history of computers.第 2 章 计算机系统 11 2.1.1 TURING MODELThe idea of a universal computational device was first described by Alan Turing in 1937. He proposed that all computation could be performed by a special kind of machine, now called a Turing machine. Although Turing presented a mathematical description of such a machine, he was more interested in the philosophical definiton of computation than in building the actual machine. He based the model on the actions that people perform when involved in computation. He abstracted these actions into a model for a computational machine that has really changed the world.Perceptual knowledge (感性认识)计算机组成部分http:/net.pku.edu.cn/course/cs101/2008/video/computer_components.flv Introduction to Computer Hardwarehttp:/net.pku.edu.cn/course/cs101/2008/video/intro2computer_hardware.flv Install http:/net.pku.edu.cn/course/cs101/2008/video/flvplayer_setup.exe, if your computer can not show videos.图 2-1 Mother board (主板：集成多个部件、适配器，提供它们之间的互联)第 2 章 计算机系统 12 主板(Main Board)又名主机板、系统板、母板，是 PC 机的核心部件。PC 机的主板包括 CPU、芯片组（Chipset） 、高速缓存（Cache） 、ROM_BIOS 芯片、CMOS 芯片、内存 RAM、总线通道、软硬磁盘接口、串行和并行接口、USB接口、扩展槽（Slots） 、直流电源插座、可充电电池以及各种条线。图中从上到下，左到右：内存条，磁盘、光驱等的数据线接口；CPU 风扇（一般下面是散热器，和 CPU） ；棕色 AGP 槽：只能接显卡；白色 PCI 槽：能接显卡、网卡、声卡等。图 2-2 CPU = 运算器+控制器图 2-3 Alan Turing, founder of computer science, and artificial intelligencehttp:/www.builder.com.cn/2008/0331/788473.shtml 图灵是举世罕见的天才数学家和计算机科学家，仅仅在世 42 年。他的英年早逝,像他横溢的才华一样，令世界吃惊与难以置信。生命虽然短暂，但那传奇第 2 章 计算机系统 13 的人生，丰富多彩的创造力和智慧而深邃的思想，使他犹如一颗耀眼的明星，持续地照耀着人间后世在科学的浩瀚太空里探索未来的人们。 自上个世纪 60 年代以来,计算机技术飞速发展,信息产业逐渐成为影响人类社会的最重要的工业之一。支持技术与工业发展的理论基础是计算机科学。众所周知， “诺贝尔奖”是世界上最负盛名的奖项,但仅用于奖励那些在物理、化学、文学、医学、经济学与促进世界和平等方面做出开拓性重大贡献的人士。“图灵奖”则是计算机科学领域的最高奖项,有“计算机界诺贝尔奖”之称。设立这个大奖，既是为了促进计算机科学的进一步发展，也是为了纪念一位天才数学家、计算机科学的奠基人艾兰·图灵。http:/zh.wikipedia.org/wiki/图灵 图灵被视为计算机科学之父。1931 年进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统 Enigma，帮助盟军取得了二战的胜利。图灵对于人工智能的发展有诸多贡献，例如图灵曾写过一篇名为机器会思考吗？ （Can Machine Think?）的论文，其中提出了一种用于判定机器是否具有智能的试验方法，即图灵试验。至今，每年都有试验的比赛。此外，图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。http:/net.pku.edu.cn/course/cs101/2008/video/alan_turing.flvA short video describing the life and unfortunate death of Alan Turing.http:/zh.wikipedia.org/wiki/姚期智姚期智，美籍华人，计算机科学家，2000 年图灵奖得主，是目前唯一一位获得此奖项的华人及亚洲人。目前是清华大学理论计算机科学研究中心教授。 因为对计算理论，包括伪随机数生成，密码学与通信复杂度的诸多贡献，美国计算机协会（ACM）决定把该年度的图灵奖授予他。 Data processorsFigure 1.1 A signle purpose computing machine第 2 章 计算机系统 14 Before discussing the Turing model, let us define a computer as a data processor. Using this definition, a computer acts a black box that accepts input data, processes the data, and created output data (Figure 1.1). Although this model can define the functionality of a computer today, it is too general. In this model, a pocket calculator is also a computer (which it is, in a literal sense).Another problem with this model is that it does not specify the type of processing, or whether more than one type of processing is possible. In other words, it is not clear how many types or sets of operations a machine based on this model can perform. Is it a specific-purpose machine or a general-purpose machine?This model could represent a specific-purpose computer (or processor) that is designed to do a single job, such as controlling the temperature of a building or controlling the fuel usages in a car. However, computers, as the term is used today, are general-purpose mahines. They can do many different types of tasks. This implies that we need to change this model into the Turing model to be able to reflect the actual computers of today.Programmable data processors The Turing model is a better model for a general-purpose computer. This model ad