Matemática Discreta
(→Referências Básicas) |
(→Referências Complementares) |
||
| Linha 166: | Linha 166: | ||
IEZZI, GELSON; DOMINGUES, H. H. Álgebra Moderna, 4ª Edição, Atual Editora, 2003. | 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, | + | SCHEINERMAN, Edward. Matemática Discreta: Uma Introdução. São Paulo: Thomson, 2010. <!-- Página do livro na editora:http://www.thomsonlearning.com.br/detalheLivro.do?id=102629# --> |
SANTOS, J. Plínio de O.; ESTRADA, Eduardo Luis. Problemas resolvidos de combinatória. Rio de Janeiro: Ciência Moderna, 2007. 202 p. : ISBN 9788573936247 http://biblioteca.utfpr.edu.br/pergamum/biblioteca/index.php?resolution2=1024_1#posicao_dados_acervo | SANTOS, J. Plínio de O.; ESTRADA, Eduardo Luis. Problemas resolvidos de combinatória. Rio de Janeiro: Ciência Moderna, 2007. 202 p. : ISBN 9788573936247 http://biblioteca.utfpr.edu.br/pergamum/biblioteca/index.php?resolution2=1024_1#posicao_dados_acervo | ||
Edição atual tal como 11h50min de 18 de novembro de 2011
Tabela de conteúdo |
Professores Responsáveis
- Matemática Discreta - Turma S71 - 2010.1 - Professor Adolfo Neto
- 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
Material do prof. Ricardo Luders
- Listas de exercícios
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)
- 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)
- Algoritmos e teoria dos grafos - Prof. Michel Gagnon (UFPR)
- Advanced Computer Programming (ver slides sobre Graph Algoritms)
- Network Optimization - Prof. James Orlin (MIT)
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
| |
|
|
| |
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. |
| |
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. |
| |
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. |
| |
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. |
| |
Estruturas Algébricas | Propriedades das operações binárias.
Grupóides, semigrupos, monóides e grupos. Homomorfismo. |
| |
Á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. LIPSCHUTZ, Seymour. Teoria e Problemas de Matemática Discreta. 2a ed., Porto Alegre, Bookman, 2004. LOVÁSZ, L.; PELIKÁN, J.; VESZTERGOMBI, K.. Matemática Discreta – Textos Universitários. Rio de Janeiro, Sociedade Brasileira de Matemática, 2003.
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, 2010.
SANTOS, J. Plínio de O.; ESTRADA, Eduardo Luis. Problemas resolvidos de combinatória. Rio de Janeiro: Ciência Moderna, 2007. 202 p. : ISBN 9788573936247 http://biblioteca.utfpr.edu.br/pergamum/biblioteca/index.php?resolution2=1024_1#posicao_dados_acervo
Pré-requisitos
É desejável (mas não obrigatório) que o aluno tenha sido aprovado em Lógica para Computação (IF61B). Os pré-requisitos da disciplina são os mesmos de Lógica para Computação. Alguns conhecimentos adquiridos em Lógica para Computação serão exigidos nesta disciplina.
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
Dijkstra
- Algoritmo de Dijkstra (tokushima)
- Algoritmo de Dijkstra (upatras)
- Algoritmo de Dijkstra (oopweb)
- Algoritmo de Dijkstra (sunsysb)
- Algoritmo de Dijkstra (na Wikipedia)
Percurso em Grafos
Implementações de Algoritmos em Lua
- Use http://www.lua.org/demo.html para executar o algoritmo do seu browser.
Diversos
- Várias animações de algoritmos
- Diversas animações de algoritmos para grafos (em PDF e PPT), entre os quais:
- Breadth First Search
- Depth First Search
- Topological Sorting
- Dijkstra's Algorithm
- Spanning Tree Algorithms
Páginas na Internet
Algoritmo de Prim
- http://students.ceid.upatras.gr/~papagel/project/prim.htm
- http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/prim.html
- http://en.wikipedia.org/wiki/Prim%27s_algorithm
Grafos Eulerianos e Hamiltonianos
Algoritmo de Busca de Articulação
- Algoritmo de Busca de Articulação - Prof. Michel Gagnon
- Articulações e biconexão - Paulo Feofiloff (IME-USP)
- Articulações e Biconexão, Felipe Nievola
- Articulation Points (slides 34 a 42)
Álgebra Booleana e Circuitos lógicos
Software
Testes lógicos e matemáticos
Humor
Slides
- http://www.universia.com.br/mit./6/6071/PDF/f02-lec22b_val.pdf (contém somador nos slides 12 a 18)
