MC458 - Projeto e Análise de Algoritmos I

A partir de 2016

 

Pré-­requisitos:

MC202 MC358 / MC202 MS328 / MC202 MC348

Ementa:

Técnicas de projeto e análise de algoritmos. Algoritmos de ordenação.

Programa:

 
1. Revisão de conceitos
- Modelos Computacionais
- Análise de um algoritmo
- Análise de custo (tempo, espaço, etc.)
- Cota inferior de um problema
- Exemplos: busca em vetor ordenado, entrada/saída
 
2. Ferramental Matemático para Análise de Algoritmos
- Crescimento de Funções e Notação Assintótica
- Relações de Recorrência: resolução assintótica e exata
 
3. Projeto de algoritmos por indução
- Indução Matemática e Projetos de algoritmos por indução
- Projeto por Indução Simples e Forte
- Projeto por Divisão e Conquista
 
4.Busca, ordenação e estatísticas de ordem
- Busca binária. Opcional: Variações da Busca Binária
- Paradigma de divisão e conquista (mergesort, busca binária, mediana)
- Conquista pode preceder a divisão (quicksort)
- Análise de caso médio de quicksort
- Determinação da mediana e do k-ésimo menor elemento via partição do quicksort
- Algoritmo de pior caso linear para seleção do mediano e do k-ésimo menor elemento
- Benefícios da escolha de estrutura de dados adequada para projeto de algoritmos eficientes
- Cota inferior para busca em vetor ordenado, ordenação e mediana
- Algoritmos lineares para ordenação
 
5. Programação Dinâmica
- Descrição da técnica
- Exemplos de aplicação. Sugestão de exemplos:
- Multiplicação de cadeias de matrizes
- Mais longa subsequência em comum
 
6. Algoritmos Gulosos
- Descrição da técnica
- Exemplos de aplicação. Sugestão de exemplos:
- Problema da seleção de atividades
- Códigos de Huffman
 

 

Bibliografia:

1 - T. Cormen, C. Leiserson, R. Rivest, C. Stein. Algoritmos - Teoria e Prática (3a. edição), Editora Campus (2012).

2 - U. Manber, Algorithms: A Creative Approach, Addison-Wesley (1989).

3 - N. Ziviani. Projeto de Algoritmos com Implementações em Pascal e C (3a. edição). Editora Cengage Learning (2011).

4 - J. Szwarcfiter, L. Markenson. Estruturas de Dados e seus Algoritmos (3a. edição), LTC Editora (2010).

5 - R. Sedgewick, K. Wayne. Algorithms (4a. edição), Addison-Wesley (2011).