Home  |   Administração  |   Fórum  |   Livros  |   WWW  |   Diário  |   Aulas

—— Veja www.ime.usp.br/~pf/analise_de_algoritmos ——

"A análise de algoritmos é uma disciplina de engenharia.
Um engenheiro civil, por exemplo, tem métodos e tecnologia para
prever o comportamento de uma estrutura antes de constuí-la.
Da mesma forma, um projetista de algoritmos deve ser capaz de
prever o comportamento de um algoritmo antes de implementá-lo."

- Anônimo

"Ao verificar que um dado programa está muito lento,
uma pessoa prática pede uma máquina mais rápida ao seu chefe.
Mas o ganho potencial que uma máquina mais rápida pode proporcionar
é tipicamente limitado por um fator de 10, por razões técnicas ou econômicas.
Para obter um ganho maior, é preciso buscar melhores algoritmos.
Um bom algoritmo, mesmo rodando em uma máquina lenta,
sempre acaba derrotando (para instâncias grandes do problema)
um algoritmo pior rodando em uma máquina rápida.  Sempre."

- S. S. Skiena, The Algorithm Design Manual

 

Programa
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. Eis o programa desta edição de MAC0338: Elementos de análise assintótica (notação O e Omega). 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 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. Carga horária: 4 horas de aulas por semana durante cerca de 15 semanas. MAC0338 é disciplina obrigatória do Bacharelado em Ciência da Computação da USP.
Pré-requisitos
O único pré-requisito oficial é MAC0122.  Em particular, supõe-se que o aluno esteja bem familiarizado com algoritmos básicos de ordenação como Mergesort, Heapsort e Quicksort.  É recomendável, ainda que não obrigatório, que o aluno já tenha cursado  MAC0323 (Estruturas de Dados).   Também é desejável que o aluno já tenham cursado ou esteja cursando  MAC0328 (Algoritmos em Grafos)  e  MAE0121 (Introdução à Probabilidade e à Estatística I).
Professor
Paulo Feofiloff,  sala 287, bloco A.