Selected Topics in Algorithms  —  2012/2

Tópicos Especiais em Algoritmos  —  2012/2

Versão em português    English version

Main page

Página principal

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
113:00DANIEL LOPES BRAZ DOS SANTOS
213:04GUILHERME IRIA D'ABBADIA FONTES PEREIRA
313:08CARLOS FILIPE BENEVIDES
413:12JUAN CARLOS TOLEDO BAPTISTA
513:16LUIZ FELIPE DA COSTA PERICOLO BARBOSA
613:20THIAGO MACHADO SANTOS
713:24FILIPE QIANG ZHOU
813:28JADE MOREIRA DA COSTA
913:32PEDRO IVO MARQUES L DE L RIBEIRO
1013:36FÁBIO FERMAN
1113:40PEDRO FELLIPE PASSOS CORTEZ
1213:44DANIEL DAIM LOPES DE ARAUJO
1313:48WANDER MENDONÇA SOARES
1413:52BRENO ANDRADE VECCI CHAGAS
1513:56MAGNO ARLINDO GOMES FERREIRA
1614:00LUCAS SIMOES DE SOUSA ARNAUD
1714:04RODRIGO DE SOUZA STUHL
1814:08RAPHAEL DUARTE PAIVA
1914:12FABIO MEDEIROS RANGEL
2014:16LEONARDO MÕES GOMES
2114:20VITOR PEREIRA MACHADO
2214:24DIEGO DE OLIVEIRA MARTINS
2314:28MATEUS GREGORIO DE SOUZA
2414:32ANDRÉ GUSTAVO LIMA FIGUEIREDO
2514:36CARLOS VICTOR DA SILVA
2614:40THIAGO GONÇALVES ESCOBAR
2714:44BRUNO SOUSA CAMPOS DA COSTA
2814:48FLAVIO COUTINHO DA COSTA
2914:52GABRIEL RODRIGUES DO CARMO
3014:56LUIZ FELIPE ANTUNES DIAS
3115:00PALOMA THOME DE LIMA
3215:04AUGUSTO ACIOLI PINHO VANDERLEY
3315:08HÉLIO HENRIQUE MACHADO BARBOSA
3415:12MARCIO FARIAS DIAS RODRIGUES

Bibliografia sugerida

Suggested reading

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)
         

Conteúdo das aulas

Lecture notes

15/10


Início da Primeira Parte do curso.

Por quê estudar algoritmos? 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: 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) ≤ 2d 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 n2/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 Gn,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 Kj(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 Kj(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 Kj(A) é polinomial no tamanho de I. Fixa-se agora a parte da entrada de cada Kj(A) que diz respeito à instância de Π como sendo exatamente I, fixa-se o endereço da próxima instrução da entrada de K1(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 Kt(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).  
 

Voltar ao topo

Back to top