Análise de Algoritmos

Conhecimentos de Base Recomendados

Frequência das disciplinas de Métodos de Programação I e II e de Lógica.

Métodos de Ensino

Aulas tradicionais com giz e quadro. De vez em quando apresentação de uma

implementação devido a empenho de um aluno particular especialmente interessado

na realização prática dos conhecimentos transmitidos.

Resultados de Aprendizagem

Conhecer diferentes modelos abstratos computacionais, como RAM, RASP e Máquina de Turing de

k fitas, e traduzir programas entre eles.   

Estudo das complexidades sobretudo temporal, mas também espacial, de algoritmos.

Aprender a usar estruturas de dados adequados para implementação eficiente de algoritmos.

Aprender a importância da eficiência relativa de um programa.

Estudo informal da correção de programas.

Capacidade de desenvolver estimativas para fórmulas recursivas. 

Problemas polinomiais e intratáveis.

Vários algoritmos para ordenar listas e inteiros segundo critérios e especificações diferentes.

Algoritmos para encontrar caminhos mais curtos, árvores geradoras, realizar a união de listas, etc.

Estágio(s)

Não

Programa

São mencionados já na parte p, visto que os conteúdos programáticos são um subconjunto dos objetivos da unidade curricular e das competências a desenvolver. Uma mais fina lista do conteúdo programático encontra-se nos sumários da cadeira. 

Docente(s) responsável(eis)

Alexander Kovacec

Métodos de Avaliação

Final
Exame: 100.0%

Contínua
2 Minitestes : 40.0%
Frequência: 60.0%

Bibliografia

Aho, Hopcroft, Ullman, Design and Analysis of Algorithms, Addison Wesley 1974.

 

BAASE, S. and GELDER,A.Van.(2000). Computer Algorithms: Introduction to Design and Analysis.3rd Ed. Addison-Wesley.

 

WEISS, C, M.A. (1997). Data Structures and Algorithm Analysis. 2nd Ed.Addison-Wesley.