架构师训练营第八周学习总结

这周的内容包括数据结构与算法还有网络与数据库。算法和数据结构我本人比较熟悉，课程的内容也不是很复杂。课上提到了NP问题，就借此机会复习以下可计算性的一些知识。

P 问题是可以在多项式时间内解决的问题

NP 问题是可以在多项式时间内验证的问题

NP 完全问题是其他所有 NP 问题都可以用多项式时间规约到的 NP 问题

NP 困难问题至少与 NP 问题一样难，NP 困难问题可能超越可判定问题，如停机问题是 NP 困难问题但是是不可判定问题

可判定问题（Decidable problem）可以理解为图灵机可以解决的问题，即经过一段时间对于任意输入给出接受或拒绝

可识别问题（Recognizable problem）可以理解为图灵机可以接受正确的输入，对于错误的输入可能不会停机

不可识别问题（Not recognizable problem）可以理解为图灵机完全拿他没办法了



算法本身的一个重要条件是有限，图灵机是所有计算机的计算模型，所以对于后两类我们可以说不存在算法解决不可判定问题。



之后讲述了一些线性表，树，图的内容。接下来介绍了一些算法，有穷举算法、递归算法、贪心算法和动态规划。其中穷举就是搜索，递归算法老师的意思其实是分治。然后是贪心和动态规划。最后介绍了遗传算法，其本质是一种随机化算法，随机化算法有一种方法去衡量时间和结果的关系，但是已经不记得了。



接下来的内容是网络的相关知识。

OSI 七层模型和 TCP/IP 四层模型



TCP 的三次握手和四次挥手



网络数据包一层一层包装，网卡收到数据包后解析链路层数据报头并交给操作系统。操作系统解析网络层数据报头，然后解析传输层数据报头根据端口交给响应的进程。进程将收得到数据部分复制到套接字。



非阻塞IO

JAVA NIO



数据库架构



数据库事务

此外老师在讲课的时候突然提到，这两节课讲的内容很多不是我学到的，而是我猜的。我觉得应该是这样的，如果我来设计就会这样设计。看似戏谑，不过老师后来也说这其实是一种学习方法，各种技术浩如烟海且迭代速度很快，如果一个一个学下去会很容易陷入迷茫，而且视野格局也会收到局限。所以根据基本原理进行推演，猜测大概的技术形态，当具体涉及时再进行适当深入学习进行验证。不过要采取这种学习方法的前提是掌握足够的基本原理，这一点要依托于完善的知识体系。当站在高处时，再看这些技术应该就会很容易发现其核心遵循了哪项基本原理。