Matemática Discreta

De Wiki DAINF
(Diferença entre revisões)
(→Referências Complementares)
 
(Uma edição intermediária de um usuário não apresentada)
Linha 134: 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 163: 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
 
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

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