von yao Hi Vor 9 Jahren
538
学习研究算法过程及养成习惯。
社会/自然现象(遗传与进化）--宽度学习-->计算学科的(遗传)算法(计算与计算系统(浅层次))--深度学习-->计算与计算系统(深层次)(本质、应用)
NPC问题理论上可通过枚举-验证的遍历算法来进行
遗传算法提供了一种求解复杂系统问题的通用框架。
导向性群随机搜索
为进一步提高近似解的质量，可采取导向性群(体)随机搜索方法
导向性群(体)随机搜索法：同时对多个随机点的选取进行导向(导向到接近最优解的方向或路径)，多条搜索路径
基于概率论：随机选择
•多条路径下的最优，总比一条路径的最优要更优一些。
•遗传算法就是这样一种导向性群随机搜索算法。
•同一时刻多条路径上的解集合即为一个种群。多次选择，即多代进
导向性随机搜索
为提高近似解的质量，可采取导向性随机搜索方法
导向性随机搜索法：对随机点的选取进行导向(导向到接近最优解的方向或路径)
随机搜索
随机搜索法：在解空间中随机选择一些可能解进行验证，求出所选择可能解(子解空间)中的最优解---近似解
基于概率论：随机选择
•子解空间越大，求得满意解的可能性越大，但耗时也会加长
•求出的近似解并不能保证是满意解
遗传算法的基本思想
不求精确解，而求近似解-满意解，可采取随机搜索方法
遗传算法提供了一种求解复杂系统问题的通用框架。
遗传算法的适用条件
(2)关于可能解的“适应度”函数的计算方法(适应度用于判 断一个可能解接近精确解的程度或方向)。
(1)已知“解空间”，即可能解的表现型和基因型
精确解
穷举法
穷举法或称遍历法：对解空间中的每一个可能解进行验证，直到所有的解都被验证是否正确，便能得到精确的结果---精确解
突变
变异
也是新可能解的一种形成方法，它是通过随机地改变一个可能解的编码的某些片段(或基因)而使一个可能解变为一新的可能解的遗传操作
交配/杂交
交叉
即交配/杂交，是新可能解的一种形成方法，即是对两个可能解的编码通过交换某些编码位而形成两个新的可能解的遗传操作
复制
将一个解从一个解集复制到另一个解集
选择
指从种群(解集)中依据适应度按某种条件选择某些个个体(可能解)
适应度
一个可能解接近最优解的一个度量，本例直接用F(X)作为其适应度的度量，其值越小越接近最优解
基因
解编码中的若干位的bi
染色体
编码解
一个可能解的基因型，本例即是X的二进制编码。X = b6b5b4b3b2b1，其中bi=0或1。
个体
解/个体
一个可能解的表现型，本例中即是十进制的X
种群
解集/种群
若干可能解的集合
生物学
计算机学
引入生物学
1，NPC类问题
2.1算法（2->2.1）
生物界问题求解思维，
类比与借鉴
近似解
NPC类问题的解
2，计算
3，精确解
4，NPC类问题的解
基本观点： 遗传与进化 优胜劣汰
(i) 生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；
(ii) 染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；
(iii) 生物的繁殖过程是由其基因的复制过程来完成的；
(iv) 通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。
(v) 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。
遗传与进化 优胜劣汰
科学
NPC问题
nNPC问题：完全非确定性多项式问题(NP-Complete)。如果NP问题的所有可能答案都可以在多项式时间内进行正确与否的验算的话就叫做完全非确定性多项式问题，即NP-Complete问题
NP类问题
NP类问题：非确定性多项式问题(Non-deterministic Polynomial)。有些问题，其答案是无法直接计算得到的，只能通过间接的猜算或试算来得到结果，这就是非确定性问题(Non-deterministic)。虽然在多项式时间内难于求解但不难判断给定一个解的正确性的问题，即：在多项式时间内可以由一个算法验证一个解是否正确的非确定性问题，就是NP类问题。
P类问题
P类问题： 多项式问题(Polynomial Problem)，指计算机可以在有限时间内求解的问题，即：P类问题是可以找出一个呈现O(n小a)复杂性算法的问题，其中a为常数
现实
计算复杂性是指问题的一种特性，即利用计算机求解问题的
难易性或难易程度，其衡量标准：
u计算所需的步数或指令条数(即时间复杂度)
u计算所需的存储空间大小(即空间复杂度)
----通常表达为关于问题规模n的一个函数O(f(n))
计算机完全不能求解的(不可计算问题)
计算机在有限时间内不能求解的(难求解问题）
计算机在有限时间内能够求解的(可求解问题）
TSP 商旅问题 求走过的距离最短。
算法的模拟与分析：可学习算法设计与分析。
算法的复杂度：计算理论与计算复杂性。
3.7.2 复杂性(O量级)
算法的复杂性与计算的复杂性
难解性
NP问题
非确定性多项式问题。
P可求解
多项式问题
例
O（n！）
O（3n）
n是指数
4x10 28
O（n3）
3是指数
“O”表示量级
把复杂性工或运行时间表达为n的函数
基本参数n
空间效率
时间效率
3.7.1 正确性
最优解
可行解
可学习高级语言程序设计
哥尼斯堡七桥
“过路点”有什么特点呢？它应该是“有进有出”的点，有一条边进这点，那么就要有一条边出这点，不可能是有进无出或有出无进。如果只进无出，它就是终点；如果有出无进，它就是起点。因此，在“过路点”进出的边总数应该是偶数，即“过路点”是偶点。
如果起点和终点是同一点，那么它也是属于“有进有出”的点，因此必须是偶点，这样图上全体点都是偶点。
如果起点和终点不是同一点，那么它们必须是奇点，因此这个图最多只能有二个奇点。
把上面所说的归纳起来，说简单点就是：
能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形
程序构造的表达方法
步骤描述法
用自然语言和数学语言描述算法步骤。
流程图
菱形（判断）
矩形（执行语句）
圆形（开始/结束）
基本控制结构
条件循环
当Q条件成立时，无限执行。
有界循环
循环次为正整数N
算法包含数据结构与逻辑结构。
就是针对选定的算法策略，设计其相应的数据结构及其运算规则。不同的算法可能需要不同的运算规则。
可学习算法与数据结构
数组
3.4.4 逻辑结构的存储（树）
设计不同的存储结构会有不同的效果。
3.4.3 指针（地址）
本质是一个地址。
3.4.2 变量
变量是占位符，占一定的存储单元。
3.4.1 数据结构
3.4.1.2 存储结构及操作
3.4.1.1 逻辑结构
用数学语言描述实际问题。
数学建模：可学习离散数学
算法策略设计：可学习算法设计与分析
方法
2，设计算法策略
动态规划算法
贪心算法
做当前最优的选择。
分治算法
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
遍历/搜索算法
1，描述输入与输出
输入问题与输出问题的描述。
数学模型
对实际问题的抽象简化的结构。
现实问题抽象成数学描述后，可以发现其是否可以求解甚至找到解决问题的方法。
算法性质
5，可能性
2，时间可能
1，基本操作可能
4，输出
3，输入
2，确定性
1，有穷性
有穷规则的集合，运算序列
算法的复杂度
问题
数学建模
算法策略
程序设计
问题求解
控制结构
数据结构
接受自然数x或自然数的元组，并产生自然数的一个映射。
投影函数
后继函数
S（n）＝n+1
常函数
h(0,x)
递推/迭代
递归：可以自递归基础开始，由前向后依次计算或直接计算；但有些，只能由后向前代入，直到递归基础，寻找一条路径，然后后再由前向后计算。
迭代(递推)：可以自递归基础开始，由前向后依次计算或直接计算
自递归基础开始，由前向后计算。
表达相似性对象及动作的无限性构造和执行方法。
递归包含递推，但递推不能覆盖递归。
由后向前代入，直至代入到递归基础，再由递归基础向后计算至计算出最终结果，即由前向后计算。
由前n项或第n项定义第n+1项；第低阶f（k）且k<n，来构造高阶f（n+1）的值。
定义、构造和计算的起点直接给出。
递归的构造
递归是一种算法或程序的构造技术（自身调用自身，向阶调用低阶，构造无限的计算步骤。
递归的定义
用递归定义无限相似的事物
引入
递推式
一个数列中An与该数列的其它项存在某种对应关系。
自相似性的东西无限重复构造。
问题：怎样在表达中既去省略号，又表达近乎无限的内容。
定义新运算符
命名新运算符和构造中使用新运算符及执行中以过程替换新运算符
(define (square x) (* x x))
(* x x)过程体，用于表示新运算符的具体计算规则，其为关于形式参数x的一种计算组合。
形式参数x，使用时将被实际参数所替代
名字的定义：定义名字square为一个新的运算，即过程或称函数另一种类型的名字：运算符型的名字
抽象：将经常使用的、可由低层次系统实现
的一些复杂动作，进行命名，以作为高层次
系统的指令被使用
例：（NewProc (+ 3 1))
命名计算对象和构造中使用名字及计算中以计算对象替换名字。
运算符提前
程序是由基本动作指令构造的，若干指令的一个组合或一个执行序列，用以实现复杂动作。
指令：控制基本动作的命令。
程序执行机构
程序执行机构= 负责解释程序即解释指令之间组合，并按次序调用指令即调用基本动作执行的机构
对新构造的组合。进行重命名，然。后。用到另一个新构造中。
抽象是一个命名过程。
将经常使用的、可由低层次系统实现的一些复杂动作进行命名，以作高层次系统的指令使用。
将低层次的复杂指令构抽象成高层次的一个指令。
组合后再进行抽象。
将一个构造放入到另一个构造中。
本质
基本动作的组合。
作用
构造复杂动作。
计算机系统
计算系统= 基本动作+ 指令+ 程序执行机构
迭代
递归步骤
递归基础
递归计算/执行
用递归构造
1
抽象
1->2
执行
计算对象
运算符
组合
计算机语言定义了基本元素的集合，以及基本元素的组合构造规则，所谓基本元素即是指标识符和保留字，所谓组合构造规则即是指语句的书写模式，即不同标识符和保留字的组合规则。
其中标识符可以是常量、变量名，也可以是函数名；保留字可以是赋值符号如“=”、语句结束符号如“；”、基本运算符号如“+”“-”“*”“/”、程序段落符号如“{ }”等，保留字还可以是其他语句模式的标志性符号。
越来越高效开发发展
basic
visual basic
pascal
perl
delphi
smalltalk
java
simula
javascript
c#
FORTRAN
algol
B
c
c++
python
不同抽象层面的计算机，由低层向应用层(高层)的基本层次划分是：微程序机器实际机器操作系统机器汇编语言机器高级语言机器
实际机器层面之上，不同层次的计算机，其本质是为用户提供一个计算机语言，用户可用该语言表达具体的操作需求，同时提供一个编译器将操作需求转换为机器可以执行的程序，最终实现用户的操作需求
用高级语言定义的算法的结果。
构造方式
自底向上
先构造基础函数，再组建骨架。
自顶向下
构建方法框架，再写细节。
函数（构造而不是编的）
构造
调用
定义
循环结构
分支结构
顺序结构
赋值语句
表达式（变量/常量组成）
比较表达式
逻辑表达式
算术表达式
所谓“高级语言”和“低级语言”是指其和机器硬件的相关程度，不涉及机器硬件的语言为高级语言，而与机器硬件相关的语言则为低级语言。
高级语言编程效率高是因为其可用大粒度积木块来构造程序，比一行行语句、一条条指令来编程效率高出很多
高级语言执行过程
汇编语言执行过程
机器语言执行过程
概念
编译器
封装编译程序与汇编程序的的程序
高级语言源程序
用高级语言编写的程序
编译程序
将高级语言翻译成机器语言的程序。
高级语言
便于人类理解记忆的、有一定语法结构，可翻译成机器语言的
用类似自然语言编写程序的语言。
汇编程序
将汇编源程序转化为机器语言的程序
汇编源程序
用汇编语言编写的程序
汇编语言
用符号来代替01
机器语言
计算机能识别的语言，如01
由提供计算机、软件、产品转为提供服务
机器理解人类语言、自我学习、自适应问题求解
万物、随时随地联网
速度、负载、可靠
软件工程一级学科
l软件科学与理论（Software Science & Theory）：又称软件工程理论与方法，包含软件范型、软件语言、形式化方法、软件自动生成与演化、软件建模与分析等
l软件工程技术（Software Engineering Technology）：包含软件需求工程、软件设计方法、软件体系结构、软件分析与测试、软件维护与演化、软件工程管理、软件工程支撑工具、平台与环境等
l软件服务工程（Software Service Engineering）：包含面向服务的软件体系结构、面向服务的业务过程与建模、软件服务工程方法、软件服务运行支撑等
l领域软件工程（Domain Software Engineering）：包含领域分析、领域设计、领域实现、各类行业或领域的软件应用工程等
学科是某一领域的分支。
计算机应用技术
l中文信息处理（Chinese Information Processing）
l计算机图形学（Computer Graphics）
l数字图像处理（Digital Image Processing）
l多媒体技术（Multimedia Technology）
l计算机信息系统（Computer Information Systems）与管理信息系统（MIS）
l企业计算技术，企业与行业信息化应用
l计算机辅助技术（Computer Aided Technology）与计算机集成制造（Computer Integrated Manufacturing）
计算机应用技术(续)
l计算机控制（Computer Control）
l计算机仿真（Computer Simulation）
l服务计算（Service Computing）
l生物计算(Bio-Computing)与生物信息学（BioInformatics）
l社会计算(Social Computing)
l绿色计算（Green Computing）
l智慧地球（Smarter Planet）
l新型学科交叉技术
人工智能
l机器学习(Machine Learning)与数据挖掘（Data Mining）
l知识工程(Knowledge Engineering)与专家系统（Expert Systems）
l模式识别（Pattern Recognition）与计算视觉
l自然语言处理（Natural Language Processing）与机器翻译（Machine Translation）
l智能机器人（Intelligent Robots）
l分布式人工智能（DAI）与多主体计算（Multi-Agent based Computing）
l计算智能(Computing Intelligence)与仿生物智能计算
计算机软件
l软件语言与程序设计语言（Programming Language）
l软件方法学（Software Methodology）与程序设计方法学（Programming Methodology）
l操作系统（Operation Systems）
l数据库系统(Database Systems)
l语言处理系统与编译技术(Compiler)
l中间件(Software Middleware)
l软件工程（Software Engineering）与软件体系结构（Software Architecture）
计算机网络
l计算机通信与数据通信（Data Communication）
l网络体系结构（Network Architecture）
l网络管理（Network Management）
l移动通信与计算（Mobile Communication and Computing）
l网络安全（Network Security）
l互联网(Internet)与网络互连（Internetworking）
l分布计算（Distributed Computing）、网格计算与云计算
l物联网与传感网（IoT and Sensor Network）
l计算机网络应用(Computer Network Applications)
计算机系统结构
l并行计算（Parallel Processing）与高性能计算
l高可信计算（Trusted Computing）与高可靠性计算
l嵌入计算（Embedded Computing）
l集成电路设计（IC Design）与多核计算(Multi-Core )
l分布计算（Distributed Computing）、网格计算与云计算
l计算机存储技术（Computer Storage Technology）
l计算机性能评价（Computer Performance Evaluation）
l新型计算：量子计算（Quantum Computing）、光计算（Optical Computing）、生物计算（Bio-computing）、非传统计算（数据流机、推理机、神经计算机、归约机等）
前面加计算机，下面同理。
计算机科学理论
l离散数学（Discrete Mathematics）：集合论、图论、逻辑学（数理逻辑）、代数学、计算数论、组合学、密码学等
l计算理论（Computational Theory）：算法学、计算复杂性理论、可计算性理论、自动机理论、形式语言理论等
l数值计算（Numerical Computation）：数值变换、数理统计
与随机过程、代数方程、微分方程、矩阵、计算几何等
l程序理论（Program Theory）：形式语义、类型论、开发模型、程序逻辑、混合计算模型、程序验证等
l运筹学（Operations Research）：规划论、排队论、决策
论、对策论、最优化方法、博弈论、可靠性理论等
发表高水平文章；博士学位论文, 学术文章
科学研究：大量文献阅读、项目与工程；问题发现
；问题求解；科学实验与模拟；比较与分析；创新
思想提炼。
发表文章；硕士学位论文
科学研究：项目与工程；文献阅读；问题发现与求解；实验与模拟；总结与提高。
硕士生课程学习
本科毕业设计/论文(综合实践)
较为完整的项目(需求-设计-构造-测试-应用)；
抽象--设计的训练。实现能力与表达能力。
课堂：专业课与领域课程学习(原理和知识拓展)；
(3)最新文献阅读与知识拓展
(2)数学建模、业务建模、软件建模；算法与系统
(1)综合系统的设计与实现
课堂：专业基础课程学习(原理、应用和训练)
(3)创新项目构思与表达
(2)计算思维与算法与程序构造能力实践
(1)课程实验，如数据结构实验等
课堂：基础课程学习(术语、知识和思维)
(3)阅读经典文献与原版教材
(2)计算思维训练和程序设计训练
(1)数理思维训练和外语交流能力训练
贯通的知识才叫思维
应用程序进程
操作系统的进程
为让应用程序执行的辅助性进程
作业
小粒度工作
任务
大粒度工作，一个应用程序的完整执行，由多个进程组成
进程
读入内存中的程序
存储体系中的文件
化简复杂的问题，进行复杂问题求解的重要思维
内存管理
负责内存的分配和回收
内存空间的回收
内存外存信息的自动交换
内存空间的分配
内存空间的管理
磁盘管理
管理磁盘信息的回收
几个重要的区域
数据区域
根目录区域
文件分配表区域
保留扇区
结构
扇区
512字节
磁道
盘面
原理
磁盘块
文件分配表（FAT）
文件夹（目录）找到文件开始位置
CPU管理
管理执行哪个程序
切换的状态保存
控制内存程序的切换
内存中执行程序送到PC计数器
操作系统
控制和管理计算机系统各种资源（硬件资源、软件资源和信息资源），合理组织计算机系统工作流程、提供与计算 之间接口以解释用户对计算机各种操作需求，并完成这些操作的一组程序集合，是最基本最重要的并能够执行程序的系统软件
功能
完成应用程序的执行
管理内存、外存、CPU资源
协同
合作
分工
不同性能资源的组合优化
外存：顺序存储，永久存储
磁性材料制作
速度慢，价格低
按块交换以批量换速度
存储原理：化整为零，还零为整
内存： 临时存储
管理
特性
速度快，价格高
半导体材料制作
按存储单元读取
CPU
基本思维
5，程序执行的管理与控制
硬件不同功能软件化
4，作业与进程
外存程序内存进程化
3，操作系统
管理分工协同化
2，磁盘读取
1，存储体系
资源组合利用体系化
目标：理解现代计算机的工作思维（CPU/内存/外存）
算法：解决问题的操作规则及步骤
程序/算法思想
程序与数据以同等的地位存于存储器中
机器指令：计算机可直接分析并执行的指令≈操作码与地址码
000001 取数指令 000010 存数指令 000011 加法指令 000100 乘法指令
解决了程序装载在内存便可被CPU执行
5，输出设备
4，存储器
存储容量
（存储单元的）地址
地址空间
存储单元（的内容）
存储字长
3，运算器
算术逻辑部件：算术、逻辑、移位运算
寄存器
程序的执行过程：控制台->控制器->存储器->控制器->
2，控制器
组成
时钟周期与信号发生器（主频）
时钟周期：最小的时间区隔单位
机器周期：完成一个基本操作所需要的时间。指令执行的过程分若干个阶段，每个阶段完成一项工作，这项工作称基本操作。
指令由电信号组成
信号控制器
指令寄存器（IR）存储当前指令内容
程序计数器（PC）存储下一要执行指令的地址
CPU：由控制器和计算器组成
1，输入设备
内容
6，机器级程序的执行
5，运算器与控制器
4，存储程序
3，存储器
2，机器指令与指令系统
1，机器级算法与程序
思维
执行信号化
指令存储化
程序指令化
算法程序化
浮点数
双精度
52个尾数位
11个指数位
单精度
23个尾数
8个指数位（平移）
1个符号位
定点数
全小数
全整数
6，构造集成化
5，分层构造化
4，01自动化
3，计算0和1化
进制转换
十转其它进制
小数部分：“乘基取整”
整数部分：除基取余
数位
为什么用二进制：
二进制可以用逻辑运算实现算术运算
二进制运算规则简单，易实现
两种状态的元器件容易实现
2，符号计算化
逻辑运算
异或：相同为0
非：非1即0
或：00为0
与：11为1
1，语义符号化
目的：符号组合的变化方式
关键：区分与命名--术语体系
符号，组合，命名，“本体”，“用体”
输入设备的发展（解决输入问题）
发展：穿孔-》键盘-》鼠标-》感知输入（接触与非接触输入）
存储器的发展（解决存储问题）
储取速度越来越快
可靠性越来越强
体积越来越小
容量越来越高
微处理器（核心就是计算）
主频（计算速度）
字长（计算单位）
网络化
智能化
大型化（）
微型化
如何自动执行
如何自动存取
数据/规则的表示
计算
计算规则
数据
人没有办法计算并获得结果，计算机也不行
3，可以类比解决社会/自然问题
2，在思维指导下学知识更快
1，有融会贯通、联想启发的能力
人类要具备的三大思维
计算思维
理论思维
实验思维
思维（启发）->知识（实践）->能力（贯通）
社会/自然问题--到--社会/自然问题解决
5，数据化和网络化思维
未来互联网将发展为包括物联网、社会网络、服务网络以及与现实中各种网络深度融合的网络系统
4，问题/求解思维
系统
算法
3，社会/自然与计算整合思维
2，通用计算环境演变思维（程序执行环境）
Subtopic
云计算虚拟计算环境
多CPU-多存储环境
CPU-存储体系环境
CPU-内存计算
1，计算机技术的奠基性思维
递归
程序
0和1
