算分期末复习

  • 复习得很用心吧。。但是考得挺难的。。感觉有点白给了。。

  • 最后一题题面没说整数,顺手写了个梯度下降,好不容易老师溜达过来问了一嘴发现是整数。。。

课本例题
课本习题 还差 7,9,11
ppt 例题
21 个 npc http://wmdcstdio.com/2018/06/23/karp-npc-21/
24 网络流 https://blog.csdn.net/herano/article/details/70180828
https://www.zjyelizaveta.com/2017/09/21/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92%E4%B8%8E%E7%BD%91%E7%BB%9C%E6%B5%8124%E9%A2%98-Part-1/
算导 平摊分析 网络流

可行流:加一个新源点 限制流量
上下界网络流

最小割输出方案 https://blog.csdn.net/semiwaker/article/details/62883701
残量网络里和 S 连通的点是 S 点集里的点

回溯法 各种树 多米诺性质
image
image最后的结果是 z0?

image

image
逆序数列:在 i 右边,并且小于 i 的元素个数记作 B_i
heapify 是从 i 向叶子调整(把儿子中较大的换到父结点),复杂度依赖于结点的高度
image
image
image
image
image
P 规约到 Q,说明 Q 至少和 P 一样难,复杂度不会低于 P

image
image
image
image

image
image
递归树
dp: 一个最优决策序列的任何子序列本身一定是相对于
子序列的初始和结束状态的最优的决策序列
贪心:
image
image
套路
image
image
image
image

贪心证 prim,kruskal,dijkstra

3SAT 是说 3 元合取范式,MAX-SAT 是说一堆合取范式里能不能满足 k 个

构件设计法

image

近似算法的证明。。
image

NPC 证明

Karp 的 21 道 NPC 证明(去年小班课必读论文)

https://people.eecs.berkeley.edu/~luca/cs172/karp.pdf

中文简易版

http://wmdcstdio.com/2018/06/23/karp-npc-21/

14 个 NPC 证明

http://www.docin.com/p-789421911.html

CSDN 比较好的博客

https://blog.csdn.net/golden1314521/article/details/51470999

百度文库 NPC 问题整理

https://wenku.baidu.com/view/65e548191a37f111f0855b2c?pcf=2

网络流 24 题

一篇比较全的博客

https://www.cnblogs.com/zsnuo/p/8909613.html

09

image
平摊分析的三种方法
– 聚集分析
– 记账法
– 势能法
image

image

我觉得有问题的:平摊分析、网络流、近似、随机
贪心证明:线段覆盖

image
dinic n^3 ff mC ek nm^2

网络流 24

最大权闭合子图的权值等于所有正权点之和减去最小割 https://blog.csdn.net/yo_bc/article/details/75322370 S 连正权,T 连负权,原图的边容量 inf
最小路径覆盖:方案即为 S 出发的所有满流边,每条满流边上的点
二分图最小点权覆盖、最大点权独立集 转化为最大匹配
|最大独立集| = |V|-|最大匹配数|
路径互不相交 -> 不能重点,不能重边 -> 说明了每个点只能经过一次
仅在数字结点处相交 -> 可以重点,不能重边 -> 不用拆点,只限制边权即可
最大权不相交路径问题转化为最大费用最大流模型
21、最长 k 可重区间集问题 要想一会。。把重复 k 次转换成选 k 条路径,每条路径内部区间互不相交

  1. 平面上线段:为了避免线段与 x 轴垂直的情况,需要将所有的端点坐标 ×2 ,然后左端点 −1

18

恰好覆盖:写出算法及复杂度
NPC 证明:证明强独⽴集是 NPC 的
近似算法:证明最⼩顶点覆盖的 MVC 算法的正确性即近似⽐

有向环覆盖对应拆点后二分图的完备匹配 https://blog.csdn.net/u013480600/article/details/39159407
我们找到这 n 条边,起点互不相同、终点互不相同,可以认为是构成若干个环

近似

近似算法:写出求极大匹配的贪心算法,求该算法和最大匹配算法的近似比,找出紧实例
证明最⼩顶点覆盖的 MVC 算法的正确性即近似⽐

随机

伪码,输出一个不是最大的随机数

npc

恰好覆盖:写出算法及复杂度

找数组中出现次数超过一半的元素 O(n)

课后题
Select 算法 3 个一组,nlogn
5 个 n

12

image

image

image
image
image
image
image

image

image

https://cs.stackexchange.com/questions/1240/how-do-i-construct-reductions-between-problems-to-prove-a-problem-is-np-complete

First, unless you’re just doing homework, you have to decide which NP-hard problem to reduce to your problem. This is largely a question of “smell”. If the number 3 appears anywhere in the problem statement, try reducing from 𝟥𝖲𝖠𝖳 or 𝟥𝖢𝗈𝗅𝗈𝗋 or 𝟥𝖯𝖺𝗋𝗍𝗂𝗍𝗂𝗈𝗇. (Yes, I’m serious.) If your problem involves finding an optimal subsequence or permutation or path, try reducing from 𝖧𝖺𝗆𝗂𝗅𝗍𝗈𝗇𝗂𝖺𝗇𝖢𝗒𝖼𝗅𝖾 or 𝖧𝖺𝗆𝗂𝗅𝗍𝗈𝗇𝗂𝖺𝗇𝖯𝖺𝗍𝗁. If your problem asks for the smallest subset with a certain property, try 𝖢𝗅𝗂𝗊𝗎𝖾; if it asks for the largest subset with a certain property, try 𝖨𝗇𝖽𝖾𝗉𝖾𝗇𝖽𝖾𝗇𝗍𝖲𝖾𝗍. If your problem involves doing something in the plane, try 𝖯𝗅𝖺𝗇𝖺𝗋𝖢𝗂𝗋𝖼𝗎𝗂𝗍𝖲𝖠𝖳 or 𝖯𝗅𝖺𝗇𝖺𝗋𝖳𝖲𝖯. And so on. If your problem doesn’t “smell” like anything, 𝟥𝖲𝖠𝖳 or 𝖢𝗂𝗋𝖼𝗎𝗂𝗍𝖲𝖠𝖳 is probably your best bet.
image