Disciplina

Área

Área Científica de Metodologia e Tecnologia da Programação > Algoritmia

Activa nos planos curriculares

SISE 2015 > SISE 2015 > 3º Ciclo > Sise - Algoritmos e Estruturas de Dados

Nível

A avaliação é composta pelo seguinte conjunto de componentes: Projecto em grupo (50%), Exame (50%)

Tipo

Não Estruturante

Regime

Semestral

Carga Horária

1º Semestre

1.072 h/semana

1.072 h/semana

54.0 h/semestre

Objectivos

Visão geral dos conceitos básicos sobre análise e síntese de algoritmos e estruturas de dados, focando aqueles que encontramos na maioria das bibliotecas. Adquirir noções de complexidade computacional. Aplicar estas noções na resolução de problemas práticos, tendo em conta a viabilidade, eficiência e escalabilidade. Analisar a implementação de algoritmos e estruturas de dados

Programa

A unidade curricular cobre as seguintes temáticas: - Introdução à resolução de problemas, aos algoritmos e às estruturas de dados. - Introdução ao desenho de algoritmos, desde o uso de recursão e da estratégia dividir para conquistar a estratégias gananciosos e à programação dinâmica. - Introdução à análise de algoritmos e complexidade computacional. - Vectores e algoritmos de ordenação e seleção. O problema fundamental das estruturas de dados. Listas ligadas, filas e pilhas. Funções e tabelas de dispersão. Árvores de pesquisa. Conjuntos e mapas. - A Java Collections Framework e implementações típicas. Utilização prática de algoritmos e estruturas de dados, problemas básicos em grafos e de otimização, aplicação em bases de dados e em problemas de aprendizagem. Classes de problemas e a sua complexidade. Paralelização e os seus limites. - Intratabilidade e como lidar com problemas intratáveis. Big Data ou quando o tempo polinomial pode ser demais.

Metodologia de avaliação

A avaliação é composta pelo seguinte conjunto de componentes: Projecto em grupo (50%), Exame (50%)

Bibliografia

Principal

Introduction to Algorithms (3rd Edition)

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

2009

MIT Press


Secundária

Algorithms (4th Edition)

Robert Sedgewick and Kevin Wayne

2014

Addison-Wesley (Resources and code available at http://algs4.cs.princeton.edu)