Matemática Discreta

De Wiki DAINF
(Diferença entre revisões)
(→Material do prof. Ricardo Luders)
(→Referências Complementares)
 
(48 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]]
+
 
−
** [[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 ==
  
−
* [http://www.dainf.cefetpr.br/~luders/IF63E.htm Matemática Discreta - Prof. Ricardo Lüders (UTFPR)]
+
* [http://www.dainf.ct.utfpr.edu.br/~luders/IF63E.htm Matemática Discreta - Prof. Ricardo Lüders (UTFPR)]
  
 
==== Material do prof. Ricardo Luders ====
 
==== Material do prof. Ricardo Luders ====
Linha 15: Linha 18:
 
** [http://www.dainf.ct.utfpr.edu.br/~luders/Notas_aula3.pdf Notas de aula 3 - Permutações, Arranjos e Combinações]
 
** [http://www.dainf.ct.utfpr.edu.br/~luders/Notas_aula3.pdf Notas de aula 3 - Permutações, Arranjos e Combinações]
 
** [http://www.dainf.ct.utfpr.edu.br/~luders/Notas_aula4.pdf Notas de aula 4 - Funções e Relações]
 
** [http://www.dainf.ct.utfpr.edu.br/~luders/Notas_aula4.pdf Notas de aula 4 - Funções e Relações]
−
** [http://www.dainf.ct.utfpr.edu.br/~luders/Notas_aula5.pdf Notas de aula 5]
+
** [http://www.dainf.ct.utfpr.edu.br/~luders/Notas_aula5.pdf Notas de aula 5 - Grafos - Parte I (Árvores)]
−
** [http://www.dainf.ct.utfpr.edu.br/~luders/Notas_aula6.pdf Notas de aula 6]
+
** [http://www.dainf.ct.utfpr.edu.br/~luders/Notas_aula6.pdf Notas de aula 6 - Grafos - Parte II (Algoritmos)]
−
** [http://www.dainf.ct.utfpr.edu.br/~luders/Notas_aula7.pdf Notas de aula 7]
+
** [http://www.dainf.ct.utfpr.edu.br/~luders/Notas_aula7.pdf Notas de aula 7 - Linguagens Formais]
  
 
* Listas de exercícios
 
* Listas de exercícios
Linha 29: Linha 32:
 
== Links para oferecimentos da disciplina em outras universidades ==
 
== Links para oferecimentos da disciplina em outras universidades ==
  
 +
* [http://www.inf.ufpr.br/renato/ci237/ Matemática Discreta - Prof. Renato Carmo (UFPR)]
 
* [http://www.dcc.unicamp.br/~campos/Welcome_files/1s2009.html Matemática Discreta - Profa. Christiane Neme Campos (UNIFESP - São José dos Campos)]
 
* [http://www.dcc.unicamp.br/~campos/Welcome_files/1s2009.html Matemática Discreta - Profa. Christiane Neme Campos (UNIFESP - São José dos Campos)]
 
* [http://www.inf.ufpr.br/jair/md.html Matemática Discreta - Prof. Jair Donadelli (UFPR)]
 
* [http://www.inf.ufpr.br/jair/md.html Matemática Discreta - Prof. Jair Donadelli (UFPR)]
Linha 34: Linha 38:
 
** [http://www2.dc.ufscar.br/~jose/courses/08-2/MD/Matematica%20Discreta.pdf Apostila de Matemática Discreta do prof. José Guimarães]
 
** [http://www2.dc.ufscar.br/~jose/courses/08-2/MD/Matematica%20Discreta.pdf Apostila de Matemática Discreta do prof. José Guimarães]
 
* [https://fenix.ist.utl.pt/publico/department/showCompetenceCourse.faces?action=ccm&competenceCourseID=4302&selectedDepartmentUnitID=61127&contentContextPath_PATH=/departamentos/dm/topo/inicio&_request_checksum_=56877ed0c2b24b3f07b5c70ec82e508b34b4bb74 Matemática Discreta - Prof. Carlos Caleiro (IST)]
 
* [https://fenix.ist.utl.pt/publico/department/showCompetenceCourse.faces?action=ccm&competenceCourseID=4302&selectedDepartmentUnitID=61127&contentContextPath_PATH=/departamentos/dm/topo/inicio&_request_checksum_=56877ed0c2b24b3f07b5c70ec82e508b34b4bb74 Matemática Discreta - Prof. Carlos Caleiro (IST)]
 +
* [http://www.cin.ufpe.br/~if670/ Matemática Discreta (IF670) - CIn - UFPE]
 +
* [http://md.pt.to/ Matemática Discreta - Luís Sequeira - Universidade do Porto]
 
* [http://www.cs.cmu.edu/~15251/  Great Theoretical Ideas in Computer Science - Anupam Gupta & John Lafferty (Carnegie-Mellon University)]
 
* [http://www.cs.cmu.edu/~15251/  Great Theoretical Ideas in Computer Science - Anupam Gupta & John Lafferty (Carnegie-Mellon University)]
 +
* [http://www.inf.ufpr.br/andre/Disciplinas/BSc/CI065-2009-2/ Algoritmos e teoria dos grafos (2009.2) - Prof. André Guedes (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://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 124: 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 153: 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, 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
  
−
=== Materiais Complementares ===
+
== 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 ===
  
 
* [http://www.cle.unicamp.br/prof/coniglio/LIVRO.pdf Apostila de Introdução à Lógica, de Marcelo Coniglio, Walter Carnielli e Ricardo Bianconi]
 
* [http://www.cle.unicamp.br/prof/coniglio/LIVRO.pdf Apostila de Introdução à Lógica, de Marcelo Coniglio, Walter Carnielli e Ricardo Bianconi]
 
** Ver 1o. capítulo, que fala de Cantor.
 
** Ver 1o. capítulo, que fala de Cantor.
 +
 +
=== Animações de Algoritmos ===
 +
 +
==== Prim ====
 +
* [http://www.unf.edu/~wkloster/foundations/PrimApplet/PrimApplet.htm Algoritmo de Prim (unf)]
 +
* [http://students.ceid.upatras.gr/~papagel/project/prim.htm Algoritmo de Prim (upatras)]
 +
 +
==== 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://oopweb.com/Algorithms/Documents/PLDS210/Volume/dijkstra.html Algoritmo de Dijkstra (oopweb)]
 +
* [http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html Algoritmo de Dijkstra (sunsysb)]
 +
* [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Algoritmo de Dijkstra (na Wikipedia)]
 +
 +
==== Percurso em Grafos ====
 +
 +
* [http://www.ansatt.hig.no/frodeh/algmet/animate.html#chap29 Várias animações de percurso em grafos]
 +
** [http://sziami.cs.bme.hu/~gsala/alg_anims/3/graph-e.html Depth First Search (bme)]
 +
** [http://sziami.cs.bme.hu/~gsala/alg_anims/3/graph2-e.html Breadth First Search (bme)]
 +
 +
==== Implementações de Algoritmos 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]
 +
 +
 +
* Use http://www.lua.org/demo.html para executar o algoritmo do seu browser.
 +
 +
==== Diversos ====
 +
 +
* [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 ===
 +
 +
==== 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 ====
 +
 +
* [http://www.professeurs.polymtl.ca/michel.gagnon/Disciplinas/Bac/Grafos/EulerHam/euler_ham.html Grafos Eulerianos e Hamiltonianos - Prof. Michel Gagnon]
 +
 +
==== Algoritmo de Busca de Articulação ====
 +
 +
* [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://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)]
 +
 +
 +
==== Á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