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