"Can you do addition?" the White Queen asked. "What's one and one and one and one and one and one and one and one and one and one?"
"I don't know," said Alice. "I lost count." --- Lewis Carrol, Through the Looking Glass.

CI237 - Matemática Discreta

PA-01

Segundo semestre de 2003

Ementa -- Bibliografia -- Provas -- Listas -- Aulas -- Notas -- Links

Atendimento

Ementa:

Indução.
Análise Combinatória.
Recorrência.
Funções Geradoras.

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:

Introdução à Análise Combinatória, J.P.O. Santos, M.P. Mello, I.T.C. Murari, 3a. edição, editora Unicamp
Discrete Mathematics: Applied Combinatorics and Graph Theory, M. Townsend.
Concrete Mathematics, R. Graham, D. Knuth e O. Pataschink (ou sua tradução: Matemática Concreta).

Bibliografia complementar:

Matemática Discreta, E.R. Scheinerman
The Art of Computer Programming vol. 1, D.E. Knuth
Introduction to Algorithms, Cormen, Leiserson, Rivest (Capítulos iniciais)
Computer Mathematics, D.J. Coone, H.E. Bez
Applied Combinatorics, A. Tucker

Leitura complementar:

Sistema de avaliação

Média aritmética de duas 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

Prova 1:quinta dia 06/11 21hs na PA02
Prova 2: nova data:29/01/04 as 19hs na PA02
Prova Final: 17/02/04 as 21hs na PA02
2a. chamada: 05/02/04 as 19hs

Não haverá aulas em:

de 15/12/2003 ate 18/01/2004 - recesso

Listas de exercícios

Tópicos das aulas

Aula 01 - 16/09 - ementa e bibliografia.

Aula 02 - 18/09 - Conjuntos, notações de somatório e produtório. Ref.: pags. 1 -- 10.

Aula 03 - 23/09 - Indução. Ref.: pags. 10 -- 12

Aula 04 - 25/09 - Indução - exemplos. 2a. forma do PI. Ref.: pags. 12 -- 18

Aula 05 - 30/09 - Indução - exemplos.

Aula 06 - 02/10 - Inducao - exercicios.

Aula 07 - 07/10 - Principios aditivo e multiplicativo. pags. 27 -- 42

Aula 08 - 09/10 - Arranjos e Combinações. pags. 42 -- 54

Aula 09 - 14/10 - No. de solucoes inteiras positivas/nao-negativas de equacoes. pags. 67 -- 73

Aula 10 - 16/10 - Arranjos, Combinacoes e Permutacoes com repeticao. pags. 73 -- 80

Aula 11 - 21/10 - Binomios. triangulo de Pascal. pags. 80 -- 85

Aula 12 - 23/10 - Principio da Incusao/Exclusao. pags. 89 -- 93

Aula 13 - 28/10 - Principio da Incusao/Exclusao - exemplos. pags. 93 -- 98.

Aula 14 - 30/10 - Principio da Incusao/Exclusao - funcao de Euler e permutacoes caoticas. pags. 98 -- 106.

Aula 15 - 04/11 - Era pra ser prova mas a sala foi "invadida" por engenheiros!.

Aula 16 - 06/11 - PROVA

Aula 17 - 11/11 - Correção da prova.

Aula 18 - 13/11 - Contagem de funções. pags. 106 - 108

Aula 19 - 18/11 - Funcoes geradoras. pags. 113 - 118

Aula 20 - 20/11 - Funcoes geradoras. pags. 113 - 123

Aula 21 - 25/11 - Funcoes geradoras. pags. 123 - 127.

Aula 22 - 27/11 - Funcoes geradoras exponenciais. pags. 127 - 135.

Aula 23 - 02/12 - Relações de recorrencia.

Aula 24 - 04/12 - Solução de recorencias por função geradora.

Aula 25 - 09/12 - Solução de recorencias por função geradora.

Aula 26 - 11/12 - Solução de recorencias por função geradora.

RECESSO 14/12/03 - 18/01/2004

Aula 27 - 20/01 - Solução de recorencias

Aula 28 - 22/01 - Solução de recorencias por raizes caracteristicas

Aula 29 - 27/01 - Solução de recorencias por raizes caracteristicas

Aula 30 - 29/01 - PROVA

Aula 31 - 03/02 - nao havera aula

Aula 32 - 05/02 - nao havera aula

September 2003 October 2003 November 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 6 1 2 3 4 1 7 8 9 10 11 12 13 5 6 7 8 9 10 11 2 3 4 5 6 7 8 14 15 16 17 18 19 20 12 13 14 15 16 17 18 9 10 11 12 13 14 15 21 22 23 24 25 26 27 19 20 21 22 23 24 25 16 17 18 19 20 21 22 28 29 30 26 27 28 29 30 31 23 24 25 26 27 28 29 December 2003 January 2004 February 2004 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 6 1 2 3 1 2 3 4 5 6 7 7 8 9 10 11 12 13 4 5 6 7 8 9 10 8 9 10 11 12 13 14 14 15 16 17 18 19 20 11 12 13 14 15 16 17 15 16 17 18 19 20 21 21 22 23 24 25 26 27 18 19 20 21 22 23 24 22 23 24 25 26 27 28 28 29 30 31 25 26 27 28 29 30 31 29

Links

cut-the-knot (sugerido pelo Nilson Thome)
Discrete Mathematics From Wikipedia, the free encyclopedia.

``I was interviewed in the Israeli Radio for five minutes and I said that more than 2000 years ago, Euclid proved that there are infinitely many primes. Immediately the host interuppted me and asked: `Are there still infinitely many primes?' ´´
Noga Alon, (Distinguished Lecture series, Princeton Applied and Computational Mathematics Program, Feb. 13, 2003).