Of.: S-5 T:04 L:00 HS:04 SL:04 C:04

Pre-Req.: MC202

Ementa:

Conceitos básicos de matemática discreta. Noções básicas de projeto e análise de algoritmos. Algoritmos para ordenação e grafos.

Programa:

1. Conceitos básicos de matemática discreta
1. Revisão da noções básicas de Teoria dos conjuntos. Seuqência e tuplas. Funções e relações
2. Funções inteiras: mod, piso e teto
3. Crescimento de funções e notação assintótica. Somatórias
4. Relações de recorrência
5. Noções básicas de contagem e probabilidade
6. Noções básicas de grafos: nomenclatura, classes, representação
7. Técinicas básicas de demosntração
2. Noções básicas de análise e projeto de algoritmos
1. Noções básicas: o que é um algoritmo; o que significa projetar um algoritmo, e o que é análise de um algoritmo. Ênfase: corretude. O modelo RAM
2. Técnica de projeto: indução
3. Técnica de projeto: divisão e conquista
4. Técnica de projeto: gula
5. Técnica de projeto: busca exaustiva
3. Algoritmos para ordenação e grafos
1. Revisão dos algoritmos principais para ordenação: Inserção, Seleção, Mergesort e Quicksort
2. Árvore binária de decisão e limite inferior para ordenação com comparações
3. Algoritmos lineares para ordenação
4. Caso médio dos algoritmos de ordenação
5. Algoritmos para o k-ésimo, incluindo algoritmo linear
6. Algoritmos para percursos em grafos: largura e profundidade. Aplicações: conexidade, ordenação topológica
7. Algoritmos para árvore espalhada mínima
8. Algoritmos para caminhos mais curtos: a partir de um vértice e entre todos os pares de vértices. Fecho transitivo

Bibliografia:

G. Brassard e P. Bratley, Fundamental of Algorithmics, Prentice-Hall, 1995

T. Cormen, C.Leiserson e R. Rivest, Introduction to Algorithms, MIT Press, 1990

U. Manber, Introduction to Algorithms, Addison-Wesley, 1989