Matemática Discreta

De Wiki DAINF
(Diferença entre revisões)
(→Professores Responsáveis)
Linha 7: Linha 7:
  
 
* [http://www.dainf.cefetpr.br/~luders/IF63E.htm Matemática Discreta - Prof. Ricardo Lüders (UTFPR)]
 
* [http://www.dainf.cefetpr.br/~luders/IF63E.htm Matemática Discreta - Prof. Ricardo Lüders (UTFPR)]
 +
 +
== Plano de Ensino ==
 +
 +
{| class="prettytable"
 +
| '''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.'''
 +
 +
 +
 +
 +
|}
 +
 +
{| class="prettytable"
 +
| '''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.'''
 +
 +
 +
 +
 +
|}
 +
 +
{| class="prettytable"
 +
| <center>'''ITEM'''</center>
 +
| <center>'''EMENTA'''</center>
 +
| <center>'''CONTEÚDO'''</center>
 +
 +
|-
 +
| <center>1</center>
 +
| 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.
 +
 +
|-
 +
| <center>2</center>
 +
| 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.
 +
 +
|-
 +
| <center>3</center>
 +
| 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.
 +
 +
|-
 +
| <center>4</center>
 +
| 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.
 +
 +
|-
 +
| <center>5</center>
 +
| Estruturas Algébricas
 +
| Propriedades das operações binárias.
 +
 +
Grupóides, semigrupos, monóides e grupos.
 +
 +
Homomorfismo.
 +
 +
|-
 +
| <center>6</center>
 +
| Á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
 +
 +
|}
 +
 +
{| class="prettytable"
 +
| '''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.
 +
  
 
=== Links para oferecimentos da disciplina em outras universidades ===
 
=== Links para oferecimentos da disciplina em outras universidades ===

Edição de 11h42min de 3 de agosto de 2009

Tabela de conteúdo

Professores Responsáveis

Oferecimentos Anteriores na UTFPR

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.



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.


Links para oferecimentos da disciplina em outras universidades

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