The twelvefold way $f: N\to M$, $|N|=n$, $|M|=m$ 等价于 Basic EnumationTuples $[m]=\\{0,1,2,\cdots, m-1\\}$ $n$-tuple of $[m]$: $[m]^n$ $|[m]^n|=m ...

最小割和最大割1 最小割1.1 Karger’s Contraction algorithmContraction操作: $Contract(G, uv)$表示将图G中点u和v合并, uv之间的边删除 RandomContract算法RandomContract算法: while |V| > ...

Hello, OS world编译, 链接 strace -f查看进程和他的子进程的所有系统调用 gcc -o hello hello.c 子进程1: 编译器compiler写入a.s汇编代码 子进程2: 汇编器assembler写入a.o(ELF…) 子进程3: 链接器linker写入a.out( ...

Hello World的故事: Hello World的一生是从execve()开始的 继承父进程的文件描述符(./a.out > /dev/null; ./.a.out | cat, …) 内核会为a.out创建代码、数据、堆栈 执行的第一条指令 从ELF的entry开始执行 静态链 ...

线程threadspthread_create() 创立线程 pthread_join() 等待某线程结束 线程是操作系统能够进行运算调度的最小单位 进程是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位 顺序、原子性、可见性的丧失 原子性: 一个操作是不可中断的 ...

存储介质 磁: 磁铁方向, 磁盘 光: 挖坑填坑, 光盘 电: SSD 存储介质相当于是一个字节数组bool bits[CAPACITY]; I/O设备与驱动 I/O设备: 设备是三种操作的集合: (别人)发送命令(给他)、(别人)读取(他的)状态、(互相)传输数据 键盘: 按键信息会 ...

进程抽象 如果程序只完成“计算”的任务而不做任何输入输出，它就可以看成是一个状态机。程序的内存M和寄存器R构成了程序任意时刻的状态(M,R). 进程的机器状态：内存（地址空间）、寄存器（PC、IP、栈指针、帧指针等）、IO信息等。 每个线程有它自己的资源 const char *name - 它的名 ...

启发性算法 非常狭义定义： 用来设计最优化问题的随机算法的鲁棒性技术； 不能保证解的效率和质量 没有有界常数概率 模拟退火 Simulated Annealing概念 局部搜索+跳出局部最优的随机决策 局部搜索：找到一个可行解；找到邻域中的最优解替换并且循环这一步 多起点局部搜索 thresh ...

随机算法是非确定性算法, 但是可以看做一个额外有随机数序列作为输入的确定性算法. 随机算法的复杂度或者输出可以看做随机变量 输出可以看做随机变量的随机算法称为蒙特卡洛算法 永远输出正确答案但是复杂度是随机变量的随机算法称为拉斯维加斯算法 常常不知道随机化是否是有效的, 也不知道是否能在不牺牲资 ...

概念 提供不比最优解差太多的可行解 定义: 对于最优化问题 $U = \{\Sigma_I, \Sigma_O, L, L_I, M, cost, goal\}$ , A是U的一个一致性算法. 对于所有问题实例$x\in L_I$, A对于x的相对误差$\epsilon_A(x)$定义为 \epsi ...