Desenvolvimento e Análise de Algorítmos › 47980

código no paco
47980
área científica
Informática / Ciência e Tecnologia da Programação
créditos
6
escolaridade
ensino teórico-prático (TP) - 3 horas/semana
idioma(s) de lecionação
a inserir brevemente
objectivos
A compreensão das características e do funcionamento de algoritmos de diferentes tipos, bem como conhecimento quanto às possíveis estratégias de abordagem para determinados problemas, são componentes fundamentais da formação em Engenharia de Computadores.
Pretende-se fornecer formação adicional em Algoritmia tendo como pontos principais:
1. os paradigmas mais importantes de projecto/desenvolvimento de algoritmos,
2. os métodos de análise da complexidade de algoritmos,
3. exemplos de aplicação em diferentes áreas.
competências

Compreender e usar:
• As principais estratégias de desenvolvimento de algoritmos
• Os métodos habituais de análise da complexidade de algoritmos
Ser capaz de :
• Usar a estratégia apropriada para desenvolver algoritmos para diferentes tipos de problemas
• Analisar, de modo formal e de modo empírico, a complexidade de algoritmos
• Reconhecer a aplicabilidade e as limitações de diferentes soluções algorítmicas para instâncias particulares de alguns problemas

conteúdos
1. Revisão de conceitos fundamentais da análise da complexidade de algoritmos
2. Algoritmos de força bruta ("brute-force")
3. A estratégia "dividir-para-reinar" ("divide-and-conquer")
4. A estratégia "diminuir-para-reinar" ("decrease-and-conquer")
5. Programação dinâmica
6. Algoritmos vorazes ("greedy")
7. Estratégias avançadas: "backtracking"; "branch-and-bound"; determinação de soluções aproximadas
avaliação

A avaliação, do tipo discreta, compreende:
- um exame escrito, com um peso de 50% da nota final,
- trabalhos / projectos, abrangendo o desenvolvimento, teste, análise de resultados de diferentes algoritmos e escrita de relatórios, com um peso de 50% da nota final.

requisitos
Domínio dos conceitos fundamentais da programação (usando diferentes paradigmas) e do desenvolvimento de software; experiência de desenvolvimento de programas de média e elevada complexidade.

Conhecimentos fundamentais de algoritmia e análise da complexidade de algoritmos.

metodologia
Os conceitos e algoritmos fundamentais são apresentados de modo expositivo e ilustrados com exemplos de aplicação.

Em laboratório de computadores são desenvolvidos, implementados e testados algoritmos para problemas de diferentes tipos, e analisado o seu desempenho e aplicabilidade a instâncias de diferentes características.

bibliografia base
Introduction to the Design and Analysis of Algorithms / A. Levitin / 3rd Ed. / 2012
bibliografia recomendada

A. Levitin. Introduction to the Design and Analysis of Algorithms - 3rd Ed. Pearson, 2012.
R. Johnsonbaugh and M. Schaefer. Algorithms. Pearson Prentice Hall, 2004.
T. H. Cormen et al. Introduction to Algorithms - 3rd Ed. MIT Press, 2009.
S. Baase and A. Van Gelder. Computer Algorithms - Introduction to Design and Analysis - 3rd. Ed. Addison-Wesley, 2000.

Este sítio web utiliza cookies sem recolher informação pessoal que permita a identificação dos utilizadores. Ao navegar neste sítio está a consentir a sua utilização.saber mais
Para que esta página funcione corretamente deve ativar a execução de Javascript. Se tal não for possível, algumas funcionalidades poderão estar limitadas.