熊猫圈里的老鼠屎

2023年02月考研日记

2/21/2023

二月日记

Todo

  1. 算法刷题
  2. 编译原理
  3. 高分课程
  4. 项目回顾
  5. 毕业设计

20230221

总分380，排名3

政治 英语 数学1 408
72 72 124 112

数学出乎意料了，改的肯定很松；408有点烂了考的，但烂了还是意料之中的

自我介绍

Good morning, dear teachers! My name is Zhang Yaowen, I'm thrilled to be here today for the postgraduate entrance exam interview. I come from Wenzhou, a coastal city in Zhejiang Province. Currently, I am senior undergraduate student majoring in Computer Science and Technology.

Generally speaking, I am a hard-working student, especially when doing the things that I'm intererted in, and I got good scores in almost every subject.At the same time, I was rewarded with the Provincial Government Scholarship and the First-class scholarship. Apart from my good performance, I have also worked on some website project. In 2021, I joined the project of Zheli Zhilian WeChat applet, responsible for front-end and back-end development, and server deployment. Through this project, I have gained valuable experience in web development and design, as well as in content creation and management.

Secondly, as a determined person, I'm striving to achieve higher goals. In my spare time, I like runing, jumping rope, and playing basketball. I think exercise can release my pressure, make me relaxed and build my body, which is fundamental condition for further study and research.

Lastly I want to tell you my plans in near future. I'm passionate about the field of computer science, and I believe that postqraduate studies will enable me to further explore this field and gain advanced knowledge and skills.I am confident that I have the necessary motivation, academic ability, and sense of responsibility to succeed in a rigorous postgraduate program.

That's all about me. I would be honored if you could grant me the opportunity to study in this university.

电脑

位置 型号 价格
主板&CPU msi z790 carbon+i9 13900k 6779
显卡 msi 4090超龙 15499
内存 宏基 32G DDR5 899
外存 宏基 ssd 2T 999
散热 vk gl360 769
电源 segotep 昆仑 1250W 1299
机箱 msi 暗黑 100S 629
显示器 LG 27英寸 4K 144HZ 4299

算法

错排问题

已知n-1和n-2人的错排情况，n人两种情况

  1. b拿了新加入的a，a拿了b，
  2. b拿了新加入的a，a没拿b，

b有n-1种情况，res[n]=(n-1)*(res[n-1]+res[n-2])

折现分割平面

龟兔赛跑

经典dp，在加油站中操作，从第j个（依次算0到i-1）加油站到第i个加油站并在第i个加油站加油，如果j点有余量要不要加油?不用考虑，j处计算肯定是满油的，没有满油的情况在计算time是判断了，直接在加油站穿过去a

二分图最大匹配-匈牙利算法

先匹配第一个能匹配的，在看下一个，如果下一个能匹配之前的并且之前的有下家，那就替换；最后匹配成功了++res;利用递归

最短路径

做了两种答案，单源最短dijkstra和全图的floyd；

dijkstra

#include <algorithm>
#include <cstring>
#include <iostream>
#define INF 0x3f3f3f3f
using namespace std;
int mark[1010], cost[1010][1010], dis[1010];
int des[1010], start[1010];
int N, t, s, d;
int a, b, c;
void dijkstra(int s) { //单源最短路径
  memset(mark, 0, sizeof(mark));
  memset(dis, INF, sizeof(dis));
  dis[s] = 0;
  while (1) {
    int next = -1;
    for (int i = 1; i <= N; ++i) {
      if (!mark[i] && (next == -1 || dis[i] < dis[next]) && dis[i] != INF) next = i;
    }
    if (next == -1) break;
    mark[next] = 1;
    for (int i = 1; i <= N; ++i) {
      dis[i] = min(dis[i], dis[next] + cost[next][i]);
    }
  }
}
int main() {
  while (cin >> t >> s >> d) {
    N = 0;
    memset(cost, INF, sizeof(cost));
    while (t--) {
      cin >> a >> b >> c;
      if (cost[a][b] > c) cost[a][b] = cost[b][a] = c;
      if (a == b) cost[a][a] = 0;
      N = max(N, max(a, b));
    }
    for (int i = 1; i <= s; i++)
      cin >> start[i];
    for (int i = 1; i <= d; i++)
      cin >> des[i];
    int res = INF;
    for (int i = 1; i <= s; i++) {
      dijkstra(start[i]);
      for (int j = 1; j <= d; j++) {
        res = dis[des[j]] < res ? dis[des[j]] : res;
      }
    }
    cout << res << endl;
  }
  return 0;
}

floyd

#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int total = 1010;

int main() {
  int tmp, des, res = -1, max_c = -1;
  int dp[110][110], near[110] = {0};
  int a, b, c, time;
  int t, s, d;
  while (cin >> t >> s >> d) {
    for (int i = 1; i <= total; ++i) {
      for (int j = 1; j <= total; ++j) {
        dp[i][j] = INF;
      }
    }
    for (int i = 0; i < t; ++i) {
      cin >> a >> b >> time;
      if (dp[a][b] > time || dp[a][b] == 0) dp[b][a] = dp[a][b] = time;
      if (a == b) dp[a][b] = 0;
      max_c = max(max_c, a);
      max_c = max(max_c, b);
    }
    for (int i = 1; i <= max_c; ++i) {
      for (int j = 1; j <= max_c; ++j) {
        if (!dp[i][j]) dp[i][j] = 9999;
      }
    }
    for (int k = 1; k <= max_c; ++k) {
      for (int i = 1; i <= max_c; ++i) {
        for (int j = 1; j <= max_c; ++j) {
          dp[i][j] = dp[i][k] + dp[k][j] < dp[i][j] ? dp[i][k] + dp[k][j] : dp[i][j];
        }
      }
    }
    for (int i = 0; i < s; ++i) {
      cin >> near[i];
    }
    for (int i = 0; i < d; ++i) {
      cin >> des;
      for (int j = 0; j < s; ++j) {
        if (near[j] == des) {
          res = 0;
        }
        if (res == -1) res = dp[near[j]][des];
        res = min(res, dp[near[j]][des]);
      }
    }
    cout << res << endl;
  }
}

因子相关

一个数的因子通过对称可以判断出小半部分不大于n\sqrt{n}

一个数的连乘的因子不大于n+1\sqrt{n}+1

最最

long long gcd(long long a, long long b) { //最大公约数
  return b == 0 ? a : gcd(b, a % b);
}
long long lcm(long long a, long long b) { //最小公倍数
  return a / gcd(a, b) * b;
}

母函数问题

用母函数解题，就是用多项式的指数来代表某一属性(质量、分数、体积...)，前面的系数为它的种数。

系数相乘指数相加

比如: 若有1克、2克、3克、4克的砝码各一 枚，能称出哪几种重量？各有几种可能方案？ 按上面讲的，我们把X的指数设为质量。所以:

  • 1克能表示0克和1克两种，所有是:X0+X1=1+X1X^0 + X^1 = 1 + X^1
  • 2克能表示0克和2克两种，所有是:X0+X2=1+X2X^0 + X^2 = 1 + X^2
  • 3克能表示0克和3克两种，所有是:X0+X3=1+X3X^0 + X^3 = 1 + X^3
  • 4克能表示0克和4克两种，所有是:X0+X4=1+X4X^0 + X^4 = 1 + X^4

dp背包

01背包

#include <iostream>
using namespace std;
const int maxn = 1005;

int main() {
  int N, V;
  int v[maxn], w[maxn];
  int dp[maxn][maxn] = {0}; // dp[i][j]表示从i件物品中选，空间最大为j的价值的最大值
  cin >> N >> V;
  for (int i = 1; i <= N; ++i)
    cin >> v[i] >> w[i];
  for (int i = 1; i <= N; ++i) {
    for (int j = V; j > 0; --j) {
      if (w[i] > j) { // 放不下
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
      }
    }
  }
  cout << dp[N][V] << endl;
}

#include <iostream>
using namespace std;
const int maxn = 1005;

int main() {
  int N, V;
  int v[maxn], w[maxn];
  // int dp[maxn][maxn] = {0}; // dp[i][j]表示从i件物品中选，空间最大为j的价值的最大值
  int dp[maxn] = {0};
  cin >> N >> V;
  for (int i = 1; i <= N; ++i)
    cin >> v[i] >> w[i];
  for (int i = 1; i <= N; ++i) { //遍历所有物品
    for (int j = V; j >= v[i]; --j) { //改为一维数组得逆序
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
  }
  cout << dp[V] << endl;
}

完全背包

#include <iostream>
using namespace std;
const int maxn = 1000 + 10;

int main() {
  int N, V;
  int v[maxn], w[maxn], dp[maxn];
  cin >> N >> V;
  for (int i = 1; i <= N; ++i)
    cin >> v[i] >> w[i];
  for (int i = 1; i <= N; ++i) {
    for (int j = v[i]; j <= V; ++j) {
      dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
  }
  cout << dp[V] << endl;
}

二分查找

想要找最左边的数字，if a[mid]>=x ; r=m ,想找最右边的if a[mid]<=x ; l=m

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], n, q, x;

int main() {
  scanf("%d %d", &n, &q);
  for (int i = 0; i < n; ++i)
    scanf("%d", &a[i]);
  while (q--) {
    scanf("%d", &x);
    int l = 0, r = n - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (a[mid] >= x) // r往左边挤一挤
        r = mid;
      else
        l = mid + 1;
    }
    if (a[l] != x) {
      printf("-1 -1\n");
    } else {
      printf("%d", l);
      l = 0, r = n - 1;
      while (l < r) {
        int mid = (l + r + 1) >> 1; //避免死循环
        if (a[mid] <= x)            // l往右边挤一挤
          l = mid;
        else
          r = mid - 1;
      }
      printf(" %d\n", l);
    }
  }
}

编译原理

第一章

分析树生成，最左最右推导，二义性判断；

文法类型

  1. 0型，没限制

  2. 1型，上下文相关

  3. 2型，上下文无关

  4. 3型，正则，最左或最右都是终结或者空

  5. 短语，先构建语法树，列出所有的非终结符，再用叶子节点的组合去替换；两层或两层以上的子树末端连接

  6. 直接短语，语法树中，一步就能够用叶子节点替换掉非终结符的短语，也就是最左边的语法树；两层子树末端

  7. 句柄，最左边的直接短语；（最左直接短语）

  8. 素短语，包含终结符，并且不被其他素短语包含的短语；就是有终结符但是不能再被划分成素短语的短语就是素短语，没有“因子”，在树里最深，优先级比左右都高

  9. 最左素短语，在树的位置看下来，在最左边的素短语；

第二章

NFA转换DFA，子集构造法

从开始符号出发先找他的空闭包，输入终结符，达到集合T，再找T的空闭包；

最小化DFA

注意接收不可接收相同才可以合并

第三章

FIRSTVT(P)

非终结符P的最左边的终结符，a...或Qa...，加上FIRST(Q);

对于一个aP，在左边的a小于所有的在右边的FIRSTVT(P)

LASTVT(P)

非终结符P的最左边的终结符，...a或...Qa，加上LASTVT(Q);

对于一个Pb，所有的在左边的LASTVT(P)高于在右边的b

左递归

使用到递归的非终结符可能也要消除左递归

左公因式

做改造文法别忘了LL1不能有左公因子

预测分析表

看产生式的右部的fisrt而不是左部的first，填入，有空则要看follow

LR(0)

规约-规约冲突和移入-规约冲突

SLR

由于LR的移入-规约冲突，根据fellow集进行判断，如E->T·和E->T·*F看E的follow集合，如果*不在E的follow集中则不规约；即如果下一个符号是follow集中的一个元素则规约，

LR(1)

规范LR，超出·后的非终结符后的符号的fisrt

LALR

合并LR(1)的相同核心的项，

FELLOW

计算A->B,FELLOW(B)+=FELLOW(A)，FELLOW(A)不动

分析表

  • LL
步骤 分析栈(abc#/#cbd) 输入 动作
  • 算符
步骤 符号栈 优先关系 当前符号 输入 动作
  • LR
步骤 状态栈 符号栈 剩余输入 动作

第四章

后缀式表达式=逆波兰表达式，a+b->ab+

三地址码，x:=y op z,x:=op y,x:=y,goto L,if xx goto ,param x,call,return,x:=y[i],x:=

四元式，op,arg1,arg2,res

三元式，op,arg1,arg2,(结果位置通过计算实现)

间接三元式，三元式表+间接码表（执行顺序）

研究方向

有无监督学习，事先知不知道输入数据对应的输出结果是什么

NLP，自然语言处理

卷积神经网络

  • 卷积层，提取特征
  • 激活函数，如果输入变化很小，导致输出结构发生截然不同的结果，这种情况是我们不希望看到的，为了模拟更细微的变化，输入和输出数值不只是0到1，可以是0和1之间的任何数，
  • 池化层，对输入的特征图进行压缩，一方面使特征图变小，简化网络计算复杂度；一方面进行特征压缩，提取主要特征，
  • 全连接层，连接所有的特征，将输出值送给分类器

-泛化能力，是指机器学习算法对新鲜样本的适应能力，学习好了后运用的能力；

服务计算

面向服务

  • 服务是一组能力（Capabilities）的集合

  • 服务者（Server）是拥有能力的实体

  • 客户是（Client）是使用能力的实体

  • 边缘计算

边缘计算是使信息存储和计算能力更接近产生该信息的设备和使用它的用户的过程。传统上，应用程序将数据从传感器和智能手机等智能设备传输到中央数据中心进行处理。然而，前所未有的复杂性和数据规模已经超过了网络能力。通过将处理能力转移到更靠近用户和设备的位置，边缘计算系统显著提高了应用程序性能，降低了带宽需求，并提供了更快的实时洞察力。

  • 数据挖掘

数据挖掘是一种计算机辅助技术，用于分析以处理和探索大型数据集。借助数据挖掘工具和方法，组织可以发现其数据中隐藏的模式和关系。数据挖掘将原始数据转化为实用的知识。公司利用这些知识来解决问题、分析业务决策对未来的影响以及提高利润率。

  • 机器学习

简而言之，ML是使用统计(或数学)技术从观察到的数据中构建模型(或系统)的一个计算机科学领域，而不是让用户输入一组定义该数据模型的特定指令。有时ML可以做的非常简单，如线性回归问题，一个更复杂的示例是邮箱中的垃圾邮件检测器，它可以“学习”哪些电子邮件是垃圾邮件，尽管从未针对每种电子邮件给出说明。

  • 深度学习

深度学习本质上是一组技术，可以用来帮助你参数化深度神经网络结构，也就是具有许多层和参数的神经网络。

虽然深度学习已经存在了一段时间，但由于广泛的适应，现在它正受到越来越多的关注。它是机器学习的一个子集，还提供监督学习、非监督学习和强化学习等。

深度学习是机器学习方法的更广泛的系列，它试图从给定的数据中学习高级功能。 因此，它解决的问题减少了为每种数据类型（语音，图像等）制作新的特征提取器的任务。

例如，对于ML中的图像识别来说，深度学习算法将在向他们呈现图像识别任务时尝试学习诸如眼睛之间的距离，鼻子的长度，或者目前无法解释的一些特征。 他们可以使用这些信息进行分类，预测等任务。 因此，这是与以前的“浅层学习算法”（ML学习）相比迈出的重要一步，也可以称为是更“智能”的一种机制。

英语口语

  • please introduce your hometown

Wenzhou, located in Zhejiang Province, China, boasts a rich culture and picturesque scenery. One of its most famous natural attractions is the Yandang Mountain, a UNESCO World Heritage site known for its stunning landscapes. The Nanxi River, with its crystal-clear water and charming rural landscapes, is also a popular spot for tourists.

As for cuisine, Wenzhou is famous for its fresh seafood and local specialties such as Wenzhou dumplings and Wenzhou noodles. Another popular dish is "nuo mi fan," or glutinous rice, which is often served with savory meat and vegetables, making it a must-try for food lovers visiting the city.

  • What would you like to be doing after your postgraduate graduation

Thank you for you asking.

As a computer science and technology major, I am eager to expand my knowledge in the fields of deep learning, machine learning, and natural language processing (NLP) during my graduate studies. To achieve this goal, I plan to take courses in these areas, and participate in research projects related to these topics.And I aim to participate in research projects related to deep learning, machine learning, and NLP to gain hands-on experience and contribute to the advancement of these technologies. Through these efforts, I hope to become a skilled and knowledgeable practitioner in these cutting-edge areas of computer science and technology.I hope I can use what I have learned to do some studies about my interested fields. Now I am just starting to learn about machine learning and deep learning. I hope to further study during my postgraduate study and make certain achievements in these fields.

  • What is your greatest strength

I am someone who possesses a great strength in persevering through tough situations. I have a high tolerance for hardship and am willing to put in the necessary effort and time to achieve my goals. I believe that this quality is essential in both personal and professional pursuits, as it helps me to stay focused and determined even in challenging circumstances. Overall, my ability to endure hardships and persist through difficult times has been a key factor in my success and growth, and I am confident that it will continue to serve me well in the future.

  • What is your greatest weakness

I struggle with socializing and find it difficult to connect with others. This has been a challenge for me in both personal and professional settings. However, I am aware of this weakness and am actively working to improve my social skills through practice and self-reflection.

  • English important?

Yes, I believe that English is crucial for graduate studies, especially in fields such as computer science and technology where much of the research and literature are written in English. Strong English skills will allow me to communicate effectively with my peers and professors, understand complex research papers, and access a wealth of resources in my field. It will also enhance my career prospects and opportunities for international collaboration.

  • book

"A Song of Ice and Fire" is a book series written by George R.R. Martin. Set in a medieval-style fantasy world, it follows the story of several noble families as they battle for control of the Seven Kingdoms. The series is known for its complex characters, political intrigue, and epic battles. It has been widely praised for its rich storytelling, detailed world-building, and realistic portrayal of human nature. The series has also been adapted into a successful television show, "Game of Thrones," which has further popularized the franchise. Overall, "A Song of Ice and Fire" is a must-read for fans of epic fantasy and political drama.

2024年03月读研日记