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

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

2、本书层次分明，由浅入深，具有学习和实用双重意义。本书可作为高等院校各专业一、二年级学生的教学参考书和技术资料，对广大从事计算机相关研究和应用开发的科技人员也有很大的参考价值。i前 言计算概论是普通高校面向理工科低年级学生开设的计算机基础教育课。课程前 1/3 部分为计算机文化，后 2/3 部分为程序设计。任教此课两年来，发现没有合适的教材，因此根据授课经验，汇编各书和参考资料，编成此书。编 者2009 年 1 月 于 北 大 燕 园ii目 录前言iii图 示iv表 格第一章 引论 1 第 1 章 引论计算机文化（Computer Literacy）这个词的出现到被广泛认可的时间并无确切的考证，

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

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

5、ems） ，研究计算机在一个广泛的有组织环境（商业为主）中的计算机应用。 信息技术（Information Technology） ，指计算机相关的管理和维护。计算概论课程关注的是计算机学科。全球有三个较大规模的致力于计算机科学的组织：英国计算机学会（British Computer Society, 简称 BCS） ；美国计算机协会（Association of Computing Machinery, 简称 ACM） ；美国电气电子工程师协会（Institute of Electrical and Electronics Engineers，简称为 IEEE） 。1 Computing C

6、urricula 2005: The Overview Report, http:/www.acm.org/education/curric_vols/CC2005-March06Final.pdf 第一章 引论 2 1.1 计算机科学计算机科学是一门包含各种各样与计算和信息处理相关主题的系统学科，从抽象的算法分析、形式化语法等等，到更具体的主题如编程语言、程序设计、软件和硬件等。作为一门学科，它与数学、计算机程序设计、软件工程和计算机工程有显著的不同，却通常被混淆，尽管这些学科之间存在不同程度的交叉和覆盖。 2计算机科学研究的课题是： 计算机程序能做什么和不能做什么（可计算性） ； 如何使程

7、序更高效的执行特定任务（算法和复杂性理论） ； 程序如何存取不同类型的数据（数据结构和数据库） ； 程序如何显得更具有智能（人工智能） ； 人类如何与程序沟通（人机互动和人机界面） 。 计算机科学的大部分研究是基于“冯诺依曼计算机”和“图灵机”的，它们是绝大多数实际机器的计算模型。作为此模型的开山鼻祖，邱奇-图灵论题（Church-Turing Thesis）表明，尽管在计算的时间，空间效率上可能有所差异，现有的各种计算设备在计算的能力上是等同的。尽管这个理论通常被认为是计算机科学的基础，可是科学家也研究其它种类的机器，如在实际层面上的并行计算机和在理论层面上概率计算机、oracle 计算机和

8、量子计算机。在这个意义上来讲，计算机只是一种计算的工具：著名的计算机科学家 Dijkstra 有一句名言“计算机科学之关注于计算机并不甚于天文学之关注于望远镜。 ”。计算机科学根植于电子工程、数学和语言学，是科学、工程和艺术的结晶。它在 20 世纪最后的三十年间兴起成为一门独立的学科，并发展出自己的方法与术语。早期，虽然英国的剑桥大学和其他大学已经开始教授计算机科学课程，但它只被视为数学或工程学的一个分支，并非独立的学科。剑桥大学声称有世界上第一个传授计算的资格。世界上第一个计算机科学系是由美国的普渡大学在1962 年设立，第一个计算机学院于 1980 年由美国的东北大学设立。现在，多数大学都

9、把计算机科学系列为独立的部门，一部分将它与工程系、应用数学系或其他学科联合。计算机科学领域的最高荣誉是 ACM 设立的图灵奖，被誉为是计算机科学的诺贝尔奖。它的获得者都是本领域最为出色的科学家和先驱。华人中首获图灵奖的是姚期智博士。他于 2000 年以其对计算理论做出的诸多“根本性的、意2 http:/zh.wikipedia.org/wiki/计算机科学 第一章 引论 3 义重大的”贡献而获得这一崇高荣誉。1.2 摩尔定律http:/en.wikipedia.org/wiki/Moore%27s_Law Moores law describes a long-term trend in th

10、e history of computing hardware. Since the invention of the integrated circuit in 1958, the number of transistors that can be placed inexpensively on an integrated circuit has increased exponentially, doubling approximately every two years.The trend was first observed by Intel co-founder Gordon E. M

11、oore in a 1965 paper.It has continued for almost half of a century and is not expected to stop for another decade at least and perhaps much longer.图 1-1 CPU Transistor Counts 1971-2008 & Moores Law, Growth of transistor counts for Intel processors (dots) and Moores Law (logarithmic vertical scale) A

12、lmost every measure of the capabilities of digital electronic devices is linked to Moores law: processing speed, memory capacity, even the number and size of pixels in digital cameras.All of these are improving at (roughly) exponential rates as well.This has dramatically increased the usefulness of

13、digital electronics in nearly 第一章 引论 4 every segment of the world economy. Moores law describes this driving force of technological and social change in the late 20th and early 21st centuries.http:/ 计算机第一定律摩尔定律 Moore 定律。归纳起来，主要有以下三种“版本”： 集成电路芯片上所集成的电路的数目，每隔 18 个月就翻一番。 微处理器的性能每隔 18 个月提高一倍，而价格下降一倍。 用一

14、个美元所能买到的电脑性能，每隔 18 个月翻两番。a 图 1-2 Computer SpeedupMoores Law: “The density of transistors on a chip doubles every 18 months, for the same cost” (1965)半导体集成电路的密度或容量每 18 个月翻一番 Moores Law is still valid. His law has nothing to do with the speed of the proccesor. It has to do with the number of transitotrs which is still doubleing every couple of years. Case in point there is now multiple cores in the same space instead of one core.