《计算机软件技术》选修考试提纲

《计算理论》
1)有穷自动机的形式定义p21
2)计算的形式定义p24
3)什么是正则运算p26
4)正则语言在正则运算下是封闭的。
5)NFA和DFA是等价的。
6)上下文无关文法的形式定义p61。
7)下推自动机的形式定义。
8)下推自动机和上下文无关文法是等价的。
9)图灵机的形式定义。p82。
10)图灵机的稳健性-〉多带图灵机和单带图灵机是等价的，非确定性图灵机和确定性图灵机是等价的。
11)证明：图灵机的停机问题，即Atm的不可判定性。p104
12)证明：一个语言是可判定的，当且仅当它是图灵可识别的，也是补图灵可识别的。p109

《UNIX操作系统设计》
1)索引节点的主要字段P46-P47.
2)给出文件的三级结构及块大小，计算文件的最大尺寸限制。P53。
3)铭记索引节点的作用。
4)算法:空闲算引节点的分配和释放。P60-P62.
5)算法:空闲磁盘块的分配和释放。P60-P62.
6)用户文件描述符表，文件表和索引节点表的关系图P72，使用三级表的好处是什么？
7)进程的状态转换图P114.
8)存储器管理寄存器三元组的工作机理P119-P120.
9)进程表都有那些内容。P115
10)U区都有那些内容。P116
11)进程上下文的组成。P122
12)进程上下文是怎样进行切换的。
13)处理中断算法。P125
14)系统调用算法。P127
15)如何在系统和用户地址空间之间拷贝数据。P131
16)软中断信号在什么时候检测，什么时候处理。P155。
17)fork和wait算法。p148，p165
18)sleep和wakeup算法。

用的是什么书？