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.

Alguma influência ainda exercida pelo empenho nas aulas: resolução de problemas (trabalhos de casa) propostos e sugeridos mas não obrigatórios.

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.

 

Espera-se ainda a continuação do desenvolvimento de certas competências genéricas que fazem parte do estudo da Matemática, como o são:

Capacidade de generalização e abstração;

Capacidade de formular e resolver problemas;

Argumentação lógica;

Espírito crítico.

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. 

Métodos de Avaliação

Avaliação Final
Exame 20 pontos: 100.0%

Avaliação Contínua
2 Minitestes de 4+4 pontos. Frequência de 12 pontos: 100.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.