Algoritmos e Complexidade › 47003

código no paco
47003
área científica
Informática / Ciência e Tecnologia da Programação
créditos
8
escolaridade
ensino teórico (T) - 3 horas/semana
ensino prático e laboratorial (PL) - 2 horas/semana
idioma(s) de lecionação
Português, Inglês
objectivos

Fornecer formação sobre o projecto e a análise do desempenho de algoritmos iterativos e recursivos, com particular ênfase na análise da sua complexidade computacional.

Estudar os algoritmos e as estruturas de dados mais habituais, associados aos tipos abstractos de dados árvore de pesquisa, dicionário e grafo.

Apresentar alguns dos fundamentos teóricos da computação.

competências
compreender e usar:
  • A terminologia e as notações habituais para classificar a complexidade de algoritmos
  • As estruturas de dados dinâmicas habituais para representar listas, árvores e grafos, bem como as operações mais comuns (consultas, travessias, inserções e remoções) associadas
  • Os tipos abstractos de dados árvore de pesquisa, dicionário e grafo
  • Conceitos fundamentais da Teoria da Computação
ser capaz de:
  • analisar, de modo formal e de modo empírico, a complexidade de algoritmos iterativos e recursivos
  • escolher o algoritmo e a estrutura de dados apropriados, em termos do desempenho previsto, para diferentes instâncias de um mesmo problema
  • desenvolver tipos abstractos de dados, estabelecendo as funcionalidades necessárias e usando estruturas de dados apropriadas
aprender a:
  • trabalhar em equipa
conteúdos

1. análise da complexidade de algoritmos: terminologia e conceitos fundamentais; análise de algoritmos iterativos e recursivos para diferentes tipos de problemas

2. árvores binárias de pesquisa: conceitos e operações fundamentais; travessias; árvores avl; splay trees

3. dicionários: tabelas de dispersão, funções de hashing e resolução de colisões; skip lists; b-trees

4. grafos: terminologia e conceitos fundamentais; representação computacional; travessias; determinação de caminhos mais curtos; problemas típicos

5. tópicos de teoria da computação: computabilidade; algoritmos deterministas e não deterministas; as classes p e np; problemas np-completo

avaliação

A avaliação 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, nalguns casos, escrita de relatórios, com um peso de 50% da nota final.

Os trabalhos / projectos de programação são realizados em grupos de dois alunos.

requisitos

Domínio dos conceitos fundamentais da programação modular e do desenvolvimento de software, bem como experiência suficiente de desenvolvimento de programas de média complexidade, adquiridos nas disciplinas anteriores de programação.

metodologia

As aulas teóricas têm um carácter expositivo, ilustrado, sempre que possível, com exemplos de aplicação.

As aulas práticas decorrem em laboratório de computadores e permitem desenvolver, implementar e testar algoritmos, estruturas de dados e tipos abstractos de dados.

A realização de cada tarefa, com base num guião divulgado antes das aulas, consolida, aplica e explora as matérias ensinadas nas aulas teóricas.

É usada a linguagem de programação C.

bibliografia base
Data Structures and Algorithm Analysis in C - 2nd Ed. / M. A. Weiss / 1997
bibliografia recomendada

J. J. McConnell. Analysis of Algorithms: An Active Learning Approach - 2nd Ed. Jones and Bartlett, 2008

M. A. Weiss. Data Structures and Algorithm Analysis in C - 2nd Ed. Addison-Wesley, 1997

A. Adrego da Rocha. Análise da Complexidade de Algoritmos. FCA, 2014

A. Adrego da Rocha. Estruturas de Dados e Algoritmos em C - 3a Ed. FCA, 2014

R. Sedgewick. Algorithms in C (Parts 1-4) - 3rd Ed. Addison-Wesley, 1998

R. Sedgewick. Algorithms in C (Part 5) - 3rd Ed. Addison-Wesley, 2002

A. Levitin. Introduction to the Design and Analysis of Algorithms - 3rd Ed. Pearson, 2012

R. Johnsonbaugh and M. Schaefer. Algorithms. Pearson Prentice Hall, 2004

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.