大三上资源汇总贴 | fufu酱のNoteBook

type

status

slug

summary

📝 主要课程

💡

计算理论

计算机网络

计算机体系结构

操作系统

日语

BS （大作业）

英美文学赏析（大作业）

统计与大数据分析（大作业）

计算理论

quiz相关：JXG老师是每章布置作业后的第1/2周的课前进行Quiz，切勿迟到

笔记资源

www.cc98.org

https://www.cc98.org/topic/5586121/2#1

学习方法：

金小刚两次quiz+四次作业（其中一次不需要提交）+期末

建议可以上课不听看myc的回放

另一方面是平时事比较少，如果大三上很忙只能补天的话jxg应该是更好的选择。

jxg老师会有两次小测，小测题目和上课讲的例题质量都挺高的。因为上课前面进度比较慢，后面飞速赶进度，最后一节课还在讲最后一章，所以一定要提前学最后一章。最后一章的内容可以看myc老师的智云，讲得非常清晰。强烈推荐这位大佬前辈的笔记 https://github.com/zyxNova/ZJU-CKCMix-CS-Course-Material 非常详细，概念和证明都无遗漏且很清晰，复习非常有效。今年考试题型变化比较大，感觉比较强调后两章的证明，尤其是一道十几分的证明大题要是没看过证明过程就很难写出来。有时间刷刷qsc仓库里面那个关于undecidability的证明题集，刷完undecidability就大成了（。今年的考试变化比较大，选择判断和往年难度差不多，但是大题难度都比往年难度高，且容易出错，没有明显送分的（八股文成为历史）大题判断是否正则是06-07年的原题，lz刷题的时候第一次做两个都判断错了。

学期内可以慢慢额外做一些前辈整理的证明题锻炼思维，并且注意整理和积累

客观来说这门课的考试难度没有特别特别大，在掌握知识点的前提下成绩是会不错的，只是不能像往年一样一晚历年卷速成了。考了一些偏定义的东西，比如用三带图灵机实现非确定图灵机。比较大的改变是今年的卷子开始限制PDA，DFA之类题目的状态数量和转移关系了，所以在构造的时候可能不能过于随意。这门课毕竟知识点比较少，考前花一天过完毛老师的回放，再花一天刷题基本问题不大。

平时作业交了就能满分，但是有两次quiz还是比较难顶（金老师喜欢课前半小时测，而且不会提前通知，记住一定不要迟到! 一般小测是在每章结束后1-2周，记得提前复习（时间有点紧）另外也可以关注下往年的智云课堂。

关注所有历年卷和quiz题作业题就可以了

subset construction method

Describe an algorithm that can convert a NFA to an equivalent DFA,

and analyze its time complexity

Algorithm to Convert an NFA to an Equivalent DFA and Its Time Complexity Analysis

Introduction

A Nondeterministic Finite Automaton (NFA) can be converted to an equivalent Deterministic Finite Automaton (DFA) using the subset construction algorithm, also known as the powerset construction. This algorithm systematically constructs a DFA that recognizes the same language as the given NFA by considering all possible subsets of NFA states.

Algorithm Description

Given an NFA \( N = (Q_N, \Sigma, \delta_N, q_{0N}, F_N) \), where:

\( Q_N \): Set of NFA states.

\( \Sigma \): Input alphabet.

\( \delta_N \): Transition function \( \delta_N: Q_N \times \Sigma \rightarrow 2^{Q_N} \).

\( q_{0N} \): Initial state.

\( F_N \): Set of accepting (final) states.

We aim to construct a DFA \( D = (Q_D, \Sigma, \delta_D, q_{0D}, F_D) \), where:

\( Q_D \): Set of DFA states (each state is a subset of \( Q_N \)).

\( \delta_D \): Transition function \( \delta_D: Q_D \times \Sigma \rightarrow Q_D \).

\( q_{0D} \): Initial state (subset of \( Q_N \)).

\( F_D \): Set of accepting states.

Algorithm Steps

Initialize the DFA

Initial State: Start with the initial state \( q_{0D} \) of the DFA, which is the epsilon-closure of the NFA's initial state \( q_{0N} \): \[ q_{0D} = \epsilon\text{-closure}(\{q_{0N}\}) \]

Epsilon-Closure: The epsilon-closure of a set of states \( S \) is the set of states reachable from any state in \( S \) via epsilon (empty string) transitions, including \( S \) itself.

Construct the DFA States and Transitions

Worklist Algorithm: Use a queue or stack to keep track of unprocessed DFA states.

Initialize: Add \( q_{0D} \) to the worklist and \( Q_D \).

Process States:

While the worklist is not empty:

Remove a state \( T \) from the worklist.
For each input symbol \( a \in \Sigma \):

Compute the set of NFA states \( U \) reachable from \( T \) on input \( a \): \[ U = \epsilon\text{-closure}\left( \bigcup_{q \in T} \delta_N(q, a) \right) \]
Add New State:

If \( U \) is not already in \( Q_D \):

Add \( U \) to \( Q_D \).
Add \( U \) to the worklist.

Define Transition:

Set \( \delta_D(T, a) = U \).

Define Accepting States

Accepting States: A DFA state \( T \) is accepting if it contains at least one accepting state of the NFA: \[ F_D = \{ T \in Q_D \mid T \cap F_N \neq \emptyset \} \]

Time Complexity Analysis

Let \( n = |Q_N| \) be the number of states in the NFA, and \( m = |\Sigma| \) be the size of the input alphabet.

Number of DFA States

Theoretical Upper Bound: The number of possible subsets of \( Q_N \) is \( 2^n \). Therefore, \( |Q_D| \leq 2^n \).

Practical Observation: Not all subsets are reachable from the initial state, so the actual number of DFA states may be less.

Processing Each DFA State

For each DFA state \( T \) and input symbol \( a \), we compute the set \( U \) as described.

Computational Steps:

Transition Retrieval:

For each state \( q \in T \), retrieve \( \delta_N(q, a) \).

Set Union:

Combine the resulting sets for all \( q \in T \).

Epsilon-Closure:

Compute the epsilon-closure of the combined set.

Time per Transition:

Retrieving transitions: \( O(n) \) (since \( |T| \leq n \)).
Epsilon-closure computation: \( O(n^2) \) in the worst case (if the NFA has epsilon transitions forming a connected graph).
Total per transition: \( O(n^2) \).

Total Time Complexity

Total Number of Transitions:

Up to \( |Q_D| \times m \).
In the worst case: \( 2^n \times m \).

Total Computation Time:

Time per transition \( \times \) total number of transitions.
\( O(2^n \times m \times n^2) \).

Simplified Complexity:

\( O(m n^2 2^n) \).

Space Complexity

DFA States Storage:

Up to \( 2^n \) states, each storing a subset of \( Q_N \).

Transition Table:

Up to \( 2^n \times m \) transitions.

Total Space:

\( O(2^n \times n) \) (for states) \( + \) \( O(2^n \times m) \) (for transitions).
Combined: \( O(2^n (n + m)) \).

Conclusion

The subset construction algorithm effectively converts an NFA to an equivalent DFA by considering all possible combinations of NFA states. However, due to the exponential growth of possible state subsets, the algorithm has:

Time Complexity: Exponential in the number of NFA states (\( O(2^n) \)).

Space Complexity: Exponential in the number of NFA states (\( O(2^n) \)).

Despite the exponential worst-case complexity, this method is fundamental in automata theory and compiler design, and optimizations or alternative representations are often used in practical applications to mitigate the exponential growth.

Summary of the Algorithm Steps

Initialization:

Start with the epsilon-closure of the NFA's initial state.

Initialize the DFA states and worklist.

State Processing Loop:

For each DFA state and input symbol:

Compute the move and epsilon-closure to find the new DFA state.
Add new DFA states to the worklist.

Defining Accepting States:

Any DFA state containing an NFA accepting state becomes an accepting state.

Time Complexity:

Exponential due to the potential \( 2^n \) number of DFA states.

Practical Notes

Optimizations:

In practice, many of the possible subsets are unreachable, so the actual number of DFA states may be much less than \( 2^n \).
Techniques like memoization and state minimization can help reduce the number of states and transitions.

Applications:

Essential in lexical analysis, where regular expressions are converted to NFAs and then to DFAs for efficient pattern matching.

Limitations:

For NFAs with a large number of states, the subset construction may become computationally infeasible due to resource constraints.

Reference

Automata Theory: The study of abstract machines and problems they can solve.

Powerset Construction: Method of converting NFAs to DFAs by representing each DFA state as a set of NFA states.

计算机网络

备考建议：计网有很多可以参考的资源，包括课本，学长的网课，一些dl的笔记。但是就从备考的角度来说，王道是比较好的选择。这学期的期末考试题目有很大部分从平时作业（四次习题和lkj100题）重复出现。lz不是擅长考前冲刺的选手，建议每周写完对应章节的王道，考前看一遍再把lkj100题做一遍就可以。

这门课自底向上讲解计算机网络，分别是物理层、数据链路层、网络层、传输层、应用层，以及额外的网络安全内容。成绩组成：作业 10 + 随堂测验 10 + 出勤 5 + 实验 25。总的来说，这门课的理论、实验、期末考试不能说是完全正交，但确实关系不大。许海涛老师今年是第一次教计算机网络这门课，因此对教学的很多内容都不熟悉，讲课方面一言难尽。但……同时也会根据大家的情况延长 ddl、删减实验，最后一节课的复习课也基本覆盖了考试的所有内容。23-24 秋冬学期没有点过名。因为老师课程进度紧张，随堂测验仅做了 2 次，基本上是教材或者其他书课后的作业题。计网的实验长期为人诟病，数十年一成不变的实验内容，几乎为零的实验指导，时常灵异的 GNS3。但是本学期许老师、助教和同学们商量，只布置了 4 个实验，其中 1 个 Wireshark，2 个 GNS3，1 个 socket 实验，绝对是本学期计网教学班里任务最轻的了。老师和助教让这门暗黑的课程有了一抹光亮。笔者做实验时，秉承着尽快脱离牢笼的原则，基本上是和同学互帮互助，并且参考往年的实验报告进行完成。期末：这门课的内容可以说是非常多，而且大部分老师的讲课都一言难尽，期末考试则几乎完全对标考研题（只是把中文换成英文）。准备期末考试最好的方式是面向考研书（王道）预习 / 复习，[咸鱼喧学长的朋辈辅学视频](

https://www.bilibili.com/video/BV1Xr4y1r7gM/

)也可以用来速成。考试里有相当多的部分是考研原题，再补充网络安全（这部分王道上面没有）的知识。许老师今年的复习 PPT 值得参考，还有大名鼎鼎的 lkj100 题，考前一定要过一遍。

王道+xyx的视屏

计算机体系结构

体系的期末是最抽象的，基本没有历年卷然后作业不能说和期末完全不关，但也是关系不大，所以我是觉得主要还是把ppt搞懂比较重要。然后因为有一张A4纸，感觉除了一些背不下来的，比如如何提高cache效率啥的之外，还可以抄点例题，说不定就用上了。我这边写了历年卷，这个是我同学从何水兵老师上课的录播里一帧帧截下来的，真的很感谢他。这边我暂时找不到了，欢迎大家补充。实测历年卷能很大程度提高期末，起码不会对题型陌生。

这门课主要讲的是 cahce 的分析和策略、乱序流水线、Cache 和内存一致性、SIMD 和 GPU 的简单介绍。其中前半学期的内容（复习流水线，Cache 分析）与计组内容重叠较高，

这门课内容看起来很多，但是实际上不多，但是比较杂，所以复习的时候会感觉有点没头绪，总体的内容是非常少的，但是非常杂，复习的时候找到思路就很快，但是迷茫的话可能就要寄了。我这门课非常的稳健，前一天计网考完才开始复习，复习一下午加一晚上，第二天早八考。主要思路就是先看朋辈辅学视频，主要的记分牌和另一个大题怎么做，然后看其他同学的笔记，然后还有其他老师的复习ppt，再做了几份题。最后结果还行。

操作系统

24-25秋冬伍赛班OS实验文档

yuque.zju.edu.cn

https://yuque.zju.edu.cn/ytqfu3/mgf5fz

一共三次quiz，当作签到。quiz的题目质量比较高，值得认真完成。

平时作业在学在浙大完成，一共有5次测试。如果第一次做相关题目很容易做错，小测一共占总评五分，很容易丢分。做的时候可以和同学一起做，今年前几次作业提交了就会公布成绩，所以也可以和同学一起轮流献祭。

实验一共7次，前六次是必做。可以solo或两人组队。实验发布的比较早，可以提前完成。实验的难度都不算大，框架设计的比较完善，主要是需要理解清楚。

os的参考资料有很多，包括学长的笔记，各种网课等等。但是对于一门课程来说，个人认为找一到两个资料研究清楚就可以，资料太多会让人精力分散。王道和os期末考察的内容重合率可以达到85%以上，在上课听课的基础上可以很容易分辨出哪些内容不需要看。在王道的基础上把quiz，作业题在考前刷一遍，足以拿到比较好的成绩。

这门课的课程内容应该和计网一起是最多的，但是相比起其他几门课（包括课程内容少很多的计算理论和体系结构）要友好的多。首先就是整个课程的整体思路非常清晰，复习的时候跟着老师给的复习思路侧重点，先看修佬的笔记看一遍，再把每个ppt过一遍，顺便把没记住的写上A4（我自己是没写A4，感觉不重要，就顺便用了一份学长的），就差不多了，然后做一遍jjm的作业和小测（这个很重要）就差不多了。

感觉要是平时抽时间把王道刷完考试周就会从容很多

这是一门平时如果付出多考试前能轻松一些的课程，从我补天的经历可以看出，如果要求比较高，尽量是平时做好王道的题目、做实验bonus，考前做jjm老师班的作业小测题。

一遍xyx学长朋辈辅学的录像，另外花了一天过了一遍ws老师的复习课，最后花了一天过了一遍quiz和hw（其实挺多的，因为有自己班和其他班老师的），考试的时候主干知识都能cover，但是今年选择题太多了，部分没有复习到，大题都是会做的

理论方面的话，虽然章节较多，但知识点相比计网而言真的少了很多，但是不太像计网是偏文科背书课