[ MAC5711 - ANÁLISE de ALGORITMOS]

"Ao verificar que um dado programa está muito lento,
uma pessoa prática pede uma máquina mais rápida ao seu chefe.
[...] Entretanto, 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 de desempenho, é preciso buscar melhores algoritmos.
Como veremos adiante, um algoritmo rápido rodando em uma máquina lenta sempre acaba vencendo
para instâncias grandes do problema. Sempre."

- S. S. Skiena, The Algorithm Design Manual

Programa

Segundo o programa oficial, os objetivos da disciplina MAC5711 são

• Introduzir as técnicas básicas de análise de eficiência de algoritmos, com cálculo de tempo de pior caso e tempo médio. Isso é feito simultaneamente com a formação de um grande repertório de algoritmos eficientes, que ilustram as técnicas de análise e servem como ponto de partida para o desenvolvimento de novos algoritmos.

A justificativa oficial da disciplina MAC5711 é a seguinte:

• O desenvolvimento de algoritmos é uma atividade fundamental na Computação, e a análise é parte indispensável nesse desenvolvimento. Tipicamente o aluno deste curso já está familiarizado com os outros aspectos do projeto de algoritmos, e esse curso complementa a formação nessa atividade.

Ainda segundo o programa oficial, o conteúdo de MAC5711 é o seguinte:

• Noções sobre modelos de computação e eficiência de algoritmos.
• Técnicas de estruturação de algoritmos.
• Algoritmos de classificação e busca.
• Algoritmos de manipulação de conjuntos.
• Grafos e algoritmos de busca.
• Noções de complexidade: as classes P, NP e coNP.

A disciplina tem carga de 4 horas de aulas teóricas por semana durante cerca de 12 semanas e dá direito a 8 créditos.

Pré-requisitos

Os pré-requisitos de MAC5711 são noções básicas de estruturas de dados e teoria dos grafos. Esses pré-requisitos correspondem aos conteúdos das disciplinas  MAC5710 (Estruturas de Dados e sua Manipulação)  e  MAC5770 (Introdução à Teoria dos Grafos).  

Também é desejável que os alunos tenham uma certa experiência de programação,  particulamente em linguagem C. Familiaridade com a manipulação de ponteiros é especialmente importante.