Saber: Técnicas básicas para a resolução de problemas: tipos abstractos de dados fundamentais (lista, conjunto, pilha, fila, dicionário, dicionário ordenado) e do domínio do problema; técnicas básicas de desenho de algoritmos: estruturas de dados fundamentais (vector, lista ligada simples e dupla, tabela de dispersão, árvores binárias); técnicas básicas para análise de algoritmos: complexidade espacial e temporal.

Saber Fazer: modelar programas usando tipos abstractos de dados; definir e implementar tipos abstractos de dados no domínio do problema; calcular a complexidade espacial e temporal de algoritmos; implementar os tipos abstractos de dados fundamentais, utilizando as estruturas de dados mais adequadas; conceber e implementar soluções eficientes para problemas concretos.

Soft-skills: Capacidade para avaliar soluções, capacidade para seleccionar as técnicas apropriadas a um problema; capacidade de comunicação escrita: relatórios de projetos da disciplina.

1. Estruturação dum programa em tipos abstractos de dados.
   • Método para análise e concepção da solução
   • Definição e implementação de tipos abstractos de dados no domínio do problema
2. Introdução à análise de algoritmos.
3. Especificação formal de tipos de dados abstractos:
   • Fila
   • Pilha
   • Sequência (Lista)
   • Conjunto
   • Dicionário
   • Dicionário Ordenado
4. Estudo das principais estruturas de dados, sempre acompanhado da análise da complexidade das primitivas suportadas, no melhor caso, no pior caso e no caso esperado.
   • Vectores circulares.
   • Listas simplesmente e duplamente ligadas.
   • Tabelas de dispersão. Funções de dispersão. Dispersão aberta. Dispersão fechada.
   • Árvores binárias. Árvores de pesquisa.

Mark Allen Weiss.
Data Structures and Algorithm Analysis in C (second edition).
Addison-Wesley, 1997.
ISBN 0-201-49840-5 (Hard cover)

Linguagem de Programação C

Brian Kernighan and Dennis Ritchie
The C Programming Language (second edition).
Prentice-Hall, 1988.
ISBN 0-13-110362-8 (Paperback)

Pedro Guerreiro.
Elementos de Programação com C (3ª edição).
FCA - Editora de Informática, 2005.

Luis Damas.
Linguagem C (12ª edição).
FCA - Editora de Informática, 2005.

Precedência obrigatória:

- Programação de Microprocessadores