Matemática Discreta

Professores Responsáveis

• Em 2009.2:
  • Matemática Discreta - Turma S71 - 2009.2 - Professor Adolfo Neto
  • Matemática Discreta - Turma S73 - 2009.2 - Professor João Fabro

Oferecimentos Anteriores na UTFPR

• Matemática Discreta - Prof. Ricardo Lüders (UTFPR)

Material do prof. Ricardo Luders

• Notas de Aula (completo)
  • Notas de aula 1 - Métodos de Prova
  • Notas de aula 2 - Conjuntos e Contagem
  • Notas de aula 3 - Permutações, Arranjos e Combinações
  • Notas de aula 4 - Funções e Relações
  • Notas de aula 5 - Grafos - Parte I (Árvores)
  • Notas de aula 6 - Grafos - Parte II (Algoritmos)
  • Notas de aula 7 - Linguagens Formais

• Listas de exercícios
  • Lista de Exercícios 1
  • Lista de Exercícios 2
  • Lista de Exercícios 3
  • Lista de Exercícios 4
  • Lista de Exercícios 5
  • Lista de Exercícios 7

Links para oferecimentos da disciplina em outras universidades

• Matemática Discreta - Prof. Renato Carmo (UFPR)
• Matemática Discreta - Profa. Christiane Neme Campos (UNIFESP - São José dos Campos)
• Matemática Discreta - Prof. Jair Donadelli (UFPR)
• Matemática Discreta - Prof. José Guimarães (UFSCAR -Sorocaba)
  • Apostila de Matemática Discreta do prof. José Guimarães
• Matemática Discreta - Prof. Carlos Caleiro (IST)
• Matemática Discreta (IF670) - CIn - UFPE
• Matemática Discreta - Luís Sequeira - Universidade do Porto
• Great Theoretical Ideas in Computer Science - Anupam Gupta & John Lafferty (Carnegie-Mellon University)
• Algoritmos e teoria dos grafos (2009.2) - Prof. André Guedes (UFPR)

Plano de Ensino

Objetivo

Capacitar o aluno a compreender os aspectos formais da Ciência da Computação, apresentando as principais estruturas matemáticas discretas utilizadas, assim como desenvolver seu raciocínio abstrato e relacionar este conhecimento com sua capacidade de desenvolver e caracterizar formalmente diversos algoritmos.

Ementa

Métodos de Prova, Indução e Recursão; Conjuntos e Análise Combinatória; Relações e Funções; Grafos, Árvores e Algoritmos; Estruturas Algébricas; Álgebra Booleana e Circuitos Lógicos.

Conteúdo

ITEM	EMENTA	CONTEÚDO
1	Métodos de Prova, Indução e Recursão	Técnicas de demonstração matemática: direta, contraposição, absurdo e indução. Seqüências definidas por recorrência. Solução de relações de recorrência. Algoritmos recursivos.
2	Conjuntos e Análise Combinatória	Conjuntos. Operações binárias e unárias. Operações com conjuntos. Cardinalidade. Princípios da multiplicação e adição. Princípio da inclusão e exclusão. Princípio das casas de pombos. Permutações e Combinações.
3	Relações e Funções	Relações binárias. Autorrelação e propriedades reflexiva, simétrica, anti-simétrica e transitiva. Fecho de uma relação. Relações de ordem parcial e de equivalência. Funções.
4	Grafos, Árvores e Algoritmos	Grafos e suas representações. Terminologia. Isomorfismo. Grafos planares. Matriz de adjacência. Árvores, propriedades e aplicações. Acessibilidade. Algoritmo de Warshall. Caminho de Euler e circuito Hamiltoniano. Caminho mínimo. Árvore geradora mínima. Algoritmos de Dijkstra e Prim. Busca em nível e em profundidade. Pontos de articulação.
5	Estruturas Algébricas	Propriedades das operações binárias. Grupóides, semigrupos, monóides e grupos. Homomorfismo.
6	Álgebra Booleana e Circuitos Lógicos	Circuitos lógicos. Propriedades da Álgebra de Boole. Funções e expressões booleanas. Formas normais e expressões booleanas equivalentes. Minimização de expressões booleanas. Mapas de Karnaugh

Referências

Referências Básicas

GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação, 5ª Edição, Rio de Janeiro: LTC, 2004.

Referências Complementares

ROSEN, Kenneth H. Discrete Mathematics and Its Applications, 6th Edition, New York: McGraw-Hill, 2006.

ROSEN, Kenneth H. Student's Solutions Guide to accompany Discrete Mathematics and Its Applications, 6th Edition, New York: McGraw-Hill, 2006.

LIPSHUTZ, S.; LIPSON, M. Teoria e Problemas de Matemática Discreta, Coleção Schaum, 2ª Edição, Rio de Janeiro: Bookman, 2004.

LIPSHUTZ, S. 2000 Solved Problems in Discrete Mathematics, Coleção Schaum, 1ª Edição, McGraw-Hill, 1991.

MENEZES, Paulo B. Matemática Discreta para Computação e Informática, 2ª Edição, Porto Alegre: Editora Sagra Luzzatto, 2005.

ROSS, K. A.; WRIGHT, C. R. Discrete Mathematics, 5th Edition, Prentice-Hall, 2002.

EPP, S. S. Discrete Mathematics with Applications, 3ª Edição, Brooks Cole, 2003.

EPP, S. S. Solutions Manual for Epp's Discrete Mathematics with Applications, 3ª Edição, Brooks Cole, 2004.

MELLO, M. P.; SANTOS, J. P.; MURARI, I. T. C. Introdução à Análise Combinatória, 1ª Edição, Rio de Janeiro: Ciência Moderna, 2008.

SANTOS, J. P.; ESTRADA, E. Problemas Resolvidos de Combinatória, 1ª Edição, Rio de Janeiro: Ciência Moderna, 2007.

BOAVENTURA NETTO, PAULO O. Grafos – Teoria, Modelos, Algoritmos, 4ª Edição, Edgard Blücher, 2006.

NICOLETTI, M. C.; HRUSCHKA JR.. E. R. Fundamentos da Teoria dos Grafos para Computação, 1ª Edição, Editora da UFSCar, 2007.

IEZZI, GELSON; DOMINGUES, H. H. Álgebra Moderna, 4ª Edição, Atual Editora, 2003.

SCHEINERMAN, Edward. Matemática Discreta: Uma Introdução. São Paulo: Thomson, 2003. Página do livro na editora:http://www.thomsonlearning.com.br/detalheLivro.do?id=102629#

Materiais Complementares

Apostilas

• Apostila de Introdução à Lógica, de Marcelo Coniglio, Walter Carnielli e Ricardo Bianconi
  • Ver 1o. capítulo, que fala de Cantor.

Animações de Algoritmos

Prim

• Algoritmo de Prim (unf)
• Algoritmo de Prim (upatras)

Dijkstra

• Algoritmo de Dijkstra (upatras)
• Algoritmo de Dijkstra (oopweb)
• Algoritmo de Dijkstra (sunsysb)
• Algoritmo de Dijkstra (na Wikipedia)

Percurso em Grafos

• Várias animações de percurso em grafos
  • Depth First Search (bme)
  • Breadth First Search (bme)

Implementações de Algoritmos em Lua

• Algoritmo de Warshall em Lua
  • Warshall's Algorithm in Lua

Diversos

• Várias animações de algoritmos

Páginas na Internet

Grafos Eulerianos e Hamiltonianos

• Grafos Eulerianos e Hamiltonianos - Prof. Michel Gagnon

Algoritmo de Busca de Articulação

• Algoritmo de Busca de Articulação - Prof. Michel Gagnon