Matemática Discreta
(→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.
|
|
|
|
|
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. |
|
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. |
|
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. |
|
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. |
|
Estruturas Algébricas | Propriedades das operações binárias.
Grupóides, semigrupos, monóides e grupos. Homomorfismo. |
|
Á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
|