Think World

从个人成长角度来说，从经历中学点什么总是重要的

0%

Posted on In

使用方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from pytorch_grad_cam import GradCAM, ScoreCAM, GradCAMPlusPlus, AblationCAM, XGradCAM, EigenCAM
from pytorch_grad_cam.utils.image import show_cam_on_image
from torchvision.models import resnet50
import torchvision.transforms as transforms
import cv2 as cv
import numpy as np


#加载函数模型
model = resnet50(pretrained=True)
#设置要测量那个网络层的效果
target_layer = model.layer4[-1]

#网络输入，转换成 Tensor格式，要符合网络的输入 (batch_size,c,w,h)
image = cv.imread("C:/Users/doris/Desktop/image.jpg").astype(np.float32)/255
transf= transforms.ToTensor()
input_tensor = transf(image).unsqueeze(0)

#加载GradCAM
cam = GradCAM(model=model, target_layer=target_layer, use_cuda=False)

#设置要关注的类别，如果不设置，默认返回得分最高的类别
# will be used for every image in the batch.
# target_category can also be an integer, or a list of different integers
# for every image in the batch.
target_category = 1

#计算网络可视化结果
# You can also pass aug_smooth=True and eigen_smooth=True, to apply smoothing.
grayscale_cam = cam(input_tensor=input_tensor, target_category=target_category)

# In this example grayscale_cam has only one image in the batch:
grayscale_cam = grayscale_cam[0, :]

#注意这里image 和 grayscale_cam都是narray.float32格式
visualization = show_cam_on_image(image, grayscale_cam)

#将结果写入到本土图片中
cv.imwrite("C:/Users/doris/Desktop/result.jpg",visualization)

Posted on Edited on In

t-SNE介绍

  • t-SNE是由t-分布和随机近邻嵌入(Stochastic neighbor Embedding)组成
  • 其重要用途是 可视化和探索高维数据。它的主要目标是将高维数据集转换为低维数据集，并且可视化效果更好。采用非线性降维技术，可以捕获复杂的流行数据。

t-SNE工作原理

SNE算法

在介绍t-SNE之前，我们先介绍SNE算法

​ 核心思想：

数据降维时，要保证： 在高维空间相似的数据点，映射到低维空间也是相似的。常规做法是使用欧式距离来表示这种相似性，而SNE把距离关系转换成一种条件概率来表示相似性

把距离映射到某一概率分布上：

对于高维空间中的两个点$x_i$​​​​,$x_j$​​​​， $x_i$​​​​以条件概率$p_{j|i}$​​​​选择$x_j$​​​​作为它的临近点。 考虑以$x_i$​​​​为中心点的高斯分布，如果$x_j$​​​​​越靠近$x_i$​​，则条件概率$p_{j|i}$​​​越高，相似性越高。

在SNE中，在高维空间中，条件概率$p_{j|i}$定义为
$$
p_{j|i} = \frac{exp(-||x_i-x_j||^2/{2\sigma_i^2})}{\sum_{k \neq i} exp(-||x_i - x_k||^2 /{2\sigma^2_i)}}
$$
考虑其它所有点与$x_i$的条件概率分布，可以构成一个条件概率分布$P_i$.

同样的，当数据映射到低维空间之后，我们也用类似上面条件概率的形式，定义低维空间中两点​的相似性.

这里我们假设高维数据点$x_i,x_j$在低维空间中的映射点分别是$y_i,y_j$。类似的，低维空间中的条件概率用$q_{j|i}$表示，这里$\sigma$均固定为$1/\sqrt{2}$
$$
q_{j|i} = \frac{exp(-||y_i-y_j||^2/{2\sigma_i^2})}{\sum_{k \neq i} exp(-||y_i - y_k||^2 /{2\sigma^2_i)}}
$$
考虑其它所有点与$y_i$​的条件概率分布，可以构成一个条件概率分布$Q_i$​.

高维空间的条件概率分布$P_i$应该和低维空间中的概率分布$ Q_i$相同,我们可以用KL散度来衡量两个分布之间差异。

SNE的最终目标就是对所有数据点最小化KL距离，其代价函数可以定义为
$$
C = \sum_{i} KL(P_i || Q_i) = \sum_{i} \sum_{j} p_{j|i} log \frac{p_{j|i}}{q_{j|i}}
$$
不过目前的SNE存在两个问题：不对称 和 拥挤问题

  • 不对称：$p_{j|i}$​ 和 $q_{j|i}$​不相等
  • 拥挤：不同类别的簇挤在一起，没有办法分开。因为高维空间距离分布和低维空间存在差异。简单来说，更高维的空间距离相等的点的数据量更多。在10维流行性，存在11个点两两数据相等，而在2维空间，最多能使3个点之间两两数据相等。所以将高维空间中的距离关系完全保留到低维空间中是不可能的.

t-SNE算法

针对上述提到的SNE算法中的两点不足，t-SNE提出了相应的解决方法。

不对称

对于不对称问题，我们用更加简答直观的方式重新定义了概率分布
$$
p_{ij} = \frac{p_{i|j} + p_{j|i}}{2n}
$$
相应的损失函数可以定义为
$$
C = KL(P||Q) = \sum_{i} \sum_{j} p_{ij} log\frac{p_{ij}}{q_{ij}}
$$
相应的梯度变为：
$$
\frac{\grad C }{ \grad{y_i}} = 4 \sum_{j}(p_{ij} - q_{ij})(y_i-y_j)
$$

拥挤

随着维度的增加，大部分数据点与$x_i$​之间的距离分布极其不均衡，很多点与$x_i$之间的距离接近，如果直接把高维距离关系保留到低维空间。很容易出现拥挤问题。我们用t-分布的方法，解决该问题。

t-分布

​ t-分布:从正态总体中抽取容量为N的随机样本，如果该正态总体的均值为$\mu$,方差为$\sigma^2$.随机样本均值为$\hat x$,方差为$s^2 = \frac{1}{N-1} \sum_{i=1}^{N} (x_i - \hat x)^2$,

随机变量t可以表示为
$$
t = \frac{\hat x - \mu}{ s / \sqrt{N} }
$$
我们称t服从自由度为n-1的t分布。

t-分布是长尾分布。相比于高斯分布，他尾部更宽一些，处理小样本和异常点时，鲁棒性较高

如上图所示，要是$p_{ij}$ 和$q_{ij}$相等，在高维空间中比较接近的点(对应正态分布)，在低维空间中要更接近(对应t-分布)；而对与高维空间中较远的点，在低维空间中需要更远。

所以在t-SNE中，用t-分布，重新定义了低维空间中的概率分布，如下所示
$$
q_{ij} = \frac{(1+||y_i - y_j||^2)^{-1}}{ \sum_{k\neq l}(1+||y_k - y_l||^2)^{-1}}
$$

代码实现

“封装成一个函数”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import numpy as np
import matplotlib.pyplot as plt
from sklearn import manifold 
'''
    tSNE对数据进行t-sne可视化
    @para：
    X：shape（num,dim) num为数据点的个数，dim是每个数据点的特征的维度  eg：（100，3）表示一共有100个数据点，每个数据点是3维向量
    label：shape(num,1) 对应每个数据点的类别标签
    colorlist: dict:{"red":red}每个类别对应的颜色
    n_components:数据点降维之后的维度，默认是2
    init:和库函数的含义一样，可以选择"pca: "random"
    perplexity:建议5-50，数据量越大，该值应该设置的越大
'''
def tSNE(X,label,colorlist,n_components=2,init="pca", perplexity=10):
    #降维
    tsne = manifold.TSNE(n_components=n_components,init=init,random_state=0, perplexity=10)
    X_tsne = tsne.fit_transform(X)#(187500, 2)
    #可视化
    for color in colorlist.keys():
        plt.scatter(X_tsne[colorlist[color][:,0]][:,0], X_tsne[colorlist[color][:,0]][:,1],s=0.01, c=color)
    plt.show()

“应用实例”

使用时，需要自己计算colorlis

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from PIL import Image
import numpy as np
#加载图片和标签
X= np.asarray(Image.open("D:/Users/July/Desktop/image1.jpg")) #(366, 500,3)
label = np.asarray(Image.open("D:/Users/July/Desktop/label1.png")) #(366,500)

#调整尺寸
label = label.reshape(-1,1)
X=X.reshape(-1,3)

#计算colorlist
red= label==0
green= label ==5
blue = label ==255
yellow = label ==11
colorlist={}
colorlist['red']=red
colorlist['green']=green
colorlist['blue']=blue
colorlist['yellow']=yellow
#调用函数
tSNE(X,label,colorlist)

运行结果

Posted on Edited on In

友情链接：

研究生面试常见问题（英文＋中文） - 知乎 (zhihu.com)

自己被问到过的

北深：

​ 你觉得ai十年后会发展成什么样子？

中科大:(当时问了超级多的内容，问到快排的时候，我都懵了==)

自我介绍,介绍一下家乡(河南)，兴趣爱好，介绍一些自己较好的学习习惯(写博客)，简单解释一下快排的含义，介绍一下U-net结构

研究生计划

　　Thanks for the question!

　　I am planning it based on my interest and theoretical foundation.First, I will make reasonable arrangements according to the curriculum, with particular attention on the study of basic theory and methodology in my field. In my spare time, I may read various books regarding ai and compuer vision regularly.Try to put forward creative ideas and new opinions,so that I can better communicate with my professors and counterparts.

　　Then,assisting my instructor with his/her work is very important and I believe it a great way to make progress. If possible, I hope to attend some academic seminars and publish a paper with high quality under the guidance of my adviser.At last, I want to have my English ability consistently improved ,which is beneficial to paper-reading ,you know.

　　If I can be accepted ,I will start my postgraduate plan very soon in my rest of college time,like reading classical academic work and paper to cultivate independent thinking and research ability.I am looking forward to realizing my dream here!

​

个人介绍

​ I’m very honored to be here to present myself.I am sherry wang, a twenty-two years-old girl. I’ll graduate from JLU and my major is CS.

During my college life, I have worked very hard at my courses.So that I have achieved excellent grades in major courses.The GPA for the first five semeters is 3.86.I also have passed CET-6 smoothly.

Apart from that.I have participated in various scientific research.One of the most satisfying is the landmark detection of human joints system. And at present, our system has been applied to the clinic, and is welcomed by doctors.I’m the leader and responsible for the implementation of the system algorithm. Those progress were a little difficult, but I learned a lot from them. And it was those experience that inspired my interest in adamic research.

I think my search and study in the undergraduate stage is colorful but shallow .So I hope to have a chance to study here.I’ll spare no effort to do research in my major.

Thanks for your attention!

介绍学校

JLU is founded in 1946 and located in Changchun,China. As a leading national research university , It’s strongly supported by state key projects such as Project 985 and Project 211.

It has seven campuses in six districts that are home to 47 colleges covering 13 academic disciplines, including philosophy, economics, law, literature, education, history, science, engineering, agriculture, medicine, management, military science and art.

And JLU is very beautiful. There are lots of flowers, plants, and the air is very fresh. The teachers are very responsible and the students are energetic. I learned a lot and made great progress. I am very grateful to my college , because it makes me better.

　In a word,I enjoy the past three years spend in JLU very much !

介绍家乡

Changchun, my hometown, sits in the hinterlands of the Song Liao plain of Northeast China. It is the capital city of Jilin Province. Here is the most fertile soil in China. When you are walking on this modern and civilized city, you cannot fail to feel the vitality and prosperity of this city.

介绍长春

​ Changchun sits in the hinterlands of the Song Liao plain of Northeast China. As the capital city of Jilin Province, it is the economic and cultural center of the whole province. And it is famous for its developed automobile industry. Here is the most fertile soil in China. When you are walking on this modern and civilized city, you cannot fail to feel the vitality and prosperity of this city.

It still enjoys great reputation for culture. There are not only rich varieties of modern entertainment facilities, but also some special entertainment items only for Changchun, such as Yangge Dance and Errenzhuan, which is a song-and-dance duet in the Northeast of China.

If you have the opportunity of doing some sightseeing in Changchun, I recommend you to taste my hometown’s specialties.There are two kinds of famous dishes in Northeast China: Stewed young chicken with mushroom and Stewed Pork with Vermicelli.

做的项目遇到困难最多的是什么？ 你是如何克服的

What impressed me the most is the distributed development course in the first semester of the junior year.
This course is a synchronized course with a school in Portugal, we need to complete a medical assistant software system.
I am the leader of the group. Our group is responsible for the development of deep learning algorithms and completes the task of detecting key points of medical x-ray image.
Encountered the following problems

  1. In terms of communication and cooperation, the group members include students from Portugal and China. Due to language and time difference issues, it is not very convenient for us to communicate.
    In order to solve this problem, we communicated in various ways through WeChat and email, and developed using github.
    The members are more serious and enthusiastic, so our project development is very smooth.
  2. In terms of technology, you know, the algorithm is the core of the project and affects the performance of the software.
    Initially, we had no idea how to complete the key point detection task.
    Later, after checking literature, reading papers, group discussions, asking teachers for opinions, etc., an algorithm with a relatively high accuracy rate was designed.

I learned a lot from it.

  1. cooperation and communication is importrant for team work. Team members should have a common goal and work hard for it . As a leader, I should be gentle and kind, and very responsible. I always encourages everyone to share their opinions.

  2. I learn how to solve a problem in a better way.

    First of all, you must analyze the problem to be solved, draw up a preliminary idea,

    Then, check the literature, ask teachers and classmates, and further determine the detailed solution.

    In this process, the most important thing is that the team must be creative and good at rigorous thinking.

选择本校读研的原因

　Thanks for your question!

　　Well, what attracts me most is your resounding influence in the field of CS and AI . During my undergraduate period, I have shown some interest in AI and tried to pursue further study in this area. As I know, this is the predominant part in your school. And, you have so many excellent teachers and I want to be guided by them in theory and practice.

　　Location is another critical factor prompting my decision. Beijing, as the capital city of China, has provided various study and work resources for our young people, which I would never have thought without coming here. Though I may be encountered with fierce competition and harsh challenges, I still like to embrace its vigor and vitality.

　　The last one I want to say, this is a comprehensive university, which,I believe, can give students comparatively all- round development. I’m looking forward to studying here!

自己的优缺点

Well,Thanks for the question!

　　In my view, I’m a pragmatic person(务实的),willing to focus on the current thing and optimize it. Recalling my undergraduate times when I was doing some research or finishing some task, I would always amend them for many times until I’m totally satisfied. I can bear hardships(克服困难) and cooperate well with other people, with all the makings of awell-done job.This may be trained by the teamwork and practice inside and outside the campus.

　　Nobody is perfect.I can never eschew my shortcomings. As a matter of fact, I‘m not good at time management, which may result from my insistence on one thing,I guess.Sometimes,when I’m immersed in my task,I will not stop it until it has been completed. As a result, my schedule is often tight, sometimes losing balance between life and study. I am trying hard to get over with this and act myself decisively and effectively.

最喜欢的书/专业课

最喜欢读的书

Up to now I have read a lot of books， for example，magazines，novels and storybooks and so on．But one of the books that I like best is My Life Story．It was created by an American writer—Helen Keller in 1902．She was a blind，deaf and dumb person．In the book，she wrote that she had not been able to see，hear or speak since the age of one year and seven months．This unusual thing made her very sad．When she was seven years old，she knew Miss Sullivan，her good teacher．Helen was getting happier every day．Then，Miss Sullivan helped her learn how to write English words．At first，Miss Sullivan wrote some words on Helen’s hands with her own fingers again and again．Helen was a very diligent girl．Because of this，she tried as much as possible to remember words．After that，she wrote and published many famous works．My Life Story is one of them.

​ Therefore, when I select a team in the future, responsibility and the efficiency of teamwork will be the main elements for me. Only fighting side by side can bring success.

​ My Life Story described her hard struggle to become an outstanding writer and educationist of the world． It shows us a universal truth：“Nothing is difficult if you put your heart intoit！”This is why I like it best．

最喜欢的课程是编译原理

Compilation principle is an important professional course for computer majors, which aims to introduce the general principles and basic methods of compiling program construction.

The content includes language and grammar, lexical analysis, grammatical analysis, grammar-guided translation, intermediate code generation, storage management, code optimization and target code generation.

The interesting and challenging course content has made me gain a lot.I learned hwo to code a compiling program.

It’s amazing!

AI的含义，应用，发展趋势，发展难点，应用案例之类的

​ The full name of AI is artificial intelligence, which can be explained as machines that are built to act and behave like human, contains features of human like facial recognition, voice recognition, decision making, vision system etc.

发展趋势&& 发展难点

At present, AI has the following problems

  1. Data cost, a successful and effective deep learning network requires massive data support.

  2. The interpretability of the model.
    At present, most machine learning models are “black box” models, which are difficult for people to understand

As for development trend, I think there two points as follow:

  1. AI chips development

Even fast and advanced CPUs cannot increase the speed of AI models. It is necessary to develop smaller and more powerful embedded chips to run better algorithms for real-time tracking, facial recognition and other applications.

  1. AI edge computing and integrated development of the Internet of Things

I n short, many AI research results have profoundly changed people’s lives. In the future, the development of AI will be faster and will have a greater impact on people’s lives, work and education.

他们的未来是什么?

One of the future trends of computer science is artificial intelligence, which is the study and artificial simulation of human thoughts, which will eventually enable machines to think like humans. Serve humanity and help people solve problems.

After all, people thought it was unique, there are feelings, there are a variety of character, this will be very difficult to achieve in the machine.In fact, to do the same as the human thinking machine, the only one of the artificial intelligence, is by no means all. Through the study of artificial intelligence, can resolve all kinds of scientific problems, and promote the development of other science, the artificial intelligence is the best!

I believe that the science of artificial intelligence is waiting for humanity to explore it step by step the real connotation.’

描述你参加过的最好的/最差的团队

　　The best team I have ever participated in is the Law School Society during my undergraduate study. This is a very warm collective. As a whole, we have a common goal, and everyone works hard for it.At the same time, we have a very good leader, he is gentle and kind, and very responsible. He always encourages everyone to share their opinions, we often have brainstorm, and he will use his experience and vision to help us summarize to find the best way. After the leader assigns the tasks, each of us will actquickly, and the strong action makes the team efficient, so the activities orprojects held by us are always exceptionally successful. Everyone in the society is proud of it.

　　In contrast, I have participated in acharity team with the goal of helping the old people who have no children to take care of them. However, the people involved in this team do not have enough responsibility. The activities are often to be half-finished. The leaders in the team often find various reasons to cover up their mistakes. Members always don’t take their tasks seriously. The whole team is in disarray.

　　Therefore, when I select a team in the future, responsibility and the efficiency of teamwork will be the main elements for me. Only fighting side by side can bring success.

专业问题

快速排序

​ Quicksort is a divide-and-conquer algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort.[4] The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.

​ Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

hash

​ In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type. It can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.

​ In many situations, hash tables turn out to be on average more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.

U-net

Unet原文

​ It consists of a contracting path (left side) and an expansive path (right side). The contracting path follows the typical architecture of a convolutional network. It consists of the repeated application of two 3x3 convolutions (unpadded convolutions), each followed by a rectified linear unit (ReLU) and a 2x2 max pooling operation with stride 2 for downsampling. At each downsampling step we double the number of feature channels. Every step in the expansive path consists of an upsampling of the feature map followed by a 2x2 convolution (“up-convolution”) that halves the number of feature channels, a concatenation with the correspondingly cropped feature map from the contracting path, and two 3x3 convolutions, each followed by a ReLU. The cropping is necessary due to the loss of border pixels in every convolution. At the final layer a 1x1 convolution is used to map each 64- component feature vector to the desired number of classes. In total the network has 23 convolutional layers.

Posted on Edited on In

计算机网络

数据链路层

​ 介质访问控制子层：主要任务是为每个节点隔离来自同一信道上其它节点所传送的信号，以调节活动节点的传输。

​ 常见的介质控制方法有：信道划分介质访问控制，随机访问介质访问控制和轮询访问介质访问控制，

CSMA协议(carrrier sense multiple access)

​ CSMA/CD：

​ 发送前先侦听，等待信道变为空闲时再发送，碰撞检测就是边发边侦听，如果遇到碰撞时，就发送一个48bit的拥塞信号

​ ”先听后发，边听边发“

​ 适用于总线型网络或者半双工网络。

最小帧长的计算：

​ 原理是 因为是边发边侦听，所以要确保发送站在发送数据的同时，能检测可能存在的冲突，需要在发送完帧之前能够收到自己发送出去的数据(对方发出的拥塞信号)

1
2
最小帧长 = 2* 总线传播时延 * 数据传输率
总线传播时延 = 信道长度 * 信道宽度

CSMA/CA协议

适用于无线网络。

TCP 流量控制和差错控制

-==流量控制：是一个速度匹配服务，匹配发送方的发送速率和接收方的读取速率==

-==TCP 拥塞控制： 是为了防止过多的数据注入网络，保证网络中的路由器或链路不致过载。拥塞往往表现为通讯时延的增加。==

流量控制和差错控制的共同点：都是可以通过控制发送方发送数据的速率来达到控制效果。

区别在于 拥塞控制是为了让网络能够承受现有的网络负荷，是一个全局性的过程，涉及所有的主机，所有的路由器以及降低网络传输性能的有关因素；相反流量控制只是单纯的 接收端控制发送端。

TCP拥塞控制算法： 慢开始，拥塞避免，快重传，快恢复。

Http协议

数据结构

关于排序算法

​ 元素移动次数与关键字的初始排列次序无关的是：基数排序

​ 元素比较次数与关键词的初始序列无关的是 选择排序

​ 算法的时间复杂度与初始序列无关的是 选择排序

KMP算法

二叉树

计算机组成原理

浮点运算

Cache结构

cache地址映射

​ cache结构： 标记项|数据项

​ 标记项：标记地址+有效位+脏位(可选,写回法)+替换计数位(可选)

  1. 直接映射方法

    ​ 直接映射的地址结构： 标记地址+cache块号+块内地址

  2. 全相联映射

    ​

  3. 组相联映射

Cache中替换算法和写策略

写策略

​ 命中时，

​ 写直达：对cache写命中时，必须把数据同时写入主存中。

​ 写回法：只修改cache中，不立即写回，之后被换出时，写回到主存

​ 非命中时

​ 写分配：加载主存中的块写到cache中，然后之后更新主存中的块

​ 写不分配：直接写到主存中，不加载到内存中

访问冲突

内存地址计算

内存地址 = 基址寄存器+形式地址

操作系统

中断

死锁

[之前OS的复习笔记]

死锁的4个必要条件：资源独占，不可剥夺，保持申请，循环等待

① 资源独占。一个资源在同一时刻只能被分配给一个进程。如果某一进程申请某一资源，该资源正在被另外的某一进程所占有，则申请者需要等待，直到占有者释放该资源。

② 不可剥夺。资源申请者不能强行地从资源占有者手中夺取资源，即资源只能由其占有者在使用完后自愿地释放

③ 保持申请。进程在占有部分资源后还可以申请新的资源，而且在申请新资源的时候并不释放它已经占有的资源。

④ 循环等待。存在一个进程等待序列{p1， p2，…， pn}，其中 p1 等待 p2 所占有的某一资源，p2 等待 p3 所占有的某一资源……pn 等待 p1 所占有的某一资源。

死锁处理：死锁预防，死锁避免，死锁恢复，死锁检测

  • 死锁预防
    • 对进程有关的资源活动加以限制，所有进程遵循这种限制，即可保证没有死锁发生。
    • 优点： 简单，系统不需要做什么。 缺点： 对进程的约束比较难保证，如果违反时就有可能发生死锁
    • 预先分配法[系统：如果可以满足，全部分配；否则一个也不分配，破坏保持请求的条件]，
    • 有序分配法[按照资源编号由小到大的次序申请资源,破坏循环等待条件]
  • 死锁避免
    • 它不会对于申请进程有关资源的命令施加任何限制，而是对于进程发出的每一个系统能够满足的资源申请命令实施动态检查，并根据检查结果决定是否==实施资源分配==。
    • 银行家算法(Need数组，需要知道程序运行所需资源总量信息)
  • 死锁检测(死锁已发生时，检测并解决)
    • 死锁检测(在进程等待时检测，定时检测。。)
    • 死锁恢复：资源剥夺法，进程撤销法，进程回退法(要求系统保持进程的历史信息)

缺页发生的调度

​

Posted on Edited on

==感觉时间真的是不够了，呜呜呜，裂开都不够的

尽管在等通知的同时，自己很焦急（头都快炸了），还是要把该做的做好

今天没刷几道题目，感觉就是练练手，重新捡起来之前断掉的机试训练。

aa，还需要提醒的是，哈工深好像有笔试题目，自己要把简单的专业课给过一遍，计算之类的，能学多少是多少吧

/=\ 感觉机器学习数据挖掘之类的学习起来好有意思！！gg

在这里列一下我之后机试的计划

  • 贪心算法(背包问题==我想起来之前参加pat时候遇到的问题)
  • 动态规划
  • KMP
  • 大整数运算（一般作为签到题）
  • 二分算法
  • 之后就是针对院校进行机试

加油！今天的收获

  1. 万能头文件

    1
    #include<bits/stdc++.h>

  2. 关于memset和fill的用法

    -> 柳神的blog

    数组

1
2
3
4
5
6
7
8
9
10
11
12
//关于二维数组的初始化

    int dp[1000][1000];
//memset(str_ptr, val , len ); //好像只能初始化为0或者1
    memset(dp[0],0,sizeof(dp)/sizeof(int)); //只能初始化为0 

//fill(str_ptr,end_ptr, val)
fill(dp[0],dp[0]+1000*1000,4);

//一维数组
    int dp[1000];
    fill(dp,dp+1000,4);

​ vector

1
2
3
fill(v.begin(), v.end(), 要填入的内容);
vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
fill(v.begin(), v.end(), -1);
  1. C/C++关于字符串的读取

题目：[日期差值]

这里需要判断闰年： 年份能够被100整除，同时被400整除； 能被4整除，但是不能被100整除

1
2
3
4
5
6
bool isRui(long long y1){
    if((y1%400==0 &&y1%100==0) || (y1%4==0 && y1%100!=0)){
        return true;
    }
    return false;
   }
1
2
3
4
5
6
7
8
9
//利用char数组
    char date1[20],date2[20];
    scanf("%s", date1);
    scanf("%s", date2); //按照空格换行符作为分隔符

//c++ string类，好象是不需要括头文件的，不知道为什么我之前写的是一直出错了 gg
    string s1,s2;
    cin>>s1>>s2;
    cout<<s1<<" "<<s2;

  1. 动态规划经典题型的复习

    ==自己最开始忘记设置dp数组的边界，调试了好久

    最大连续子序列和

    LIS最长不下降子序列

    LCS最长公共子序列

    最长回文子串**可以多刷

  2. 分块思想

    如何维护一个栈，可以在线取出其中第K大的元素

  3. 开坑线段树

Posted on Edited on

methods_弹窗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8"></meta>
    <title>index</title>
<script src="https://unpkg.com/vue"> </script>

</head>
<body>


    <div id ="app">
        <!---生成一个按钮-->
        <button v-on:click="sayHi"> click me </button>

    </div>
    <script> 
        var vm = new Vue({
            el: "#app",
            //model: 数据模型，泛指后端进行的各种业务逻辑和数据操控，mvvm
            data: {
                message:"this'a a blog"
            },
            //事件
            methods: { //方法必须定义在Vue的Method对象中,为了达到监听的效果，必须传递event参数
                sayHi: function(event){
                    alert(this.message);
                }

            }
        });
    </script>
</body>
</html>

双向数据绑定

view　通过 <input v-model= “item”>将用户的输入绑定到名外item的数据上

​ 通过,绑定显示后台名为item的数据

​ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8"></meta>
    <title>index</title>
<script src="https://unpkg.com/vue"> </script>

</head>
<body>


    <div id="watch-example">
        <p>
            Ask a yes/no question:
            <input v-model="question">
        </p>
        <p> 
            {{ answer }}
        </p>
    </div>


<script src="https://cdn.jsdelivr.net/npm/axios@0.12.0/dist/axios.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/lodash@4.13.1/lodash.min.js"></script>
<script>
    var watchExampleVM = new Vue({
        el: '#watch-example',
        data: {
        question: '',
        answer: 'I cannot give you an answer until you ask a question!'
    },
    watch: {
    // 如果 `question` 发生改变，这个函数就会运行
        question: function (newQuestion, oldQuestion) {
            this.answer = 'Waiting for you to stop typing...'
            this.debouncedGetAnswer()
        }   
    },
    created: function () {
    // `_.debounce` 是一个通过 Lodash 限制操作频率的函数。
    // 在这个例子中，我们希望限制访问 yesno.wtf/api 的频率
    // AJAX 请求直到用户输入完毕才会发出。想要了解更多关于
    // `_.debounce` 函数 (及其近亲 `_.throttle`) 的知识，
    // 请参考：https://lodash.com/docs#debounce
        this.debouncedGetAnswer = _.debounce(this.getAnswer, 500)
    },
    methods: {
        getAnswer: function () {
            if (this.question.indexOf('?') === -1) {
                this.answer = 'Questions usually contain a question mark-"?" . ;)'
            return
        }
        this.answer = 'Thinking...'
        var vm = this
        axios.get('https://yesno.wtf/api')
            .then(function (response) {
            vm.answer = _.capitalize(response.data.answer)
            })
            .catch(function (error) {
            vm.answer = 'Error! Could not reach the API. ' + error
        })
    }
  }
})
</script>

</body>
</html>

vue组件

用户自定义的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8"></meta>
    <title>index</title>
<script src="https://unpkg.com/vue"> </script>

</head>
<body>
    <div id="app">
        <!--ｖ-bind后面不能加空格 -->
        <!--v-bind:a=b,将实参b与形参a绑定，类似于函数调用，这里item是v-for遍历的结果-->
        <qinjiang v-for="item in items" v-bind:qin="item"> </qinjiang>
    </div>
    
    
    <script> 
       //定义一个vue组件
        Vue.component('qinjiang',{
                //props:定一个形参，　template：利用{{}}，取形参中的值来显示一些内容
                props: ['qin'],  
                template: '<li>{{qin}}</li>'
        });

        var vm = new Vue({
            el: "#app",
            //model: 数据模型，泛指后端进行的各种业务逻辑和数据操控，mvvm
            data: {
                items: ["java","linux","前端"]
            }
        });
    </script>
</body>
</html>

Axios异步通信

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8"></meta>
    <title>index</title>
<script src="https://unpkg.com/vue"> </script>
<script src="https://unpkg.com/axios/dist/axios.min.js"></script>

</head>
<body>
    <div id="vue">
        点我
        <div>
            {{info.name}}
        </div>
        <div>
            {{info.address.street}}
        </div>
    </div>

    <script type="text/javascript"> 
        var vm = new Vue({
            el: '#vue',
            data(){
                return{
                    //请求的返回参数格式必须和json串一样,return的只是一个函数，data()方法会自己捕获
                    info:{
                        name : null
                        address:{
                               street: null,
                                city: null,
                                country: null
                        }
                    }
                }
            },
            //
            mounted(){//钩子函数
                axios.get('data.json').then(response=>(this.info=response.data));

            }
        })
    </script>
</body>
</html>

对应的json文件data.json

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
{
  "name" : "狂神说java",
  "url" : "htp://baidu.com",
  "page" : 1,
  "isNonProfit" : true,
  "address" : {
    "street": "含光门",
    "city" : "陕西西安",
    "country": "中国"
  },
  "links": [
    {
      "name" : "B站",
      "url": "https://www.bilibili.com/"
    },
    {
      "name": "4399",
      "url": "https://www.4399.com/"
    },
    {
      "name": "百度",
      "url": "https://www.baidu.com/"
    }
  ]
}


计算属性

计算属性的重点突出在属性两个字上，首先它是一个属性，其次它有计算的能力，这里计算就是一个函数；它能够将计算结果缓存起来．

​ 内存中执行，虚拟Dao

计算属性的主要特征就是为了将不经常变化的计算结果进行缓存，以节约我们的系统开销．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8"></meta>
    <title>index</title>
<script src="https://unpkg.com/vue"> </script>
<!-- <script src="https://unpkg.com/axios/dist/axios.min.js"></script> -->

</head>
<body>
    <div id="vue">
        <p> {{currentTime1()}}</p>
        <p> {{currentTime2}}</p>
    </div>

    <script type="text/javascript"> 
        var vm = new Vue({
            el: '#vue',
            data:{
                message: "hello!!"
            },
            methods:{ //函数,调用时需要带括号
                currentTime1: function(){
                    return Date.now();
                }
            },
            //method中的方法名和computed中的属性名不建议一致，methods优先级更好
            computed:　{
                currentTime2: function(){
                    return Date.now(); //计算属性，只有第一次被调用时，进行计算，之后直接在内存中查找结果
                }
            }
        })
    </script>
</body>
</html>

VUE插槽(slot)//内容分发

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8"></meta>
    <title>index</title>
<script src="https://unpkg.com/vue"> </script>
<!-- <script src="https://unpkg.com/axios/dist/axios.min.js"></script> -->

</head>
<body>
    <div id="vue">
        <todo>
            <todo-title slot="todo-title" :title="title"></todo-title>
            <todo-items slot="todo-items" v-for="item in todoItems" :item="item"></todo-items>
        </todo>
    </div>

    <script type="text/javascript"> 
       Vue.component("todo",{
            template: '<div>\
                            <slot name="todo-title"></slot>\
                            <ul>\
                                <slot name="todo-items"> </slot>\
                            </ul>\
                        </div>'
       });
       //通过指定solt的name来绑定组件
       Vue.component("todo-title",{
           props:['title'],
           template:'<div>{{title}}</div>'
       });

       Vue.component("todo-items",{
            props:['item'],
            template: '<li>{{item}}</li>'
       });
        
       var vm = new Vue({
            el:"#vue",
            data:{
                title: "what do you like?",
                todoItems: ["happiness","movie","runnig","reading"]
            }
       });
    </script>
</body>
</html>

自定义事件

通过以上代码不难发现，数据项在Vue的实例中，但删除操作要在组件中完成，那么组件如何才能删除Vue实例中的数据呢?此时就涉及到参数传递与事件分发了，Vue为我们提供了自定义事件的功能很好的帮助我们解决了这个问题;

使用this.$emit (‘自定义事件名’,参数)

vue1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8"></meta>
    <title>index</title>
<script src="https://unpkg.com/vue"> </script>
<!-- <script src="https://unpkg.com/axios/dist/axios.min.js"></script> -->

</head>
<body>
    <div id="vue">
        <todo>
            <todo-title slot="todo-title" :title="title"></todo-title>
            <todo-items slot="todo-items" v-for="(item,index) in todoItems" 
                :item="item" v-bind:index="index" v-on:remove="removeItems(index)" ></todo-items>
        </todo>
    </div>
    <!--：是v-bind的简写，通过v-on将vue中的函数和组件中的自定义方法进行绑定，key是绑定remove中用到的参数-->
    <script type="text/javascript"> 
       Vue.component("todo",{
            template: '<div>\
                            <slot name="todo-title"></slot>\
                            <ul>\
                                <slot name="todo-items"> </slot>\
                            </ul>\
                        </div>'
       });
       //通过指定solt的name来绑定组件
       Vue.component("todo-title",{
           props:['title'],
           template:'<div>{{title}}</div>'
       });

       Vue.component("todo-items",{
            props:['item','index'],
            template: '<li>{{item}}     <button @click="remove"> delete </button></li>' ,
            methods: {
                remove: function (index){
                    this.$emit('remove',index) //这里的remove的名称就是自定义的函数名
                    // alert("111");
                }
            }

       });

       var vm = new Vue({
            el:"#vue",
            data:{
                title: "what do you like?",
                todoItems: ["happiness","movie","runnig","reading"]
            },
            methods:{
                removeItems: function(index){
                    this.todoItems.splice(index,1);//利用javascript中的语法
                }
            }
           
       });
    </script>
</body>
</html>

Posted on Edited on In

机试的难度

个人认为，机试难度可以分四个等级：

第一级，清北难度，能通过且取得不错成绩的很多都是打ACM竞赛的大佬，没受过专业训练很难拿高分，这个难度下题目很多都是ACM竞赛等级。不过北大的难度貌似没有那么高。

第二级，华五难度，题目涉及基础算法和数据结构，如果只会暴力算法无法通过机试，但如果你刷过一些算法和数据结构的题目，非低分通过机试应该不成问题。

第三级，基础难度，以北航华科为代表，题目涉及大量基础数据结构和编程细节，主要考察编程而非算法能力，个人认为接触过基础数据结构且编程细心的同学应该能够通过。但这些高校往往会限定标准C编程，这点还要注意。

第四级，不进行机试，以国防科大、中科院自动化所为代表，这些学校只有面试没有机试。
刷题

整理出一些典型题目或“板子”以备考前复习。

南大计算机 300分的题目一共三道题，每道题100分、通过样例点给分（每道题10个样例点），是在线OJ形式、可以看到自己的实时排名（和浙大类似）,动态规划多一些 120以下的同学貌似被淘汰了、同学190都是专硕。
浙大 三小时四道英文题，题目难度号称PTA甲级难度（实际难度是PTA乙级到甲级之间），题目分值是20,25,25,30这样.题目是OJ形式，根据通过的样例点得分，不计罚时，采用PTA的系统，能够看到自己的实时得分和排名
中科大 机试和上交的机试形式差不多，都是非OJ形式。具体而言，三小时做五道算法题，开始的时候给你发纸质的题目和示例（中文），然后自己写程序自己想样例测试，最后工作人员拷走你电脑上的程序。题目采用C/C++，允许使用STL，编译器有VC,VS,code blocks, dev c++等。题目样例没有全通过的话最后会有老师阅卷打分，这点和北航一样。
 2019
北航 题目采用C/C++，允许使用STL，编译器有VC,VS,code blocks, dev c++等。虽然之前的通知和宣讲会说最好是C标准编程，但实际上都是可以用的。然而北航的评测系统不是OJ形式，只能显示你提交的代码编译是否通过，具体能不能AC只能靠本地自己编用例测试了（所以一定要细心！！）。不过还好，如果你有一道题没有AC的话，老师会查看你的源代码，根据你代码体现的思想和编码习惯什么的给分，所以就算做不完也一定要记得提交呀！
上交 上交的机试不是OJ形式的，而是发给你英文的纸质题目描述和一个样例（运行时间10s以内都ok），自己编写、本地调试，结束后由老师过来把源代码和可运行的exe文件拷走，可选择的编译器有VS/code blocks/DEV C++等
北深
清深

参考: https://blog.csdn.net/qq_38633884/article/details/97178586

自动化所:问数学和机器学习多一些，自动化所只有面试没有机试

中科大的考核机制：学院机试+学院面试+课题组考核，其中学院的机试、面试小分和学院考核总成绩都达标即可获得优营资格，听过优营比例很高的，我们这届计算机夏令营貌似有六七十人

二分图模板题

https://www.cnblogs.com/shenben/p/5573788.html

位运算

[link]

找出只出现一次的数

给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。

所有的数进行异或

m的n次方

也可以参考快速幂的做法

1
2
3
4
5
6
7
8
9
10
11
12
//快速幂的递归写法,复杂度为 logb 
long long mypow(long long a,long long b){
    if(b==0)   return 1;
    else{
        if(b&1==0){//为偶数
            return mypow(a,b/2)*mypow(a,b/2);
        }
        else if(b&1==1){
            return a*mypow(a,b-1);
        }
    }
}

找出不大于N的最大的2的幂指数

​ 把N的二进制中最左边的 1 保留，后面的 1 全部变为 0, 如何实现?

​ ans=最左侧的1,eg: N=19 = 0001 0011, ans = 0001 0000

代码实现:

1
2
3
4
5
6
7
int findN(int n){
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8 // 整型一般是 32 位，上面我是假设 8 位。
    return (n + 1) >> 1;
}

上交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1. 给定两个英文单词，每次操作可以删去任一单词中的任一字母，求使两个单词最终一样的最少操作次数
Eg：给定eat和sea，最少操作次数为2。
输入：eat/sea
输出：2

2. 商店中有若干商品，它们也会打包在一起优惠出售，现给出需要购买的商品数量，求最低购买价格。要求购买的商品数量刚好符合题目要求。
eg：
输入信息：[2,4],[[3,0,5],[1,2,10]],[3,2]
题目解释：
输入：第一个矩阵是商品单买的价格，第二个矩阵为各种打包售卖时的数目与价格，第三个矩阵是各类商品需要购买数量
输出：最低价格
举例：商店中有A、B两种商品，A价格为2元，B价格为4元；优惠组合一包含3个A商品，0个B商品，共5元；优惠组合二包含1个A商品，2个B商品，共10元；现在要购买3个A商品，2个B商品；
答案：最低价格是，购买1个优惠组合一（含3个A、0个B），5元；再单独购买2个B，8元；共计13元
输出信息：13

3. 一个有序三元组（a,b,c）, 1<=a<=X, 1<=b<=Y, 1<=c<=Z，且a，b，c皆为正整数。
 给定X,Y,Z求所有能够形成三角形的(a,b,c)的数目。(3,4,5)和(3,5,4)为两个三角形。
 输入:X Y Z（三个数都在1到10的九次方之间）
 输出数量。输出结果对1000000007取模。
 样例:
 输入：2 3 3
 输出：9

Posted on Edited on In

判断一个无向图是否是一棵树

树的定义是连通的有向无环图，所以需要判断图是否是连通而且没有环，一次dfs或者bfs即可，遍历时需要加访问标记,时间复杂度是O(V) //每条边都遍历了一次.

各种排序算法的稳定性，复杂度的对比，简单思路

[link]

高度k的树最少节点数

感觉不是很严谨，如果没有规定，树可以退化成链表,最少是k个点。

对于完全二叉树而言，高度为h的二叉树 2^h个结点，至少有 2^h 个结点

对于高度为h的m叉树至多包含 (m^h-1)/(m-1) 个结点。[等比数列]

哈夫曼编码(huffman code)

在含有n个带权叶结点的二叉树中,其中带权路径长度(WPL)最小的二叉树被称为哈夫曼树。

含有n个叶子结点的huffman树，一共有2n-1个结点，huffman中只包含叶子结点和度为2的点.

可以用堆来构造。，时间复杂度是O(nlogn)

构建过程

huffman编码：

​ 可变长编码，把字符出现的频率看作是结点的权重

后缀表达式

运算符紧跟在操作数的表达式，没有括号，运算符之间不存在优先级的差别，计算过程完全按照运算符出现的先后顺序进行。

中缀转后缀

link

后缀表达式计算

  • 从左依次读取后缀表达式的一个符号
    • 如果是操作数，则压栈
    • 如果是运算符，则从栈中连续弹出两个元素，进行相应的运算，并将结果压入栈
  • 如果读入的是结束符，则栈顶就是计算结。

快速排序的时间和空间复杂度

快速排序的核心思想是　partition操作（分治策略）

  • 选取一个基准元素（pivot）

  • 比pivot小的放到pivot左边，比pivot大的放到pivot右边

  • 对pivot左边的序列和右边的序列分别递归的执行步骤1和步骤2

    一次partition的时间复杂度是O(n). 当每次S(n)划分后，左右两个序列变成S(1)和S(n-1)，快排退化成冒泡，时间复杂度变成O(n*n)

    所以每次partition可以利用随机算法选择基准元素。

    快排为什么会快？

    ​ 在堆排序中，存在大量的随机存取(包括一些无效的swap操作)，而在快速排序中，数组指针的移动都是在相邻的区域内的，符合空间局部性的特点，经常访问cache中的数据，cache比主存快的多。

堆及其应用

[link]

堆维护一个偏序关系，能够支持的操作是

1
2
3
4
void up(int index); //尝试将index元素上浮
void down(int index);　//尝试将index处元素下沉
void inser(int val);//直接在堆的最末尾插入值为val的结点，之后为并使用up(len)操作，维护堆的有序性
void delete(int index);//删除index处的元素，实现是先将index处元素和堆最后的元素交换，删除最后的元素，并采用down维护堆的操作

应用：　1.优先级队列 　2.堆排序

时间复杂度//空间复杂度

​ 时间：一个语句的频度是指该语句在算法中被重复执行的次数，算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要是为了分析T(n)的数量级。

​ 空间：算法所耗费的存储空间，它是该算法问题规模n的函数

​ 算法的特点是：有限性，可行性，确定性，输入，输出.

广义表

[link]

NP和NPC问题

[link]

  • P类问题：能在多项式时间内可解的问题。
  • NP类问题：在多项式时间内“可验证”的问题。也就是说，不能判定这个问题到底有没有解，而是猜出一个解来在多项式时间内证明这个解是否正确。P类问题属于NP问题，但NP类问题不一定属于P类问题。
  • NPC问题：存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。其定义要满足2个条件：
    • 它是一个NP问题
    • 所有的NP问题都可以规约到它
  • NP-hard问题: 即所有的NP问题都能约化到它，但是他不一定是一个NP问题

如何判断一个树是否是一个完全二叉树

​ 通过层次遍历的方式：

基本思路是层次遍历该树，从第一个度不为２的结点开始，之后的结点的度都为0．

[link]