计算机技术杂谈

大数据与云计算

大数据不是数据存储技术，而是和海量数据相关的抽取、集成、管理、分析、解释方法，是一个庞大的框架系统。宏观上讲，对数据进行映射和提炼，发现其数据特征并加以利用。从技术上说，是通过获取、存储、分析，从大容量数据里挖掘价值的技术架构。

大数据的量级在 PB(1024TB)或者EB级，其关键特点有 Volume(量)、Variety、**Velocity(时效性短)**、Value(价值密度低)

云计算：这种基于互联网的计算方式，可以更好的对软硬计算资源进行整合，在我看来，这个概念有些类似操作系统中提供虚拟化资源的概念，相当于是面向互联网计算的虚拟计算环境，使用户能够方便、有效地共享和利用网络上的资源

前端 & 后端

• 广义上说，任何和UI直接相关的工作，都属于前端，狭义上讲，前端就是网页端
• 后端 是具体实现功能的地方，并且负责关键的 状态维护 和 控制权限，这些控制机制不能被放在前端

JavaScript，CSS与HTML的关系

• HTML定义页面结构和核心内容，CSS则为这些内容加上样式，JS则可以同时做到这两件事。
  • 抽象的说，html是骨，负责将信息结构化，CSS则是肉，负责添加装饰性内容
  • CSS可以更简单的完成一些html完成很麻烦的工作，比如将所有的标题居中。
• JS可以完成html和css的工作，但复杂一些，其主要功能是 指导浏览器如何动态建立结构和作用样式，也就是负责控制逻辑

SSL & SSH

在原本的HTTP协议中，内容是明文形式传输，而HTTPS => SSL/TLS(Secure Sockets Layer / Transport Layer Security) 协议，默认为443端口，本身可以看作是传输层的附加层。有三个好处

• 加密。防窃听
• 校验。防篡改
• 证书。防冒充

其基本思路在于 **使用公钥加密加密会话密钥**，注意：会话密钥本身是对称加密的密钥，实际上https客户端和服务器的通信是使用对称加密的，这样更快。

SSL和SSH Secure Shell

两者间建立一条加密通道，将数据加密并且压缩传输。 SSL并非协议，而SSH则是建立在SSL基础上的协议。 SSH可以代替telnet 和 ftp

成为后端工程师

语言： Java(Spring)、Golang、C++， 和语言对应的Web框架

• 计算机网络 TCP/IP详解「卷一」，HTTP相关
• 算法导论
• OS OS黑皮
• 数据库
  • MySQL， 高性能MySQL 面之前要看前半段
  • 非关系数据库 redis
• linux 鸟叔私房菜，30天入门linux

Web项目： 开源项目

AI

深度学习是基于 DBN(Brief) 深度置信网络来设计的，
DeepLearning 和 神经网络的关系， 深度学习 ≈ 神经网络， 算是传统神经网络的升级版本，**深度学习的特征是自己提取的， 而不是人工提取的**

DL 学习能力更强，也能解决更复杂的问题，但是需要更大量的数据和更高的硬件要求，容易出现偏见的情况。
DL的应用：计算机视觉、NLP

4个典型的DL算法

CNN，RNN(循环) ， GANS(生成对抗网络)， RL

后续会专门介绍CNN， 这里简要介绍一下RNN、GANS和RL

• RNN 用来处理 序列数据 如文章、语音、股票，一般就用来翻译、语音识别等等。
• GANS
• RL 其实RL和监督/无监督学习的区别就在于，它不需要数据喂养，而是自己尝试, 注意强化学习是一种深度学习算法

CNN convolution neutral network

CNN是受到人类视觉神经系统启发。 实际应用在图片分类、检索，目标分割、人脸识别等等。 说白了，==主要就是处理图像用的==，其关键就在于可以对图像进行降维(1000 pix -> 200 pix 其实不会影响识别)

典型CNN由 **卷积层、池化层、全连接层**来组成

• 卷积层 负责提取图像特征
• 池化层 降维 防止过拟合现象
• 全连接层 输出结果

卷积层干了啥：

• ==卷积是什么：将一个函数翻转，然后 滑动叠加 (求积分、加权求和)==
• 可以有很多个卷积核，每个代表了一种图像模式，用卷积核去遍历图像，某个图像块如果和这个卷积核卷积出的值大, 就认为这个图像块比较类似此卷积核。 通过这个方法提取出整个小区域的特征。注意边界需要进行padding，填充一下
• 卷积层的输出是一张特征图, 需要通过全连接转化成特征向量.

池化层(简单来说就是 下采样，降低数据维度)

• Convolved feature => Pooled feature ， 其实卷积也是降低数据维度，但是池化的降低非常有效，并且可以有效的避免过拟合

全连接层

• 首先要注意的是，典型的CNN并不一定是，3层结构，而是多层结构

• 全连接本质上 是一个classification, 在FCN中, 就用1x1的卷积代替了全连接的功能(先把特征图平铺, 然后用1x1卷积核遍历)

• NLP 是什么，我的理解是， 让计算机可以理解文字的意义，并做出回答。实际上，人类的语言比较随便，不确定性很大，像单词边界界定、单词的多义、句法的模糊性、不正确的输入，都是NLP需要解决的问题。
• 贝叶斯分类： 一种分类算法，以贝叶斯定理为基础， 朴素贝叶斯又是里面最基础的？
• SVM 支持向量机 完成分类
• 什么是梯度下降
  • 寻找极小值的方法，沿着梯度反方向迭代搜索
• 什么是反向传播
  • 对所有权重计算损失函数的梯度

其他

区块链:

• 分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的 新型应用模式，狭义来讲，区块链是一种按照时间顺序将数据区块以顺序相连 的方式组合成的一种链式数据结构， 并以密码学方式保证的不可篡改和不可伪造的分布式账本

P问题、NP问题、NP难、NP完全问题

• P => Polynomial 可以在多项式时间内解决的问题(计算机在有限时间可以解决)
• NP => nonderministic polynomial 可以在多项式时间内验证的问题 ，但不能确定是否能在多项式时间内解决(典型：是否存在哈密顿回路)
• NP难， 未必可以在多项式时间内验证解的正确性，比如每个广播站有个圆形范围，我们要用最少的广播站覆盖全美，我们无法在有限时间里验证答案的正确性.
• NPC => NP complete， NP里面难解的问题，如果NPC有解，那么说明P = NP(因为NPC问题可以转化成NP问题)

计算机安全学

• 古典密码基本模块：Substitution 代换、置换 permutation
• 对称和公钥的区别：公钥匙俩密钥，其实对称加密，对密钥的使用、加密解密算法都可以不同
• AES在做什么： 是一种分组密码 基本上思想是 扩散和混淆
  • 分组长度128， 密钥 128 等三种，N轮加密，10、12、14 由密钥决定
  • 128位例 输入的密钥被扩展成44个数组，每一轮用4个作为轮密钥
  • 每一轮进行4个操作，(加解密时最后一轮少一个) 字节代换(查表SBOX)，行移位、列混淆然后轮密钥加(分组和扩展密钥中的4行进行按位XOR)
• RSA 公钥加密，私钥解密
  • 找两个大素数、 n = p*q， phi(n) = (p-1)*(q-1)
  • 选一个和phi(n)互素的e， d 是 e 在 phi(n)下的 的逆元
  • 可以公开e 和 n， 但必须保密 p和q以及d
  • P^e^ = C (mod n), C^d^ = P (mod n)
• 数字签名： 私钥只有你能掌握，你用私钥加密报文就可以了
• 密码学的HASH： 完整性认证(防篡改、数字签名、生成随机数 就记这么几个)
  • HASH函数： 分块、填充、迭代压缩
  • 报文认证码 可以用hash实现，也可以不用 懂了吧
• 什么是XSS攻击，在动态网页里植入恶意链接
• SQL注入： 将恶意的SQL查询/添加语句插入到输入参数里，然后进行解释执行

计组

• DRAM 主存， SRAM Cache
• 哈夫曼树原理， 指令拓展(一地址 二地址 三地址) 和 计网里IP地址分配， 都有一定的哈夫曼树思想
• CPU里包含： ALU、PC、IR、寄存器组，CU(ID), 一般MAR和MDR也集成在CPU中

数据结构

• Tree

  • BST 注意中序有序的性质， AVL 最小不平衡子树的概念 是BST的特殊形式

  • RBT 如果问到这个 建议是展开聊一下 unordered_map和map(RBT 因为需要有序)的不同实现

  • Huffman Tree 给叶子的权值，想要建一颗WPL最小的树

    • 每次在优先队列里挑出俩最小的合并

  • 字典树 Tire ，利用 共同前缀设计的，一路走下去就是一个字符串，可以快速查找和插入

  • 线段树 ，用来维护区间信息

• 查找

  • B树 用在磁盘，BST的进化，其插入和删除都比较复杂
  • B+ 用在关系型数据库，叶子连着，中无信息，可以顺序查找，启动磁盘的次数更少！
  • 散列： 我感觉散列的核心就是： hash函数、冲突处理、物理结构

• 图算法， 我们看待图问题，应该从图算法需要解决的问题来考虑

  • 十字链表 邻接多重表，图算法的复杂度和存储结构的关系很大
  • 统计连通分量： BFS、 并查集
  • 最小生成树： Prim(点优先) Kruskal 边优先
  • 最短路径：BFS(无权图)、Dij(带权, 贪心思想)、Floyd(动态规划)
    • Diji final, dist, path, 三个数组, 在dist里找最小，更新final，找相连 再更新dist
  • 拓扑排序：找到做事的先后顺序，使用优先队列，可以完成特殊的拓扑排序(可以stack)
    • DFS在退栈时输出，可以直接完成逆拓扑排序 毕竟是统计出度的
  • 关键路径 我不管了
  • 并查集：判环(拓扑排序)、求联通分量 、kruskal算法利用了USF

• 排序

  • 冒、选、插、堆、归、快速、希尔、桶排序、基数排序
    • 希尔：按照间隔进行插入排序
    • 快排：什么时候最快，什么时候最慢，如果你的基准元素选第一个元素，那么已经有序是最慢的。 两个指针轮流走(其中一个指针指的是空的)，走到不符合的地方，把自己的元素拿过去，然后另一个走，两指针相遇算结束，两指针相遇的地方就是**枢轴**元素正确的位置，然后对两边递归的再次快排。
    • 归并排序：有的时候想给磁盘里的东西排序，但是内存不够大，于是通过归并来完成
    • 桶排序就是 利用某种规则，比如/10， 把元素们分别放到若干个桶里，然后每个桶内部再排
    • Radix Sort 是特例，设置10个桶，从个位开始，放入，收集，放入收集。和桶排序都一样是空间换时间，不是基于比较的排序, 不受到nlogn的下限影响

算法

• 动态规划

  • LCS 子串必须连续，子序列则是去掉几个元素后形成的序列

    LCS作为典型的动态规划问题，二维动态规划， 可以画表来解决，

• 贪心和动态规划如何选？

  • 两个人其实都是求最优解，而且都是划成小问题吧，贪心的小问题 没有后效性(换句话说就是每个小问题的结果对后面的问题没有影响)

• 分治 Divide and Conquer

  • 树的算法 其实经常就是分治法(一个大问题 分成好几个问题)， 值得注意的是， 斐波那契数列是有分治思想的

• 是否存在一条合理的路径， 是否存在一个合理的解， 深度优先搜索

• 回溯算法的思想：一条路走到黑，走不通就退回来，典型问题 八皇后，我觉得回溯的效率是比较低的，不喜欢使用

操作系统

• 大内核和小内核： 大内核复杂但效率高，小内核方便维护但需频繁切换目态和管态

• ==操作系统做什么： 管理资源，向上层提供接口，扩充机器，保护系统？，直接去利用硬件资源是困难的==

• 一个C++ 文件如何运行： 编译 -> 链接 -> 装入 -> 运行

• 是不是连续分配(有无分页？)，有没有虚拟化？ 只要不是按需分配 就一定会存在内部碎片！

• 逻辑地址A 我们要知道逻辑地址和物理地址 是解读方式不一样

  • 页号 + 页内偏移量 这个页号拿去跟TLB比一下，不行就拿去跟页表比一下

• 内存管理时 ==stack用来函数调用， 堆则用来存动态分配的变量==

• 死锁： 满足4个条件，互斥、不可剥夺、请求和保持、循环等待

  • 预防死锁(破坏这4个条件)，避免死锁(银行家)，检测死锁 要提到并发度的影响

• 锁(只用来实现互斥)与条件变量(只用来实现同步 因为没有值 就是等待队列) 讲一下和信号量的

  • 为什么有锁呢，因为有些资源必须要互斥访问，进入临界区时获得锁，出去时释放锁
  • 自旋锁 就是说 忙等，在多核系统上好使

计网

• SDN是什么
  • 软件来控制整个网络，包括路由器的转发表和路由表，在传统网络里这都是需要路由器自己计算的
• 数据链路是什么 点对点信道
• IP A 10开始 B 172. C. 192. ,
  • ARP： 发广播回单波，不知道人家的MAC地址， RARP是不知道自己的IP地址
• TCP
  • 为什么三次握手：两次 服务器不知道自己接受连接的消息有没有送到客户端，会浪费资源。 第三次握手 可以传数据，但是一般不传
  • 为什么四次挥手： CSSC的顺序，等待2MSL是看服务器是否还有消息(信道)
• 应用层
  • FTP： 两条连接，是C/S模式，只有两种格式
  • 发SMTP 收 POP3，IMAP，HTTP
  • HTTP： 传输层是TCP，但HTTP本身不依赖连接。 浏览器向Web服务器发HTTP请求报文(在这之前先要向域名解析服务器要到IP)，Web服务器发送HTTP响应，然后释放TCP连接。 短连接、无状态是描述HTTP最好的方式，但在HTTP1.1 之后支持KEEP ALIVE

科普

• UTF-8 是什么：可变长的Unicode编码，因为正常的Unicode要2个字节，用哈夫曼编码的思想改组一下。 注意，ASCII编码可以看作是Unicode(UTF-8)编码的一部分。
  • UTF-8是存储和传输时的编码，在运行时是Unicode编码！！