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álises é tão importante quanto as demais.

  MAC0338 é uma continuação natural de MAC0323 Estrutura 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 são, 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 da graduação em Ciência da Computação da USP. A disciplina tem como pré-requisitos, prática em programação e em estruturas de dados, tais como os adquiridos em disciplinas de graduação em Ciência da Computação (MAC0122 Princípios de desenvolvimento de algoritmos e MAC0323 Estruturas de dados).  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 tenha algum conhecimento de probabilidade.