CrashCourseComputerScience(2)-编程及操作系统

早期的编程方式

硬件编程方式的演变

1801年使用打孔卡的可编程织布机发明-->之后60年,程序员使用插线板编程-->1948年使用内存进行编程,冯诺依曼结构Store-Programmer_Computer出现-->1980年出现面板编程,使用开关进行编程

冯诺依曼结构: 拥有CU,内存,ALU,data register, instruction register, instruction address register的计算机

编程语言发展史

伪代码

1940年之前,计算机只能识别二进制,早期变成时,人脉会先使用特定英文进行编程,在按照翻译表将这些伪代码手工转化为二进制,再交给计算机去执行

助记符

1940年之后,汇编语言出现, 程序员使用助记符变成(如: LOAD_A 14),在通过汇编语言转化成二进制代码.一条汇编语言,对应一个二进制指令

编译器

1950年,高级编程语言出现,使用编译器对编程语言进行翻译,一个程序可以翻译成多条二进制指令

1959年,通用编程语言COBOL出现,一次编译到处执行.1970s出现C,1990s出现Java,Python

编程语言

简单的编程语句

1. 赋值语句

   a = a + 1 ,永远先计算 = 右边的表达式 , 计算a+1 ,然后赋值给a

2. 控制语句: 用于程序执行流程控制,如if,while

封装: 为了方便调用和理解,将常用的代码封装成函数,在执行程序或者另一个函数中调用

第三方库:别人编写的高效率的第三方函数库

算法入门

可以通过多种算法实现同一种功能,但一个好的算法,可以使用更短的代码,占用更少的内存,更快的运行速度.

排序算法

冒泡算法

0. 对于一个array=[a,b,c,d,e…z]
1. 从index 0,1开始,不断对比相邻2个数的大小,如果array[n+1]>array[n],则2个数交换.–>最终最大的数到了最后一位
2. 对集合[a,-1]再次进行步骤1的操作
3. 不断循环步骤2的操作,直至全部循环完毕 –>我们得到了排序完的集合

老生常谈的算法,只需要记住是循环套循环的算法结构

算法复杂度

输入数据大小和算法步骤的关系称为算法复杂度

如冒泡算法时间复杂度大概为O( N^2 )

没弄懂计算方法

归并排序Merge Sort

0. 对于一个array=[a,b,c,d,e…z]

1. 将长度为n的数组氛围n个数组

2. 22合并, 数组1和数组2合并,如果数组1的数据大于数组2,则新数组为[b,a],以此类推

3. 在进行22合并,先对比2个数组index=0的数据,最小的数放在新数组0的位置,较大的数和另一个数组index=1的数据对比,较大的数放在新数组1的位置,以此类推

4. 最终所有数组合并为一个排序完成的新数组,这个算法复杂度为O( NlogN )

此算法高效的地方在于,每次对比数据先对比2个数组最小的数字

图搜索Graph Search

类似于高德地图,找到最短距离的算法,图搜索中最经典的是Dijkstra算法,大概原理为

1. 每次都从花费最少得路线出发
2. 计算到后续某一节点最短的路径及花费
3. 不断循环,直至到达终点

图搜索问题示意图:

graph LR
苏州--5h-->连云港--3h-->徐州
苏州--2h-->无锡--3h-->宿迁--1h-->徐州
苏州--3h-->盐城--1h-->连云港

14数据结构

数组如何在内存中储存和查询的?

0. 如数组j = [a,b,c]在数据结构中储存Location为[1000,1001,1002]
1. 数组对象本身储存location=1000,length=3
2. 取数据j[1],则到内存1000位置处,再偏移1,在Location=1001处得到数据 b

String

1. String是一种特殊的数组,在内存中也像数组连续排列
2. 内存中最后一位是(zero),告诉计算机字符串到此结束

矩阵Matrix

即数组套数组

链表Linked List和节点Node

0. Node存储2个数据,value和pointer,而pointer指向一下个数据所在的内存位置
1. 多个node数据相连,即组成了链表
2. 链表的最后一个数据可以指向第一个数据做成循环链表,也可以指向null,告诉计算机链表结束了

链表存在意义在于,数组,String都是连续储存的,如果要对数组进行改变,则要读取数据CPU处理成新数据写入到一个新的内存地址中,效率很低.而链表只需要更改nodepointer指向的Location就能轻松解决这个问题.

队列Queue

0. 一个先进先出FIFO的特殊的链表

1. 第一个node存储第一个加入的数据,如果要删除第一个数据,直接将队列中记录的node Location改为第二个node. 称为出队dequeuing

2. 如果要在队列增加一个新Node,则需要遍历整个队列,在最后一个Node,修改pointer指向新Node. 称为入队enqueuing

栈Stack

0. 先进后出(LIFO)的链表,与Queue相反
1. 第一个node储存的是最新加入的数据,拿取第一个数据称为出栈pop
2. 如果要新增数据,直接将Stack对象中的Location记为新node,新node的pointer指向原第一个node.加入新数据称为入栈push

树Tree

0. 一个node拥有2个pointer,这样的node组成的数据结构称为树Tree
1. 最高的节点称为root node,没有子节点的node称为leaf node
2. 从根节点到叶节点是单向的

图Graph Data

0. 数据互相连接,无指向性,如图搜索中的图

15阿兰·图灵Alan Turing

0. 1902出生英国伦敦,计算机科学之父
1. 24岁时,为了解决”可判断性问题”,阿兰图灵提出了图灵机
   1. 图灵机是一种计算机模型,可以做任何计算
   2. Truing利用停机问题悖论证明了,计算不能解决所有问题
2. 二战时,Truing帮忙盟军解码德国情报
3. 1950s,Truing提出了人工智能和图灵测试

16软件工程Sofrware Engineering

0. 现代的软件所需代码量过大,软件工程解决如何高效开发高代码软件的问题
1. 面向对象编程:封装组件,隐藏复杂度
   1. 使用API控制那些函数或者数据露出
2. 使用IDE提高开发效率
3. 使用Readme文档和注释,提高代码可读性
4. 使用git等平台进行版本控制
5. 测试,就是找bug

17集成电路&摩尔定律

0. 1940-1960电脑使用分离器件,如真空管,晶体管等,使用电线连接
1. 1950s后期,Noyce所在的仙童半导体使用硅制造集成电路IC,芯片的核心就是一小块IC
2. 印刷电路板使用金属线连接组件
3. 使用光刻制造复杂的集成电路,
4. 1964年,摩尔定律提出:每2年IC集成电路密度翻一番
5. 因为光刻波长精度和量子隧穿效应,摩尔定律逐渐走向终结

18操作系统Operate System

0. 操作系统OS拥有操作硬件的特殊权限,管理其他应用和程序,OS的目的让计算机自己运行,提高人机交互效率

1. 操作系统充当软件和硬件之间的媒介,OS提供API抽象硬件:设备驱动程序

2. 批处理: 1次给计算机多个任务,让计算机按顺序自动处理

3. 多任务处理:1950s,Atlas计算机使用调度,解决外部设备存在瓶颈导致CPU的闲置问题

   1. 对于需要长时间等待的程序,Atlas会将次程序休眠,运行下一个程序
   2. 程序运行完成,Atlas将程序标记成可继续执行,执行后续程序

4. 虚拟内存: 一个应用程序所占的物理内存可能不连续分布,OS隐藏了内存复杂性,提供虚拟内存映射物理内存.

   从使用者和程序来看虚拟内存都是从0开始而且连续的,在我们对虚拟内存进行改变时,OS通过映射改变对应物理内存数据

5. 动态内存分配: 虚拟内存使得,程序使用的物理内存不连续分布不再是个问题,OS可以灵活的对程序的内存进行删减,这种机制成为动态内存分配

6. 内存保护: OS对每个程序的内存做了隔离,一个程序崩溃不会影响其他内存

7. 分时操纵系统Time_sharing:给每个用户分配一段内存和处理器

8. 1970s,Unix系统由内核和外部程序构成

   1. 内核kernel:内存管理,IO,多任务
   2. 外部程序: 执行的代码或者应用

19内存&储存介质

0. 内存一旦遭遇断电等意外,数据就会丢失,而Storage用于储存长期数据
1. 硬盘Hard Disk Drivers: 使用表面的磁性储存0/1
2. 光盘Compact Disk: 在镜面上坐上凹坑,使用光学反射储存数据
3. 固态储存Solid State Drivers: 使用集成电路储存数据

20文件系统

0. txt格式文件储存text文本,使用ASCII解码可以看到文本信息
1. 波形文件Wave file, WAV格式,存储音频文件
   1. 元数据:储存在文件最开始,储存音频文件声道,码率
   2. 使用数字代表振幅,最终形成波形交给扬声器播放
2. 位图Bitmap: bmp格式
   1. 元数据:储存图片大小分辨率等信息
   2. 1个字节代表1个三原色,3个字节代表一个颜色
3. 目录文件: 为了对文件的物理内存信息,数据信息进行管理,目录文件储存了当前文件夹中文件的元数据,大小及起始目录位置
4. 文件管理系统
   1. 为每个文件分配一个块,预留一定空间用于文件新增数据
   2. 原本的块满后,文件管理系统为文件新增数据再分配一个块,并将新快的信息储存到目录文件中
   3. 对文件进行删除,只会将目录地址中的文件信息删除,在写入新数据之前,原本的文件所在块数据依然保持不变
   4. 碎片管理: 将storage中不连续的块,复制粘贴组合在一起
5. 分层文件系统: 从根目录开始,目录文件不止指向文件还指向下一级的目录文件

21压缩Compressing

0. 使用压缩,我们可以将传输的数据转化为更小的数据,更小的数据意味着更快的传输速度

1. 游程编码run-length encoding: 通过 重复次数+ 数据的格式, 减少重复数据,可以达到无损压缩

2. 字典编程dictionary code: 通过字典生成紧凑代码,可实现无损压缩

   1. 将数据划分为不同的块
   2. 将数据的重复频率制作成频率树,通过频率进行二进制编码,越靠近Leaf node, 块映射的二进制代码越长
   3. 通过字典将数据转为映射的二进制代码, 如 YY WW YY WY可以表示为011010
   4. 如何解码?
      1. 将二进制代码按一下规则分割成不同的块
         1. 从当前位置到0,为一个块, 如0, 10
         2. 到达频率树最大长度,为一个块(如下图示例频率树最大长度为2, 则碰到11,则为一个块)
      2. 对照字典,将二进制代码转化为原有的数据

   频率树示意:

      graph
   8--0-->YY:0就代表频率最高的代码块YY
   8--1-->_--1-->WW:10代表频率最3高的代码块WW
   _--0-->WY:10代表频率最2高的代码块WY

   Dictionary Code高效的秘密?

   1. 每个块对应的二进制代码都是独一无二的,节省了标记块对应二进制长度的代码,即无代码前缀
   2. 频率越高的块对应的二进制代码越短,提高了压缩效率

3. 有损压缩

   1. 有损压缩丢掉人感知不强的信息
   2. mp3丢掉超声波等人类无法听到的声音
   3. 图片压缩,在微观用将多个颜色的颜色块用更少的颜色替代
   4. 视频压缩只储存画面变化的数据

22命令行页面Keyboard&Command line interface

通过按钮等机械设备录入设备,打印机打印结果 –> 1950年输入设备使用punch cards–>1950s后期,输入设备开始使用QWERTY键盘–> 使用电传打字机作为交互设备,打字输入,打印在纸上作为输出–>1970s开始使用屏幕作为内容输出设备,目前流行的命令行页面出现

23屏幕&2D图形显示

1. 早期的屏幕分辨率较低,只用于显示临时值,如registers

2. 最早期的屏幕显示就似乎为阴极射线管Cathode Ray Tubes(CRT),使用电子撞击磷光体图层从而产生光,使用磁场控制电子的轨迹,从而在屏幕上显示图形.

   1. 矢量扫描Vector Scanning: 引导一条电子束不断在屏幕上按着图形的轨迹撞击

      同一时间,电子束只会在屏幕上轰击一个点 比如张麻子在黄老爷的门上用枪打上问号

   2. 光栅扫描Raster Scanning:按照固定路径,一行一行,从上到下从左到右,不断重复,磁场周期性变化,而只在特定的时间打开电子束,从而产生图案

3. LCD(Liquid Crystal Displays): 使用光缆扫描,

   1. 早期电脑因为内存问题,不存01二进制,而是存符号.计算机先通过字符生成器将字符等数据转化为符号,再发送给显示器
   2. 为了绘制形状,计算机开始使用矢量图形和矢量指令,产生了动画

4. 1962年计算机辅助设计软件Computer-Aided Design(CAD)出现,使用光笔在屏幕上绘制图形

5. 1960s后期,位图显示Bitmaped Display出现: 显卡内存中的bits对应屏幕上显示的像素

24冷战和消费主义-The Cold war and Consumerism

0. 1940-1970年是电子计算机蓬勃发展的阶段,本节主要讲述这段时间的历史背景
1. 电子计算机在二战时即展示了重要的价值,1950年商业计算机 Univac出现
2. 1950s,范内瓦布什预言了维基百科,CAD等未来发展路线并帮助美国创建了国家科学基金会,用于资助对科技研究
3. 1950s,晶体管进入消费者领域,日本获得了晶体管授权,并专注于消费者市场
4. 苏联1957发出卫星,1961载人航空,同年肯尼迪提出登月计划,使用集成电路制造计算机助力了阿波罗登月计划的成功
5. 1970s,冷战结束,美国政府计算机订单缩减,美国半导体公司大量倒闭,而消费者市场已经被日本公司占领,同事微处理器出现,手持计算机,街机等小型计算机设备出现
6. 总结: 计算机早期在政府资金资助下技术逐渐成熟,在冷战结束后,又依靠消费者市场进一步发展

25个人计算机革命The Person Computer Revolution

0. 1970年代由于内存,CPU价格的降低, 使得个人计算机出现,最开始出现的microcomputer
1. 1975年Altair 8800出现并取得商业成功,使用machine code编程
2. 比尔盖茨和伙伴为了Altair编写了编译器interpreter,可以将BASIC语言转化为Altair可以识别的语言
3. 家酿计算机俱乐部的史蒂夫·乔布斯在1977年设计制造了开箱即用的Apple-2,并取得了商业成功,同样用Basic语言进行编程
4. 1980s,IBM使用了外部的处理器,系统造了自己的 PC,并取得了商业成功,使用开放式架构IBM兼容平台,用户可以自定义更换 IBM兼容的硬件.
5. 苹果为了与IBM兼容电脑竞争,努力提供软硬件体验,成为了BOM兼容电脑外唯一存活的独立企业

26图形用户界面Graphical User Interface

0. 苹果1984年发布了Macintosh,是第一台图形用户界面的电脑.而此前的个人计算机只能使用命令行
1. 1968年秋季计算机联合会议上,Engelbart演示了具有位图图像,文字图像,鼠标,多界面的系统,影响了未来计算机的发展
2. 1973年,XEROX ALTO发布,图形界面使用了桌面的概念,窗口可以互相遮挡,还有计算机等桌面组件.
   1. Alto团队使用windows,icons,menus和pointer来实现桌面的制作,这样的界面成为WIMP interface
   2. GUI界面使用多选框,button等组件
   3. Alto在创建一个应用时,会打开一个窗口,定义文字显示以及button按钮等元素,还有事件触发代码
   4. GUI使用事件驱动编程event_driver programming,用户使用鼠标点击了按钮等动作,就会触发事件代码
   5. 施乐还创造了文件剪切,复制,粘贴等概念,还有文档打印的所见即所得
3. 1983年 苹果公司受施乐的启发,建造了Macintosh,并且大卖.但由于不兼容IBM,缺乏软件,不久之后,史蒂夫被赶出苹果,微软发布了windows1.0(基于DOS),并逐渐占领了个人消费者市场

27 3D 图形 3D Graphics

0. 为了在屏幕上实现3D效果, 我们一般制作3D模型,将3D模型转化为2D展示在屏幕上

1. 3D投影: 使用投影算法将3D图形转化为2D展示在电视屏幕,投影有有以下算法

   1. 正交投影: 平行的线段,在投影中互相平行
   2. 透视投射: 平行的线段叫会在一点

2. 线框渲染: 将3D图形坐标转化成2D,然后使用线段连接

   1. 一般使用三角形作为基础头像来制作3D图像因为3个点可以定义一个平面

3. 我们得到2D投影后,还需要填充颜色

   1. 扫描线渲染 Scanline Rendering : 填充图形的经典算法. 简化来说,填充一个三角形时,会在屏幕上画无数条横线,与三角形的2条边相交的2点之间填充像素

   2. 扫描线渲染重启产生锯齿,因为他是一个像素一个像素填充的,图形边缘的像素和其他图形形成严重对比.而抗锯齿就是将图形边缘的像素填充淡一点的颜色以形成过渡

      图形和数字在屏幕的展示都利用了抗锯齿

4. 2D图形优化

   1. 图形遮挡算法
      1. 画家算法;计算机根据排序算法,先渲染远的图形,再渲染近的图形,这种算法被称为
      2. 深度缓冲Z-buffering:
         1. Z-buffering按像素记录图形远近的距离,
         2. 如果扫描到新的图形发现距离更近,则此像素点替换成更近的距离,颜色后续也会展示为新的图形的颜色
         3. 配合渲染线算法只渲染最近距离的颜色,忽略被遮挡的部分
   2. 背景剔除, 只做展示的出来的一面,不会展露的背面不做图形处理,以节省工作量
   3. 照明算法: 对3D模型进行明暗处理
   4. 纹理Texture: 对提供的图案进行取色,使3D模型形成纹理

5. GPU: 专门为图形算法建造的硬件, 配合专用的RAM装在显卡上