Começar. É Gratuito
ou inscrever-se com seu endereço de e-mail
Rocket clouds
Scribe por Mind Map: Scribe

1. Recap

1.1. Paging

1.1.1. Cobra para retirar da cache

1.1.2. Objetivo é minimizar # pgs retiradas

1.1.3. K pgs 1..k

1.1.4. 1,2,..k,k+1,1,2,3...,k

1.1.5. OPT

1.1.5.1. Coloca 1..k

1.1.5.2. Retirar k, Colocar k+1

1.1.5.3. Qnd chegar em k, trocar k+1 por k

1.1.5.4. Só faz 2 trocas

1.1.6. LRU

1.1.6.1. Least Recently Used

1.1.6.2. Troca 1 por k +1

1.1.6.3. Troca 2 por 1

1.1.6.4. Faz ~k remoções

1.1.6.5. É >= k/2-compet

1.1.7. Lemma

1.1.7.1. Todo Algo Determinístico é >= k-compet

1.1.7.2. Prova

1.1.7.2.1. Instancia: K = k +1

1.1.7.2.2. Pensar como um adversário

1.1.7.2.3. Sequencia tem n elementos

1.1.7.2.4. algoritmo paga n-K

1.1.7.2.5. OPT paga <= n/K

1.1.7.2.6. Prova:

2. Algoritmo

2.1. Definições

2.1.1. Phase

2.1.1.1. Maior Prefixo que contenha k pgs distintas

2.1.1.2. Começa na primeira requisição e vai até o final

2.1.1.3. Criar quantas phases sejam necessárias

2.1.1.3.1. Podem ser computadas de forma on-line

2.1.1.4. Ex:

2.1.1.4.1. K = {1..10}

2.1.1.4.2. k = 2

2.1.1.4.3. 1,2,3,4,5,6,7,8,9,10

2.1.1.4.4. (1,2),(3,4),...

2.1.2. Marking

2.1.2.1. Algo é marking se qnd pg é colocada na cache em uma phase, ela fica na cache até o fim da phase

2.1.2.1.1. Algo Phase é marking

2.1.2.2. Lemma

2.1.2.2.1. Qualquer algo de marking tem custo <= k * #phases

2.1.2.3. LIFO não é marking

2.2. Analises

2.2.1. # misses de um algo det

2.2.1.1. Só pode haver no max k misses por phase

2.2.1.2. total <= k*#phases

2.2.2. teorema

2.2.2.1. LRU é marking

2.2.2.1.1. Considere a fase no instante t

2.2.2.1.2. Seja p subconjunto de {1,2,... K} a pg requirida na fase |P| <= k

2.2.2.1.3. Seja St pertencendo a P

2.2.2.1.4. Prova por indução em t

2.3. Algos

2.3.1. Algo phases

2.3.1.1. Qnd trocar a phase, limpa a cache

2.3.1.1.1. paga k

2.3.1.2. Durante a fase, só adiciona

2.3.1.2.1. Todas caberão

2.3.2. OPT

2.3.2.1. Lemma

2.3.2.1.1. OPT >= # phases -1

2.3.2.2. OPT > 0.5 * # phases

2.3.2.2.1. considerar 2 phases

2.3.2.2.2. O OPT precisa pagar 1 na troca de phase

2.3.2.2.3. paga 1 a cada 2 phases

3. Further Reading

3.1. Algos Aleatorizados

3.1.1. Teorema

3.1.1.1. Fiat et al '91

3.1.1.2. Mark Random

3.1.1.2.1. ~ (lg k)-compat

3.1.1.2.2. LRU + aleatoriedade

3.1.1.2.3. mantém mark pg na cache q são recentes

3.1.1.2.4. qnd miss acontece

3.1.1.2.5. 1 bit - LRU

4. AD-Words

4.1. Anunciante i

4.1.1. Pode pagar b(i,k) qnd o aúncio i for mostrado na busca p/ palavra-chave k

4.1.2. Mas paga no máx B(i) por dia

4.2. Jogo

4.2.1. tempo t

4.2.1.1. Google recebe palavra-chave kt

4.2.1.2. Escolher qual o anuncio (it) mostrar

4.2.1.3. ganha min(b(it, ki), quanto sobra de B(it))

4.2.1.3.1. ~b(i,k)

4.2.2. Objetivo

4.2.2.1. Mas total ganho

4.2.3. Ver exemplo na nota

4.3. Algo Guloso

4.3.1. Escolhe AD c/ maior ganho

4.3.2. ~b(i,k) = min(B(it, kt), qnt sobra de B(i))

4.3.3. Teorema

4.3.3.1. Guloso é 0.5-compat

4.3.3.1.1. Algoritmo (I) >= 0.5OPT(I) p/ todo I

4.3.4. Observação

4.3.4.1. Se remover e > 0 do budget, ela perde, no máx, e de valor

4.3.4.1.1. Prova