MAC310 Matemática Concreta / MAC5827 Tópicos em Combinatória

BCC / Pós - 2o. Semestre de 1999

Aulas

• 9/8/99 Apresentação da disciplina; questionário.
• 11/8/99 Discussão sobre contagem de mems; a relação entre mems e tempo de execução. O exemplo do miles_span [miles_span.dvi.gz | miles_span.ps.gz | miles_span.w.gz]. Quicksort; discussão inicial.
• 16/8/99 Quicksort (continuação), caso médio.
• 18/8/99 Quicksort (continuação), variância, desigualdades de Markov e Chebyshev, concentração em torno da média. Distribuição limite.
• 23/8/99 Introdução a recorrências. Classificação de recorrências. Recorrências lineares de ordem t com coeficientes constantes. Teorema 2.2.
• 25/9/99 Teorema 2.2, continuação. Recorrências do tipo divisão-e-conquista (introdução).
• 30/9/99 Não haverá aula.
• 1/9/99 Recorrências do tipo divisão-e-conquista (continuação). Teoremas 2.5 e 2.6.
• 6/9/99 Semana da Pátria, recesso escolar.
• 8/9/99 Semana da Pátria, recesso escolar.
• 13/9/99 Aula de exercícios. Entrega de exercícios.
• 15/9/99 Introdução a funções geradoras. Funções ordinárias e exponenciais.
• 20/9/99 Mais funções geradoras.
• 22/9/99 Mais funções geradoras; solução de recorrências.
• 27/9/99 Teorema 3.3, recorrências lineares e funções geradoras. A recorrência do quicksort.
• 29/9/99 Expansão de funções geradoras. Teorema de Taylor e o binômio de Newton generalizado. Transformações com f.gs, a transformada binomial. Análise do quicksort com a escolha do pivô pela regra da "mediana de três."
• 4/10/99 Funções geradoras e enumeração. Árvores binárias. O método simbólico e o teorema de transferência (Teorema 3.7). O problema do troco de Pólya.
• 6/10/99 Enumeração não-rotulada (e funções geradoras ordinárias) e enumeração rotulada (e funções geradoras exponenciais). O exemplo das permutações. O teorema de transferência (Teorema 3.8). Enumeração de partições de um conjunto (números de Bell). O operador z(d/dz)log.
• 11/10/99 Enumeração rotulada, continuação.
• 13/10/99 Enumeração rotulada: o formalismo de Wilf. A URL do livro de Herb Wilf: http://www.math.upenn.edu/~wilf/DownldGF.html. Cartas, mãos, e baralhos. Exemplos: grafos conexos e desconexos, permutações e partições de conjuntos. O teorema exponencial (Teorema 3.4.1 de Wilf).
• 15/10/99 Evento especial: Dia de Algoritmos e Combinatória.
• 18/10/99 O teorema exponencial, continuação. Exemplos: permutações, partições de conjuntos, grafos 2-regulares. Recorrência para enumeração de grafos conexos rotulados através do teorema exponencial e do operador z(d/dz)log. Enumeração de árvores rotuladas e a fórmula de Cayley. A fórmula de inversão de Lagrange (Teorema 3.9 de Sedgewick-Flajolet). Seminário. Os alunos deverão estudar o paper de Knuth sobre hashing com probing linear [lpg.tex.gz] para fazerem um seminário dentro de algumas semanas. A referência bibliográfica completa deste paper é Knuth, D.E., Linear probing and graphs, Algorithmica 22 (1998), no. 4, 561-568.
• 20/10/99 Inversão de Lagrange, continuação. Exemplos: fórmula de Cayley, árvores ternárias. Funções geradoras para distribuições de probabilidade.
• 25/10/99 Funções geradoras de probabilidade (FGP), continuação. Esperança e média pela FGP. A partir deste ponto, passamos a seguir algumas seções do Capítulo 8 de Matemática Concreta, de Graham, Knuth, e Patashnik. O jogo de moedas.
• 27/10/99 O jogo de moedas, continuação. O jogo Penney ante. Veja http://www.ime.usp.br/~yoshi/opta-fun/.
• 1/11/99 Recesso escolar.
• 3/11/99 Hashing (Seção 8.4 do Matemática Concreta). O caso de busca sem sucesso e o caso de busca com sucesso (introdução).
• 8/11/99 O caso de busca com sucesso (continuação). Seminário sobre o trabalho de Knuth (Linear Probing and Graphs).
• 10/11/99 Seminário sobre o trabalho de Knuth (continuação).
• 15/11/99 Recesso escolar.
• 17/11/99 Seminário sobre o trabalho de Knuth (continuação).
• 22/11/99 [Yoshi em Brasília] Não houve aula.
• 24/11/99 [Yoshi em Brasília] Aula de exercícios.
• 29/11/99 [Yoshi no Workshop Mambucaba] Não houve aula.
• 1/12/99 [Yoshi no Workshop Mambucaba] Seção 3 do trabalho de Knuth (Linear Probing and Graphs), exercícios e discussão sobre a matéria (código de Prüfer).
• 6/11/99 Reunião breve sobre avaliação.
• 8/11/99 Análise assintótica.

Last modified: Mon Dec 13 08:30:28 EDT 1999