"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

2º semestre de 2008

3ª 15:30, 6ª 13:30 na sala CT 11

Notícias:

Sumário: Ementa -- Bibliografia -- Provas -- Listas -- Aulas -- Calendário -- Notas -- Links -- Monitor -- Atendimento

Conteúdo:

Noções elementares da matemática.
Indução.
Análise assintótica.
Relações de Recorrência.

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.

Pré-requisito: Introdução à Álgebra (obrigatório)

Cálculo 1 (fortemente recomendado)

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

Bibliografia:

How to prove it Daniel Velleman. (biblioteca)
Language, proof and logic, Jon Barwise e John Etchemendy. (bibkioteca)
Concrete Mathematics, R. Graham, D. Knuth e O. Pataschink (biblioteca) ou sua tradução: Matemática Concreta, Livros Técnicos e Científicos, Rio de Janeiro, 1995. (biblioteca).
The Art of Computer Programming vol. 1, D.E. Knuth. (biblioteca)
Introduction to Algorithms, Cormen, Leiserson, Rivest e Stein (Capítulos iniciais). (Biblioteca)
Introduction to algorithms Udi Manber. biblioteca
Bibliografis complementar
Discrete mathematics : a unified approach, Stephen A. Wiitala. (biblioteca)
Discrete mathematics : applied combinatorics and graph theory, Michael Townsend. (biblioteca)
Discrete mathematics with algorithms Michael O. Albertson, Joan P. Hutchinson. (biblioteca)(parcialmente disponível aqui)
Discrete mathematics with applications, H. F. Mattson, Jr. (biblioteca)
Introdução à Análise Combinatória, J.P.O. Santos, M.P. Mello, I.T.C. Murari, 3a. edição, editora Unicamp. (biblioteca)

Material de apoio

C. A. R. Hoare. "An axiomatic basis for computer programming". Communications of the ACM, 12(10):576–585, October 1969. doi:10.1145/363235.363259
R. W. Floyd. "Assigning meanings to programs." Proceedings of the American Mathematical Society Symposia on Applied Mathematics. Vol. 19, pp. 19–31. 1967.
A constructive approach to the problem of program correctness, Edsger W. Dijkstra.
A constructive approach to the problem of program correctness A, Edsger W. Dijkstra
Towards correct programs, Edsger W. Dijkstra
Concern for correctness as a guiding principle for program construction, Edsger W. Dijkstra
A non algebraic example of a constructive correctness proof, Edsger W. Dijkstra
Correctness concerns and, among other things, why they are resented, Edsger W. Dijkstra
Why correctness must be a mathematical concern, Edsger W. Dijkstra
George S. Lueker, Some Techniques for Solving Recurrences, ACM Computing Surveys Volume 12 , Issue 4 (December 1980) Pages: 419 - 436 clique aqui

Avaliação

São 3 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, 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.

O aluno que faltar de uma prova pode pedir segunda chamada, desde que o motivo que o levou a perder a prova esteja previsto na seção V da resolução 37/97 e desde que quem perdeu a prova cumpra as formalidades exigidas pela resolução.

Calendário

28/07 - Início das aulas.
19/09 - Prazo final para protocolar cancelamento de disciplinas semestrais.
02/09 - Prova 1.
07/10 - Prova 2.
21/11 - Prova 3.
22/11 - Último dia letivo do 1o semestre de 2008.
02/12 - Prova final.

 
         July 2008               August 2008             September 2008   
     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 



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

Listas de exercícios

Programação das aulas: (tentativa)

Aula 01 -- "e", "ou", "não".  (referencia:1)
Aula 02 -- "se-então", "se e somente se", quantificadores. (referencia:1)
Aula 03 -- conjuntos, somatórios e produtório. (referencia:1,11)
Aula 04 -- Exemplos de técnicas provas. (referencia:1,2)
Aula 05 -- Indução: axioma/princípio da indução. (referencias:1,2,4)
Aula 06 -- Indução: exemplos. (referencias:1,4,8)
Aula 07 -- Indução: +exemplos, 2a forma do PIF (referencias:1,4,8)
Aula 08 -- Indução: principio da boa ordenação. (referencias:1,4,8)
Aula 09 -- Indução: +exemplos (referencias:1,4,8)
Aula 10 -- aula de exercicios.
Aula 11 -- prova 1
Aula 12 -- correção da prova 1.
Aula 13 -- Indução: correção de algoritmos (referencia)
Aula 14 -- Indução: invariante de laço. (referencia:2 (§16.5))
Aula 15 -- Indução: invariante de laço. (referencia:2 (§16.5))
Aula 16 -- Funções (referencia:1). Funções inteiras: chao e teto. (referencia:3)
Aula 17 -- chao e teto. 
Aula 18 -- Funções definidas recursivamente. (referencias: §6.3 em 1)
Aula 19 -- comportamento assintótico de funções.(referencias: 3) 
Aula 20 -- aula de exercicios.
Aula 21 -- prova 2
Aula 22 -- correção da prova 2.
Aula 23 -- Notação assintótica.(referencias: 4,5,6)
Aula 24 -- Notação assintótica.(referencias:4,5,6)
Aula 25 -- Notação assintótica em equações.(referencias:6)
Aula 26 -- Solução assintótica de Recorrências.(referencias:5,6)
Aula 27 -- Solução assintótica de Recorrências.(referencias:5,6)
Aula 28 -- Solução assintótica de Recorrências.(referencias:5,6)
Aula 29 -- Aula de exercícios.
Aula 30 -- prova 3

O monitor é Leandro Zatesko (gmail:zehtesko). Ele atende as 5as. das 20 até 21 hs na mesa de estudos no saguao do dinf.

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

Pré-requisito:	Introdução à Álgebra (obrigatório)
	Cálculo 1 (fortemente recomendado)