Bibliografia básica:
- Concrete Mathematics, Graham, Knuth e Pataschink, ou sua tradução.
- Discrete Mathematics: Applied Combinatorics and Graph Theory, Townsend, M.
- Discrete Mathematics, Lovász e Vesztergombi.
Bibliografia complementar:
- Combinatorics for Computer Scientists, D. Breslauer, D.B. Dubhashi
- The Art of Computer Programming, Knuth, D.E..
- Introduction to Algorithms, Cormen, Leiserson, Rivest (Capítulos iniciais)
- Computer Mathematics, Coone, D.J., Bez, H.E.
- Applied Combinatorics, Tucker, A.
- generatingfunctionology, H. Wilf
Sistema de avaliação
- Média aritmética de três provas dá a média final.
- Tendo 75% de freqüência, o aluno com nota maior ou igual a 70 estará aprovado.
- Tendo 75% de freqüência, o aluno com nota maior ou igual a 40 e menor do que 70 estará habilidato a fazer a prova final.
- Em qualquer outro caso o aluno estará reprovado e será indicado se houve ou não infreqüência.
- O aluno que fizer a prova final estará aprovado apenas se a média aritmética da prova final e da média final for maior ou igual a 50.
Calendário de provas
Listas de exercícios
Referências para alguns exercícios das
listas
Resposta de alguns exercícios das listas: pdf1 (no último exercício o cálculo do constante não está correto, acho que tem que ser c < 0,4. Confiram.),pdf2,pdf3,pdf4
- 4a. Lista de exercícios .
- 5a. Lista de exercícios .
- 6a. Lista de exercícios .
- 7a. Lista de exercícios .
Tópicos das aulas
Aula 1 (16/10) - Motivação. Apresentação do curso.Aula 2 (18/10) - Axiomas de Peano. Princípio da Indução Finita (leia mais e faça os exercícios!).
Aula 3 (23/10) - Funções definidas por recorrência. Método iterativo. Números de Fibonacci.
Aula 4 (25/10) - Fórmula fechada para os números de Fibonacci.
(teto e chão).
Aula 5 (06/11) - Teto/Chão/Recorrência: análise de pior caso do algoritmo recursivo para Busca Binária.
Aula 6 (08/11) - Teto/Chão/Recorrência: análise de pior caso do Merge-Sort.
Aula 7 (13/11) - Teto/Chão/Recorrência: caso geral para Divisão-e-Conquista. (leia mais)
Aula 8 (20/11) - Aula de exercícios.
Aula 10 (27/11) - Correção da prova.
Aula 11 (29/11) - Solução geral de recorrências: equações lineares com coeficientes constantes.
Aula 12 (04/12) - Solução geral de recorrências: equações homogêneas com coeficientes constantes.
Aula 13 (06/12) - Solução geral de recorrências: equações homogêneas com coeficientes constantes.
Aula 14 (11/12) - Solução geral de recorrências: equações não-homogêneas com coeficientes constantes. leia mais)
Aula 15 (22/01) - Séries formais. (Ref: cap 2 do generatingfunctionology, leia mais)
Aula 16 (24/01) - Funções geradoras.
Aula 17 (29/01) - Resolvendo recorrências usando funções geradoras.
Aula 18 (31/01) - Resolvendo recorrências usando funções geradoras.
Aula 19 (05/02) - Resolvendo recorrências usando funções geradoras.
Aula 20 (07/02) - Permutações.
Aula 21 (12/02) - Combinações.
Aula 22 (14/02) - Multiconjuntos.
Aula 23 (19/02) - Probabilidade Discreta: definições e exemplos.
Aula 24 (21/02) - Probabilidade Discreta: eventos, probabilidade da união, intersecção,... de eventos
Aula 25 (26/02) - Probabilidade Discreta: variáveis aleatórias, independência de eventos.
Aula 26 (28/02) - Probabilidade Discreta: distribuição binomial.
Aula 28 (12/03) - Probabilidade Discreta: probabilidade condicional. (leia mais)
Aula 29 (14/03) - Probabilidade Discreta: esperança e variância.
Aula 30 (19/03) - Funções geradoras de probabilidade.
Aula 31 (21/03) - PROVA. October 2002 November 2002 December 2002 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 5 1 2 1 2 3 4 5 6 7 6 7 8 9 10 11 12 3 4 5 6 7 8 9 8 9 10 11 12 13 14 13 14 15 16 17 18 19 10 11 12 13 14 15 16 15 16 17 18 19 20 21 20 21 22 23 24 25 26 17 18 19 20 21 22 23 22 23 24 25 26 27 28 27 28 29 30 31 24 25 26 27 28 29 30 29 30 31 January 2003 February 2003 March 2003 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 1 1 5 6 7 8 9 10 11 2 3 4 5 6 7 8 2 3 4 5 6 7 8 12 13 14 15 16 17 18 9 10 11 12 13 14 15 9 10 11 12 13 14 15 19 20 21 22 23 24 25 16 17 18 19 20 21 22 16 17 18 19 20 21 22 26 27 28 29 30 31 23 24 25 26 27 28 23 24 25 26 27 28 29 30 31