Mathematical Logic Cheating Paper
ML CT Paper 前言 这是留给25级往后ACM班学弟学妹的一份遗产了，很详细地总结了CS2950 Mathematical Logic这门课程涉及的主要知识点（有所删减）。特别值得注意的是，我在25.6.5晚在前三位作者整理的基础上，增添了6个example，是拟合了近3年ML Final的结果。今晚考完，更觉得整理地挺到位（精准吧 这是能说的嘛🤣）。分数还没出，也不知道实际到底考的怎样
25 Fall
25 Fall Learning Record 25 Fall 开始，依托的RCompiler，混乱的Arch课程，两门😇 的数学课，三节早八的物理课，毫无想法的xzjt，TA 工作， 原来已经大二了😥 学期有些规划。 该如何收场。 CSAPP 和 CAAQA。 快让我润出去吧，每天都在幻想能不能直接跳过本科3年直接润美😇 我要换 Macbook 了. 还是不换了，thinkpad还能用（
Graph Algorithm
Graph Algorithms ps: 上机课是05.18上的，算法是05.23学的🤣（评价是这周事还是太多了）perhaps和这节上机课量巨大也有关系吧😢 术语回顾 DAG 有向无环图 点度 = 入度 + 出度 SPT 最短路径树 最短路 单源/多源 Q：给出一个加权图和图上的一个节点s，找出s到图中每一节点的最短路径 Dijkstra 算法 Core: v=argmin_u∈SPT,
Theories and Decidability
Theories and Decidability Recall The 4 Questions we’re gonna answer. Q1: What is a mathematical proof? Q2: What makes a proof correct? Q3: Is there a boundary of provability? Q4: Can computers find
Proof of the Undecidabilty of FO
Mathematical Logic 11 Proof of the undecidability of FO Undecidability of FO Basic Thoughts of the Proof We’ve already proved that Π halt is not R-decidable by using Π’halt ⩽m Π halt. So we only need
LCA DS MST
LCA ———— Least Common Ancestors 如何计算？ 深度相同一起跳 深度不同，深度大的跳 显然，一层一层跳复杂度将会来到O(N) 空间换时间 一次多跨几步 联系：ST表 考虑保存2 的幂次级 祖先 于是我们有了一种很棒的倍增做法： 假设 y 比 x 深，则 y 需要向上跳 a = h(y) - h(x) 对 a 进行二进制拆分 令 f[x][i]为结点 x 的
Mathematical Logic 10 Halting Problem
Mathematical Logic 10 Halting Problem R-computable Let F: A* -> B* (A,B are 2 alphabets) (1)A program P computes F if for all w ∈\in∈ A*, P: w->F(w) (2)F is R-computable if there is a program w
MIT 6.006 Shortest Path Algorithm
MIT 6.006 4 Shortest Path Algorithm Overview Weighted Graph General Approaches Negative Edges Optimal Substructure Mainly 2 Algorithms： Dijkstra with O(V + E) for non-negative edge weights Bellman F