Vinícius Gusmão Pereira de Sá

Tópicos Especiais em Algoritmos — 2021/2

Informações

Sala do Google Meet: meet.google.com/koi-dbka-iaa.
Horário: 6as, das 8h às 12h.

Jamboard com as notas de aula para aulas de Randomizados.

Conteúdo aproximado (fortemente sujeito a mudanças ao longo do curso, sob demanda):
Algoritmos Randomizados, Algoritmos Aproximativos, backtracking, algoritmo guloso, PD, memoização, brain teasers e problemas algorítmicos em geral, problemas NP-completo.

Primeira lista de exercícios aqui.

Exercício (valendo como parte da avaliação), para ser entregue até as 23:59 do dia 10/03/22: implemente uma solução em programação dinâmica clássica (bottom-up) para o problema da pirâmide. Entrada: uma lista contendo n listas de inteiros. A primeira tem tamanho 1, a segunda tem tamanho 2, etc., até a n-ésima lista, que tem n inteiros, constituindo portanto uma pirâmide. Deseja-se encontrar a MENOR soma possível a partir do topo da pirâmide e até a sua base, sempre seguindo para a linha abaixo da atual pela mesma coluna ou pela coluna imediatamente à direita. Em outras palavras: da posição (i, j), pode-se seguir pelas posições (i+1, j) ou (i+1, j+1), começando da posição (0,0) e terminando na posição (n-1, k) para algum k entre 0 e n-1. A abordagem top-down já foi feita (em Python) aqui.

Avaliação final: entregue por e-mail (vigusmao@dcc.ufrj.br) até o fim do dia 11/03/22 um texto contendo os seguintes pontos:
(1) uma auto-avaliação, abordando a sua participação e a sua assimilação de cada um dos conteúdos vistos, realçando de forma muito sucinta (uma ou duas linhas por item) o que você entendeu de cada tema visto;
(2) uma avaliação do curso, de forma geral;
(3) uma nota (entre 0 e 10) que considere justa para si próprio, que bem represente seu aproveitamento do curso.

Bibliografia sugerida

Randomizados
Randomized Algorithms		Probability and Computing	Introdução aos Algoritmos Randomizados
(Raghavan & Motwani)		(Upfal & Mitzenmaker)	(Figueiredo, Fonseca, Lemos & Pereira de Sá)


NP-Completude
Computers and Intractability
(Garey & Johnson)


Aproximativos	Approximation Algorithms
Approximation Algorithms		Introduction to Algorithms	Uma Introdução Sucinta aos Algoritmos de Aproximação
(Vazirani)		(Cormen, Leiserson, Rivest & Stein)	(Cerioli, Feofiloff, Fernandes & Miyazawa, editores)

Conteúdo das aulas

16/11

Conversa inicial sobre o curso.
Primeira conversa sobre algoritmos randomizados. Exemplo de bom uso de randomização: robôs de paraquedas. Exemplo de péssimo uso de randomização: RandomSort.
Fisher-Yates shuffle.

Slides emprestados do 26 Colóquio Brasileiro de Matemática aqui.
Slides sobre os robôs de paraquedas aqui.
Código em Python para o problema dos robôs aqui.
Artigo com a análise dos robôs, caso interesse a alguém. :-)

Aula gravada no Google Meet.

19/11

Algoritmos de Monte Carlo. Erro unilateral e erro bilateral. Monte Carlo baseado no sim e baseado no não.
Refinando a probabilidade de erro via repetição (exponencial negativa).

Revisão de probabilidades: probabilidade da união e da interseção, probablidades condicionais, probabilidade total.
Link para a Jam sobre probabilidades.

Aula gravada no Google Meet.

23/11

Segundo exemplo de algoritmo de Monte Carlo, dessa vez baseado no sim e sem qualquer parâmetro interno para refinamento da probabilidade de erro.
Exemplo: corte mínimo em grafos. Slides.

Monte Carlo de erro bilateral.
Exemplo: o problema dos atiradores no clube. Código em Python para acompanhar a evolução das probabilidades (modelo de crenças).

Aula gravada no Google Meet.

26/11

Variáveis aleatórias. Bernoulli, Binomial, Geométrica. Esperança. Linearidade da Esperança.
Exemplo: o problema dos piratas bêbados. Código em Python para uma simulaçãozinha.

Algoritmos de Las Vegas: acertam sempre, tempo de execução é uma V.A.
Quick Sort Randomizado. Análise.
Aula gravada no Google Meet.

03/12

Análise de caso médio de algoritmo determinístico versus análise do tempo esperado de uma execução de algoritmo de Las Vegas.
Desigualdades de Markov e Chebyshev.

Transformação Monte Carlo em Las Vegas, e vice-versa.

Paradigmas combinatórios: bolas e latas, colecionador de coupons. Exemplo: identifação de roteadores (reservoir sampling).

O Método Probabilístico (para provas de existência): o método da esperança, o método da probabilidade estritamente positiva.
Código em Python para uma estimativa empírica da média da VA geométrica.

Aula gravada no Google Meet.

10/12

As classes de complexidade P e NP. NP-dificuldade. NP-completude. Transformações polinomiais. Provas de NP-completude. O problema "P==NP?"" e suas consequências.
O problema do Conjunto Independente Máximo.

Aula gravada no Google Meet.

17/12

A técnica do Sample and Modify como coadjuvante do Método Probabilístico para provas de existência.

Anotações feitas durante a aula.
Aula gravada no Google Meet.

07/01

Introdução aos algoritmos aproximativos. Caixeiro-Viajante Euclideano (CVE). Algoritmo 2-aproximativo RSL para o CVE.

Segunda parte da aula: participação do Prof. Paulo Eustáquio abordando Bloom Filters e alternativas recentes a Bloom Filters.

Anotações feitas durante a aula.
Aula gravada no Google Meet.

14/01

Algoritmo 1.5-aproximativo de Cristofides para o CVE.
Algoritmos pseudo-polinomiais.

Correção da Lista 1.

Anotações feitas durante a aula.
Aula gravada no Google Meet.

21/01

Algoritmo aproximativo para Conjunto Dominante Mínimo em Grafos de Disco Unitário. Slides. Artigo.

Término da correção da Lista.

Aula gravada no Google Meet.

28/01

Bloom Filters. Aplicações em MMO (multi-player massive online games). Implementação from scratch (em Java).

Aula gravada no Google Meet.

04/02

Finalização da implementação de Bloom Filter. Armadilha: funções hash mal escolhidas.

Acerto de relógio entre máquinas de um cluster, ou entre servidor e cliente.

Brain teasers: o problema do prédio e das duas bolas idênticas; o problema dos condenados encapuzados; o problema dos armários. Aula gravada no Google Meet.

11/02

O Problema-Sanduíche para Conjunto Homogêneo. Square-root decomposition e sua aplicação no PSCH. Algoritmo de Monte Carlo para o PSCH.
Artigo.

Aula gravada no Google Meet.

18/02

Programação Dinâmica top-down (com memoização) vs bottom-up (PS clássica, com o preenchimento completo de uma tabela). Exemplo: subset sum.

Código em Python.
Aula gravada no Google Meet.

25/02

PD top-down vs bottom-up: liberação de memória possível no bottom-up, em muitos casos. Exemplo: o problema da soma da pirâmide.

Código em Python.
Aula gravada no Google Meet.