PUC-Rio Departamento de Informática Prof. Marcus Vinicius S. Poggi de Aragão Período: 2009.1 Horário: 3as-feiras e 5as-feiras de 17 às 19 hs Local: 774L 3as-feiras e 508L 5as-feiras
ESTRUTURAS DISCRETAS (INF 1631)
Objetivos:
Capacitar o aluno a manipular e provar propriedades
sobre estruturas discretas e usar esse conhecimento na criação e
análise de 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.
· Noções de Grafos: Terminologia e notação,
caminhos, ciclos, representações, caminho mais curto, árvore
geradora mínima, emparelhamento mínimo, 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 ( Apostila).
J.P. Santos, M.P. Mello e I.T. Murari, Introdução à
Análise Combinatória, Editora da UNICAMP, 1995.
Judith L. Gersting, Fundamentos Matemáticos para Ciência da Computação,
Livros Técnicos e Científicos Editora (LTC),
1993. ISBN: 0-7167-8259-6.
Ronald L. Graham, Donald E. Knuth, e Oren Patashnik
Matemática Concreta: Fundamentos para a Ciência da Computação,
Rio de Janeiro, Livros Técnicos e Científicos Editora, 1995.
S.B. Maurer e A. Ralston, Discrete Algorithmic
Mathematics, Addison-Wesley, 1991. (Caps: 0, 1, 2, 3 e 4)
U. Manber, Algorithms: A Creative Approach,
Addison-Wesley, 1989. (Caps. 2, 5, 6, 7)
AVALIAÇÃO
Serão realizadas três provas (graus P1, P2 e P3), que são
utilizadas para obter o grau G1 juntamente com os graus T1 e T2 referentes
aos trabalhos práticos. Estes trabalhos
poderão ser feitos em grupo. Um exame
final (EX) será realizado por aqueles que não forem aprovados
com o grau G1. A nota final será calculada de acordo
com a fórmula e com o critério de aprovação abaixo: