MAC0338 Análise de Algoritmos

  Correção e eficiência são dois dos aspectos fundamentais a serem considerados no projeto de algoritmos. É aconselhável que programas salvaguarda de pilotos automáticos ou usinas nucleares funcionem como esperado. Eficiência é um ingrediente importante em aplicações de algoritmos a problemas que manipulam um volume muito grande de dados, como projetos genoma e buscas na internet.

  Segundo A.V. Goldberg, as três maneiras mais populares para medir a eficiência de um algoritmo são análise de pior caso, análise de caso médio e análise experimental. A maneira mais efetiva para analisar um algoritmo é utilizar os três métodos. Engenharia de algoritmos combina idéias bem justificadas teoricamente, heurísticas intuitivas, e estudos experimentais. Tudo isto para alcançar uma melhor compreensão dos pontos fortes, fracos e o do desempenho das operações algorítmicas na prática a fim de obter programas eficientes e robustos.

  Em MAC0338 nos concentraremos na análise de pior caso. Alguma vezes estudaremos a eficiência média de um algoritmo e raramente faremos análise experimental. Entretanto, é aconselhável ter em mente que qualquer uma dessas análise é tão importante quanto as demais.

  MAC0338 é uma continuação natural de MAC0122 (Princípios de Desenvolvimento de Algoritmos) e MAC0323 (Estruturas de Dados).  A disciplina

• estuda algoritmos eficientes e elegantes para alguns problemas computacionais básicos;
• prova a correção de algoritmos iterativos a partir de suas relações invariantes;
• explora a estrutura recursiva dos problemas para construir algoritmos eficientes;
• formaliza o conceito de desempenho (assintótico) de algoritmos;
• calcula o desempenho de vários algoritmos básicos.

  Através do estudo de exemplos, métodos e analogias gostaríamos de aprimorar um certo raciocínio que resulte em descrições de algoritmos em que a correção seja transparente.

  A ênfase de MAC0338 será em problemas para os quais se conhecem soluções eficientes (e elegantes). Apenas nas últimas aulas veremos problemas que têm resistido às tentativas de solução por algoritmos eficientes. Principais tópicos de MAC0338, não necessariamente nesta ordem:

• Elementos de análise assintótica (notação O, Omega e Theta).
• Solução de recorrências.
• Análise da correção e desempenho de algoritmos iterativos.
• Análise da correção e desempenho de algoritmos recursivos.
• Análise de pior caso e análise probabilística (caso médio).
• Algoritmos de busca e ordenação.
• Algoritmos de programação dinâmica.
• Algoritmos gulosos.
• Algoritmos para problemas em grafos.
• Análise amortizada de desempenho.
• Introdução à teoria da complexidade: problemas completos em NP.

  MAC0338 é disciplina obrigatória do Bacharelado em Ciência da Computação da USP. A disciplina tem como pré-requisitos MAC0122 e MAC0323.  Em particular, supõe-se que o aluno esteja bem familiarizado com algoritmos básicos de ordenação como Mergesort, Heapsort e Quicksort. 

  Também é desejável que o aluno já tenha cursado ou esteja cursando  MAE0121 (Introdução à Probabilidade e à Estatística I). Dizem por aí que é mais produtivo cursar MAC0338 juntamente com MAC0328 (Algoritmos em Grafos).