Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algorithm (:moneybag:NP (:moneybag:NP问题 (:moneybag:Problem (:one:Hamilton…

- - - - :fast_forward:停机问题
      - :explode::one:程序H可以判断程序P在Input下是否为死循环 :two:程序U内调用了H.程序U先用H看U的参数是否为死循环,如果U的参数是死循环的话,自己就停机,否则自己死循环. :three:让H检查U在U的参数下的情况 :four:如果U查出自己参数(实际就是他自己U)是死循环的话,自己就停机.否则自己就死循环. 显然这是不可能的
      - :snowflake:如果你判断我死循环,我就停止;如果你判断我停止,我就死循环
  - - - :explode:一个问题如果能得到解决,那么另一个问题也得到解决.我们称他们为同样难.或者说等价.他们的集合成为复杂度类
  - - - :one:Hamilton Cycle
        
        :explode:Hamilton cycle problem: Find a single cycle that contains every vertex – does this simple circuit include all the vertices?
        
        :check:NPC problem
        
        :moneybag::fast_forward:哈密顿图
      - :two:Traveling Salesman Problem
        
        :explode:给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路
        
        :fast_forward:旅行推销员问题
        
        :check:NPC Problem
      - :three:Clique Problem
        
        :moneybag:Clique
        
        :explode:一个图,里面的点两两相连
        
        :explode:一个图里是否有大小为k的clique
        
        :check:NPC Problem
      - :four:Vertex Cover
        
        :check:NPC Problem
      - :five:Knapsack Problem
        
        :check:NPC Problem
    - - :explode:复杂度至少是NP的问题,只要这个问题解决了,就所有NP问题都能解决
    - - :explode:既是NP困难问题,又是NP问题的问题
  - - - :explode:我们可以给出很多图,这些图就是实例.然后也有很多解,虽然这些解中只有一个是正解
- - - - :moneybag:算法
        
        :two:First Fit
        
        :bread:遍历箱子,这个箱子找到能放的第一个物品就放进去.找不到就新开一个
        
        :moneybag:近似比
        
        :explode:1.7M
        
        :explode:Allocate the first hole that is big enough
        
        :one:Next Fit
        
        :moneybag:近似比
        
        :explode:2.1M
        
        :explode:遍历物品,能放下这个物品就放下,否则就开下一个箱子
        
        :three:Best Fit
        
        :explode:Allocate the smallest hole that is big enough
        
        :moneybag:近似比
        
        :explode:1.7M
        
        :bread:遍历物品,放在最能填满的箱子里.
        
        :fast_forward:稍微的介绍
        
        :four:First Fit Decreasing
        
        :moneybag:近似比
        
        :explode:11/9M+6/9
        
        :five:worst fit
        
        :explode:Allocate the largest hole;
    - - :explode:2-approximation
      - :warning:unless P=NP, there is no r-approximation for any r<2
  - - - :one:梯度下降算法
      - :two:Hopfield Neural Network
        
        :explode:给定一个图,这个图的所有边有w(e)信息,要求找出一个配置(给每个节点赋一个值),使得这个图稳定.w(e)<0表示s(u)=s(v),否则表示u和v有不同的状态
        
        :moneybag:边是好/坏的
        
        :explode:如果w(e)*s(u)*s(v)<0,其中e=<u,v>,那么这条边就是好的.否则就是坏的
        
        :moneybag:节点得到满足
        
        :explode:如果这个节点的所有边的w(e)*s(u)*s(v)总和<=0,那么我们就说这个节点得到了满足.否则没有满足
        
        :moneybag:图是稳定的
        
        :explode:所有节点都得到了满足
        
        :maple_leaf:State-Flipping Algorithm
        
        :explode:给每个节点一个初始值.然后看是不是有节点没有得到满足,如果是的话,就把这个节点的配置值取反.然后继续查看
        
        :star::one:会停止 :two:这个算法的任何一个局部最优得到的图都是稳定的配置 :three:目前不知道是不是多项式算法
        
        :explode:The state-flipping algorithm terminates at a stable configuration after at most W = sum(|w(e)|) iterations.
        
        :explode:Any local maximum in the state-flipping algorithm to maximize sum(|w(e)|,e is good) is a stable configuration.
        
        :moneybag:Maximum Cut Problem
        
        :explode:给定一个图,每个边上有权重.找到最适合的将所有节点划分两份(A,B)的方法,使得所有横跨(A,B)的边的权重和最大
        
        :bulb:State-Flipping Algorithm.只要把A和B记作不同状态.刚开始初始化值,然后如果W = sum(|w(e)|)小的话,就翻转
        
        :moneybag:分析
        
        :one:局部最优和全局最优相比怎么样:question:
        
        :explode:局部最优>=1/2全局最优
    - - :explode:需要定义
- - - - :explode::fast_forward:orris/algorithm/parallel/brent.png
      - :tornado::one:W(n)为平行算法总共的操作量,T(n)为运行时间 :two:假设操作量为3+7+11=21,总共运行时间为3秒 :three:我们有4个处理器,则ceiling(3/4)=1,ceiling(7/4)=2,ceiling(11/4)=3.所以4个处理器的时候时间为1+2+3=6 :seven:根据Brent定理,运行时间最大为(21/4+3)=8.25,因此是正确的
      - :star:不要提前做,操作量不能分成小数,肯定要大于运行时间ed
        
        :explode::one:W(n)为操作数的总数,是整数,分在不同时间点也是整数的形式 :two:一个操作只能由一个处理器完成.运行时间1可以理解为一个操作所花的时间,所以向上取整,多余的处理器只能闲着没事干 :three:后面的操作不能先于前面的操作,所以多余的处理器没办法事先执行后面的. :four:要提高效率,必须当前任务都分给所有处理器才行(时间步)
      - :key:操作数,时间步
  - - - :fast_forward:orris/algorithm/parallel/sum.png
      - :moneybag:问题描述
      - :explode:n个数据各自存在n个处理器中,一个时间步里n个处理器分别把自己的和旁边的数据加起来,最后指数级的累加了起来
    - - :snowflake:先利用并行算法构造平衡的线段树.然后我们从下到上求出Prefix Sum
      - :tornado:求a1+a2+...+a7的话,就是:one:(初始为最底层)因为7为奇数,所以(7-1)/2=3所以找上一层的第3个,并且还有本层的第7个. :two:要求上一层的第3个,因为3是奇数,所以找上一层的第(3-1)/2=1个,并且还有本层的第3个 :three:要求上一层的第1个,则因为1=1,所以直接就是这个node了. :four:将找到的点加起来就OK了
      - :explode::fast_forward:平行算法PPT
    - - :explode:一个序列中找出最大值
      - :maple_leaf:思路
        
        :one:比较所有pairs
        
        :explode:如果有N个数的话 :one:N个处理器将它填0 :two:N*(N-1)/2个处理器进行比较,发现不是最小值的话,就置1 :three:最后N个处理器再一起看,如果是0的话,就是最大值了
        
        :moneybag:代价
        
        :one:T(N)=O(1)
        
        :two:W(N)=O(\(N^2\))
        
        :two:按square(N)分
        
        :moneybag:代价
        
        :one:T(N)=O(loglogN)
        
        :two:W(N)=O(NloglogN)
        
        :three:按loglogN分
        
        :moneybag:代价
        
        :one:T(N)=O(loglogN)
        
        :two:W(N)=O(N)
  - - - :explode:SISD,MISD,SIMD,MIMD
    - - :explode:EREW,ERCW,CREW,CRCW
- - - - :one:内存大小
        
        :explode:内存多大,一个run就多大
        
        :snowflake:把内存大小的数据放入内存进行排序
      - :two:Replacement Sorting
        
        :explode::fast_forward:解析
        
        :snowflake:内存空间有限,每次读入后取最小值压入.但如果上一个最小值比新的最小值大的话,就标记为No,预留到下一个run.一直到所有都为No,那么新的run就开始了
        
        :snowflake:取最小值可以用heap
        
        :star:可以获得比内存空间还大的run :smile:
  - - - :explode:原来有k个run的话,最好分成斐波那契数列的前2项.如34分成(13,21).这样好直接保留排序的2个tape中的1个tape后面部分,从而和第3个tape的新runs进行归并.
- - - - :explode:先摆满第一行/列,然后摆满第2行/列..如果这个阶段已经不能放了,就不再此基础上弄了
    - - :explode:x轴上有若干个点,给出这些点相对距离的集合,求出这些点的位置
      - :snowflake:通过最大值,确定x0和xN.然后在新的最大值(在集合中删除已知点的相对位置)中,确定可能的点的位置,回溯这些点.不断递归这个过程,直到相对位置集合里没有结果
      - :moneybag:详细的解释
- - - - :explode:You are given n activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.
      - :fast_forward:Greedy Algorithms | Set 1 (Activity Selection Problem)
- - - - :explode:宏观出发,n次操作花费C,则复杂度为C/n
      - :tornado:最坏情况是前n次压栈,第n+1次multipop.那么共n+1次操作,操作数为n+n=2n,所以复杂度为O(2n/(n+1))=O(1)
    - - :snowflake:完成自己的计划时,先提前做点,虽然我当天代价很高,但我之后就可以轻松了.如果我一直都拖的话,那么我没法把结果作为完成所需的时间了
      - :explode:给每一个操作实际代价和信用代价.然后累积它们就可以了
      - :tornado:push的话我们让它亏点,就push了一定要pop,那么push
      - :warning:每次操作后,前面的信用和不能为负
    - - :explode:摊还代价=实际代价+当前势能-上一个状态的势能=实际代价+势能的增量=amortized cost=actual cost+delta_potential
      - :tornado:explaination
        
        :one:push,pop实际代价为1,而push能让势能+1,而pop-1.所以push摊还代价为2,pop摊还代价为0,而multipop摊还代价也是0,所以又回到核算法
        
        :two:Binomial Queue
        
        :explode:A binomial queue of N elements can be built by N successive insertions in O(N) time
        
        :moneybag:分析
        
        :key:插入一个item如果cost=c的话,导致树的数量增加2-c个
        
        :moneybag:cost
        
        :explode:这里定义的cost举例来说,就是如果没B0,cost=1;如果B0有,B1无,cost=2
        
        :explode:actual cost+amortized cost=c+2-c=2.所有N个加起来就是2N.所以就是O(N)时间
- - - - :explode:字典排序的BST,每个单词有probability.目标是让所有单词的(概率\*(深度+1))的总和最小
      - :warning:深度+1表示从根开始到指定单词的比较次数
- - - - :explode:共有n天,每天面试1个人.面试1个人的话要找到这个应聘者,这需要花费费用c1;最后总共雇佣了m个人,每次雇佣都要替换掉现任,费用是c2.其中c1<<c2.
      - :maple_leaf:思路
        
        :one:按天遍历,直接如果说当前应聘者比现任好的话,就录用了
        
        :moneybag:分析
        
        :explode:如果应聘者的质量是递增的话,那么m=n,费用很高
        
        :two:猎头公司提供n个候选人列表,我每天随机取应聘者
        
        :three:打分
        
        :explode:先面试前面k个,都不雇佣,每个人都打分.这样就能获得最高分.然后面试剩下的几个,如果这几个中有分数比这个最高分高的,就录用了,否则就取最后一个
        
        :snowflake:蛟川书院考个分数,然后镇中按这个分数录取
        
        :moneybag::fast_forward:给定k,我们雇佣到最好的员工的概率
      - :warning:关心的是费用 :red_cross:程序的运行时间
      - :moneybag:费用
        
        :explode:n*c1+m*c2