计算机操作系统知识点总结（有这一篇就够了！！！）
一、操作系统概述1.1操作系统的定义与目标定义：操作系统是控制管理计算机系统的硬软件，分配调度资源的系统软件。
目标：方便性，有效性（提高系统资源的利用率、提高系统的吞吐量），可扩充性，开放性。
1.2操作系统的基本功能统一管理计算机资源：处理器资源，IO设备资源，存储器资源，文件资源;实现了对计算机资源的抽象：IO设备管理软件提供读写接口，文件管理软件提供操作文件接;提供了用户与计算机之间的接口：GUI（图形用户界面），命令形式，系统调用形式。1.3操作系统的特征最基本的特征，互为存在条件：并发，共享；
（1）并行：指两个或多个事件可以在同一个时刻发生，多核CPU可以实现并行，一个cpu同一时刻只有一个程序在运行；
（2）并发：指两个或多个事件可以在同一个时间间隔发生，用户看起来是每个程序都在运行，实际上是每个程序都交替执行。
（3）共享性：操作系统的中资源可供多个并发的程序共同使用，这种形式称之为资源共享。
互斥共享：当资源被程序占用时，其它想使用的程序只能等待。同时访问：某种资源并发的被多个程序访问。虚拟和异步特性前提是具有并发性。
（4）虚拟性：表现为把一个物理实体转变为若干个逻辑实体。
时分复用技术：资源在时间上进行复用，不同程序并发使用，多道程序分时使用计算机的硬件资源，提高资源的利用率。空分复用技术：用来实现虚拟磁盘（物理磁盘虚拟为逻辑磁盘，电脑上的C盘、D盘等）、虚拟内存（在逻辑上扩大程序的存储容量）等，提高资源的利用率，提高编程效率。（5）异步性：在多道程序环境下，允许多个进程并发执行，但由于资源等因素的限制，使进程的执行以“停停走走”的方式运行，而且每个进程执行的情况（运行、暂停、速度、完成）也是未知的。
1.4操作系统的中断处理中断机制的作用：为了在多道批处理系统中让用户进行交互；
中断产生：
发生中断时，CPU立马切换到管态，开展管理工作；（管态又叫特权态，系统态或核心态，是操作系统管理的程序执行时，机器所处的状态。）发生中断后，当前运行的进程回暂停运行，由操作系统内核对中断进行处理；对于不同的中断信号，会进行不同的处理。中断的分类：
内中断（也叫“异常”、“例外”、“陷入”）-------信号来源：CPU内部，与当前执行指令有关；外中断（中断）----------信号来源：CPU外部，与当前执行指令无关。外中断的处理过程：
每执行完一个指令后，CPU都需要检查当前是否有外部中断信号；如果检查到外部中断信号，则需要保护被中断进程的CPU环境（如程序状态字PSW，程序计数器PC、各种通用寄存器）把他们存储在PCB（进程控制块中）；根据中断信号类型转入相应的中断处理程序；恢复原进程的CPU环境并退出中断，返回原进程继续执行。二、进程管理2.1进程管理之进程实体为什么需要进程：
进程是系统进行资源分配和调度的基本单位；进程作为程序独立运行的载体保障程序正常执行；进程的存在使得操作系统资源的利用率大幅提升。+进程控制块（PCB）：用于描述和控制进程运行的通用数据结构,记录进程当前状态和控制进程运行的全部信息，是进程存在的唯一标识。
进程（Process）与线程（Thread）：
线程：操作系统进行**运行调度的最小单位**。进程：系统进行**资源分配和调度的基本单位**。区别与联系：
一个进程可以有一个或多个线程；线程包含在进程之中，是进程中实际运行工作的单位；进程的线程共享进程资源；一个进程可以并发多个线程，每个线程执行不同的任务。2.2进程管理之五状态模型就绪状态：其它资源（进程控制块、内存、栈空间、堆空间等）都准备好、只差CPU的状态。 执行状态：进程获得CPU，其程序正在执行。 阻塞状态：进程因某种原因放弃CPU的状态，阻塞进程以队列的形式放置。 创建状态：创建进程时拥有PCB但其它资源尚未就绪。 终止状态：进程结束由系统清理或者归还PCB的状态。
2.3进程管理之进程同步生产者-消费者问题：有一群生产者进程在生产产品，并将这些产品提供给消费者进程进行消费，生产者进程和消费者进程可以并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程需要将所生产的产品放到缓冲区中（+1操作），消费者进程可以从缓冲区取走产品消费（-1操作）。
产生问题：当两者并发执行时可能出差错，导致预期的结果与真实的结果不相符：当执行生产者+1和消费者-1操作之后，缓冲区的值从10变为了11。
哲学家进餐问题：有5个哲学家，他们的生活方式是交替的思考和进餐，哲学家们共同使用一张圆桌，分别坐在5张椅子上，圆桌上有5只碗和5只筷子。平时哲学家们只进行思考，饥饿时则试图取靠近他们的左右两只筷子，只有两只筷子都被拿到的时候才能进餐，否则等待，进餐完毕后，放下左右筷子进行思考。
这会导致以下的问题，筷子就相当于临界资源：
临界资源指的是一些虽作为共享资源却又无法同时被多个线程共同访问的共享资源。当有进程在使用临界资源时，其他进程必须依据操作系统的同步机制等待占用进程释放该共享资源才可重新竞争使用共享资源。
进程同步的作用：对竞争资源在多进程间进行使用次序的协调，使得并发执行的多个进程之间可以有效使用资源和相互合作。
进程间同步的四原则：
空闲让进：资源无占用，允许使用；忙则等待：资源被占用，请求进程等待；有限等待：保证有限等待时间能够使用资源；让权等待：等待时，进程需要让出CPU。2.3.1进程同步的方法（重要）1.使用fork系统调用创建进程：使用fork系统调用无参数，fork会返回两次，分别返回子进程id和0，返回子进程id的是父进程，返回0的是子进程。
fork系统调用是用于创建进程的；fork创建的进程初始化状态与父进程一样；系统会为fork的进程分配新的资源2.共享内存：在某种程度上，多进程是共同使用物理内存的，但是由于操作系统的进程管理，进程间的内存空间是独立的，因此进程默认是不能访问进程空间之外的内存空间的。
共享存储允许不相关的进程访问同一片物理内存；共享内存是两个进程之间共享和传递数据最快的方式；共享内存未提供同步机制，需要借助其他机制管理访问；3.Unix域套接字
域套接字是一种高级的进程间通信的方法，可以用于同一机器进程间通信。
套接字（socket）：为网络通信中使用的术语。
Unix系统提供的域套接字提供了网络套接字类似的功能，如Nfinx、uWSGI等。
服务端和客户端分别使用Unix域套接字的过程：
2.3.2线程同步的方法（重要）线程同步的方法：
互斥锁：互斥锁是最简单的线程同步的方法，也称为互斥量，处于两态之一的变量：解锁和加锁，两个状态可以保证资源访问的串行。原子性：指一系列操作不可被中断的特性，要么全部执行完成，要么全部没有执行。
自旋锁：自旋锁是一种多线程同步的变量，使用自旋锁的线程会反复检查锁变量是否可用，自旋锁不会让出CPU，是一种忙等待状态，即死循环等待锁被释放，自旋锁的效率远高于互斥锁。特点：避免了进程或者线程上下文切换的开销，但是不适合在单核CPU使用。
读写锁：是一种特殊的自旋锁，允许多个读操作同时访问资源以提高读性能，但是对写操作是互斥的，即**对多读少写的操作效率提升**很显著。
条件变量：是一种相对比较复杂的线程同步方法，条件变量允许线程睡眠，直到满足某种条件，当**满足条件时，可以给该线程信号通知唤醒**。
2.3.3线程同步方法对比（重要）2.4Linux的进程管理进程的类型：
前台进程：具有终端，可以和用户交互；后台进程：没有占用终端，基本不和用户交互，优先级比前台进程低（将需要执行的命令以“&”符号结束）；守护进程：特殊的后台进程，在系统引导时启动，一直运行直到系统关闭（进程名字以“d”结尾的一般都是守护进程），如crond、sshd、httpd、mysqld…进程的标记：
进程ID：非负整数，进程的唯一标记，每个进程拥有不同的ID；进程的状态标记：R表示进程处于运行状态，S表示进程处于睡眠状态…操作Linux进程的相关命令：
ps命令：列出当前的进程，结合-aux可以打印进程的详细信息（ps-aux）；top命令：查看所有进程的状态；kill命令：给进程发送信号。三、作业管理3.1作业管理之进程调度定义：指计算机通过决策决定哪个就绪进程可以获得CPU使用权。
什么时候需要进程调度？
主动放弃：进程正常终止；运行过程中发生异常而终止；主动阻塞（如等待I/O）；被动放弃：分给进程的时间片用完；有更高优先级的进程进入就绪队列；有更紧急的事情需要处理（如I/O中断）；进程调度方式：
非抢占式调度：只能由当前运行的进程主动放弃CPU；
处理器一旦分配给某个进程，就让该进程一直使用下去；调度程序不以任何原因抢占正在被使用的处理器；调度程序不以任何原因抢占正在被使用的处理器；抢占式调度：可由操作系统剥夺当前进程的CPU使用权。
允许调度程序以一定的策略暂停当前运行的进程；保存好旧进程的上下文信息，分配处理器给新进程；进程调度的三大机制：
就绪队列的排队机制：为了提高进程调度的效率，将就绪进程按照一定的方式排成队列，以便调度程序可以最快找到就绪进程。
选择运行进程的委派机制：调度程序以一定的策略，选择就绪进程，将CPU资源分配给它。
新老进程的上下文切换机制：保存当前进程的上下文信息，装入被委派执行进程的运行上下文。
进程调度算法：
先来先服务算法：按照在就绪队列中的先后顺序执行。短进程优先调度算法：优先选择就绪队列中估计运行时间最短的进程，不利于长作业进程的执行。高优先权优先调度算法：进程附带优先权，优先选择权重高的进程，可以使得紧迫的任务优先处理。时间片轮转调度算法：按照FIFO的原则排列就绪进程，每次从队列头部取出待执行进程，分配一个时间片执行，是相对公平的调度算法，但是不能保证就是响应用户。3.2作业管理之死锁3.2.1进程死锁、饥饿、死循环的区别：死锁：两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。永远在互相等待的进程称为死锁进程。
饥饿：由于长期得不到资源导致进程无法推进；
死循环：代码逻辑BUG。
死锁的产生：竞争资源（共享资源数量不满足各进程需求）、进程调度顺序不当，当调度顺序为A->B->C->D时会产生死锁，但改为A->D->B->C则不会产生。
死锁的四个必要条件：
互斥条件：必须互斥使用资源才会产生死锁；请求保持条件：进程至少保持一个资源，又提出新的资源请求，新资源被占用，请求被阻塞，被阻塞的进程不释放自己保持的资源；不可剥夺条件：进程获得的资源在未完成使用前不能被剥夺（包括OS），只能由进程自身释放；环路等待条件：发生死锁时，必然存在进程-资源环形链,环路等待不一定造成死锁，但是死锁一定有循环等待。死锁的处理策略：
一.预防死锁的方法：破坏四个必要条件的中一个或多个。
破坏互斥条件：将临界资源改造成共享资源（Spooling池化技术）；（可行性不高，很多时候无法破坏互斥条件）破坏请求保持条件：系统规定进程运行之前，一次性申请所有需要的资源；（资源利用率低，可能导致别的线程饥饿）破坏不可剥夺条件：当一个进程请求新的资源得不到满足时，必须释放占有的资源；（实现复杂，剥夺资源可能导致部分工作失效，反复申请和释放造成额外的系统开销）破坏环路等待条件：可用资源线性排序，申请必须按照需要递增申请；（进程实际使用资源顺序和编号顺序不同，会导致资源浪费）二.银行家算法：检查当前资源剩余是否可以满足某个进程的最大需求；如果可以，就把该进程加入安全序列，等待进程允许完成，回收所有资源；重复1，2，直到当前没有线程等待资源；
三.死锁的检测和解除：死锁检测算法，资源剥夺法，撤销进程法（终止进程法），进程回退法；
四、存储管理存储管理为了确保计算机有足够的内存处理数据；确保程序可以从可用内存中获取一部分内存使用；确保程序可以归还使用后的内存以供其他程序使用。
4.1存储管理之内存分配与回收内存分配的过程：单一连续分配（已经过时）、固定分区分配、动态分区分配（根据实际需要，动态的分配内存）。 动态分区分配算法：
首次适应算法：分配内存时，从开始顺序查找适合内存区，若无合适内存区，则分配失败，每次从头部开始，使得头部地址空间不断被划分；最佳适应算法：要求空闲区链表按照容量大小排序，遍历以找到最佳适合的空闲区（会留下越来越多的内部碎片）。快速适应算法：要求有多个空闲区链表，每个空闲区链表存储一种容量的空闲区。内存回收的过程：
回收区在空闲区下方：不需要新建空闲链表节点；只需要把空闲区1的容量增大即可；回收区在空闲区上方：将回收区与空闲区合并；新的空闲区使用回收区的地址；回收区在空闲区中间方：将空闲区1、空闲区2和回收区合并；新的空闲区使用空闲区1的地址；仅仅剩余回收区：为回收区创建新的空闲节点；插入到相应的空闲区链表中去；4.2存储管理之段页式存储管理页式存储管理：将进程逻辑空间等分成若干大小的页面，相应的把物理内存空间分成与页面大小的物理块，以页面为单位把进程空间装进物理内存中分散的物理块。
页面大小应该适中，过大难以分配，过小内存碎片过多；页面大小通常是512B~8K；
现代计算机系统中，可以支持非常大的逻辑地址空间(232~264)，具有32位逻辑地址空间的分页系统，规定页面大小为4KB，则在每个进程页表中的页表项可达1M(2个20)个，如果每个页表项占用1Byte，故每个进程仅仅页表就要占用1MB的内存空间。
段式存储管理：将进程逻辑空间分成若干段（不等分），段的长度由连续逻辑的长度决定。
页式和者段式存储管理相比：
段式存储和页式存储都离散地管理了进程的逻辑空间；页是物理单位，段是逻辑单位；分页是为了合理利用空间，分段是满足用户要求页大小由硬件固定，段长度可动态变化；页表信息是一维的，段表信息是二维的；段页式存储管理：现将逻辑空间按照段式管理分成若干段，再将内存空间按照页式管理分成若干页，分页可以有效提高内存利用率，分段可以更好的满足用户需求。
4.3存储管理之虚拟内存虚拟内存概述：是操作系统内存管理的关键技术，使得多道程序运行和大程序运行成为现实，把程序使用内存划分，将部分暂时不使用的内存放置在辅存，实际是对物理内存的扩充。 局部性原理：指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。 虚拟内存的置换算法：先进先出（FIFO）、最不经常使用（LFU）、最近最少使用（LRU）
虚拟内存的特征：
多次性：无需再作业运行时一次性全部装入内存，而是允许被分成多次调入内存；对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出；虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存用来，远大于实际的容量；4.4Linux的存储管理Buddy内存管理算法：经典的内存管理算法，为解决内存外碎片的问题，算法基于计算机处理二进制的优势具有极高的效率。 Linux交换空间：交换空间（Swap）是磁盘的一个分区，Linux内存满时，会把一些内存交换至Swap空间，Swap空间是初始化系统时配置的。 Swap空间与虚拟内存的对比：
五、文件管理5.1操作系统的文件管理文件的逻辑结构：
逻辑结构的文件类型：有结构文件（文本文件，文档，媒体文件）、无结构文件（二进制文件、链接库）。顺序文件：按顺序放在存储介质中的文件，在逻辑文件当中存储效率最高，但不适合存储可变长文件。索引文件：为解决可变长文件存储而发明，需要配合索引表存储。辅存的存储空间分配：
辅存的分配方式：连续分配（读取文件容易，速度快）、链接分配（隐式链接和显式链接）、索引分配辅存的存储空间管理：空闲表、空闲链表、位示图。目录树：使得任何文件或目录都有唯一的路径。
Linux文件的基本操作：参考链接
Linux的文件系统：FAT、NTFS（对FAT进行改进）、EXT2/3/4（扩展文件系统，Linux的文件系统）
六、设备管理I/O设备的基本概念：将数据输入输出计算机的外部设备；
广义的IO设备：
按照使用特性分类：存储设备（内存、磁盘、U盘）和交互IO设备（键盘、显示器、鼠标）；按照信息交换分类：块设备（磁盘、SD卡）和字符设备（打印机、shell终端）；按照设备共享属性分类：独占设备，共享设备，虚拟设备；按照传输速率分类：低速设备，高速设备；IO设备的缓冲区：减少CPU处理IO请求的频率，提高CPU与IO设备之间的并行性。
SPOOLing技术：虚拟设备技术，把同步调用低速设备改为异步调用，在输入、输出之间增加了排队转储环节(输入井、输出井)，SPoOLing负责输入（出）井与低速设备之间的调度，逻辑上，进程直接与高速设备交互，减少了进程的等待时间。
七、实现支持异步任务的线程池线程池：线程池是存放多个线程的容器，CPU调度线程执行后不会销毁线程，将线程放回线程池重新利用。
使用线程池的原因：
线程是稀缺资源，不应该频繁创建和销毁；架构解耦，业务创建和业务处理解耦，更加优雅；线程池是使用线程的最佳实践。实现线程安全的队列Queue
队列：用于存放多个元素，是存放各种元素的“池”。实现的基本功能：获取当前队列元素数量，往队列放入元素，往队列取出元素。注意：队列可能有多个线程同时操作，因此需要保证线程安全，如下两种情况：实现基本任务对象Task实现的基本功能：任务参数，任务唯一标记（UUID），任务具体的执行逻辑
实现任务处理线程ProcessThread：任务处理线程需要不断地从任务队列里取任务执行，任务处理线程需要有一个标记，标记线程什么时候应该停止。实现的基本功能：基本属性（任务队列、标记），线程执行的逻辑（run），线程停止（stop）。
实现任务处理线程池Pool：存放多个任务处理线程，负责多个线程的启停，管理向线程池的提交任务，下发给线程去执行。实现的基本过程：基本属性，提交任务（put，batch_put），线程启停（start，join），线程池大小（size）。
实现异步任务处理AsyncTask：给任务添加一个标记，任务完成后，则标记为完成；任务完成时可直接获取任务运行结果；任务未完成时，获取任务结果，会阻塞获取线程。主要实现的两个函数：设置运行结果（set_result），获取运行结果（get_result)
人工智能 知识总结
一、机器学习 1、基本概念:机器学习是研究如何让计算机来模拟人类学习活动的一门学科。 2、学习系统的基本模型结构:
3、学习策略 学习策略分为记忆学习、归纳学习、类比学习、传授学习、演绎学习和联结学习等。 （1）记忆学习:原来结果的搜寻过程 记忆学习系统的模型结构:
（2）归纳学习中的实例学习（有监督的学习) 学习过程:
训练集:用于求解参数 测试集/验证集:验证 特殊化:由一般到特殊 泛化:由特殊到一般。
4、规则空间的偏序关系:
计算机基础知识点总结
系列文章目录文章目录系列文章目录一、计算机系统知识计算机组成进制转换数据编码校验码Flynn分类CISC与RISC流水线cache输入输出技术总线结构内存信息安全计算机性能局部性原理编译原理文法操作系统基础知识软件工程软件生存周期系统分析基础：软件测试计算机网络多媒体知识数据库E-R模型面向对象技术设计模式：标准化和软件产权基础知识参考文献一、计算机系统知识计算机组成CPU：中央处理器
内存
主板
输入、输出设备
硬盘
显卡
冯·诺依曼体系：计算机的硬件基础架构都是依赖于冯诺依曼提出的冯诺依曼体系结构。现代计算机的核心架构可以抽象为五个基础组件：运算器、控制器、存储器、输入设备和输出设备。
CPU功能：程序、操作、时间控制和数据处理。组成：运算器、控制器、寄存器组、内部总线。运算器：ALU-算术逻辑单元、AC-累加寄存器、DR-数据缓冲寄存器、PSW-状态条件寄存器。控制器：IR-指令寄存器、PC-程序计数器、AR-地址寄存器、ID-指令译码器
进制转换不同进制之间的转换有：R进制转十进制：按权展开；十进制转R进制：短除法；二进制转八、十六进制：分组快速转换
数据编码原码：负数把第一位改成1；反吗：正数的反码与原码相同，负数的反码是其绝对值按位求反；补码：正数的补码与原码相同，负数补码等于在其反码的末尾+1；移码：在数X上增加一个偏移量（实际上，将补码的符号位取反）。
校验码1.奇偶校验码（在编码中增加一个校验位来使编码中1的个数为奇数（奇校验）或者偶数（偶校验），从而使码距变为2）=>只能检验一位的错误。特点：只能检测出奇数位出错但不知道哪位出错，并且不可以纠正。
2.海明码：在数据位中之间插入k个校验位，通过扩大码距来实现检错和纠错，既可以检测数据传输过程中出现的一位数据错误的位置加以纠正。特点：可以检错和纠错.
3.循环冗余校验码：利用生成多项式为k个数据位产生r个校验位来进行编码，长度为r+k，校验码越长，校验能力越强。特点：可以检错但不能纠错。
4.结构、组织、实现、性能。结构指的是计算机系统各种应用的互联，组织指的是各种不见的动态联系和管理，实现指的是各模块设计的组装完成，性能指计算机系统的行为表现。
Flynn分类单指令流单数据流（SISD）：单控制器单处理器单指令流多数据流（SIMD）：单控制器多处理器多指令单数据流（MISD）：多控制器单处理器多指令多数据流（MIMD）：多控制器多处理器
CISC与RISCCISC-复杂指令集计算机（指令数量多，指令频率差别大，多寻址、使用微程序控制技术）RISC-精简指令集计算机（指令数量少，操作寄存器，单周期，少寻址，多通用寄存器，硬布线逻辑控制，适用于流水线）
流水线流水线：是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。流水线建立时间：一条指令执行时间。流水线周期：执行时间最长的一段。吞吐率：单位时间内流水线处理机流出的结果。对指令而言就是单位时间内处理的指令数。
cachecache替换算法：随机替换算法、先进先出算法、近期最少使用算法、优化替代算法。
输入输出技术IO设备与主机之间交换数据主要有物种方式：程序查询方式、程序中断方式（当IO系统与主机之间交换数据时，当IO系统完成了数据传输后用中断信号通知CPU，CPU保护现场并转入IO终端服务程序完成与IO系统的数据交换。）、DMA方式、通道方式、IOP输入输出处理机、DMA传送方式优先级高于中断方式。
总线结构1.数据总线（databus）：在CPU与RAM之间来回传送需要处理或是需要储存的数据。2.地址总线（addressbus）：指定在RAM之中储存的数据的地址。3.控制总线（controlbus）：将微处理器控制单元的信号，传送到周边设备。
内存静态数据区、代码区、栈区、堆区。静态数据区：全局变量和静态变量存储时放在这块区域代码区：存放函数体的二进制代码；栈区：编译器自动分配释放；堆区：一般由程序员分配释放，或OS管理。
信息安全保密性、完整性、可用性、可控性、可审查性。加密技术：对称加密技术（发送和接受数据的双方必须使用相同的、对称的密钥对明文进行加密和解密）。数据加密标准：DES，采用替换和移位的方法加密；非对称加密技术：需要两个密钥，公开和私有密钥；算法：RSA算法（公开密钥，安全性在于基于大素数分解）；PKI,公开密钥体系。认证技术：hash函数与信息摘要、数字签名、SSL协议（安全套协议）、数字时间戳技术。
计算机性能性能衡量评价：时钟频率、指令执行速度、等效指令速度法、数据处理速率。
局部性原理1.概念；程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应的，执行所访问的存储空间也局限于某个内存区域，2.时间局部性：如果程序中的某条指令一旦执行，则不久后该指令可能再次被执行。3.空间局部性：一旦程序访问了某个存储单元，则不久之后，其附近的存储单元也将被访问。程序大部分情况下处于顺序和循环或者某个模块中执行。
编译原理文法概念：以又穷的集合描述无穷的计划的工具字母表：元素的非空有穷集合，其中元素称为符号，所以也叫符号集；符号串：由字母表中的元素组成的任何有穷序列，串中的元素个数叫做符号串的长度，空符号串ε，长度为0。
符号串的运算：连接-符号串x=ab,y=cd,xy=abcd方幂-z=xn，当n=0,z=ε，当n=2,z=xx集合的闭包-∑*=∑0∪∑1∪∑2∪…∪∑n∑+为正闭包=∑1∪∑2∪…∪∑n
规则|产生式|生成式，是形如α->β的有序对，读作α定义为β，相同左部的产生式可缩写A->a|b|c|d。
文法定义的形式-四元组（Vn,Vt,P,S）:Vn为非终结符集，Vt为终结符集，P为规则集，S为识别符|开始符，至少要在一个规则中作为左部出现，Vn∩Vt=∅。直接推导=>，长度为n(n>=1)的推导+=>，长度为n(n>=0)的推导=>【+在=上面】，v=0S1,w=0011,直接推导：0S1=>0011，使用规则：S->01，γ=0，δ=1;可以说w是v的直接推导，或者w直接归约于v，由识别符号S推导出来的符号串称为文法的句型，如果该符号串仅由终结符号组成，称为句子。
G[S]称为文法，L[G]为文法的集合表示形式若L[G1]=L[G2]，则称文法G1和G2是等价的。G[S]：S->0S1，S->01G[A]：A->0R，A->01，R->A1L[S]=L[A]={0n1n|n>=1}
操作系统基础知识1.作用：通过资源管理提高计算机系统的效率，改善人机界面，向用户提供友好的工作环境。2.特点：并发性、共享性、虚拟性、不确定性。3.功能：处理机管理、文件管理、存储管理、设备管理、作业管理。4.类型：批处理、分时、实时、网络、分布式操作系统。批处理操作系统，例子：薪资系统、银行对账单等。它支持多个用户，CPU空闲时间短，通过多个作业分组位较少批处理来工作，但是批处理系统的成本很高，调试难度大。分时操作系统，例子：Unix、Multics等，它位每个作业分配一定的时间限制“量子”。完成一项工作后，将位另一项分配时间，每个作业在CPU获得相等时间。网络操作系统：例子：UNIX、LINUXNOVELLNETWARE等。它们可以在互连模型上工作，但是该模型由客户端服务器组成。与松散耦合的分布式系统不同，它是紧密耦合的系统，它的连接和网络稳定，位于不同位置的不同系统可以轻松访问服务器，完成文件共享，但是服务器和维护、更新的成本很高。分布式操作系统：例子：LOCUS；它允许使用共享通信网络在全世界范围内互连各种系统。但是所有互连的系统都是独立的，所以一个系统的故障不会影响网络中的任何其他系统，计算任务也很快，减少了仅一台计算机上的负载。实时操作系统：实时操作系统可以快速的处理输入和对应关系，很小的响应延迟也会导致故障。实时操作系统分为两类：硬实时，响应时间不得超过安全时间。软实时，时间限制不严重，但是系统仍然认为是有故障的。这些用于游戏的软件应用程序开发。
5.前趋图：有向无循环图，进程=程序+数据+PCB（进程控制块）。进程控制是由操作系统内核kernel中的原语实现。
6.信号量机制：解决进程同步与互斥工具。信号量分为公用与私用信号量。
高级通信方式：共享存储模式（共享某些数据结构存储区域实现进程之间的通信）、消息传递模式（进程之间的数据交换以消息为单位）、管道通信（管道只用于连接一个读进程和写进程，实现他们之间通信的共享文件pipe文件）。进程调度：FCFS先来先服务、时间片轮转、优先级调度、多级反馈调度。死锁：两个以上的进程因为互相都要求对方已经占用的资源导致无法运行下去的线下，产生原因时资源竞争以及进程推进顺寻非法。死锁产生条件：互斥条件、不可抢占条件、占用且申请条件、循环等待条件。处理：死锁预防、死锁避免、死锁检测、死锁接触。线程是比进程更小的能独立运行的基本单位，是处理器分配的最小单元。线程最为调度和分配的基本单位，进程作为独立分配资源的单位。存储管理：地址重定位是指将逻辑地址变换成主存物理地址的过程。静态重定位是指在程序装入内存时已经完成逻辑地址到物理地址的变换，在程序执行器件不再发生变化。动态重定位是指在程序运行期间完成逻辑地址到物理地址的变化，基地址寄存器BR。分页存储管理：将一个进程的地址空间划分为若干个大小相等的区域叫做页，将主存空间划分成与页相同大小的若干个物理块，称为块或者页框。再将进程的每一页离散的分配再主存的多个物理快中后，系统为每个进程建立了一张页面映射表，称为页表。地址变换机构的基本任务是利用表页把用户程序中的逻辑地址变换成主存中的物理地址，实际就是将用户程序中的页号变换成主存中的物理块号，再系统这设置页表寄存器，用来存放页表的始址和页表的长度。页式存储管理至少需要两次访问内存。分段式存储管理：作业地址空间被划分为若干个段，每个段多是一组完整的逻辑信息，有主程序段、子程序段、数据段和堆栈段。段面是信息的逻辑单位。二维。页面是信息的物理单位，一维。段页式系统，整个主存划分为大小相等的存储块，将程序按逻辑关系分为若干个块。每个段赋予一个段名，每个段再划分若干个页。其中段表中的内容不再是段的主存始址和段长，而是页表的始址和页表长度。虚拟存储器是为了扩大主存容量采用的一种设计方法，它的容量是由计算机的地址结构决定，实现：请求分页系统、请求分段系统、请求段页式系统。页面置换算法：最佳值换算法、先进先出算法、最近最少使用LRU、最近未使用NUR、工作集，文件存储设备管理系统：位图向量法（用向量描述磁盘），空闲块链表连接法（用链表将空闲表组织起来）。文件存储空间的管理：空闲表法、位示图、空闲块链、成组链接法。文件逻辑结构：由结构的记录式文件、无结构的流式文件。文件的物理结构：连续结构、链接结构、索引结构、多个物理块的索引表。系统再管理文件时必须的数据结构是文件存在的唯一标识，称FCP。文件的使用：目录管理命令、文件控制命令、文件存取命令。文件共享：将多个文件名与一个文件体建立链接。作业是系统位完成一个用户的计算任务所做的工作总和，提交、后背、执行、完成。作业响应时间位作业进入系统的等待时间与作业的执行时间之和。
进程的状态：三态模型：运行、就绪、等待，五态模型：静止就绪、静止阻塞、活跃就绪、活跃阻塞，临界资源：各进程采取互斥的方式，实现共享的资源称作临界资源。临界区：每个进程中访问临界资源的那段代码称为临界区，临界区中的临界资源同一事件只能由一个进程（线程）访问。互斥：互斥是进程（线程）之间的间接制约关系，当一个进程（线程）进入临界区使用临界资源。另一个进程必须等待。只有当使用临界资源的进程退出临界区后，这个进程（线程）才会解除阻塞状态。同步：同步时进程（线程）之间的直接的制约关系，相互合作的进程（线程）需要在某些确定的点协调他们的工作，当一个进程（线程）达到这些点后，除非另一个已经完成相应某些操作，否则只能等待这些操作结束。信号量：信号量semaphore的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程，值与相应资源的使用情况有关。值S>=0:表示某资源的可用数；S=0，则执行P操作的进程继续执行。若S0，则执行V操作的进程继续执行，若S
你不得不了解的人工智能基础知识
你不得不了解的人工智能基础知识1.什么是人工智能？首先我们利用传统的软件和人工智能进行比较，就容易使大家更容易理解。
(1)传统软件VS人工智能传统软件是[基于规则]的，需要人为的设定条件，并且告诉计算机符合这个条件后该做什么。
人工智能则是机器从[特定]大量数据中总结规律，归纳出某些[特定知识]，然后将这种知识应用到特定的场景中去解决实际问题。
然而，当前的人工智能知其然，但不知所以然。
也正是因为归纳逻辑，所以需要依赖大量的数据。数据越多，归纳出来的经验越具有普适性。
而我们在探寻AI的边界时，我们可以简单粗暴的把AI分成3个级别：
2.图灵测试图灵测试的提出是因为图灵在思考一个问题：机器能否思考？
并且图像相信是可以制作出会思考的机器，于是就在想第二个问题：如何判断机器能否思考？
于是就有了图灵测试。
那么什么是图灵测试呢？
让一个人坐在电脑前，跟另一边用键盘进行对话，如果这个人分不清跟自己对话的是一个人还是一个机器，那么这个对话机器就通过了图灵测试并具备人工智能。
3.什么是算法？算法简单来说，就是解决问题的手段，并且是批量化解决问题的手段。
比如你想要木头桌子，那么制造桌子的工厂就是“一套算法”。提供（输入）木头，就会得到（输出）桌子。
关于算法，有3点需要注意：
1.没有某种算法是万能的。2.算法没有高级和低级之分。3.根据不同的环境选择合适的算法很严重。4.人工智能中的算力是什么？在普通的电脑中，CPU就提供了算力帮助电脑快速运行，而在玩游戏中就需要显卡来提供算力，帮助电脑快速处理图形，。那么在人工智能中，就需要有类似的CPU和GPU的硬件来提供算力，帮助算法快速运算出结果。
在上述声什么是算法里讲过，在制造木桌的过程中，工厂的流水线就是算法。在那个例子中，工厂中的机器就像算力，机器越好越先进，制造的过程就越快
5.什么是监督学习？监督学习是机器学习中的一种训练方式/学习方式：
监督学习需要有明确的目标，很清楚自己想要什么结果。比如：按照“既定规则”来分类、预测某个具体的值…
监督学习的流程：
1.选择一个适合目标任务的数学模型2.先把一部分已知的“问题和答案(训练集)”送给机器去学习3.机器总结除了自己的“方法论”4.人类把“新的问题(测试集)”给机器，让它去解答。监督学习的2个任务：
1.回归：预测连续的、具体的数值。2.分类：对各种事物分门别类，用于离散型数据预测。6.什么是无监督学习？无监督学习是机器学习中的一种训练方式/学习方式：
下面通过跟监督学习的对比来理解无监督学习：
1.监督学习是一种目的明确的训练方式，你知道得到的是什么；而无监督学习则是没有明确目的的训练方式，你无法提前知道结果是什么。2.监督学习需要给数据打标签；而无监督学习不需要给数据打标签。3.监督学习由于目标明确，所以可以衡量效果；而无监督学习几乎无法量化效果如何无监督学习是一种机器学习的训练方式，它本质上是一个统计手段，在没有标签的数据里可以发现潜在的一些结构的一种训练方式。
无监督学习的使用场景：
1.发现异常数据：通过无监督学习，我们可以快速把行为进行分类，虽然我们不知道这些分类意味着什么，但是通过这种分类，可以快速排出正常的用户，更有针对性的对异常行为进行深入分析。2.用户细分：这个对于广告平台很有意义，我们不仅把用户按照性别、年龄、地理位置等维度进行用户细分，还可以通过用户行为对用户进行分类。常见的2类无监督学习算法：
1.聚类：简单说就是一种自动分类的方法，在监督学习中，你很清楚每一个分类是什么，但是聚类则不是，你并不清楚聚类后的几个分类每个代表什么意思。2.降维：降维看上去很像压缩。这是为了在尽可能保存相关的结构的同时降低数据的复杂度。7.如何合理划分数据集？首先先来介绍这三种数据集，训练集测试集验证集。先用一个不恰当的比喻来说明3种数据集之间的关系：
1.训练集相当于上课学知识2.验证集相当于课后的的练习题，用来纠正和强化学到的知识3.测试集相当于期末考试，用来最终评估学习效果(1)什么是训练集
训练集（TrainingDataset）是用来训练模型使用的。
(2)什么是验证集
当我们的模型训练好之后，我们并不知道他的表现如何。这个时候就可以使用验证集（ValidationDataset）来看看模型在新数据（验证集和测试集是不同的数据）上的表现如何。同时通过调整超参数，让模型处于最好的状态。
作用：
1.评估模型效果，为了调整超参数而服务2.调整超参数，使得模型在验证集上的效果最好(3)什么是测试集
当我们调好超参数后，就要开始「最终考试」了。我们通过测试集（TestDataset）来做最终的评估。
(4)如何合理的划分数据集
数据集的划分并没有明确的规定，不过可以参考3个原则：
1.对于小规模样本集（几万量级），常用的分配比例是60%训练集、20%验证集、20%测试集。2对于大规模样本集（百万级以上），只要验证集和测试集的数量足够即可，例如有100w条数据，那么留1w验证集，1w测试集即可。1000w的数据，同样留1w验证集和1w测试集。3.超参数越少，或者超参数很容易调整，那么可以减少验证集的比例，更多的分配给训练集。3种主流的交叉验证法
1.留出法（Holdoutcrossvalidation）:按照固定比例将数据集静态的划分为训练集、验证集、测试集。的方式就是留出法。2.留一法（Leaveoneoutcrossvalidation）:每次的测试集都只有一个样本，要进行m次训练和预测。这个方法用于训练的数据只比整体数据集少了一个样本，因此最接近原始样本的分布。但是训练复杂度增加了，因为模型的数量与原始数据样本数量相同。一般在数据缺乏时使用。3.K折交叉验证（k-foldcrossvalidation）静态的「留出法」对数据的划分方式比较敏感，有可能不同的划分方式得到了不同的模型。「k折交叉验证」是一种动态验证的方式，这种方式可以降低数据划分带来的影响。具体步骤如下：1.将数据集分为训练集和测试集，将测试集放在一边2.将训练集分为k份3.每次使用k份中的1份作为验证集，其他全部作为训练集。4.通过k次训练后，我们得到了k个不同的模型。5.评估k个模型的效果，从中挑选效果最好的超参数6.使用最优的超参数，然后将k份数据全部作为训练集重新训练模型，得到最终模型。8.机器学习的评估指标大全所有事情都需要评估好坏，尤其是量化的评估指标。
1.高考成绩用来评估学生的学习能力2.杠铃的重量用来评估肌肉的力量3.跑分用来评估手机的综合性能为了快速理解各项指标的计算方式，用具体的例子将分类问题进行图解，帮助大家快速理解分类中出现的各种情况。
例子：
我们有10张照片，5张男性、5张女性。如下图：
有一个判断性别的机器学习模型，当我们使用它来判断「是否为男性」时，会出现4种情况。如下图：
实际为男性，且判断为男性（正确）实际为男性，但判断为女性（错误）实际为女性，且判断为女性（正确）实际为女性，但判断为男性（错误）这4种情况构成了经典的混淆矩阵，如下图：
TP–TruePositive：实际为男性，且判断为男性（正确）
FN–FalseNegative：实际为男性，但判断为女性（错误）
TN–TrueNegative：实际为女性，且判断为女性（正确）
FP–FalsePositive：实际为女性，但判断为男性（错误）
准确率-Accuracy
预测正确的结果占总样本的百分比，公式如下：
准确率=(TP+TN)/(TP+TN+FP+FN)
虽然准确率可以判断总的正确率，但是在样本不平衡的情况下，并不能作为很好的指标来衡量结果。举个简单的例子，比如在一个总样本中，正样本占90%，负样本占10%，样本是严重不平衡的。对于这种情况，我们只需要将全部样本预测为正样本即可得到90%的高准确率，但实际上我们并没有很用心的分类，只是随便无脑一分而已。这就说明了：由于样本不平衡的问题，导致了得到的高准确率结果含有很大的水分。即如果样本不平衡，准确率就会失效。
精确率-Precision
所有被预测为正的样本中实际为正的样本的概率，公式如下：
精准率=TP/(TP+FP)
精准率和准确率看上去有些类似，但是完全不同的两个概念。精准率代表对正样本结果中的预测准确程度，而准确率则代表整体的预测准确程度，既包括正样本，也包括负样本。
召回率（查全率）-Recall
实际为正的样本中被预测为正样本的概率，其公式如下：
召回率=TP/(TP+FN)
召回率的应用场景：比如拿网贷违约率为例，相对好用户，我们更关心坏用户，不能错放过任何一个坏用户。因为如果我们过多的将坏用户当成好用户，这样后续可能发生的违约金额会远超过好用户偿还的借贷利息金额，造成严重偿失。召回率越高，代表实际坏用户被预测出来的概率越高，它的含义类似：宁可错杀一千，绝不放过一个。
F1分数
如果我们把精确率（Precision）和召回率（Recall）之间的关系用图来表达，就是下面的PR曲线：
可以发现他们俩的关系是「两难全」的关系。为了综合两者的表现，在两者之间找一个平衡点，就出现了一个F1分数。
ROC曲线
真正率（TPR）=灵敏度=TP/(TP+FN)
假正率（FPR）=1-特异度=FP/(FP+TN)
ROC（ReceiverOperatingCharacteristic）曲线，又称接受者操作特征曲线。该曲线最早应用于雷达信号检测领域，用于区分信号与噪声。后来人们将其用于评价模型的预测能力，ROC曲线是基于混淆矩阵得出的。
ROC曲线中的主要两个指标就是真正率和假正率。其中横坐标为假正率（FPR），纵坐标为真正率（TPR），下面就是一个标准的ROC曲线图。
ROC曲线的阈值问题
与前面的P-R曲线类似，ROC曲线也是通过遍历所有阈值来绘制整条曲线的。如果我们不断的遍历所有阈值，预测的正样本和负样本是在不断变化的，相应的在ROC曲线图中也会沿着曲线滑动。
如何判断ROC曲线的好坏？
改变阈值只是不断地改变预测的正负样本数，即TPR和FPR，但是曲线本身是不会变的。那么如何判断一个模型的ROC曲线是好的呢？这个还是要回归到我们的目的：FPR表示模型虚报的响应程度，而TPR表示模型预测响应的覆盖程度。我们所希望的当然是：虚报的越少越好，覆盖的越多越好。所以总结一下就是TPR越高，同时FPR越低（即ROC曲线越陡），那么模型的性能就越好。参考如下：
ROC曲线无视样本不平衡
无论红蓝色样本比例如何改变，ROC曲线都没有影响。
AUC（曲线下的面积）
为了计算ROC曲线上的点，我们可以使用不同的分类阈值多次评估逻辑回归模型，但这样做效率非常低。幸运的是，有一种基于排序的高效算法可以为我们提供此类信息，这种算法称为曲线下面积（AreaUnderCurve）。
比较有意思的是，如果我们连接对角线，它的面积正好是0.5。对角线的实际含义是：随机判断响应与不响应，正负样本覆盖率应该都是50%，表示随机效果。ROC曲线越陡越好，所以理想值就是1，一个正方形，而最差的随机判断都有0.5，所以一般AUC的值是介于0.5到1之间的。
AUC的一般判断标准
0.5–0.7：效果较低，但用于预测股票已经很不错了
0.7–0.85：效果一般
0.85–0.95：效果很好
0.95–1：效果非常好，但一般不太可能