Vinícius Gusmão Pereira de Sá

Selected Topics in Algorithms — 2012/2

Tópicos Especiais em Algoritmos — 2012/2

Informações

Info

Local: DCC room.
Time: Mondays and Wednesdays, from 1pm to 3pm.
Started on October 15th, 2012.

There will bo no classes on:
- Oct 24th (presenting a seminar at COPPE);
- Nov 07th (referee at JIC);
- Nov 19th (oficial off day due to holiday).

Topics: Randomized Algorithms, Approximation Algorithms, brain teasers and general algorithmic problems.

Evaluation: there will be two lists with exercises and possibly a final exam for those who dare not obtain direct approvement.

First list of exercises here.
Due date: January 11th, 2013.

Second list of exercises here.
Due date: March 3rd, 2013.

Obs.: The lists of exercises can be solved in pairs.
In case any explanation is demanded, any student of the pair may be requested to provide it.

We'll have normal class (or almost) on Wed, March 6th, from 13h to 13h30. Please try not to be late.

Final exam: Friday, March 15th, at 1pm, DCC room.

Timetable for March 11th:

Local: Sala do DCC.
Horário: 2as e 4as, das 13h às 15h.
Início: 15 de outubro de 2012.

Não haverá aula nos dias:
- 24/10 (apresentarei seminário na COPPE);
- 07/11 (estarei em banca da JIC);
- 19/11 (recesso oficial por feriado).

Conteúdo: Algoritmos Randomizados, Algoritmos Aproximativos, brain teasers e problemas algorítmicos em geral.

Avaliação: duas listas de exercícios e uma prova final para aqueles que ousarem não passar direto.

Primeira lista de exercícios aqui.
Data de entrega: 11 de janeiro de 2013.

Segunda lista de exercícios aqui.
Data de entrega: 3 de março de 2013.

Obs.: As listas podem ser feitas individualmente ou em dupla.
Caso alguma explicação seja necessária, qualquer aluno da dupla poderá ser convocado a prestá-la.

Atenção: haverá aula (não exatamente aula, mas precisamos nos encontrar) na quarta-feira, dia 06/03, às das 13h às 13h30. Tentem não atrasar, por favor. ;-)

Prova final: sexta-feira, dia 15 de março, às 13h, sala DCC.

Horários para o fechamento de notas no dia 11/03:
(Desculpem a divulgação no próprio dia. O professor de vocês passou mal no fim-de-semana e esteve fora de combate até essa madrugada.)

#	Horário	Aluno
1	13:00	DANIEL LOPES BRAZ DOS SANTOS
2	13:04	GUILHERME IRIA D'ABBADIA FONTES PEREIRA
3	13:08	CARLOS FILIPE BENEVIDES
4	13:12	JUAN CARLOS TOLEDO BAPTISTA
5	13:16	LUIZ FELIPE DA COSTA PERICOLO BARBOSA
6	13:20	THIAGO MACHADO SANTOS
7	13:24	FILIPE QIANG ZHOU
8	13:28	JADE MOREIRA DA COSTA
9	13:32	PEDRO IVO MARQUES L DE L RIBEIRO
10	13:36	FÁBIO FERMAN
11	13:40	PEDRO FELLIPE PASSOS CORTEZ
12	13:44	DANIEL DAIM LOPES DE ARAUJO
13	13:48	WANDER MENDONÇA SOARES
14	13:52	BRENO ANDRADE VECCI CHAGAS
15	13:56	MAGNO ARLINDO GOMES FERREIRA
16	14:00	LUCAS SIMOES DE SOUSA ARNAUD
17	14:04	RODRIGO DE SOUZA STUHL
18	14:08	RAPHAEL DUARTE PAIVA
19	14:12	FABIO MEDEIROS RANGEL
20	14:16	LEONARDO MÕES GOMES
21	14:20	VITOR PEREIRA MACHADO
22	14:24	DIEGO DE OLIVEIRA MARTINS
23	14:28	MATEUS GREGORIO DE SOUZA
24	14:32	ANDRÉ GUSTAVO LIMA FIGUEIREDO
25	14:36	CARLOS VICTOR DA SILVA
26	14:40	THIAGO GONÇALVES ESCOBAR
27	14:44	BRUNO SOUSA CAMPOS DA COSTA
28	14:48	FLAVIO COUTINHO DA COSTA
29	14:52	GABRIEL RODRIGUES DO CARMO
30	14:56	LUIZ FELIPE ANTUNES DIAS
31	15:00	PALOMA THOME DE LIMA
32	15:04	AUGUSTO ACIOLI PINHO VANDERLEY
33	15:08	HÉLIO HENRIQUE MACHADO BARBOSA
34	15:12	MARCIO FARIAS DIAS RODRIGUES

Bibliografia sugerida

Conteúdo das aulas

Lecture notes

15/10

Início da Primeira Parte do curso.

Por quê estudar algoritmos?

Indústria — brain teasers e problemas de algoritmos costumam ter peso extremamente alto nas entrevistas de emprego para admissão nas melhores empresas de TI; a qualidade dos algoritmos utilizados é, sem muita margem para discussão, o principal diferencial entre um bom e um mau produto.
Academia — a quantidade de melhorias possíveis nos algoritmos existentes para uma infinidade de problemas, além do grande número de problemas em aberto ou computacionalmente difíceis (muitos dos quais com aplicações práticas que demandam soluções criativas, restrições de entradas, algoritmos de aproximação, heurísticas etc.) faz desta uma das mais profícuas áreas para pesquisa em Ciência da Computação.
Diversão — É muito divertido. Ponto. :-)

Problema dos números k-complementares: queremos localizar, numa lista, se há dois números que somem k.

Problema das Ramson notes: dada uma string "revista" e uma string "frase", queremos saber se é possível escrever a frase a partir de um recorte-e-colagem das palavras da revista.

Problema da adição de polinômios: dados dois polinômios na forma de listas de pares (grau, coeficiente), precisamos somar os coeficientes dos termos de mesmo grau de forma eficiente.

Problema da localização do mínimo em um array ordenado e "rodado".

17/10

Problema de se ordenar um array. Que perguntas são pertinentes? Sabendo-se, por exemplo, que se trata de um array de idades de pessoas, e ainda que se leve em conta o "fator Niemeyer" :-), é possível ordená-lo em tempo linear?

Introdução aos algoritmos randomizados:

Experimentos aleatórios;
Dados e moedas no computador: geradores de números pseudo-aleatórios;
Ganho em tempo e/ou simplicidade;
Algoritmos de Monte Carlo e de Las Vegas;
Exemplo de algoritmo de Monte Carlo de erro unilateral: problema da identidade de polinômios, com algoritmo determinístico quadrático e randomizado linear.

Revisão de teoria de probabilidades: probabilidade condicional, Bayes, probabilidade total, exemplo dos atiradores no clube.

22/10

Problema do k-ésimo inteiro positivo com todos os seus fatores primos contidos em {3,5,7}.

Mais Bayes: exemplo das três moedas, uma das quais com 2/3 de probabilidade de sair cara, em que queremos saber qual a probabilidade de a primeira moeda ser a desonesta dado que os resultados das três moedas foram, respectivamente, cara, cara e coroa.)

24/10

Não houve aula. Seminário COPPE.

29/10

Problema de se encontrar o menor inteiro r que satisfaz binom(r, r / 2) ≤ 2^d para todos os valores de d num intervalo dado. Implementamos em sala (Python).

Exemplo de algoritmo de Monte Carlo: problema do corte mínimo.

31/10

Continuação do problema do corte mínimo.

Slides introdutórios sobre Algoritmos Randomizados (emprestados do mini-curso que dei no IMPA em 2007, junto dos professores Celina Figueiredo, Guilherme Fonseca e Manoel Lemos), até o diagrama apresentando as probabilidades condicionais associadas aos algoritmos de Monte Carlo de erro unilateral.

05/11

Problema dos armários: dado um número n de armários numerados de 1 a n e inicialmente fechados, queremos contar quantos armários estarão abertos após o seguinte procedimento: uma primeira pessoa abre todos os armários; uma segunda pessoa fecha todos os armários de número par; uma terceira pessoa muda o estado (se estiver aberto, fecha; se estiver fechado, abre) de todos os armários com números múltiplos de 3; uma quarta pessoa mudo o estado dos armários múltiplos de 4, e assim por diante até a n-ésima pessoa. (Várias abordagens possíveis, uma delas absurdamente rápida e trivial.) Implementamos em sala (Python).

Outro exemplo (mais complicado) de algoritmo de Monte Carlo: o problema-sanduíche do conjunto homogêneo. Slides aqui.

07/11

Não houve aula. JIC.

12/11

Problemas em listas encadeadas: localizar o k-ésimo último elemento, apagar sem acesso à cabeça, remover duplicatas.

Digressão: análise das complexidades de tempo de se inserir n elementos num array, desconhecendo inicialmente o valor de n, segundo duas políticas de cópia do array cheio para um de maior tamanho: a "aritmética" e a "geométrica".

Variáveis aleatórias: esperança, linearidade da esperança, indicadores de Bernoulli. Exemplo dos piratas bêbados.

14/11

Não houve aula. Professor doente semi-morto.

19/11

Não houve aula. Recesso oficial.

21/11

Demonstração da linearidade da esperança. Observe que não é necessário que as variáveis aleatórias sejam independentes!

Quick Sort randomizado. Discussão sobre a diferença entre análise de tempo médio de algoritmo determinístico e tempo esperado de algoritmo randomizado (Las Vegas).

Variáveis aleatórias binomial e geométrica.

26/11

Problema do conjunto máximo de pontos colineares.

Paradigma combinatório das bolas e latas. Paradoxo do aniversário. Colecionador de coupons. Algoritmo randomizado para o problema da identificação dos roteadores (técnica reservoir sampling).

28/11

Problema do sorteio de n-1 números distintos do conjunto {1,...,n}. Variação para n-2 números.

Desigualdade de Markov. Variância. Desvio padrão. Desigualdade de Chebyshev.

Transformação de Las Vegas em Monte Carlo de erro unilateral.

03/12

Problema dos ovos atirados do alto do prédio com n andares.

Transformação de dois algoritmos de Monte Carlo (um baseado no SIM, outro baseado no NÃO) em algoritmo de Las Vegas.

O Método Probabilístico: argumento da probabilidade estritamente positiva. Exemplo: 2-coloração de arestas do grafo completo sem cliques monocromáticas de um tamanho dado.

05/12

O Método Probabilístico: argumento da esperança.
Exemplo: corte de tamanho maior ou igual a m/2.
Exemplo: satisfazendo pelo menos 7/8 das cláusulas no problema da 3-satisfabilidade.

10/12

Problema do mercado financeiro.

Argumento da esperança com Sample & Modify. Exemplo: prova de existência de conjunto independente de tamanho pelo menos n²/4m.

12/12

Problema da lista encadeada com laço: sabe-se que uma lista (simplesmente) encadeada, de tamanho maior do que a metade da memória disponível, possui uma referência circular. Deseja-se determinar o primeiro nó (i.e. o nó mais à esquerda) que é apontado por algum um outro nó à sua direita, na lista. (Solução em tempo linear e espaço constante.)

17/12

Esperanças condicionais.

Derrandomização.
Exemplo: algoritmo guloso (derrandomizado) para obter corte de tamanho maior ou igual a m/2.

19/12

Implementação (Java) dos algoritmos Las Vegas e derrandomizado para o problema do corte de tamanho maior ou igual a m/2.
Discussão rápida sobre grafos aleatórios (o modelo G_n,p foi usado como instância de entrada para os algoritmos acima).
Discussão sobre complexidade de algoritmos em geral. Possíveis otimizações para os algoritmos implementados.

Fim da Primeira Parte do curso.

24/12 - 04/01

Recesso de fim de ano.

07/01

Início da Segunda Parte do curso.

Problema: decidir se uma lista simplesmente encadeada representa um palíndromo, com retrição de uso de memória adicional.

Classes de complexidade: a classe P; a classe NP; a classe NP-Completo. Conceito de redução polinomial.

09/01

Problema da 3-satisfabilidade (3-SAT) revisitado. Pertinência à classe NP. Inexistência de algoritmos polinomiais conhecidos.
Problema da clique máxima (MAX-CLIQUE), e a versão de decisão correspondente (CLIQUE). Pertinência à classe NP. Inexistência de algoritmos polinomiais conhecidos.
Redução polinomial de 3-SAT para CLIQUE.

14/01

O problema da satisfabilidade de circuitos (CIRCUIT-SAT) é NP-completo.

Ideia da prova: seja Π um problema de decisão qualquer da classe NP. Existe, portanto, um algoritmo A que, recebendo como entrada uma instância I de Π e um certificado C de que a resposta correta para I é SIM, é capaz de verificar em tempo polinomial que C de fato certifica esse SIM. Segue uma redução polinomial de Π em CIRCUIT-SAT. Deseja-se decidir uma instâcia I de Π. Cria-se uma instância de entrada K(A) para CIRCUIT-SAT na forma de um número t(I) de cópias da realização K_j(A), j=1,...,t(I) do algoritmo A em hardware (utilizando apenas portas lógicas NOT, AND e OR, o que é sempre possível), onde t(I) é o número máximo (polinomial!) de instruções processadas numa execução de A tendo como entrada a instância I e um certificado qualquer (para o SIM de I) de tamanho polinomial em I. A entrada de cada K_j(A) consiste de um snapshot da memória do computador antes da execução da j-ésima instrução do algoritmo A, parte da qual contém evidentemente a própria instância de Π, também um certificado para o SIM desta instância, o endereço da próxima instrução etc. É fácil ver que tanto t(I) quanto o tamanho de cada K_j(A) é polinomial no tamanho de I. Fixa-se agora a parte da entrada de cada K_j(A) que diz respeito à instância de Π como sendo exatamente I, fixa-se o endereço da próxima instrução da entrada de K₁(A) como sendo o endereço da primeira instrução de A etc., de forma que a entrada do circuito completo K(A) compreenda apenas um possível certificado para o SIM de I. Estabelece-se que a saída de K(A) fica sendo a posição de memória, na saída de K_t(I)(A), que corresponde precisamente ao resultado SIM (1) ou NÃO (0) obtido da verificação executada por A. Desta maneira, o circuito K(A) é satisfatível se, e somente se, existe algum certificado C para o SIM de I, isto é, se, e somente se, I é uma instância SIM para o problema Π.

16/01

Brain teasers: divisão do baralho com N cartas voltadas para cima em dois montes com o mesmo número de cartas com a face voltada para cima (caso em que N é conhecido e caso em que não é); problema dos condenados à morte postos em fila com capuzes azuis ou vermelhos, onde cada condenado só pode ver a cor dos capuzes dos condenados que estão à sua frente na fila e precisa acertar a cor de seu capuz para ter a vida poupada (qual a melhor estratégia para o grupo?).

Soluções para o problema do macaco digitador.

21/01

Introdução aos algoritmos aproximativos.

O Problema do Caixeiro Viajante: algoritmos aproximativos de RS&L e de Christophides para a variante euclidiana (grafo completo, custos das arestas satisfazendo a desigualdade triangular).
(Slides aqui.)

23/01

O Problema do Conjunto Dominante para Grafos de Disco Unitário: algoritmo 44/9-aproximativo linear.
(Slides aqui.)

28/01

"Experiência quase completa" com o Problema da Cobertura de Vértices: definição, tentativas de algoritmos, contra-exemplos, prova de NP-dificuldade (redução de CLIQUE). Faltam algoritmos aproximativos, tema da próxima aula.

30/01

Problema de probabilidade contra-intuitiva: "Kruskal Count". Campeão solo: Jade. Aprovação imediata. :-)

Algoritmo 2-aproximativo linear para Cobertura de Vértices.

Prova de não-aproximabilidade do Caixeiro Viajante Geral.

04/02

Problema da soma do subconjunto (SUBSET-SUM): prova de NP-completude via redução de 3-SAT.

06/02

Esquema de aproximação totalmente polinomial (FPTAS): definição e aplicabilidade ao problema da soma do subconjunto (SUBSET-SUM).

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


NP-Completude	NP-Completeness
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)