Recall from lecture 22 °Flow value:f=f(s,V) Cut: Any partition (S, T)of y such that s E S andt∈T Lemma. f=f(s, T) for any cut(S, T) Corollary. f(s, T) for any cut(S, T) Residual graph: The graph G=(v, ef) with strictly positive residual capacities c u, v) c(u,)-f(2y)>0

Graphs(review) Definition. a directed graph(digraph G=(, E)is an ordered pair consisting of a set y of vertices(singular: vertex) a sete c× of edges. In an undirected graphG=(V, E), the edge set e consists of unordered pairs of vertices In either case, we have El=O(v2).Moreover if G is connected, then E2v-l, which

How fast can we sort? All the sorting algorithms we have seen so far are comparison sorts: only use comparisons to determine the relative order of elements E. g, insertion sort, merge sort, quicksort heapsort The best worst-case running time that weve seen for comparison sorting is O(nIgn) Is o(nlgn) the best we can do?

信息安全的概念 信息安全发展历程 信息安全技术体系 信息安全模型 信息安全保障技术框架

2.1 基本概念 2.2 对称密码 古典密码 分组密码 序列密码 2.3 公钥密码 体制原理 RSA算法 2.4 散列函数和消息认证码 2.5 数字签名 数字签名简介 基于公钥密码的数字签名原理 数字签名算法 2.6 密钥管理 (自学,不考核) 公钥分配对 称密码体制的密钥分配 公钥密码用于对称码体制的密钥分配 Diffie-Hellman 密钥交换

3.1 用户认证 3.1.1 基于口令的认证 3.1.2 基于智能卡的认证 3.1.3 基于生物特征的认证 3.2 认证协议 3.2.1 单向认证 3.2.2 双向认证 3.3 3.4 PKI技术 3.4.1 PKI体系结构 3.4.2 X.509数字证书 3.4.3 认证机构 3.4.4 PKIX相关协议 3.4.5 PKI信任模型

4.1 授权和访问控制策略的概念 • 基本概念，授权管理，不足之处 • 完善自主访问控制机制 4.2 自主访问控制 4.3 强制访问控制 • 基本概念，授权管理，不足之处 4.4 基于角色的访问控制 • 基本概念，授权管理，RBAC的优势 4.5 基于属性的访问控制 • ABAC模型，ABE基本概念 • PMI基础，PKI和PMI的关系 • PMI授权管理模式、体系及模型 • PMI基础设施的结构和应用模型 4.6 PMI技术

5.1 信息隐藏的概念 5.2 隐藏信息的基本方法 5.3 数字水印 5.4 数字隐写 5.5 数字指纹 •空域算法，变换域算法 •压缩域算法，NEC算法，生理模型算法 •技术模型，分类与应用 •空域水印，DCT水印 •技术模型， •典型数字图像隐写算法 •基本概念和模型 •数字指纹编码，数字指纹协议

• 基本知识 – 计算、计算模型、并行计算模型 • 图灵机概述 – 图灵的基本思想、基本图灵机、图灵机的变种 • λ演算 – λ表达式的文法、 λ演算的变换规则、Church数码 • 递归函数 – 直观意义的可计算函数、原始递归函数、递归函数

8.1 防火墙技术 • 防火墙的概念、特性、技术， • 自适应代理技术，防火墙的体系结构 • 防火墙的应用与发展 8.2 入侵检测技术 • 入侵检测概述，入侵检测系统分类 • 分布式入侵检测，入侵检测技术发展趋势 8.3 “蜜罐”技术 • 概念，分类，关键机制，部署结构 8.4 应急响应技术 • 应急响应的概念，应急响应策略 • 应急事件处理流程，应急响应技术及工具