【笔记】技术概念笔记

目录

机器学习

移动云计算

数据挖掘

形式语言与自动机

信息安全技术

机器学习

1.人工智能、机器学习、深度学习区别:

• 人工智能包含机器学习等，是一个含有多种知识的领域
• 机器学习包含深度学习，神经网络是传统机器学习的方法，可称为传统机器学习
• 深度学习是机器学习的一个子集，一般指深度神经网络，近十年兴起

2.机器学习方法

• 监督学习：有准确的输入X(即原始数据)和输出Y(即标签)
  • 分类问题：输出是离散的值{1, ….， C}
    • 二分类问题，C = 2
    • 多分类问题，C > 2
    • 如果结果没有互斥性，就是标签问题，即一个输入多个输出
  • 回归问题：通过输入X和输出Y绘出一条连续的线，这条线就是建模的结果
• 无监督学习：有输入X，没有输出Y，要自己从输入X中去找模式(特征抽取)
  • 例如给一群人的数据，然后你根据体重来进行聚类，分成几个类别
  • 数据的降维也是无监督学习：将高维信息映射到低维空间，例如三维空间信息的点映射到二维平面，可去掉无用信息增加有用信息在总信息中的比例
• 弱监督学习：有输入X，只给一小部分输出Y
• 加强学习：根据行为给予奖励或惩罚

3.监督学习回归模型例子

• 模型结果为+
• 参数为1
  

4.最简单的线性回归模型:

y(x,w) = w₀ + w₁x₁ +…..+ w_dx_d

进阶:(即使φ(x)为非线性函数，任然称该模型是线性回归模型，因为在w空间还是线性的)

y(x,w) = w₀ + w₁φ₁(x) +…..+ w_dφ_d(x)

(w₀称为偏差，它是真实值平均值与预测值加权(w)平均值的差值)

如果定义φ₀(x) = 1，则还可写成以下形式:

y(x,w) = w^Tφ(x)

5.在线性回归模型中，t_n表示真实值，w^Tφ(x_n)表示你求出来的预测值

6.为了求解参数w用最小二乘法，需要构造最大似然函数和最小误差平方和

最大似然函数：

最小误差平方和：

7.如果过拟合现象严重却又不想修改数学模型，可以考虑修改数据(多标记数据、增加训练集的数量)

8.假设函数h指的其实就是y(x)，属于约定叫法

9.SVM

• 支持向量就是位于分类边界线上的样本点
• 超平面的选择只取决于支持向量
• 松弛变量的松弛度就是允许不考虑的样本点有多少个，即视作噪声忽略

10.深度学习的参数初始化时采用的都是随机值

移动云计算

1.课程概述

• 移动计算：讨论移动设备中的计算，介绍移动网络的演进、架构、移动设备中使用的操作系统，以及移动计算的应用于面临的挑战等
• 云计算：讨论云计算的演进、架构和应用，并描述云计算的服务模式和不同部署方案
• 移动云计算：讨论移动云计算革命，包括其架构、优点和应用，针对移动云计算的各种问题进行分析并提出解决方案
• 移动云计算中的卸载问题：为解决移动设备受资源、存储空间有限等影响，需要执行卸载
• 移动云计算中的资源分配：如何快速资源分配和释放
• 移动云计算中的隐私和安全：取决于代码之外的运营商和用户的契约
• 移动云计算中的信任

2.移动网络通常采用蜂窝结构

• 每个六边形由一个基站提供服务，相邻六边形不能使用同一频率
• 不相邻六边形可以使用同一频率，好处是可以频率重用

3.移动自组织网络：每个节点都是对等节点

4.5G系统是一种基于全IP的系统，基于IP的移动应用和服务均可以通过云计算资源，云计算是一种网络按需接入可配置计算资源(例如网络、服务器、存储等)的技术，有利于用户获取其存储的数据和运行于远端云服务器上的应用

• 本质上其实与4G没区别
• 出现目的一开始是为了提供无所不在的网络接入

5.SLA服务水平协议是服务提供商与用户之间的具有法律效益的合同，不可缺少

• 条款包括对云服务质量的定义和承诺
• SLA的保障是以一系列服务水平目标SLO定义的，如果一个SLO未被实现，即SLA的承诺未能履行，可以对违反方进行违约处罚

6.微云是一种资源丰富的计算机或计算机集群

• 微云是可信的，能够高速连接到互联网上
• 用户使用云服务时，优先将任务卸载到微云，没有微云才用其他

数据挖掘

1.数据认知报告
2.数据预处理报告

1.是数据挖掘

• 哪些新闻有相同主题
• 哪些专利属于同一个技术领域
• 下载的app是否是恶意的
• 复杂搜索引擎用理解语义查找有用信息(现在的搜索引擎大多是)

2.不是数据挖掘

• 从电话目录中查电话
• 借助简单搜索引擎用keywords查找有用信息(只是字符串匹配)

3.数据、信息和知识的定义

• 数据是信息的表现形式和载体，例如温度是36度
• 信息是数据的内涵，例如今天很热是对36度数据的一个主观解读得到的信息
• 知识是对信息的归纳，是事物本质的内容

4.数据挖掘的目的是发现知识，知识要通过一定的知识模式给出

• 广义知识：是指描述类别特征的概括性知识，这类数据挖掘系统是对细节数据的所蕴含的概念特征信息的概括、泛化的过程
• 关联知识：反映一个事件和其他事件之间的依赖或关联。关联可分为简单关联(共现关联)、时序关联、因果关联、数量关联
• 类知识：刻画了一类事物，该类事物具有某种意义上的共同特征，并明显和不同类事物相区别(分类需要类标签，聚类不需要类标签)
• 预测型知识：由立式数据产生的能预测未来趋势的知识
• 特异型知识：源数据汇总含有的极端特例或明显区别于其他数据的知识描述，揭示了事物偏离常规的异常规律

5.数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程

6.数据挖掘项目流程(优先使用现有的工具)

• 业务理解阶段：业务理解报告
• 数据理解阶段：收集原始数据，生成数据理解报告
  • 原始数据收集报告：描述如何收集原始数据的报告
  • 描述数据的报告
  • 探索数据报告：简单的统计
  • 检查数据质量的报告
• 数据准备阶段
  • 数据选择：根据数据挖掘目标和数据质量选择合适的数据，例如表的选择、记录选择和属性选择
  • 数据清洁：提高选择好的数据的质量，例如去噪声，估计缺失值
  • 数据创建：在原有数据基础上生成新的属性或记录
  • 数据合并：将几个数据合并在一起
  • 数据格式化：把数据转换成适合数据挖掘处理的格式
• 建立模型阶段
• 模型评估阶段
  • 结果评估：从商业角度评估
  • 过程回顾：回顾过程，确保正确
• 部署阶段
  • 部署计划
  • 监控和维护计划
  • 最终报告

7.开源数据挖掘产品

• Weka 3.7.2(主要用)
• Mahout 0.13.0

8.tid表示数字id

9.定性属性(不能在算法中直接计算)

• 标称Nominal(比较)
  • 例如id号、邮政代码、眼睛颜色、职业等
  • 属性值常为序号、事物名称(分类依据)
  • 属性值并不具有有意义的序列，即大小不可比较，其均值、中位数没有意义
  • 众数有意义，是一种中心趋势的度量
• 二元属性Binary attribute(比较)
  • 特殊的标称属性
  • 仅有两种状态0和1，又称布尔属性
  • 分为对称的和非对称的，对称的表示两个属性值地位相同、概率相同，非对称则表示一个属性值优于另一个
• 序数Ordinal(比较、排序)
  • 例如排序值、等级
  • 属性值之间具有有意义的序列

10.定量属性(数值类型)

• 区间标度Interval(比较、排序、加减)
  • 例如日期、温度
  • 用相等的单位尺度进行度量
  • 可以比较和定量评估不同属性值之间的差，这个差是由意义的
  • 但是不能说一个度量值是另一个的多少多少倍，例如10度比5度暖两倍，因为不存在一个绝对的零刻度
• 比率标度Ratio(比较、排序、加减、乘除)
  • 例如长度、时间、数目、重量、速度、高度
  • 可以说一个度量值是另一个的多少多少倍，因为存在一个绝对零刻度

11.对属性的运算

• 比较Distinctness:=、≠
• 排序Order:<、>
• 加减Addition:+、-
• 乘除Multiplication:*、/

12.属性还可分为:

• 离散属性:属性值个数理论上是可数的、有限的，通常用整型值表示
• 连续属性:属性值是实数，属性值个数理论上是不可数的、无限的，通常用浮点变量表示

13.数据集

• 数据记录集
• 数据矩阵
  • 每个数据对象具有相同数目的数值属性，每个对象视为多维空间的一个点，每个维度表示不同的属性
  • 表示为一个m*n的矩阵，每行表示一个对象，每列表示一个属性
• 文档数据
  • 每个文档对应着一个词向量
    • 文档中出现的每个词都是向量的一个分量(维)
    • 每个分量的值可以是该次在文档中出现的次数，也可以是是否在文档中出现过
• 事物数据
  • 每个记录(事务)涉及一个项集
  • 例如客户的一次购物就是一个事务，购物中的商品种类就是一个个项(只记种类，不计数量)
• 图数据
  • 例如表示HTML Links的图
• 有序数据
  • 例如事务序列、基因序列、时空数据

14.数据的基本统计描述

• 数据集中心趋势：均值mean、中位数median、众数mode
  • 如果三个值在同一位置的话，称为对称分布
  • 众数小于均值和中位数称为正倾斜，表示数据里面有一个极大值
  • 众数小于均值和中位数称为负倾斜，表示数据里面有一个极小值
• 数据的散布：
  • 方法一：五数概括:min、Q1、M(Q2)、Q3、max
    • 极差Range，max-min
    • 分位数Quartiles，通常划分为四部分所以也叫四分位数，Q1是0.25，Q3是0.75
    • 四分位数极差Inter-quartitle range，也叫分位数之间的极差，IQR = Q3 - Q1
    • 可视化用盒图(boxplot)
      • 盒的端点在四分位上，盒体的长度为IQR
      • 中位数用盒内的线标记
      • 盒外的两条线分别延伸到最小值和最大值
      • 孤立点指的是高于或低于1.5IQR的点
        
  • 方法二：方差和标准差
    • 先算出方差，再开根号得到标准差，用标准差来衡量数据分布，因为方差单位与数据不同
  • 图形表示
    • 分位数图，x坐标是0到1，y坐标是属性值
    • 分位数-分位数图，用于比较同一个属性从一个分布到另一个分布是否有漂移，例如同一商品两个部门的售卖单价，x坐标是属性值，y坐标也是属性值，做y=x的辅助线来观察现象
    • 直方图，二维直方图可以观察两个变量是否有关系
    • 散列图，确定双数值变量是否存在联系、模式和趋势

15.读数据图角度

• 其中一个实例是不是分布位置明显和其他实例不同，重叠部分较少
• 其中一个实例的属性的上界和下界是不是具有很明显的范围

16.相异度矩阵：存储n个对象两两之间的近似程度性，表现形式是一个n*n的矩阵，这里d(i,j)是对象i和对象j之间相异性的量化表示

17.数据预处理的任务

• 数据清理：填写空缺的值，平滑噪声数据，识别并删除孤立点，解决不一致性
• 数据集成：集成多个数据文件，即实体消歧，将来自不同数据源的同一实体合并
• 数据归约：得到数据的压缩表示，它应该小得多但是可以得到和原来数据一样或相近的结果
• 数据变换：规范化和聚集，数据离散化(通过概念分成和离散化来规约数据，对数字型特别重要)(算法要求输入是离散的才需要)

18.如何处理空缺值

• 忽略元祖：直接忽略这个样本，样本数量大的时候用
• 人工填写空缺值：工作量，可行性低
• 使用全局变量填充空缺值：比如unknown或-∞等
• 使用属性的平均值填充空缺值
• 使用与给定元祖属同一类的所有样本的平均值
• 使用最有可能的值填充空缺值：使用像bayesian公式或判定书这样的基于推断的方法

19.如何处理噪声数据

• 分箱binning
  • 首先排序数据，并将他们分到等深(即每个箱的数据数目相同)的箱中
  • 然后按箱的平均值平滑、按箱中值平滑、按箱的边界平滑等
  • 图
• 回归：通过让数据适应回归函数来平滑数据
• 聚类：监测并去除孤立点

20.如何处理冗余数据

• 进行相关度分析(适用于数值类型数据)

21.数据归约方法

• 维归约：删除不相干属性或维
• 数值归约：选择另一种表示方式来实现减少数据量，比如一百个数据你用一个线性方程就能表示，然后只保存这个方程的参数就可以了
• 数据压缩：视频压缩、音频压缩、字符串压缩，方法有小波变换、主成分分析

21.全局数据仓库的特点（数据集市就是小规模的数据仓库，以部门为范围）

• 有某个主题的
• 集成的，即数据来自不同源但是汇这一起
• 非易失的
• 数据随时间不断变化的，一段时间更新一次

22.数据仓库的星型模式

• 事实表存维表的外键
• 维表存有关这一维的属性

23.切片、切块和旋转

• 切片，某一维的值选定一个固定值
• 切块，某一维的值选定一个固定范围，可以看作切片的叠加
• 旋转，改变呈现方式，例如列出每年四个季度的值，旋转后改成每个季度下列出每年的值

24.同步概化：每次概化都将全部数据概化到同一层次，例如时间属性第一次同一概到月，下一次才概化到年，不能一部分化成月一部分化成年。

25.属性概化中，应该删除的属性是有很多种不同值且值不具备意义的

26.count()的值较小也可以作为是噪声数据的依据

27.量化区分（箭头从右向左←）中统计兴趣度度量d_权计算方法：具有这种性质的群体在目标类的数量比上具有这种性质的群体在目标类和对比类上的数量

28.关联规则的挖掘：关联规则是用于发现诸多属性之间的关联程度

• 支持度A=》B，表示同时购买A和B的概率
• 置信度A=》B，表示同时购买A和B的人在购买A的人群中的占比
• 定义两个阈值：最小支持度和最小置信度
• 然后在数据里去找同时满足这两个阈值的两个属性
• 频繁项集：满足最小支持度的项集（项集是属性值名称的集合），关联规则一定是在频繁项集中产生的
• 规则类型
  • 布尔关联：买a和买b
  • 量化关联：买多少a和买多少b
• Apriori算法
  • L_k表示有k项的频繁项集，里面的项排序是有固定顺序的
  • C_k表示是L_k的候补集
  • （重点）连接：用不同的两个L_k-1做自连接得到C_k，可以连接的两个频繁项集应满足它俩只有最后一个项不同（注意这里要考虑项具有固定顺序，即ABC和ABD符合，但是ABC与ACD不符合）

形式语言与自动机

第一题

1.任给一个上下文无关文法化成greibach范式步骤
- 消除单一产生式（A->B)、ε产生式(A->)、左递归和无用符号并化简得全用终结符打头

2.构造NPDA

3.给定符合串判断是否符合文法

第二题

1.用图灵机实现函数f(x，y)=ax的平方+by  （用一元表示法，考虑其他能不能表示）或x的y次方

1.形式语言是研究自然语言和人工语言的数学工具，只研究组成规则(即语法)，不研究语义

• 将语言看做是句子的集合
• 将句子看做是字母按照一定规则组成的字符串
• 根据规则的形式区分语言类
• 大部分问题都可以转化为判定某个句子是否属于某个语言的问题

2.程序能执行，但没有返回结果，表明语法正确，语义错误，形式语言与自动机不研究语义

3.自动机研究抽象计算装置或“机器”，是为了从实例计算上升到类计算，即不仅仅只解决某个问题，而要解决某类问题

• 以状态自动机为基础，建立抽象机器模型
• 定义划分机器可计算问题和不可计算问题

4.有限状态自动机是描述很多重要硬件和软件的有用模型，只有有限个状态，使得可以用有限的资源来实现

• 字符串匹配算法的KMP
• 词法分析器
• …….

5.字母表是一个非空有穷集合，字母表中的元素称为该字母表中的符号，*和+表示重复

6.句子是字母表*上的元素，一般把<名词短语><动词短语><句号>称为句子

7.递归定义是解决无穷语言的有穷描述的最好方法

• 基本条款：用来定义该集合的最基本的元素
• 归纳条款：用来构造集合的新元素的规则
• 最小性条款：指出一个对象所定义集合中的元素的充要条件是它可以通过有限次的使用基础条款和归纳条款中所给的规定构造出来

8.用正规式表达的语言一定是正规语言，能被自动机表达的语言都是正规语言

9.表达一种语言的四要素

• 形如<名词短语>的“符号”
• 形如形式语言的“符号”
• 形如<动词短语>的“符号”
• 句子

10.文法由四元组G=(V,T,P,S)构成

• V：变量的非空有穷集合，是一个语法范畴
• T：终结符的非空有穷集合
• P：规则或产生式的非空有穷集合(一般文法只写这个)
• S：文法的开始符号

11.a->b、a->c可以简写为a->b|c

12.=>是一步推导出，上面有+表示是至少经一步推导出，上面有*表示经n步推导出

13.句型、句子和语言关系

• 推导过程出现的式子都叫句型，但只有最后一个句型才叫句子
• 所有句子构成的集合叫做该文法G定义的语言
• 一个文法对应唯一语言，但一个语言对应若干文法，对应语言相同的文法等价

14.文法其实就是自己定义的规则，规定a=b、j=1等等形式

15.ε表示为空

16.根据语言构造文法技巧

• 第一步先划模块，出现相同次数相同的放一块，例如第一个a和第一个b的系数都是n，则文法中A->要与a、b有关，例如A->abA|ε这种形式
• 根据n或m可以为0时就说明有x|ε的形式
• A、B这种大写的是非终结符，即一个A代表aA|ε等等形式，最后都要化为a、b的终结符形式
• 用穷举法，分情况讨论画分支，例题a个数为偶数、b个数为奇数，解法则视S为a偶b奇，然后设定A为a奇b奇、B为….这样的形式，分解后就能用终结符互相表示了
• 例如要求a的个数比b多两个，可以先构造出S为a比b多一个，然后SS就表示a比b多两个了

17.三种文法

• 0型文法是短语结构语法，一个块用另一个块来替换，即用一个串去替换另一个串，例如S->ACaB、CB->E、aD->aaD等等形式，它的模型是图灵机
• 1型文法是上下文有关语言，它是在0型的基础上，规定左边的个数要小于等于右边的个数，例如S->aSBC、CB->DB等等形式
• 2型文法是上下文无关语言，在1型的基础上，规定左边只能是一个中介符，例如S->Ac|Sc、A->aAb|ab
• 3型文法是正则文法，在2型的基础上，规定右边长度只能是0、1、2且最多只有一个终结符，且大小写次序要一致否则是二型，例如A->ε、A->a、A->aB

18.|是左右是同一级的，例如C->aB|bA|aa表示C->aB或C->bA或C->aa

19.如果每次都替换句型中最左边的变量，则称这种推导(或叫派生)是最左推导(或叫最左派生)，最右边同理

20.证明一个文法有二义性不难，但至今没有找到一个方法能证明文法没有二义性。

减少文法二义性措施：

• 保证左边符合最多只在右边出现一次
• 修改编译算法：例如先乘除再加减、规定else对离它最近的if起作用这些设置

21.过程中的某符号若一直推下去最终能推出终结符号串那么就是有用符号，否则就是无用符号

• 一个符号始终用不上就是无用符号
• 一个符号用了始终推不出终结符也是无用符号

22.要消除ε的产生式，即除了开始符号S里可以有ε，其他的形如A->ε、B->b|ε都要消除(其中A直接消掉，B变成B->b)

23.有穷状态自动机的状态转换图

• 进入箭头指向的圈表示开始状态
• a、b、ε这些要画在线条上
• 双圈表示终止状态，终止状态能终止，但不表示到终止状态就一定终止

24.有穷状态自动机定义为一个五元组M = (Q,Σ,δ,q₀,F)

• Q是所有状态的集合
• Σ是输入字母表，输入的字符串都是上面的字符
• δ是状态转移函数，表示为某状态q经过Σ变成另一个q
• q₀是开始状态(可以不唯一)
• F是终止状态的集合

25.正则语言化成DFA(确定的有穷自动机)

• ε用开始状态和终止状态是同一个来表示
• *重复用自己指向自己来表示

26.DFA后继一定要为1(边上不能有ε)，NFA后继可以不为1

27.NFA区别：

• NFA的状态可以进入若干个状态（即一个状态可以有两个自循环），DFA的状态只能进入下一个状态（即一个状态最多只能有一个自循环）
• NFA允许不需要输入符号的状态转移，即由某状态直接进入另一个状态而不产生终结符

28.非终结符在终结符左边是左线性文法，否则是右线性

29.正规式改为NFA要点

• 乘改为状态一到状态二
• 或改成状态一两条路径指向状态二
• *改为自循环

30.正规语言是两个式子之间没有关联，即互不影响

31.正规语言的三个条件

• 是正规集
• 能被DFA和NFA接受（即能画自动机表示）
• 由正规文法产生

32.若R1，R2是正规语言，则以下也是正规语言

• R1|R2
• R1与R2的交集
• R1R2
• R1*
• R1的补集

33.图灵机的带可以左移也可以右移，但是一种状态只能转移到另一种状态（因为它是确定的自动机）

• 不要求扫描完，只要能到终态就说明符合
• 做重复劳动状态不变

一、文法和语言

1.名词解释

• Σ是字母表，字母表里的元素称为符号，例如00110倍称作是字母表Σ={0,1}上的符号串
  • Σ⁰ = {ε}
  • 若Σ1={a},Σ2={b}，Σ1 ∪ Σ2={ε,a,b,ab,ba}
  • 闭包Σ* = {ε,a,b,c,ab,ba,ca…….} = Σ⁰∪Σ¹∪Σ² …∪Σⁿ
  • 正闭包Σ⁺ = {a,b,c,ab,ba,ca…….} = Σ¹∪Σ² …∪Σⁿ
• ε是空符号串
• =>*是多步(可以是0步)，=>+是至少有一步

2.文法包括以下四部分，其中终结符和非终结符的并集称作是文法的字母表Σ

• 非终结符集合{A,B,C}
• 终结符集合{a,b,c}
• 规则{A->a}
• 识别符<S>

3.推导和归约

• 设有v=0S1、w=0011若经过某个规则(例如S->01)，v可以一步得到w，则称v直接推导出w，w直接归约到v，写作v=>w
• 若不是一步的话，则称v推导出w，w归约到v，写作v=>^*w

4.句型和句子

• 若符号串x是由识别符S推导出来的，则推导过程出现的式子都叫句型
• 若x中只有终结符，则称x是文法的句子
• 即过程出现的都是句型，只有最后结果才是句子

5.文法的类型

• 0型文法是短语结构语法，一个块用另一个块来替换，即用一个串去替换另一个串，例如S->ACaB、CB->E、aD->aaD等等形式，它的模型是图灵机
• 1型文法是上下文有关的，它是在0型的基础上，规定左边的个数要小于等于右边的个数，例如S->aSBC、CB->DB等等形式
• 2型文法是上下文无关的，在1型的基础上，规定左边只能是一个非终结符符，例如S->Ac|Sc、A->aAb|ab(重要，文法无特殊说明默认就是指上下文无关文法)
• 3型文法也叫正则文法，在2型的基础上，规定右边长度只能是0、1、2且最多只有一个非终结符，且大小写次序要一致否则是二型，例如A->ε、A->a、A->aB(重要)

6.句型xx的推导树(又称语法树、语法分析树、分析树)意味着：该推导树的叶子节点从左往右读正好是xx

• 一个句型的推导树可能不唯一，不唯一的说明这个文法是二义的

7.推导时

• 若每次都是对最左的非终结符进行替换称为左推导(左句型)
• 若每次都是对最右的非终结符进行替换称为右推导(又叫规范推导、规范句型，右句型)

8.自上而下与自下而上

• 自上而下，从识别符开始，反复使用各种产生式，寻找匹配输入符号串的推导
• 自下而上，从输入符号串开始，逐步进行归约，直到归约到文法的开始符号

9.句柄和短语

• 若有一个句型为abc，如果有S=>*aAc和A=>+b，即存在一个符合文法的符号串aAc且A可以推导出b，则称b是句型abc相对于A的短语
• 若A可以直接推导出b，则称b是句型abc相对于A的直接短语，一个右句型的直接短语称作该句型的句柄

二、词法分析

1.正规式又称正规表达式

2.正规式的运算顺序

• 闭包*(闭包可以是0次)
• 连接.(一般可省略不写)
• 或|

3.一个正规语言可以由一个正规文法定义，也可以由一个正规式定义，正规式和正规文法可以相互转换

• 正规文法就是包含以下内容的描述
  • 非终结符集合{A,B,C}
  • 终结符集合{a,b,c}
  • 规则{A->a}
  • 识别符<S>
• 正规式就是一个只由小写字母和运算符组成的式子

4.常用的正规式转文法技巧

• A -> xy 转成 A->xB、B->y
• A -> x|y 转成 A->x、A->y
• A -> x*y 转成 A->xB、A->y、B->xB、B->y

5.一个案例

• 已知
  • S->aA
  • S->a
  • A->aA
  • A->dA
  • A->a
  • A->d
• 解法
  • 先把左边相同的全合在一起化成S=aA|a、A = aA|dA|a|d //这个和A=(aA|dA)|(a|d)是一样的
  • 然后再对A进行化简得A=(a|d)A|(a|d)
  • 然后进一步化简得A=(a|d)*(a|d)
  • 带入S得S=a(a|d)*(a|d)|a
  • 最终化简得答案S=a(a|d)*

信息安全技术

课堂报告报告一些具体的算法、应用实例

1.网络安全是指网络系统的硬件、软件和数据收到保护，不因偶然或恶意的原因遭到破坏，系统连续可靠地运行

• 网络空间：通过全球互联网和计算机系统进行通信、控制和信息共享的动态虚拟空间

2.恶意软件检测方法

• 特征码检测技术，专业人员获取病毒样本文件，从中提取特征码，然后扫毒引擎就根据特征码识别出哪个文件是病毒，准确率高、可靠，缺点是特征码提取难度大，无法识别变种的恶意软件
• 动态仿真跟踪技术，创建一个虚拟化的运行环境来检测
• 校验和，创建新文件时保存校验和，使用文件时与先前的校验和进行比较，方法简单，准确不高
• 启发式检测技术，是对特征码技术形成补充，比较依赖专家经验，有一定误报可能

3.截获键盘输入：用钩子函数(hook)，钩住按键的进程，就能同步获得按键的信息了

4.恶意软件特征提取技术

• 文件字符串信息：通过反编译PE文件，从文件头开始读取文件连续的字符
• 文件资源信息
• 文件指令信息

5.N-gram核心思想:第N个词的出现只与前面的N-1个词有关

6.入侵检测的分析方法

• 误用检测：又称特征检测，利用已知的网络入侵特征库识别，和恶意软件提取特征码原理一样，相当于黑名单
• 异常检测：搜集正常活动的规律，将待检测的活动与正常活动规律比较，相当于白名单

7.入侵检测系统IDS根据输入数据源不同分为

• 基于主机的入侵检测系统：分析来自主机的事件日志、应用程序的事件日志、系统调用等，保护所在的主机系统
• 基于网络的入侵检测系统：分析来自网络上传输的原始流量，保护其所处网段的计算机网络，现在通常与防火墙结合在一起，结合协议和请求分析
• 混合入侵检测系统：分析来自网络流量和主机的日志的信息，性能最好，难度成本也最高

8.数据挖掘在入侵检测中的应用

• 基于分类的入侵检测：两分类问题，数据分为正常活动和入侵检测来训练机器学习模型，再用模型来预测
• 基于关联分析的入侵检测：先分类然后进行关联分析，根据入侵事件属性的关联性
• 基于聚类的入侵检测
  • 首先提取网络数据的关键特征信息，并对属性标准化
  • 采用聚类算法，分成若干簇
  • 对分出的簇进行标类操作，按照一定原理将不同簇分成正常活动或入侵行为
  • 将待检测数据与分出的簇进行距离计算，判断是哪个簇，然后根据该簇是什么分类来判断是否时入侵行为