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á
Ementa
Estudo e aplicação de técnicas avançadas para análise e desenvolvimento de algoritmos eficientes. Abordagem sistemática de paradigmas algorítmicos com foco na otimização de recursos computacionais (memória, CPU e disco) e na resolução de problemas complexos.
, com ênfase em programação competitiva.recursividade; tentativa e erro; divisão e conquista; programação dinâmica; algoritmos gulosos; Backtracking; aritmética e álgebra; análise combinatória; teoria dos números; grafos; geometría computacional.
Objetivos
Esta disciplina abrange conteúdos de programação básica, paradigmas de projeto de algoritmos e técnicas para a codificação rápida de códigos eficientes com uma abordagem prática. São introduzidos ainda conteúdos de aritmética, álgebra e geometria computacional, análise combinatória e teoria dos números, bem como algoritmos avançados em grafos. O conteúdo é abordado através da resolução de pequenos desafios computacionais avançados. Espera-se que, ao final da disciplina, o aluno esteja apto a identificar as estruturas e os paradigmas adequados para resolução de problemas.
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 - Noção de comportamento assintótico de uso de memória, CPU e disco |
8 |
| 2 | TÉCNICAS DE PROJETO DE ALGORITMOS I - Recursividade - Tentativa e erro - Divisão e conquista - Programação dinâmica |
12 |
| 3 | TÉCNICAS DE PROJETO DE ALGORITMOS II - Algoritmos gulosos - Backtracking - Aplicações em programação competitiva |
10 |
| 4 | MATEMÁTICA COMPUTACIONAL - Aritmética e álgebra - Análise combinatória - Teoria dos números - Aplicações em problemas competitivos |
10 |
| 5 | ALGORITMOS EM GRAFOS - Representação de grafos - Algoritmos de caminho mínimo - Árvores geradoras - Fluxo em redes - Problemas clássicos de programação competitiva |
12 |
| 6 | GEOMETRIA COMPUTACIONAL - Conceitos fundamentais - Algoritmos geométricos básicos - Problemas de interseção - Aplicações em competições |
8 |
| 7 | ALGORITMOS DE TRANSFORMAÇÃO DE DADOS - Algoritmos de criptografia básicos - Algoritmos de compressão - Aplicações em competições - Análise de complexidade |
4 |
| Total | 64 |
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
- DEITEL, H. M.; DEITEL, P. J. C++: Como Programar. Editora Prentice Hall. Disponível em: https://plataforma.bvirtual.com.br/Leitor/Publicacao/338/pdf/0
- MIZRAHI, Victorine Viviane. Treinamento em linguagem C++. 2. ed. São Paulo: Pearson Prentice Hall, 2006. ISBN: 978-85-7605-046-9. Disponível em: https://plataforma.bvirtual.com.br/Leitor/Publicacao/28/pdf/0
- ASCÊNCIO, A. F. G. Estrutura de Dados: algoritmos, análise da complexidade e implementações em Java e C/C++. São Paulo: Pearson Prentice Hall, 2010. ISBN: 978-85-7605-881-06. Disponível em: https://plataforma.bvirtual.com.br/Leitor/Publicacao/1995/pdf/0
- SKIENA, Steven S.; REVILLA, Miguel A. Programming challenges: the programming contest training manual. New York: Springer, 2003
- CORMEN, Thomas H. Algoritmos: teoria e prática. Rio de Janeiro: Campus, 2002
- KNUTH, Donald E. The art of computer programming. 2. ed. Reading, Mass.: Addison Wesley, 1973-1981
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 | Fundamentos: Comportamento assintótico de recursos |
| 28/04 | Técnicas I: Recursividade e tentativa e erro |
| 05/05 | Técnicas I: Divisão e conquista |
| 12/05 | Técnicas I: Programação dinâmica |
| 19/05 | Técnicas I: Aplicações e exercícios |
| 26/05 | Técnicas II: Algoritmos gulosos |
| 02/06 | Técnicas II: Backtracking |
| 09/06 | Técnicas II: Aplicações em programação competitiva |
| 16/06 | Prova 1 (Avaliação Parcial) |
| 23/06 | Matemática: Aritmética e álgebra |
| 30/06 | Matemática: Análise combinatória |
| 07/07 | Matemática: Teoria dos números |
| 14/07 | Matemática: Aplicações em problemas competitivos |
| 21/07 | Grafos: Representação e algoritmos básicos |
| 28/07 | Grafos: Algoritmos de caminho mínimo |
| 04/08 | Grafos: Árvores geradoras e fluxo em redes |
| 11/08 | Grafos: Problemas clássicos de programação competitiva |
| 18/08 | Geometria: Conceitos fundamentais |
| 25/08 | Geometria: Algoritmos geométricos básicos |
| 01/09 | Geometria: Problemas de interseção |
| 08/09 | Geometria: Aplicações em competições |
| 15/09 | Prova 2 (Avaliação Parcial) |
| 22/09 | Prova Substitutiva |
| 29/09 | Prova Final |