sin(x)

Page 4 of 10

统计学习方法:习题笔记

花了一些时间刷了一遍李航博士的《统计学习方法》,于是就有了一篇课后习题解答。由于自己的智商又低数学又差,很多难度较大的习题实在没有能力完成了。

第1章 统计学习方法概论

  • 1.1 说明伯努利模型的极大似然估计以及贝叶斯估计中的统计学习方法三要素。伯努利模型是定义在取值为0与1的随机变昼上的概率分布。假设观测到伯努利模型n次独立的数据生成结果,其中k次的结果为1,这时可以用极大似然估计或贝叶斯估计来估计结果为1的概率。

Continue reading

uCore中实现匿名管道

进程间通信是操作系统需要提供的一项重要功能,其中管道又是最为基础的进程间通信方式之一。管道的作用相当于提供了一个先进先出的队列,进程可以向管道中写入数据也可以从中读取数据。本文将介绍如何在uCore操作系统实验八的基础上实现匿名管道。

管道设备的源代码位于pipe文件夹下,测试程序源代码为pipe.c

管道简介

管道技术是进程间通信的一种方式,和文件不同,管道以及管道的变种不会占据任何的磁盘空间,而只是使用了内核中的一个缓冲区。如果缓冲区满了,那么进程会被阻塞。管道通常是单工的,通常只有一个发送端和一个接收端。当然,多个发送端或者多个接收端也是完全可行的。

Continue reading

uCore中实现Buddy和Slub算法

这是本学期创新实践课程uCore OS实验2的挑战部分,代码实现可见:buddy.cbuddy.hslub.cslub.h

Buddy System分配算法

初始化

在Buddy System中,空间块之间的关系形成一颗完全二叉树,对于一颗有着n叶子的完全二叉树来说,所有节点的总数为。也就是说,如果Buddy System的可分配空间为n页的话,那么就需要额外保存2n-1个节点信息。

Continue reading

算法笔记:后缀自动机

本文改编自MAXimal :: algo :: Суффиксный автомат. Построение и применения的Google机翻版(什么玩意儿)

后缀自动机是一个处理字符串相关问题很有用的工具,例如检查一个字符串在另外一个字符串中是否出现过,计算一个字符串中不同子串的数量——它们都可以在线性时间内被解决。

从直观上看,后缀自动机保存着所有子串的信息,对于长度为n的字符串来说,它的后缀自动机只需要的空间,同时构造它的时间复杂度为

Continue reading

算法笔记:后缀数组

本文改编自斯坦福大学CS 97SI: Introduction to Programming Contests的教学材料Suffix arrays – a programming contest approach

在算法竞赛中经常会遇到很多有关字符串子串的问题,或者是字符串后缀的问题,因此也就需要一种高效的数据结构及算法来处理这个问题。

什么是后缀数组?

为了更好地理解后缀数组,我们先来了解一种特殊的trie——后缀trie。一棵trie树是用来储存字符串的数据结构,其中每一个节点有和字母表大小一样多的孩子节点。本文的例子中只考虑小写字母,那么每个节点也就至多有26个孩子节点。每一条从父节点到孩子节点标注上一个字符,从根节点到叶子节点路径上标注的字符组合起来就是trie中保存着的一个字符串。显然地,在trie中查找一个字符串只需要时间复杂度(m是字符串长度),叟搜索时间和其中的字符串数量无关,这是一个实现字典的绝佳数据结构。

Continue reading

« Older posts Newer posts »

Copyright © 2019 sin(x)

Theme by Anders Noren, host by Coding PagesUp ↑