计算机科学的基本概念和基本知识(“算法”文档)共51张.pptx资源-CSDN文库

54 浏览量 2022-11-14 05:05:33 上传评论收藏 300KB PPTX 举报

资源推荐

资源详情

资源评论

第二章计算机科学的基本概念和基本知识

2.1 计算模型与二进制

数学不等于计算，但数学确实起源于对计算的研究。

数学、计算模型（计算方法、数学机器）、形式化与形式化方

法

我们说，形式是事物的内容存在的外在方式、形状和结

构的总和。所谓形式化是将事物的内容与形式相分离，用事

物的某种形式来表示事物。形式化方法是在对事物描述形式

化的基础上，通过研究事物的形式变化规律来研究事物变化

规律的全体方法的总称。

所谓计算模型是刻划计算这一概念的一种抽象的形式系统或

数学系统，而算法是对计算过程步骤（或状态

将布尔代数和前面谈到的二进制联系起来，我们可以看出，“与”、“或”、“非”门电路的作用与集合运算“交”、“并”、“补”是一致的。

程序与存储程序式计算机

add 加法 idiv 有符号除法 mul 无符号乘法

凭直觉想象给出的算法往往不是最好的算法。

每一条汇编指令用某个西文字符串的缩写来表示其所代表的操作，用符号来代表数据的二进制、八进制和十进制数字序列。

（状态，符号）→（写符号，移动，状态）；

含同时性以及微观上的流水线处理。

机器指令的格式一般分为两部分，如下所示：

由于观察计算的角度不同，产生了各种不同的计算模型。

机器指令的格式一般分为两部分，如下所示：

x≤y & x≠0 then gcd(x，y－x，z)；

算法有一个或多个输出，即与输入有某个特定关系的量；

只要建立两种进制的数据之间的转换方法，那么，二进制将具有更多的优势。

＝ ∑ ki×2i

分成几个步骤：研究并行计算方法，研究并行算法，设计并行程序，调试与运行，分析结果。

渐进增长率用复杂性度量函数表示，该函数表示了算法随问题规模大小变化引起的算法中抽象的基本运算执行的次数或存储空间量的变

化规律。

容能否被图灵机所接受。假定图灵机从左向右扫描完带子上

的内容后停机则为接受，否则为不接受。

例2 一台图灵机可以设计成识别下面的序列：

1000110, 10011101, 010101011。

第二，把图灵机看作生成器，对给定的输入集合，考察输

出集合，并研究输入输出集合性质之间的关系，这就研究了图

灵机的生成能力。

例3 设一台图灵机的输入集合为In＝{1

n

0

n

│n∈N}，可设计一台

图灵机，对给定的输入集合In，得到输出集合Out＝{0

n

1

n

│n∈N}。其

中，N是全体自然数的集合。

第三，把图灵机看作计算器，相当于一个函数。图灵机的

输入是函数的自变量的值，图灵机的输出是函数的值。

例4 图灵机可以计算下列函数：

剩余50页未读，继续阅读

内容反馈

Mmnnnbb123

粉丝: 702
资源: 8万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip