MAC5711 Análise de Algoritmos

In Pursuit of Simplicity


Home Aulas Tarefas Provas Fórum Critério Livros Algoritmos na Web

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

  MAC5711 é uma continuação natural de MAC5710 Estrutura de Dados e sua Manipulação.  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 MAC5711 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 MAC5711 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.

  MAC5711 é disciplina obrigatória da Pós-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.

Esta página é melhor visualizada
com um computador e um monitor.


Toca do coelho.
Last modified: Wed Aug 9 15:13:57 -0300 2006