PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2008.2
Horário: 2as-feiras e 4as-feiras de 17 às 19 hs
Local: 524L 2as-feiras e 456L 4as-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

  1. Livros

    Notas de aula a serem distribuidas ao longo do curso ( Apostila).

  2. J.P. Santos, M.P. Mello e I.T. Murari, Introdução à Análise Combinatória, Editora da UNICAMP, 1995.

  3. 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.

  4. 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.

  5. S.B. Maurer e A. Ralston, Discrete Algorithmic Mathematics, Addison-Wesley, 1991. (Caps: 0, 1, 2, 3 e 4)

  6. U. Manber, Algorithms: A Creative Approach, Addison-Wesley, 1989. (Caps. 2, 5, 6, 7)
AVALIAÇÃO

Serão realizadas duas provas (graus P1 e P2), que são utilizadas para obter os grau G1 e G2 juntamente com os graus T1 e T2 referentes aos trabalhos práticos. Estes trabalhos poderão ser feitos em grupos. Um exame final (EX) será realizado por aqueles que não forem aprovados com os graus G1 e G2, isto é, não obtiverem média acima de 5 nestes graus. A nota final será calculada de acordo com a fórmula e com o critério de aprovação abaixo:
G1 =
8.P1 +2.T1
10
G2 =
8.P2 +2.T2
10
NF =
G1 +G2
2
   se
G1 + G2
2
³ 5
Caso em que o aluno está aprovado sem exame final.
NF =
G1 +G2 + 2.EX
4
   se
G1 + G2
2
< 5
Ou seja, caso a média 5 não seja atingida nos graus G1 e G2 o aluno realiza um exame final. A média aritmética entre o grau anterior e o do exame final deve ser maior ou igual a 5 para a aprovação.

Datas:

P1 - 1/10 4a. feira 17-19;

P2 - 26/11 4a. feira 17-19;

EX - 03/12 4a. feira 17-19;

T1 - 26/09 6a. feira (disponível dia 27/08);

T2 - 19/11 4a. feira (disponível dia 22/10);

This document was translated from LATEX by HEVEA.