计算机文化、程序设计.pdf

《计算机文化、程序设计.pdf》由会员分享，可在线阅读，更多相关《计算机文化、程序设计.pdf（269页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计 算 概 论-计算机文化、程序设计Introduction to Computing:Computer Culture,and Programming闫宏飞陈狮编著by Hongfei Yan and Chong Chen2010/9/23内 容 简 介本书主要是汇编各书和参考资料而成，比较系统地介绍了计算机文化，和程序设计。通过这两部分有机的结合（前 者 占 1/3,后 者 占 2/3）,即理论与实践结合，使学生理解和掌握有关计算机和信息技术的基本概念和基本原理，对计算机学科有全局性的认识；学会使用计算机进行信息处理，熟练掌握C+语言编程技术，为后续相关课程的学习打好基础。本书层次分明，山

2、浅入深，具有学习和实用双重意义。本书可作为高等院校各专业一、二年级学生的教学参考书和技术资料，对广大从事计算机相关研究和应用开发的科技人员也有很大的参考价值。,*,-a-刖 H 计算概论是普通高校面向理工科低年级学生开设的计算机基础教育课。课程前1/3部分为计算机文化，后2/3部分为程序设计。任教此课两年来，发现没有合适的教材，因此根据授课经验，汇编各书和参考资料，编成此书。编者2009年1月于北大燕园目 录第1章 弓I论.-11.1 计算机科学.21.2 摩尔定律.31.3 SCOPE OF PROBLEMS.5计算机文化.9第2章统.102.1 COMPUTER INTRODUCTION.

3、102.1.1 TURING MODEL.112.1.2 VON NEUMANN MODEL.162.1.3 Computer components.182.1.4 History.192.1.5 Practice set.242.2 计 勃L系统漫游.252.1.1 Information is Bits+Context.272.1.2 Programs Are Translated by Other Programs into Different Forms.292.1.3 It Pays to Understand How Compilation SystemsWork.312.1.4

4、Processors Read and Interpret Instructions Stored in Memory.322.1.5 Caches Matter.382.1.6 Storage Devices Form a Hierarchy.392.1.7 The Operating System Manages the Hardware.402.1.8 Systems Communicate With Other Systems Using Networks.472.1.9 The Next Step.492.1.10 Summary.49第3章 糠 和 数 的 新.523.1 数 据

5、的.523.2 的.66第4章 外 设 言 和 开 发 礴-704.1 腑设言.704.2 开发环境.80下 篇 撕 设 计.86第5章C+4础.875.1 GETTING STARTED.875.2 FUNDAMENTAL TYPES.915.3 ARFTHMETIC OPERATOR.1005.4 CONTROL STRUCTURES.123第6章 耀 和 结 构.1536.1 数组.1536.1.1 Initializing arrays.未定义书签。6.1.2 Accessing the values of an array.!未定义书签。6.1.3 Multidimensional

6、arrays.!未定义书签。6.2 结构.1646.2.1 Data structures.错误！未定义书签。6.2.2 Pointers to structures.未定义书签。6.2.3 Nesting structures.未定义书签。Quiz:Structures.199第7章C+标准库.2057.1 C LANGUAGE LIBRARY.2067.2 INPUT/OUTPUT STREAM LIBRARY.2077.3 STRING LIBRARY.2087.4 STL：STANDARD TEMPLATE LIBRARY.208第8章 函数和递归-错误！未定义书签。8.1 FUNCT

7、IONS WITH NO TYPE.THE USE OF VOID.未定义书签。8.2 ARGUMENTS PASSED BY VALUE AND BY REFERENCE.!未定义书签。8.3 DEFAULT VALUES IN BRAMETERS.!未定义书签。8.4 OVERLOADED FUNCTIONS.!未定义书签。8.5 INLINE FUNCTIONS.未定义书签。8.6 RECURSIVITY.未定义书签。8.7 DECLARING FUNCTIONS.未定义书签。iii第9章 恸 和 引 用-2129.1 POINTERS.2129.1.1 Reference operat

8、or(&).2129.1.2 Dereference operator(*).2149.1.3 Declaring variables of pointer types.2159.1.4 Pointers and arrays.2189.1.5 Pointer initialization.2209.1.6 Pointer arithmetics.2219.1.7 Pointers to pointers.2239.1.8 void pointers.2249.1.9 NuH pointer.2259.1.10 Pointers to functions.2269.2 DYNAMIC MOMO

9、RY.2279.2.1 Operators new and new口.2279.2.2 Operators delete and delctcQ.2299.2.3 Dynamic memoiy inANSI-C.231第 10 章 VARIABLES:A DEEPER LOOK.23210.1 MEMORY ORGANIZATION.23210.2 VARIABLE SCDPE.23410.3 UNDERSTANDING POINTERS.235第11章 算 法.23811.1 THE ROLE OF AUJORFTHMS IN COMPUTING.23911.1.1 Algorithms.2

10、3911.1.2 Algorithms as a technology.24411.2 算 法 的 峻.24711.3 算法的三种基本结构.24711.4 算法的表示.24811.5 介绍几种基本算法.24811.6 迭代与递归.248第12章 龄 设 计.24912.1 简单计算题.24912.2 模拟.24912.3 可模型化的问题.250iv12.4 动态檄ij.250Introduction(Beginner).251Elementary.254Intermediate.255Upper-Intermediate.257Advanced.258参考文献.262第1章引论第1章引论计算机

11、文化这个词的出现到被广泛认可的时间并无确切的考证，但基本上是在 20世纪80年代后期。计算机开始是一种装置，进而到一门学科，再发展成为一种“文化”，它对人类的影响力之大的确令人惊叹。计算机文化是指能够理解计算机是什么，以及它如何被作为资源使用的。简单地说，计算机文化不但是知道如何使用计算机，更重要的是知道什么时候使用计算机。在当今世界，几乎所有专业都与计算机息息相关。但是，只有某些特定职业和学科才会深入研究计算机本身的制造、编程和使用技术。用来诠释计算机学科内不同研究领域的各个学术名词的涵义不断发生变化，同时新学科也层出不穷。五个主要的计算机学科(disipline of computing)

12、包括 计算机工程学(Computer Engineering),是电子工程的一个分支，主要研究计算机软硬件和二者间的彼此联系。计算机科学(Computer Science),是对计算机进行学术研究的传统称谓。主要研究计算技术和执行特定任务的高效算法。该门学科为我们解决确定一个问题在计算机领域内是否可解，如可解其效率如何，以及如何作成更加高效率的程序。时至今日，在计算机科学内已经派生了许多分支，每个分支都针对不同类别的问题进行深入研究。软件工程学(Software Engineering),着重于研究开发高质量软件系统的方法学和实践方式，并试图压缩并预测开发成本及开发周期。信息系统(Infbrm

13、ation System s),研究计算机在一个广泛的有组织环境(商业为主)中的计算机应用。信息技术(Infbrmation Technology),指计算机相关的管理和维护。计算概论课程关注的是计算机学科。较大规模的致力于计算机科学的组织有：美国计算机协会(Association of Computing Machinery,简称ACM)；美国电气电子工程师协会(Institute of Electrical and Electronics Engineers,简称为IEEE)1 Computing Curricula 2005:The Overview Report,http:/www.a

14、cm.org/education/curric vols/CC2005-March06Final.pdf i 第1章引论1.1 计算机科学计算机科学是-门包含各种各样与计算和信息处理相关主题的系统学科，从抽象的算法分析、形式化语法等等，到更具体的主题如编程语言、程序设计、软件和硬件等。作为一门学科，它与数学、计算机程序设计、软件工程和计算机工程有显著的不同，却通常被混淆，尽管这些学科之间存在不同程度的交叉和覆盖。2计算机科学研究的课题是：计算机程序能做什么和不能做什么（可计算性）；如何使程序更高效的执行特定任务（算法和复杂性理论）；程序如何存取不同类型的数据（数据结构和数据库）；程序如何显得更

15、具有智能（人工智能）；人类如何与程序沟通（人机互动和人机界面）。计算机科学的大部分研究是基于“冯诺依曼计算机”和“图灵机”的，它们是绝大多数实际机器的计算模型。作为此模型的开山鼻祖，邱奇-图灵论题（Church-Turing Thesis）表明，尽管在计算的时间，空间效率上可能有所差异，现有的各种计算设备在计算的能力上是等同的。尽管这个理论通常被认为是计算机科学的基础，可是科学家也研究其它种类的机器，如在实际层面上的并行计算机和在理论层面上概率计算机、oracle计算机和量子计算机。在这个意义上来讲,计算机只是一种计算的工具：著名的计算机科学家Dijkstra有 句 名 言“计算机科学之关注于

16、计算机并不甚于天文学之关注于望远镜。计算机科学根植于电子工程、数学和语言学，是科学、工程和艺术的结晶。它在20世纪最后的三十年间兴起成为一门独立的学科,并发展出自己的方法与术语。早期，虽然英国的剑桥大学和其他大学已经开始教授计算机科学课程，但它只被视为数学或工程学的一个分支，并非独立的学科。剑桥大学声称有世界上第一个传授计算的资格。世界上第一个计算机科学系是由美国的普渡大学在1962年设立，第一个计算机学院于1980年由美国的东北大学设立。现在，多数大学都把计算机科学系列为独立的部门，部分将它与工程系、应用数学系或其他学科联合。计算机科学领域的最高荣誉是ACM 设立的图灵奖，被誉为是计算机科学

17、的诺贝尔奖。它的获得者都是本领域最为出色的科学家和先驱。华人中首获图灵奖的是姚期智博士。他于2000年以其对计算理论做出的诸多“根本性的、意义重大的”贡献而获得这一崇高荣誉。2 http:/zh.wikiDedia.org/wiki/计算机科学2 第 1章引论1.2 摩尔定律http:en.wikipedia.org/wiki/Moore%27s LawMoores law describes a long-term trend in the history of computing hardware.Sincethe invention of the integrated circuit i

18、n 1958,the number of transistors that can beplaced inexpensively on an integrated circuit has increased exponentially,doublingapproximately every two years.The trend was first observed by Intel co-fbunderGordon E.Moore in a 1965 pape匚It has continued for almost half of a century and isnot expected t

19、o stop for another decade at least and perhaps much os-2,000,000,0001,000,000,000 10,000,0001,000,000 100,000 10,0002,300 JOual-Corn narnum 2 POWER.IttrtuE 2 9MB cache Core?QuadHnrMUn 2 100,000,0001980199020002008Curve shows Moores Law：transistor count doublingevery two years*IUnli*n TIA WHA GT200 R

20、V770Date of introduction图 I-I CPU Transistor Counts 1971-2008&Moores Law,Growth of transistor countsfor Intel processors(dots)and Moores Law(logarithmic vertical scale)Almost every measure of the capabilities of digital electronic devices is linked toMoore*s law:processing speed,memory capacity,even

21、 the number and size of pixels indigital cameras.All of these are improving at(roughly)exponential rates as well.Thishas dramatically increased the usefulness of digital electronics in nearly every segmentof the world economy.Moores law describes this driving force of technological and3 第 1章引论social

22、 change in the late 20th and early 21st centuries.http:/ 隔 18个月就翻一番。微处理器的性能每隔18个月提高一倍，而价格下降一倍。用一个美元所能买到的电脑性能，每 隔 18个月翻两番。图 1 -2 Computer SpeedupMoores Law:The density of transistors on a chip doubles every 18 months,for thesame cos/(1965)半导体集成电路的密度或容量每18个月翻一番Moores Law is still valid.His law has not

23、hing to do with the speed of theproccesor.It has to do with the number of transitotrs which is still doubleing everycouple of years.Case in point there is now multiple cores in the same space instead ofone core.4-第1章引论戈 登 摩 尔(Gordon Moore),CPU生产商Intel公司的创始人之一。1965年提 出“摩尔定律”，1968年创办Intel公司。摩 尔 1929年出

24、生在美国加州的旧金山。曾获得加州大学伯克利分校的化学学士学位，并且在加州理工大学(CIT)获得物理和化学两个博士学位。50年代中期他和集成电路的发明者罗伯特诺伊斯(Robert Noyce)-起，在威廉 肖克利半导体公司工作。后来，诺伊斯和摩尔 等 8 人集体辞职创办了半导体工业史上有名的仙童半导体公司(FairchildSemiconductor).,仙童成为现在的Intel和 AMD之父。1968年，摩尔和诺伊斯一起退出仙童公司，创办了 Intel。Intel初期致力于开发当时计算机工业尚未开发的数据存储领域，后来，Intel进行战略转移，专攻微型计算机的“心脏”部件-CPU。1.3 Sc

25、ope of ProblemsWhat can you do with 1 computer?What can you do with 100 computers?What can you do with an entire data center?http:en.wikiDedia.org/wiki/Distributcd comDuting#ProiectsProjects:A variety of distributed computing projects have grown up in recent years.Manyare run on a volunteer basis,an

26、d involve users donating their unused computationalpower to work on interesting computational problems.Examples of such projectsinclude the Stanford University Chemistry Department Foldinghome project,whichis focused on simulations of protein folding to find disease cures and to understandbiophysica

27、l systems;World Community Grid,an effort to create the world*s largestpublic computing grid to tackle scientific research projects that benefit humanity,runand funded by IBM;SETIhome,which is focused on analyzing radio-telescope datato find evidence of intelligent signals from space,hosted by the Sp

28、ace SciencesLaboratory at the University of California,Berkeley(the Berkeley Open Infrastructurefbr Network Computing(BOINC),was originally developed to support this project);LHChome,which is used to help design and tune the Large Hadron Collider,hostedby CERN in Geneva;and ,which is focused on find

29、ing optimal Golombrulers and breaking various cryptographic ciphers.http:folding.stanford.edu/English/Mainhttp:zh.wikiDcdia.org/wiki/Foldinghomchttp:www.stanford.edu/grouD/pandegrouD/images/FAH-May2008.png5第 1章引论http: 1-3 Foldinghome 6 第 1章引论图 1-4 Shrek Dreamworks Animation,rendering multiple frames

30、 of high-qualityanimationHappy Feet Kingdom Feature Productions;Lord of the Rings New Line Cinema图 1-5 Simulating several hundred or thousand charactersIndexing the web(Google)Google()是一个搜索引擎，由两个斯坦福大学博士生LarryPage 与 Sergey Brin 于 1998 年 9 月发明，Google Inc.于 1999 年创立 Google 网页搜索技术是来源于信息检索技术。Google的“网页快照

31、”功能，能 从 Google服务器里直接取出缓存的网页。Simulating an Internet-sized network for networking experiments(PlanetLab)http:wwwwlanet-lab.org/PlanetLab is a global research network that supports the development of newnetwork services.Since the beginning of 2003,more than 1,000 researchers at topacademic institutions

32、 and industrial research labs have used PlanetLab to develop newtechnologies for distributed storage,network mapping,peer-to-peer systems,distributed hash tables,and query processing.PlanetLab currently consists of 1128nodes at 511 sites.Speeding up content delivery(Akamai)美 国 Akamai是国际上最大的CDN服务商，它巨

33、大的网络分发能力在峰值时可 达 到 15Gbps Akamai公司是为数不多的旨在消除Internet瓶颈和提高下载速度的儿家新公司之，是一个致力于网络交通提速的“内容发布”公司，是波士顿高技术区最卓越的新兴企业之一。Akamai公司向全球企业提供发送互联网内容，汇流媒体和应用程序的服务(目前，该公司为15个国家的企业管理着8000多台服 7 第1章引论务器）。1998年，丹尼尔.L 和麻省理工学院的一些研究人员起创立了这家公司,他在麻省理工学院的硕士论文构成了 Akamai公司最初的“自由流”（Freeflow）技术的核心。根据美国航空公司的消息，丹尼尔.L31岁，在 2001年 9 月 1

34、1日撞击纽约世界贸易中心的被劫持飞机上遇难。上篇计算机文化上篇的主要目的是向读者介绍有关计算机和信息技术的基本概念和基本原理，使读者能够对计算机学科有全局性的认识。9第2章计算机系统第2章计算机系统2.1 Computer Introduction本节大部分内容取自下面这本书的第一章。等号线之间内容是我加的。Foundations of Computer Science,2e,by Behrouz Forouzan and Firouz MosharrafCengagc Learning Business Press,December 5,2007http:www.cengage.co.uk/

35、forouzan/http:/www.amazon.eom/Foundations-ComputeAScience-Behrouz-Forouzan/dp/l844807002/ref=si3 rdr bb productThe 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 firsttries to find out what

36、 a computer is,and then investigates other issues directly relatedto computers.We look first at the Turing model as a mathematical and philosophicaldefinition of computation.We then show how toda/s computers are based on the vonNeumann model.The chapter ends with a brief history of this culture-chan

37、gingdevice.the computer.ObjectivesAfter studying this chapter,the students should be able to:Define the Turing model of a compute匚 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 r

38、elated to data.*List topics related to software.*Discuss some social and eth ieel issues F elated the use of computers.,Give a short history of computers.io-第2章计算机系统2.1.1 TURING MODELThe idea of a universal computational device was first described by Alan Turing in1937.He proposed that all computati

39、on could be performed by a special kind ofmachine,now called a Turing machine.Although Turing presented a mathematicaldescription of such a machine,he was more interested in the philosophical definiton ofcomputation than in building the actual machine.He based the model on the actionsthat people per

40、form when involved in computation.He abstracted these actions into amodel for a computational machine that has really changed the world.Perceptual knowledge（感性认识）计算机组成部分http:net.D 101/2008/video/comDuter comDonents.fivIntroduction to Computer Hardwarehttp: 101/2008/video/intro2computcr hardware.flvI

41、nstall http: 101/2008/video/flvplaYer setup.exe.if yourcomputer can not show videos.图 21 Motherboard（主板：集成多个部件、适配器，提供它们之间的互联）11第2 章计算机系统主板（Main Board）又名主机板、系统板、母板，是 PC 机的核心部件。PC机的主板包括CPU、芯片组（Chipset）、高速缓存（Cache）、ROM_BIOS芯片、CMOS芯片、内 存 RAM、总线通道、软硬磁盘接口、串行和并行接口、USB接口、扩展 槽（Slots）直流电源插座、可充电电池以及各种条线。图中从上到下

42、，左到右：内存条，磁盘、光驱等的数据线接口；CPU风 扇（般下面是散热器，和 CPU）；棕色AGP槽：只能接显卡；白色PCI槽：能接显卡、网卡、声卡等。图 2-2 CPU=运算器+控制器图 2-3 Alan Turing,founder of computer science,and artificial intelligencehttp: 2 年。他的英年 12-第2 章计算机系统早逝，像他横溢的才华一样，令世界吃惊与难以置信。生命虽然短暂，但那传奇的人生，丰富多彩的创造力和智慧而深邃的思想，使他犹如一颗耀眼的明星，持续地照耀着人间后世在科学的浩瀚太空里探索未来的人们。自上个世纪60年代以来

43、，计算机技术飞速发展，信息产业逐渐成为影响人类社会的最重要的工业之一。支持技术与工业发展的理论基础是计算机科学。众所周知，“诺贝尔奖”是世界上最负盛名的奖项,但仅用于奖励那些在物理、化学、文学、医学、经济学与促进世界和平等方面做出开拓性重大贡献的人士。“图灵奖”则是计算机科学领域的最高奖项，有“计算机界诺贝尔奖”之称。设立这个大奖，既是为了促进计算机科学的进一步发展，也是为了纪念一位天才数学家、计算机科学的奠基人艾兰 图灵。http:/zh.wikiDedia.org/wiki/图灵图灵被视为计算机科学之父。1931年进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑

44、桥，后曾协助军方破解德国的著名密码系统E nigm a,帮助盟军取得了二战的胜利。图灵对于人工智能的发展有诸多贡献，例如图灵曾写过一篇名为 机器会思考吗？(Can Machine T hink?)的论文，其中提出了一种用于判定机器是否具有智能的试验方法，即图灵试验。至今，每年都有试验的比赛。此外，图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。httr:/ turing.flvA short video describing the life and unfortunate death of Alan Turing.http:zh.wikipedia.org/wiki/姚期智姚

45、期智，美籍华人，计算机科学家，2000年图灵奖得主，是目前唯一一位获得此奖项的华人及亚洲人。目前是清华大学理论计算机科学研究中心教授。因为对计算理论，包括伪随机数生成，密码学与通信复杂度的诸多贡献，美国计算机协会(A C M)决定把该年度的图灵奖授予他。Data processorsInput Output Computer Figure 1.1 A signle purpose computing machine 13 第2章计算机系统Before discussing the Turing model,let us define a computer as a data processor

46、.Using this definition,a computer acts a black box that accepts input data,processes thedata,and created output data(Figure 1.1).Although this model can define thefunctionality of a computer today,it is too general.In this model,a pocket calculator isalso a computer(which it is,in a literal sense).A

47、nother 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 clearhow many types or sets of operations a machine based on this model can perform.Is ita specific-purpose machine or a general-purpose

48、machine?This model could represent a specific-purpose computer(or processor)that isdesigned to do a single job,such as controlling the temperature of a building orcontrolling the fuel usages in a car.However,computers,as the term is used today,aregeneral-purpose mahines.They can do many different ty

49、pes of tasks.This implies thatwe need to change this model into the Turing model to be able to reflect the actualcomputers of today.Programmable data processorsThe Turing model is a better model fbr a general-purpose computer.This model addsan extra element to the specific computing machine:the prog

50、ram.A program is a setof instructions that tells the computer what to do with data.Figure 1.2 shows theTuring model.In the Turing model,the output data depends on the combination of two factors:the input data and the program.With the same input,we can generate different outputsif we change the progr