摩尔定律:集成电路上可以容纳的晶体管数目在大约每经过18个月便会增加一倍。
参与运算的数转换为二进制进行计算;
二进制的运算通过基本的布尔运算实现;
基本的布尔运算可以由电路去完成。
电路能计算,计算机能计算。
CPU就是电路
有指令集;
指令是二进制的,CPU能看懂并执行。
要让CPU按照我们的想法做事
把我们想做的事说给计算机(程序)。
程序就是人们用来告诉计算机应该做啥的表示。
用高级语言的方式(2千多种语言)。
程序必须经过编译才能转换成CPU所能接受的指令。
一条语句可能被转换成多条指令。
在控制器的协调下执行行相应的指令。
表示:图、文字、语音等等
编译:词法分析、语法分析、链接输出
程序执行结果不仅取决于算法、程序编写,而且取决于语言处理系统、操作系统、ISA、微体系结构,不同计算机课程处于不同层次,必须将各层次关联起来解决问题。
上层是下层的抽象,下层是上层的实现,底层为上层提供支撑环境!
世界上第一个计算机程序员:Ada
计算机之父:冯·诺伊曼、图灵
可计算问题
设函数 f 的定义域是 D ,值域是 R ,如果存在一种算法,对于D中任意给定的 x ,都能计算出f(x) 的值,则称函数 f 是可计算的。
即:为计算建立一个数学模型(计算模型),然后证明,凡是这个计算模型能够完成的任务,就是可计算的任务。
在艾伦·图灵1936年关于可计算数字的论文中,他提出了一个思想实验。 图灵描述了一台机器,它有一个无限长的磁带,它在上面写,读和改变符号。 他进一步表明,具有正确的最小操作集的机器可以计算任何可计算的东西,无论其复杂性如何。
图灵机
简单、强大、可实现
给出了一个可实现的通用计算模型
引入了通过读写符号和状态改变进行运算的思想
真实了基于简单字母表完成复杂运算的能力
引入了存储区、程序、控制器等概念原型
➢ 程序 = 算法 + 数据结构(1960’s )
➢ 程序 = 子程序 + 子程序(1970’s )
复用
复用的东西包括有形的和无形的成果
复用的内涵在于提高质量和生产率
分而治之
将一个复杂的问题分解成若干简单的问题,朴素的思想来源于生活,完全适合于技术领域。
今天,软件产品越来越复杂,相互之间的依赖性更强,分工也愈加细化。
程序=算法+数据结构。软件的结构与抽象集中在数据结构上。
➢ 渐渐的,人们开始希望把算法与数据结构结合起来,ADT被提了出来。