Objetivos
São objetivos da disciplina:
- Introduzir conceitos matemáticos para a análise de algoritmos
- Estudar medidas de complexidade de algoritmos
- Compreender métodos de projeto de algoritmos
- Investigar as classes de problemas P, NP e NP-completo
- Estudar métricas de desempenho
Pré-requisitos
Embora os pré-requisitos não sejam obrigatórios, o seu domínio auxiliará muito na evolução do aprendizado:
- Teoria de autômatos
- Gramáticas
- Implementação de algoritmos básicos (ordenação e busca)
- Estruturas de dados (arrays, árvores e grafos)
Competências trabalhadas
As competências trabalhadas na disciplina são:
- Compreender a complexidade de problemas e algoritmos, aplicando metodologias de cálculo relacionadas para este fim
- Analisar técnicas envolvidas para o desenvolvimento de algoritmos eficientes
- Compreender técnicas para análise de complexidade de algoritmos
- Conchecer aspectos relacionados à complexidade de problemas e intratabilidade
Unidades de Aprendizagem
As unidades de aprendizagem abordadas na disciplina são:
- Entendimento sobre a notação assintótica e crescimento de funções para a análise de algoritmos
- Análise crítica sobre a computação de algoritmos para mensurar o desempenho destes
- Compreensão sobre as ordens de complexidade e notações para a análise de algotimos
- Entendimento sobre recorrência
- Entendimento sobre o método divisão e conquista, algoritmos de busca, grafos, algoritmos gulosos e programação dinâmica para análise e desenvolminto de algoritmos
- Análise de classes de complexidade, máquinas universais e intratabilidade para análise de problemas
Estratégias metodológicas
Elaboração de artigos e trabalhos práticos individuais relacionados às unidades de aprendizagem.
Cronograma
| Grau |
Id |
Peso |
Resumo |
Entrega |
| G1 |
T1 |
3.0 |
Notações Big-O, Theta e Omega
|
29/04 |
| G1 |
T2 |
3.0 |
Recursão e Algoritmos de Divisão e Conquista
|
29/04 |
| G1 |
T3 |
4.0 |
Algoritmos Gulosos
|
29/04 |
| G2 |
T4 |
3.0 |
Programação Dinâmica
|
05/07 |
| G2 |
T5 |
4.0 |
Classes de complexidade: P, NP, EXP, NP-completo, NP-hard
|
05/07 |
| G2 |
T6 |
3.0 |
Classe de complexidade de espaço: P-SPACE
|
05/07 |
Procedimento e critérios de avaliação
A nota final será composta por trabalhos práticos de implementação e elaboração de artigos.
O grau 1 será composto por G1 = T1(3.0) + T2(3.0) + T3(4.0)
O grau 2 será composto por G2 = T4(3.0) + T5(4.0) + T6(3.0)
A nota final será a média (M) dada pela regra M = (G1 + G2) / 2
Para obter a aprovação, o aluno deve obter uma média (M) igual ou superior a 6, com frequência mínima de 8 encontros presenciais.
Material Complementar
Bibliografia
- Cormen et al. Algoritmos: Teoria e Prática. Livros Técnicos e Científicos Editora Ltda, 2022.
Recursos online
- Introduction to Algorithms MIT OpenCourseWare. 2020. (Também disponíveis os cursos de 2011 e 2008.)
- Theory of Computation MIT OpenCourseWare. 2020.
- Design and Analysis of Algorithms MIT OpenCourseWare. 2015.