CI237 - Matem�tica Discreta
1� semestre de 2009

Ementa:

1. No��es fundamentais da matem�tica.
2. Indu��o.
3. An�lise assint�tica.
4. Rela��es de Recorr�ncia.

Pr�-requisitos: Introdu��o � �lgebra (obrigat�rio); C�lculo 1 e C�lculo 2 (fortemente recomendado)

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

Bibiografia

1. Matem�tica Discreta e suas aplica��es, Kenneth Rosen. McGrawHill, 2009.

Bibliografia complementar


2. Introduction to Algorithms, Cormen, Leiserson, Rivest e Stein (Cap�tulos iniciais). (biblioteca)
3. How to prove it, Daniel Velleman. (biblioteca)
4. Introduction to algorithms, Udi Manber. (biblioteca)
5. Concrete Mathematics, R. Graham, D. Knuth e O. Pataschink (biblioteca)
6. Matem�tica Concreta, (tradu��o do Concrete Mathematics) Livros T�cnicos e Cient�ficos, Rio de Janeiro, 1995. (biblioteca).
7. The Art of Computer Programming vol. 1, D.E. Knuth. (biblioteca)
8. Language, proof and logic, Jon Barwise e John Etchemendy. (biblioteca)

Sistema de avalia��o: S�o 2 provas regulares com conte�do cumulativo mais uma prova final sobre toda a mat�ria.

• A m�dia ponderada das provas regulares com pesos 1 e 2 d� a m�dia parcial.
• Tendo 75% de freq��ncia, o aluno com m�dia parcial maior ou igual a 70 estar� aprovado.
• Tendo 75% de freq��ncia, o aluno com m�dia parcial maior ou igual a 40 e menor do que 70 estar� habilitado a fazer a prova final. A m�dia final � a m�dia aritm�tica da m�dia parcial com a nota da prova final, o aluno com m�dia final maior ou igual a 50 estar� aprovado.
• Em qualquer outro caso o aluno estar� reprovado e ser� indicado se houve ou n�o freq��ncia m�nima.

Calend�rio

• 02/03 - In�cio das aulas.
• 07/04 - Prova 1.
• 09/04 - Prazo final para protocolar cancelamento de disciplinas semestrais.
• 23/06 - Prova 2.
• 26/06 - �ltimo dia letivo.
• 07/07 - Prova final.

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

          June 2009      
     Su Mo Tu We Th Fr Sa 
         1  2  3  4  5  6 
      7  8  9 10 11 12 13 
     14 15 16 17 18 19 20 
     21 22 23 24 25 26 27 
     28 29 30 

  

Listas de exerc�cios

Programa��o das aulas: (tentativa) [Resumos]

Aula 01 -- apresenta��o.
Aula 02 -- "e", "ou", "n�o", "se-ent�o", "se e somente se", equivalencia logica.
Aula 03 -- regras de inferencias.
Aula 04 -- quantificadores, generaliza��o e instancia��o.
Aula 05 -- aula de exercicios.
Aula 06 -- Conjuntos.
Aula 07 -- Somat�rios.
Aula 08 -- t�cnicas de prova.
Aula 09 -- aula de exercicios.
Aula 10 -- Prova
Aula 11 -- Corre��o da prova
Aula 12 -- corre��o de progaramas (sem invariante de la�o).
Aula 13 -- Indu��o. 
Aula 14 -- Indu��o (outras formas).
Aula 15 -- Indu��o e boa-ordem.
Aula 16 -- Invariante de la�o. Defini��es recursivas e algoritmos. 
Aula 17 -- palestra da semana acad�mica
Aula 18 -- AULA DE EXERC�CIOS sobre indu��o.
Aula 19 -- Fun��es inteiras: chao e teto. 
Aula 20 -- Fun��es inteiras: chao e teto. 
Aula 21 -- Fun��es definidas recursivamente. 
Aula 22 -- comportamento assint�tico de fun��es e Nota��o assint�tica.
Aula 23 -- Nota��o assint�tica.
Aula 24 -- Nota��o assint�tica em equa��es.
Aula 25 -- Solu��o assint�tica de Recorr�ncias.
Aula 26 -- Solu��o assint�tica de Recorr�ncias.
Aula 27 -- Solu��o assint�tica de Recorr�ncias.
Aula 28 -- Solu��o assint�tica de Recorr�ncias.
Aula 29 -- Aula de exerc�cios.
Aula 30 -- Prova
  

Atendimento Horario de atendimento

Links
Provas de semestres anteriores.
Arquimedes fazia an�lise combinat�ria h� 2.200 anos
Problemas pra estacionar?
Laszlo Babai Discrete Math Puzzles 1, 2
Puzzles, Games and Recreations Related to Research in Foundations of Computer Science