CI237 - Matemática Discreta

Turma A

Primeiro semestre de 2003


Ementa -- Bibliografia -- Provas -- Listas -- Aulas -- Frequência

Notas


Ementa:

Objetivos:

Desenvolver nos alunos um grau satisfatório de maturidade matemática e apresentar estruturas e técnicas de interesse para estudantes de ciência da computação.

Carga horária: 60 Créditos: 4 Responsável: Jair.

Bibliografia básica:

  1. Concrete Mathematics, Graham, Knuth e Pataschink (ou sua tradução).
  2. Discrete Mathematics: Applied Combinatorics and Graph Theory, Townsend.
  3. generatingfunctionology, H. Wilf

Bibliografia complementar:

Leitura complementar:

Sistema de avaliação

Calendário de provas

Não haverá aulas em:

Listas de exercícios

Arquivo pdf com os exercícios passados em aula.
Tópicos das aulas
Aula 01 - 22/04 - Bla

Aula 02 - 24/04 - Axiomas de Peano e Indução (fraca) (Ref.: Cap 1 de [2]).

Aula 03 - 29/04 - Indução - exemplos (Ref.: Cap 1 de [2]).

Aula 04 - 06/05 - Indução forte (Ref.: Cap 1 de [2]).

Aula 05 - 06/05 - Indução forte - exemplos (Ref.: Cap 1 de [2]).

Aula 06 - 13/05 - Função definida por recorrência (Ref.: Cap 1 e Sec 4.1 de [2])

Aula 07 - 15/05 - Exemplos de recorrência (Ref.: Sec 2.1 de [2]). Somas (Ref.: Sec 2.1,2.2 de [1])

Aula 08 - 20/05 - Resolução de recorrências. Caso médio do Quick Sort. (Ref.: Sec 2.1,2.2 de [1]).

Aula 09 - 22/05 - Números harmônicos (Ref.: Sec 6.3 de [1]).

Aula 10 - 27/05 - Recorrência linear homogênea com coeficientes constantes (Ref.: Sec 4.2 de [2]).

Aula 11 - 29/05 - Solução de Recorrência linear homogênea com coeficientes constantes - Método das raízes características (Ref.: Sec 4.3 de [2]).

Aula 12 - 03/06 - Números de Fibonacci (Ref.: Sec 6.6 de [1]).

Aula 13 - 05/06 - Aula de dúvidas.

Aula 14 - 10/06 - Método das raízes características para raízes de multiplicidade >1 (Ref.: Sec 4.3.2 de [2]).

Aula 15 - 12/06 - Solução de recorrências não-homogêneas (Ref.: Sec 4.3.3 de [2]).

Aula 16 - 16/06 - Estimativas para recorrências

Aula 17 - 24/06 - Prova

Aula 18 - 26/06 - Séries Formais. (Ref.: Cap 2 de [3])

Aula 19 - 01/07 - Manipulação de séries formais. (Ref.: Sec 7.2 de [1])

Aula 20 - 03/07 - Funções geradoras. Série de potencias de 1/(1-x-x²).

Aula 21 - 10/07 - Funções geradoras e equações de recorrência.(Ref.: Sec 7.3 de [1])

Aula 22 - 22/07 - Funções geradoras e equações de recorrência -- EXEMPLOS.

Aula 23 - 24/07 - Funções geradoras e equações de recorrência -- EXEMPLOS.

Aula 24 - 29/07 - Permutações(Ref.: Cap 2 de [2])

Aula 25 - 31/07 - Combinações.(Ref.: Cap 2 de [2])

Aula 26 - 05/08 - Multiconjuntos.(Ref.: Cap 2 de [2])

Aula 27 - 07/08 - Contagem por distribuição. (Ref.: Sec 2.3.2 de [2])

Aula 28 - 12/08 - No. de soluções inteiras positivas de equações.

Aula 29 - 14/08 -

Aula 30 - 21/08 - PROVA

April 2003 May 2003 June 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 5 1 2 3 1 2 3 4 5 6 7 6 7 8 9 10 11 12 4 5 6 7 8 9 10 8 9 10 11 12 13 14 13 14 15 16 17 18 19 11 12 13 14 15 16 17 15 16 17 18 19 20 21 20 21 22 23 24 25 26 18 19 20 21 22 23 24 22 23 24 25 26 27 28 27 28 29 30 25 26 27 28 29 30 31 29 30 July 2003 August 2003 September 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 5 1 2 1 2 3 4 5 6 6 7 8 9 10 11 12 3 4 5 6 7 8 9 7 8 9 10 11 12 13 13 14 15 16 17 18 19 10 11 12 13 14 15 16 14 15 16 17 18 19 20 20 21 22 23 24 25 26 17 18 19 20 21 22 23 21 22 23 24 25 26 27 27 28 29 30 31 24 25 26 27 28 29 30 28 29 30 31