Matemática Discreta

De Wiki DAINF
(Diferença entre revisões)
(→Referências Complementares)
(→Referências Complementares)
Linha 162: Linha 162:
  
 
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, 2003. 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 de 15h25min de 8 de abril de 2010

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.

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#

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

Testes lógicos e matemáticos

Slides

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