MIT-Missing Semester01-课程概述 + Shell
这节课来自MIT的The Missing Semester of Your CS Education (2020)，旨在教会学生如何更有效地使用计算机工具，以改善开发工作流程。
课程亮点本课程将涵盖广泛的工具和技术，帮助学生更高效地工作。重点不仅仅是软件开发，还包括如何将计算机作为学习和研究的工具。关键点包括：
Shell 和终端基础：课程将介绍如何使用Shell和终端与计算机交互，逐步掌握更高级的工具和技术。
命令行的重要性：命令行工具和基于文本的界面能够提供极大的灵活性和效率，课程对此进行了重点强调。
Shell 概述Shell提供了一个基于文本的接口，用户可以通过输入命令来执行程序。以下是一些简单的命令示例：
1234# 输出文本echo "Hello, World!"# 显示日期date
命令参数与参数传递命令可以接受参数和选项来改变其行为，例如：
1echo "这是一个测试"
对于包含空格的参数，可以使用引号确保参数作为一个整体被传递：
1echo "This is a string with spaces"
环 ...
算法导论-吃灰中
属于早就买了但是没有看下去的欲望，记录下，留个flag
计算几何-算法与应用-阅读总结？
邓俊辉老师的计算几何课程的教材，也是他自己翻译的，翻了下没有看下去的欲望，也比较老了，有缘再看。
清华大学-计算几何-总结
邓老师在他的数据结构课堂就安利了他的这门计算几何课程，这个课程是数据结构课程的延申，可以说是数形结合版的数据结构和算法课。
趁着疫情在家，写毕业论文的同时也听了邓老师的这门课。收获颇多：计算几何自上世纪七十年代由Shamos和Hoey发表的一篇计算平面点集Voronoi图的论文开始，现在已经发展为了独立的学科。计算几何研究中最主要的目的就是开发出高效的算法以及数据结构来解决一些关于基本几何基元(geometric primitives)：点，线段，多边形，多面体等的问题。其中一些问题看起来是如此的简单，以至于它们直到计算机出现后才被认为是个问题。例如二维中典型的相交问题：给定平面上n条直线段，确定所有的相交点。如果暴力的逐个计算所有$n(n一1)／2$对线段对它们两两之间的相交，其计算复杂度是$O(n^2)$。幸运的是，计算几何中的经典算法可以将复杂度降到$O(nlogn)$。需要注意的是，计算复杂度是计算几何中的核心问题。尤其是在现实中，假如一个数据集中有上百万条线段，计算复杂度为$O(n^2)$和$O(nlogn)$的算法对比，他们的求解时间是几周和几秒之间的区别。典型的计算几何问 ...
清华大学-计算几何-点集三角化
1、Point Set Triangulation
目标：对一系列的点进行三角化(网格化)
当我们有一系列点集时，我们需要对这些点集数据进行结构化。对点集进行结构化的一个重要的方法就是对这些点进行三角化。
这里的对角线分为两类，如上图所示，深绿色的外面的边对应于原来的凸包，另外一些内部的浅绿色的线则是凸包的内对角线。
所谓的点集的三角化，其实就是对这个点集所对应的凸包的区域进行剖分。
对于点集的三角化并不唯一
如果一个点集的点数目是n，如果凸包的size记做h，那么任意一个极大的对角线的集合都是由3(n-1)-h条对角线组成；这些对角线剖分出来的三角形的数目为2(n-1)-h。
每新增一个点，大致就增加三条对角线，两个三角形。
边翻转（Edge Flipping）：如上面不唯一的剖分所示，从左边的竖着的那条红色的内对角线变成右边横着的内对角线的这个操作称作边翻转。每进行一次边翻转就会得到一个不同的剖分方案。
剖分算法的界
如图所示，若我们已经有两个做好剖分的子集，那么根据第一章凸包算法找上下边界的Zigzag方法，我们就可以得到两个子集连接后的三角化，时间复杂度为O( ...
清华大学-计算几何-维诺图
本周目标：对空间进行剖分，然后对这个几何体进行探究。
Voronoi图（维诺图）
1、Terminologies
几个概念
基点Site：具有一些几何意义的点
细胞Cell：这个Cell中的任何一个点到Cell中基点中的距离都是最近的，离其他Site比离内部Site的距离都要远。
Cell的划分：基点Site与其它的n-1个点所对应的那个平分线所确定的那个离它更近的那个半平面。把所有这些半平面公共的交集求出来就是这个cell.
因此每个Cell都是凸的，图中一定会有一些Cell是无界的
在本课程中只讨论二维平面上的Voronoi图，并且我们存储Voronoi图时只需要存储点和边界信息。
Voronoi图中包括Voronoi点（线段与线段之间的交点）、线段Segment、射线Ray或直线，这些线都被称为Voronoi edge。
2、Properties
（1）非空性：每个Site都拥有一个非空的Site
（2）空圆性：在任何一个Site所对应的Cell中，任何一个点以这个点为圆心，以到这个Site的距离为半径的圆必然是空的。
这里的空指的是：圆其中它的内部不包含任何的 ...
清华大学-计算几何-多边形三角剖分
目标：将多边形剖分成三角形
1、画廊问题
问题描述：在画廊（如下图的多边形）中，如何设置哨兵可以监控整个画廊？
画廊，其中的点为哨兵
直观解：如果多边形是凸多边形或星形多边形，那么只须在中间的核设置一个即可。如果多边形不规则，那么最多n个点，即n多边形的每个顶点都设置一个哨兵，就可以将整个多边形覆盖。因此问题的解的上界为n.
然而在数学上有证明指出画廊问题是NP-Hard问题，这里不做多的赘述。
实际上，对于不规则多边形而言，最对只须n/3个点即可覆盖多边形（如下图）。
锯齿形，需要最多的哨兵。因为每三个顶点构成的三角形一定需要一个哨兵。
2、Fisk’s Proof
几个概念
扇形：一个有核点的星形多边形。每个扇形可以由一个点覆盖整个扇形。
内对角线：多边形顶点之间的内部连线
切线：某个点相切。任意一个边或切线都不是对角线
对角线的集合是连续的如果任意两条对角线不相交。
上：内对角线 下：切线
三角剖分问题
多边形P的最大的连续对角线的集合称为P的三角剖分。
着色：任意一条边和内对角线连接的两个点颜色互异。
顶点着色
Fisk’s的证明指出：对于进行三角剖分后 ...
清华大学-计算几何-几何求交
目标：对一系列的几何体，判断它们是否有交集，计算它们交集的个数，枚举所有的交集，构建这些交。1、Preliminary
EU问题
问题描述：给定一系列的实数，判断是否互异。
算法：将他们排序，然后可以通过线性扫描找到。复杂度O(nlogn)
Minimum Gap：对于实轴上的n个点，找到相邻两个的最小距离
对于这个问题，我们可以利用EU问题来规约，两个问题的输入都是n个整数，Minimum Gap如果是正数，那么EU的输出为Yes，如果是0，EU的输出是No。因此Minimum Gap的下界也是O(nlogn)
Maximum Gap：
算法描述：先找到最小值lo,和最大值hi，然后将这段分成n-1段，然后对每一个元素进行整除放进桶里。接着做线性扫描，先除去那些空桶。对于前面的桶考虑最右元素和后面桶的最左元素。考虑这两者然后找到最大的缝隙。
Integer Element Uniqueness：EU问题中的元素全都为整数
2、Interval Intersection Detection：区间交问题问题描述：给定一系列数轴上的区间，判断它们是否有交
简单算法 ...
志愿活动
17289f4fd8cc2af956ca06fbbcbbc3ceee270d23331ae046282c79f19ce763204679d39279cf7a5be5a57e187d813b6f
这篇文章记录我在大学期间参加的各个社团与志愿活动、青协活动等经历，需要密钥。
慢煮生活
6d63b89221e13b3febb0d4b727fe1cb7b9a5d0e0ce86e70d76eba31de419c45e
其实我很会吃。需要密钥