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