图论

BFS(breadth)广度优先搜索->最短路径问题

  1. 使用图来建立问题模型

  2. 使用BFS解决问题
    队列(queue):FIFO
    栈(stack):LIFO

    狄克斯特拉算法(Dijkstra’s algorithm)

  3. 找出最便宜的node

不断更新开销
对每个node都运行狄克斯特拉算法

贪婪算法

快速找到NP完全问题（没有快速算法的问题）的近似解

每步都采取最优的做法

动态规划

将一个问题分成小问题，并先着手解决这些小问题 这些子问题必须都是离散的且完整的，不依赖其他子问题，动态规划才管用

得到最优解
算法从一个网格开始，不断更新

K最近邻算法（KNN）

聚类

k-means算法

k-means算法中，随着中心点的位置不断迭代，其必将在某处收敛（数学层面上已证明）
簇的数量需要事先确定
中心点初始位置的不同会导致结果的不同
（通过随机设定初始中心点位置不断尝试k-means算法，从结果中选取最适合的聚类结果）

层次聚类算法

不需要事先设置簇的数量
一开始每个数据自称一类，每个阶段不断合并，选取最合适的阶段作为聚类结果

距离的算法

  • 最短距离法
  • 最长距离法
  • 中间距离法

如何确定相似程度？
=》特征抽取

  • 分类
  • 回归（预测结果）

距离公式和余弦相似度

简单介绍

  • 二叉查找树
  • 反向索引
  • 傅里叶变换
  • 并行算法

安全算法

在互联网交互数据，数据要经过各种各样的网络和设备。
传输数据时的四个问题：

  • 窃听
  • 假冒
  • 篡改
  • 事后否认

微信图片_20220525091955.jpg

加密后的数据称为密文
加密和解密就是通过密钥对二进制文件进行数值计算

散列表(Hash Table)

散列函数+数组
e.g.python里的字典
Hash函数：可以把给定的数据转换成固定长度的无规律数值

  1. 哈希值多用十六进制表示(在计算机内部仍然是二进制)
  2. 如果输入的数据相同, 输出的哈希值也必定相同
  3. 输出相似的数据,并不会导致输出的哈希值相似
  4. 哈希冲突:即使输入的数据不同,哈希值也可能相同
  5. 不可能从哈希值逆向运算出数据
  6. 哈希值的计算相对容易

实现哈希函数的算法有很多：MD5，SHA-1，SHA-2

密钥

  • 共享密钥加密（加密解密使用相同密钥）
    • 缺点1:不安全==>
    • 实现方法：凯撒密码，AES，DES，动态口令

==>密钥分配问题：找到把密钥安全送出的办法==>

  • ==>公开密钥加密(加密解密使用不同密钥)
    • 加密使用公开密钥,解密使用私有密钥
    • 在和多人传输数据时十分便捷
    • 缺点1:加密解密耗时
    • 实现算法:RAS算法,椭圆曲线加密算法
    • 缺点2:中间人攻击:替换密钥(无法显示自己是由谁生成的)==>
  • ==>混合加密
    • 共享密钥对数据加密
      • 公开密钥对共享密钥加密
    • 不会被中间人嘛?

密钥交换协议

消息认证码MAC(Message Authentication Code)

  • 认证
  • 检测篡改

数字签名

  • 预防事后否认
  • 数字证书

聚类