CCT-UFCA/Ciência da Computação/Construção e Análise de Algoritmos
Programa do Componente Curricular
[editar | editar código]| Código: | CC0065 | ||||||||
| Componente Curricular: | Construção e Análise de Algoritmos | ||||||||
| Semestre de Oferta: | 4º Semestre | Tipo: | Disciplina | Caráter: | Obrigatória | ||||
| Unidade Acadêmica Responsável: | Centro de Ciências e Tecnologia - CCT | ||||||||
| Área: | Teoria da Computação | ||||||||
| Créditos: | 4 | Carga horária: | 64 | Teórica: | 64 | Prática: | 0 | Extensão: | - |
| Pré-requisito: | CC0017 - Algoritmos em Grafos | ||||||||
| Co-requisito: | |||||||||
| Equivalência: | CC0023 | ||||||||
Objetivos
[editar | editar código]Apresentar métodos e conceitos que permitam ao aluno avaliar a qualidade de um algoritmo; apresentar noções e conceitos de complexidade de computação. Caracterizar técnicas gerais de desenvolvimento de algoritmos que permitam ao aluno melhor projetá-los conforme sua natureza.
Ementa
[editar | editar código]Conceitos básicos: recorrências, medidas de complexidade: melhor caso, caso médio e pior caso. Técnicas gerais de projeto de algoritmos: divisão e conquista, método guloso e programação dinâmica. Classes de complexidade: P, NP e NP-completude.
Conteúdo
[editar | editar código]- Corretude e análise de algoritmos
- Notação assintótica
- Recorrências
- Divisão e conquista
- Programação Dinâmica
- Método Guloso
- Classes de complexidade: P, NP e NP-completo
Metodologia
[editar | editar código]A disciplina combina aulas expositivas de conteúdo com resolução de exercícios durante a aula. Os alunos participam de:
- Aulas de conteúdo: exposição teórica dos conceitos, métodos e técnicas relacionadas ao tema da disciplina com resolução de exercícios, discussão e apresentação de soluções passo a passo, visando consolidar o aprendizado e aplicar os conceitos na prática.
Avaliação
[editar | editar código]A avaliação da disciplina é composta por 2 provas para verificar tanto o domínio conceitual quanto a capacidade de comunicação e aplicação dos conteúdos.
- Prova 1: avaliação voltada à compreensão dos conceitos apresentados até divisão e conquista;
- Prova 2: avaliação abrangendo os conteúdos desde programação dinamica, com foco na consolidação do aprendizado;
A nota final é calculada com base nas duas provas conforme os critérios definidos pelo professor responsável.
Bibliografia Básica
[editar | editar código]- CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Algoritmos: teoria e prática. 3ª ed. LTC, 2012. 944p. ISBN-10 : 8535236996, ISBN-13 : 978-8535236996.
- DASGUPTA, S.; PAPADIMITRIOU, C.; VAZIRANI, U. Algoritmos. 1ª ed. McGraw Hill, 2009, 336p. ISBN-10: 8577260321, ISBN-13: 978-8577260324.
- ZIVIANI, N. Projeto de Algoritmos com implementação em Java e C++. 1a edição. São Paulo: Editora Thomson, 2007.
Bibliografia Complementar
[editar | editar código]- SZWARCFITER, L. M. Estruturas de Dados e seus Algoritmos. Livros Técnicos e Científicos, 1994
- OLIVEIRA, J. F.; MANZANO, J. A. N. G. Estudo dirigido de algoritmos. Editora Érika, São Paulo, 1997.
- DOBRUSHKIN, V. Métodos para Análise de Algoritmos. Editora LTC, 2012. ISBN: 9788521620662.
- CORMEN, T. Desmistificando Algoritmos. Editora Campus, 2013. ISBN-13: 978- 8535271775.
- EDMONDS, J. Como Pensar sobre algoritmos. Editora LTC, 2010. ISBN-13: 978- 8521617310