Matemática Discreta

De Wiki DAINF
(Diferença entre revisões)
(→Páginas na Internet)
(→Referências Complementares)
 
(21 edições intermediárias de um usuário não apresentadas)
Linha 1: Linha 1:
 
== Professores Responsáveis ==
 
== Professores Responsáveis ==
  
−
* Em 2009.2:
+
* [[Matemática Discreta - Turma S71 - 2010.1]] - Professor [[Adolfo Neto]]
−
** [[Matemática Discreta - Turma S71 - 2009.2]] - Professor [[Adolfo Neto]]
+
 
−
** [http://ead.ct.utfpr.edu.br/moodle/course/view.php?id=121 Matemática Discreta - Turma S73 - 2009.2] - Professor [[João Fabro]]
+
* [[Matemática Discreta - Turma S71 - 2009.2]] - Professor [[Adolfo Neto]]
 +
* [http://www.dainf.ct.utfpr.edu.br/~fabro/IF63E/ Matemática Discreta - Turma S73 - 2009.2] - Professor [[João Fabro]]
 +
 
 +
* [[Dados de aprovação/reprovação em Matemática Discreta]]
  
 
== Oferecimentos Anteriores na UTFPR ==
 
== Oferecimentos Anteriores na UTFPR ==
Linha 41: Linha 44:
 
* [http://www.professeurs.polymtl.ca/michel.gagnon/Disciplinas/Bac/Grafos/index_grafos.html Algoritmos e teoria dos grafos - Prof. Michel Gagnon (UFPR)]
 
* [http://www.professeurs.polymtl.ca/michel.gagnon/Disciplinas/Bac/Grafos/index_grafos.html Algoritmos e teoria dos grafos - Prof. Michel Gagnon (UFPR)]
 
* [http://www.csie.ntu.edu.tw/~pangfeng/ACP2004/documents/ Advanced Computer Programming (ver slides sobre Graph Algoritms)]
 
* [http://www.csie.ntu.edu.tw/~pangfeng/ACP2004/documents/ Advanced Computer Programming (ver slides sobre Graph Algoritms)]
 +
* [http://ocw.mit.edu/OcwWeb/Sloan-School-of-Management/15-082JNetwork-OptimizationSpring2003/CourseHome/index.htm Network Optimization - Prof. James Orlin (MIT)]
  
 
== Plano de Ensino ==
 
== Plano de Ensino ==
Linha 130: Linha 134:
  
 
GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação, 5ª Edição, Rio de Janeiro: LTC, 2004.
 
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 ====
 
==== Referências Complementares ====
Linha 159: 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, 2003. Página do livro na editora:http://www.thomsonlearning.com.br/detalheLivro.do?id=102629#
+
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
 +
 
 +
== 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 ==
 
== Materiais Complementares ==
Linha 175: Linha 188:
  
 
==== Dijkstra ====
 
==== Dijkstra ====
 +
* [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml Algoritmo de Dijkstra (tokushima)]
 
* [http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm Algoritmo de Dijkstra (upatras)]
 
* [http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm Algoritmo de Dijkstra (upatras)]
 
* [http://oopweb.com/Algorithms/Documents/PLDS210/Volume/dijkstra.html Algoritmo de Dijkstra (oopweb)]
 
* [http://oopweb.com/Algorithms/Documents/PLDS210/Volume/dijkstra.html Algoritmo de Dijkstra (oopweb)]
Linha 190: Linha 204:
 
* [http://www.dainf.ct.utfpr.edu.br/~adolfo/Disciplinas/MatematicaDiscreta/Codigo/Warshall.lua Algoritmo de Warshall em Lua]
 
* [http://www.dainf.ct.utfpr.edu.br/~adolfo/Disciplinas/MatematicaDiscreta/Codigo/Warshall.lua Algoritmo de Warshall em Lua]
 
** [http://www.dainf.ct.utfpr.edu.br/~adolfo/Disciplinas/MatematicaDiscreta/Codigo/Warshall.lua Warshall's Algorithm in Lua]
 
** [http://www.dainf.ct.utfpr.edu.br/~adolfo/Disciplinas/MatematicaDiscreta/Codigo/Warshall.lua Warshall's Algorithm in Lua]
 +
 +
 +
* Use http://www.lua.org/demo.html para executar o algoritmo do seu browser.
  
 
==== Diversos ====
 
==== Diversos ====
  
 
* [http://www.ansatt.hig.no/frodeh/algmet/animate.html Várias animações de algoritmos]
 
* [http://www.ansatt.hig.no/frodeh/algmet/animate.html Várias animações de algoritmos]
−
 
+
* [http://ocw.mit.edu/OcwWeb/Sloan-School-of-Management/15-082JNetwork-OptimizationSpring2003/Animations/index.htm 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 ===
 
=== Páginas na Internet ===
Linha 211: Linha 233:
  
 
* [http://www.professeurs.polymtl.ca/michel.gagnon/Disciplinas/Bac/Grafos/Busca/busca.html#Art Algoritmo de Busca de Articulação - Prof. Michel Gagnon]
 
* [http://www.professeurs.polymtl.ca/michel.gagnon/Disciplinas/Bac/Grafos/Busca/busca.html#Art Algoritmo de Busca de Articulação - Prof. Michel Gagnon]
 +
** [http://www.dainf.ct.utfpr.edu.br/~adolfo/Disciplinas/MatematicaDiscreta/Slides/PontosArticulacao/ Algoritmo de Busca de Articulação (texto do prof. Michel Gagnon e slides complementares)]
 
* [http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/articulations.html Articulações e biconexão - Paulo Feofiloff (IME-USP)]
 
* [http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/articulations.html Articulações e biconexão - Paulo Feofiloff (IME-USP)]
 
* [http://javafree.uol.com.br/artigo/874965/GRAFOS-Articulacoes-e-Biconexao.html Articulações e Biconexão, Felipe Nievola]
 
* [http://javafree.uol.com.br/artigo/874965/GRAFOS-Articulacoes-e-Biconexao.html Articulações e Biconexão, Felipe Nievola]
 
* [http://www.csie.ntu.edu.tw/~pangfeng/ACP2004/documents/Graph%20Algorithms%20I.pdf Articulation Points (slides 34 a 42)]
 
* [http://www.csie.ntu.edu.tw/~pangfeng/ACP2004/documents/Graph%20Algorithms%20I.pdf Articulation Points (slides 34 a 42)]
 +
 +
 +
==== Álgebra Booleana e Circuitos lógicos ====
 +
 +
* [http://www.ibiblio.org/kuphaldt/electricCircuits/Digital/DIGI_7.html Lessons In Electric Circuits - Boolean Algebra]
 +
 +
===== Software =====
 +
* [http://www.tkgate.org/ TKGate]
 +
 +
==== Testes lógicos e matemáticos ====
 +
 +
* [http://www.mensa.com.br/pag.php?t=puzzle Mensa]
 +
* [http://projecteuler.net/ Projeto Euler]
 +
 +
=== Humor ===
 +
 +
* [http://school.maths.uwa.edu.au/~berwin/humour/invalid.proofs.html Técnicas Inválidas de Demonstração]
 +
 +
=== Slides ===
 +
 +
* http://www.universia.com.br/mit./6/6071/PDF/f02-lec22b_val.pdf (contém somador nos slides 12 a 18)
 +
 +
=== Provas ===
 +
 +
==== POSCOMP ====
 +
 +
* [http://www.sbc.org.br/index.php?language=1&subject=189 POSCOMP]
 +
==== ENADE ====
 +
 +
* [http://bit.ly/9ErEdo ENADE de Computação 2008 - comentado]

Edição atual tal como 11h50min de 18 de novembro de 2011

Tabela de conteúdo

Professores Responsáveis

Oferecimentos Anteriores na UTFPR

Material do prof. Ricardo Luders

Links para oferecimentos da disciplina em outras universidades

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. 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

Animações de Algoritmos

Prim

Dijkstra

Percurso em Grafos

Implementações de Algoritmos em Lua


Diversos

Páginas na Internet

Algoritmo de Prim

Grafos Eulerianos e Hamiltonianos

Algoritmo de Busca de Articulação


Álgebra Booleana e Circuitos lógicos

Software

Testes lógicos e matemáticos

Humor

Slides

Provas

POSCOMP

ENADE

Obtida de "http://dainf.ct.utfpr.edu.br/wiki/index.php?title=Matem%C3%A1tica_Discreta&oldid=5592"
Ferramentas pessoais