PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2000.1
Horário: 3as-feiras e 5as-feiras de 14 às 16 horas
Local: 528L
ESTRUTURAS DISCRETAS (INF 1631)
Objetivos: Capacitar o aluno a manipular e provar propriedades
sobre estruturas indutivas, relacionando teoremas e suas provas com
algoritmos.
CONTEÚDO
· Indução Matemática: Princípio de indução,
indução forte, outras induções, provas por indução, erros comuns em
indução, algoritmos e indução e definições indutivas.
· Princípios de Contagem: Permutações e combinações,
indentidades e argumentos combinatoriais, inclusão e exclusão,
algoritmos combinatoriais e princípio da casa do pombo.
· Algoritmos: Noção de algoritmo, liguagem
algorítmica, algoritmos recursivos, procedimentos e análise de
algoritmos, noções de complexidade de algoritmos, limites inferiores e
superiores para complexidade, complexidade de problemas, exemplos.
· Noções de Grafos: Terminologia e notação, caminhos,
ciclos, representações, caminho mais curto, árvores geradora
mínima, busca em profundidade e em largura, coloração de grafos.
· Projeto de Algoritmos por Indução:
Teoremas, provas por indução e os algoritmos associados.
Exemplos: avaliação de polinômios, ordenação, caminhos eulerianos,
caminho mais curto e programação dinâmica.
BIBLIOGRAFIA
-
Livros
-
Notas de aula a serem distribuidas ao longo do curso.
-
S.B. Maurer e A. Ralston, Discrete Algorithmic
Mathematics, Addison-Wesley, 1991. (LIVRO TEXTO Caps: 0, 1, 2, 3 e 4)
-
U. Manber, Introduction to Algorithms: A Creative Approach,
Addison-Wesley, 1989. (Caps. 2, 5, 6, 7)
- Outras Referências
-
J.P. Santos, M.P. Mello e I.T. Murari, Introdução à
Análise Combinatória, Editora da UNICAMP, 1995.
-
F.S. Roberts, Applied Combinatorics,
Prentice-Hall, 1989.
-
A. Aho e J. Ullman, Foundations of Computer Science,
Freeman, 1992.
-
E. Horowitz e S. Sahni, Fundamentals of Computer Algorithms,
Computer Science Press, 1978-89.
-
T.H. Cormen, C.E. Leiserson e R.L. Rivest, Introduction
to Algorithms, McGraw-Hill, New York, 1990.
AVALIAÇÃO
Serão realizadas três provas (graus P1, P2 e P3), que são
utilizadas para obter o grau G1, e um exame
final (G2). A nota final será calculada de acordo com a fórmula
e com o critério de aprovação abaixo:
-
Se G1 ³ 5.0 - Aprovado.
- Se G1 < 5.0 e G1 + G2/2 ³ 5.0 - Aprovado.
- Se G1 < 5.0 e G1 + G2/2 < 5.0 - Reprovado.
Datas:
P1 - 11/4 3a. feira 14-16;
P2 - 25/5 5a. feira 14-16;
P3 - 6/7 5a. feira 14-16;
G2 - 13/7 5a. feira 14-16;
This document was translated from LATEX by HEVEA.