Análise e Técnicas de Algoritmos
Informações do Curso
- Curso: Engenharia de Computação
- Período: 4º
- Eixo: Fundamentos de Engenharia de Computação
- Natureza: Obrigatória
Interdisciplinaridades
- Pré-requisitos: Estrutura de Dados
- Co-requisitos: Não há
Objetivos
A disciplina deverá possibilitar ao estudante: 1. Compreender os fundamentos teóricos da análise de algoritmos 2. Aplicar técnicas de análise de complexidade de algoritmos 3. Desenvolver algoritmos eficientes para problemas computacionais 4. Implementar e avaliar diferentes estratégias algorítmicas 5. Analisar e comparar algoritmos em termos de eficiência 6. Resolver problemas práticos utilizando técnicas algorítmicas avançadas
Unidades de Ensino
| Unidade | Conteúdo | Horas |
|---|---|---|
| 1 | FUNDAMENTOS DA ANÁLISE DE ALGORITMOS - Conceitos básicos - Notação assintótica - Análise de complexidade - Recorrências |
4 |
| 2 | TÉCNICAS DE PROJETO DE ALGORITMOS - Divisão e conquista - Programação dinâmica - Algoritmos gulosos - Backtracking |
8 |
| 3 | ALGORITMOS DE ORDENAÇÃO - Algoritmos básicos - Algoritmos avançados - Análise comparativa - Aplicações práticas |
6 |
| 4 | ALGORITMOS DE BUSCA - Busca em árvores - Hashing - Busca em strings - Aplicações práticas |
6 |
| 5 | ALGORITMOS EM GRAFOS - Representação de grafos - Algoritmos de caminho mínimo - Árvores geradoras - Fluxo em redes |
8 |
| 6 | ALGORITMOS APROXIMATIVOS - Algoritmos probabilísticos - Algoritmos de aproximação - Heurísticas - Casos de estudo |
4 |
| Total | 36 |
Avaliação
| Atividade Avaliativa | Valor |
|---|---|
| P1 | 35 |
| P2 | 35 |
| Exercícios/Tarefas | 20 |
| Trabalho Final | 10 |
| Total | 100 |
Recursos
- Datashow e quadro com pincel
- Ambiente de desenvolvimento integrado
- Listas de Exercícios Online
- Materiais didáticos digitais
Bibliografia
Bibliografia Básica
- CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: Elsevier, 2012. 926 p. ISBN 978-85-352-3696-9
- SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4. ed. Boston: Addison-Wesley, 2011. 955 p. ISBN 978-0-321-57351-3
- MANBER, Udi. Introduction to algorithms: a creative approach. Boston: Addison-Wesley, 1989. 478 p. ISBN 0-201-12037-2
Bibliografia Complementar
- KNUTH, Donald E. The art of computer programming. 3. ed. Reading: Addison-Wesley, 1997-1998. 3 v. ISBN 0-201-89683-4
- SKIENA, Steven S. The algorithm design manual. 2. ed. London: Springer, 2008. 730 p. ISBN 978-1-84800-069-8
- KLEINBERG, Jon; TARDOS, Éva. Algorithm design. Boston: Pearson/Addison-Wesley, 2006. 838 p. ISBN 0-321-29535-8
Observações
- Será criado um grupo (opcional ao estudante) no aplicativo WhatsApp para agilizar a comunicação e permitir esclarecimentos de dúvidas
- Utilização do AVA CEFET-MG (MOODLE) como repositório de materiais, realização de atividades e, eventualmente, avaliações
- Implementação prática dos algoritmos será realizada em laboratório
Cronograma
| Data | Atividade |
|---|---|
| 31/03 | Apresentação da Disciplina e Plano de Ensino |
| 07/04 | Fundamentos: Conceitos básicos e notação assintótica |
| 14/04 | Fundamentos: Análise de complexidade e recorrências |
| 21/04 | Técnicas: Divisão e conquista |
| 28/04 | Técnicas: Programação dinâmica |
| 05/05 | Técnicas: Algoritmos gulosos |
| 12/05 | Técnicas: Backtracking |
| 19/05 | Ordenação: Algoritmos básicos |
| 26/05 | Ordenação: Algoritmos avançados |
| 02/06 | Prova 1 (Avaliação Parcial) |
| 09/06 | Busca: Árvores e Hashing |
| 16/06 | Busca: Strings e aplicações |
| 23/06 | Grafos: Representação e caminhos |
| 30/06 | Grafos: Árvores e fluxo |
| 07/07 | Algoritmos aproximativos |
| 14/07 | Seminários: Casos de estudo |
| 21/07 | Prova Substitutiva |
| 28/07 | Prova Final |