第三周学习总结 21-03-15【太困】

1 算法设计与分析

本周讲了两部分内容，动态规划（DP）后部分，以及网络流前部分。

动态规划

RNA序列内部最大匹配问题

给一个RNA序列——由A、U、G、T组成的串，对任意两项配对成功则连条线，求“不存在交叉线”下的最大配对可能数。

如果令OPT(i)表示前i个串下，符合题意的最大配对数是OPT(i)，是行不通的——没办法联系出“子串”间的关系。

应为OPT(i,j)表示从i到j的子串，符合题意的最大配对数是OPT(i,j)。分类讨论可写出递推公式。

双RNA序列最大匹配问题

俩RNA序列，不固定起点终点，最大匹配个数。

令OPT(i,j)表示，（与上面不同）串1的前i项与串2的前j项的最大配对数。分类讨论可写出递推公式。

引出空间复杂度优化问题——利用递推式的刷新过程是逐行的，直接把二维的DP矩阵用一维代替，迭代刷新节省空间。缺陷就是，没法保存路径了。

如何在上述情况下保存路径——正向DP加上反向DP，结合最短路算法，就能在节省空间复杂度的情况下保存路径了。

DP在最短路算法上的应用：检测负环——Bellman-Ford算法。

如果图里有负环，所有边加上一个正数跑Dijkstra行不行（Dijkstra只能跑无负环图）？答案：不行。实际上所有边加上正数会完全改变图的意义，最短路跑出来会变的。

学习一波Bellman-Ford算法——我的理解是利用所有邻接边进行松弛，如果能够松弛，那这条边下次再次尝试松弛；如果不能松弛，说明此边没有利用价值，下次不再松弛了。——我以前是没意识到Bellman-Ford是和DP有关的。

由最短路算法引入到实际应用中：

计算机网络中的RIP算法（用的是全局Dijkstra思想，会有信息滞后性继而出现错误）和OSPF算法（用的是Bellman-Ford思想）。

如何应用Bellman-Ford检测图中负环：

增加一个节点t，这个点和所有原来的结点作一条0权值的边。然后以t为起点跑Bellman-Ford，如果跑了第n-1轮不是最优解，第n轮还有更短的路径，那妥妥的是有负环了。证明略，过两天再复习…(￣▽￣)"

网络流

讲了基于增广路的最大流问题算法思想。又讲了其证明【太快未理解】；讲了最大流最小割之间的关系与证明。【太快未理解】

课程感受： 老师上课思路很清晰很快，可惜我吸收的没那么快，自行复习吧。好在本科都学过使用，但是没学过证明，理解不够深入。

2 计算机体系结构Ⅲ之HPC

本周课程讲了两个内容：Commodity Cluster与modity Cluster.介绍组成(compute node & SAN)、特点(工业化的接口、工业标准软件、采用很多中间件、高带宽要求)、优点（性价比高、配置方便）等信息。Benchmark.介绍了性能评判标准（10%的性能提升是没有意义的，40-50%的性能提升才叫“提升”）、指标（FLOPS,TepS,GupS等）、类型（Sythetic以及Application）等概念。本周作业是一份1995年的Paper Reading的Report： 《BEOWULF: A PARALLEL WORKSTATION FOR SCIENTIFIC COMPUTATION 》，1995年的作者用市场化的芯片组成了自己的一个多PC的工作站，并分析其网络与I/O性能，优点是不需要进行任何VLSI的芯片定制。

3 数字VLSI设计课程设计

本周课程依然围绕Verilog的部分语法、Coding Style的一些注意事项等内容（课程是罗列了一打Coding Style内容以及Verilog中出现的各种case内容，制成课件进行说明）。

4 研究生论文写作

本周课程内容围绕伦理道德展开（什么是有违伦理，例如基因编辑等等）。对共同作者罗列的条件、学术生活中的压力与平衡等进行了阐述与介绍。课程以老师讲故事的形式进行话疗，所以呢比较慢节奏。

5 综合英语

本周课程是罗列自己的情商参数，并想出适合自己的岗位，用英语描述未来的美好生活(￣▽￣)"。

6 数字集成电路【旁听】

本周内容是讲述CMOS的动态电气特征，例如α−Power\alpha-Powerα−Power模型，以及沟道调制模型（涉及到的栅极长度LDL_DLD​，沟道长度LLL，有效长度L′L'L′（终于有听得懂的了），阈值电压效应，漏电流问题，GIDL效应（门引起的漏极漏电问题）等等；课程感受：模电部分后面没跟上，下周课程跳出模电，希望能好点。

7 本周总结

​ 本周为摸鱼周，摸得我泪眼婆娑。(￣▽￣)"

​ 不怕摸鱼，就怕粘锅，冲冲冲！