CS导论 - 计算的限制

限制含义

  1. 界限
  2. 令人无法忍受事情(比如软件工程中的BUG)

1. 硬件限制

1.1 算数运算的限制

计算机硬件对整数和实数的表示限制:

整数

  • 计算机硬件决定了它能表示的数字的限制;
  • 超出数据会溢出;
  • 溢出问题可以通过程序克服(一系列小数通过链表表示大数);

实数

  • 精度:计算机内存单元最多可以表示的有效位数
  • 实数:符号位、指数符号位、指数位、数值位
  • 表示误差或舍入误差:算数运算结果的精度大于计算机的精度造成的算术误差
  • 下溢:计算出来的绝对值太小,计算机无法表示
  • 溢出:计算值结果太大,计算机无法表示
  • 化零误差

1.2 通信限制

策略

  • 检错码:盘点数据传输过程中是否产生了错误
  • 误差校验码:识别错误的同时,还能判断正确值是什么。

奇偶校验

  • 用于检测存储在读或者写一个字节,或者发送或接收一个字节过程中发生的错误
  • 奇校验:要求一个字节+一个校验位后,其中有奇数个1
  • 偶校验

校验数位

  • 校验每个数的和(34376=>每位之和为23)
  • 检测的错误越重要,检测算法越复杂

误差校验码

当出现故障时候,可以基于另一个副本得到正确的值; 误差校验码主要用在硬盘驱动器,做数据冗余,防止硬盘故障数据丢失;

2. 软件限制

2.1 软件复杂度

以前一个程序员解决一个问题,现在一个问题由一组程序员解决;

引入软件工程的分支;

2.2 提高软件质量方法

软件工程

  • 计算机问题求解过程:指定需求、编写规约、开发算法、实现算法、维护程序
  • 软件需求:产品功能描述
  • 软件规约:产品功能特性说明,比如功能、输入、处理、输出
  • 软件生命周期
    • 需求分析
    • 制定规约
    • 软件设计(高层、低层)
    • 软件实现
    • 维护
  • 软件走查和审计:在测试开始之前发现错误
    • 走查:小组用样本测试程序,模拟验证程序员实现需求的方法
    • 审查:由非程序开发人员,逐行读出审查的需求、设计、代码,让小组成员以发现更多的错误
  • 软件错误量衡量:指定行数的错误率
    • 标准软件:每1k行25个bug
    • 好的软件:每1k行2个bug
    • space shuttle软件:每1w行少于1个bug

臭名昭著的软件错误

  • AT&T,交换系统停9小时
  • Therac-25,射线过量
  • 91年海湾战争,飞毛腿导弹误伤,精度偏差
  • 99年火星飞船烧毁,度量转换问题
  • 62年金星探测器销毁,句号写成了逗号

3. 计算机问题

3.1 算法比较

大O分析

  • 大O符号:以函数中随着问题规模增长最快的项来表示计算时间(复杂度)的符号
  • 宠物店比喻,买大象和金鱼,忽略金鱼的价格
  • O(N): N表示问题的大小,在数据结构中,表现为结构中元素的个数
  • 把一个列表所有元素写入一个文件(打开,然后N*(读+写)),算法复杂度O(N)
  • 家庭洗衣量,函数复杂度为O(N):f(N) = c*N,c为平均每人衣服洗完耗费时间,N为家庭人数

常见的数量级

  • O(1): 有界时间/固定时间,工作量为常数,比如:给具有N个元素的数据中第i元素赋值
  • O(log2N): 对数时间,每次问题数据减少一半,比如:二分检索
  • O(N):线性时间,比如:无数列表N中,找一个数;输出N个元素的所有元素;
  • O(Nlog2N): NlogN时间,要经过N次对数算法,比如快速排序、堆排序、归并排序(快排在特定输入数据下为O(N^2))
  • O(N^2):二次时间,通常要用N次线性算法,大多数简单排序比如冒泡、选择排序时间复杂度都是O(N^2)
  • O(2^N): 指数时间,非常耗时的算法,比如国王和稻谷的故事
  • O(N!): 阶乘时间,货郎担图论算法

算法分类

  • P类算法
  • NP类算法
  • 指数算法/阶乘算法
  • 不可解决算法

P类、NP类问题

  • 多项式时间算法:复杂度能用问题大小N的多项式表示的算法;
  • P类:有所有多项式时间算法构成的类;
  • P类问题:用一个处理器能在多项式时间内解决的问题
  • NP类问题:用足够多个处理器能在多项式时间内解决的问题
  • NP类完全问题:NP类问题子集

其他

  • 图灵机
  • 停机问题:确定对于指定的输入一个程序最终是否停止的问题是不可能解决的。

4. 小结

  1. 软件、硬件,以及问题自身都对问题的解有限制
  2. 软件复杂度一定会导致错误,好的构建方式是及早关注软件质量,做好工程规划
  3. 从非常容易解决的到根本不能解决的问题种类很多
  4. 使用基于大O的分析,可以根据问题规模大小N,来决定增长速率来对比算法优劣
  5. P类问题与NP类问题,以及图灵停机问题