Matemática Discreta

De Wiki DAINF
(Diferença entre revisões)
(→Materiais Complementares)
(→Pré-requisitos)
Linha 164: Linha 164:
 
== Pré-requisitos ==
 
== Pré-requisitos ==
  
−
É desejável (mas '''não''' obrigatório que o aluno tenha sido aprovado em [[Lógica para Computação]]. Os pré-requisitos da disciplina são os mesmos de [[Lógica para Computação]].
+
É 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 ==

Edição de 14h51min de 1 de março 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#

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=2839"
Ferramentas pessoais