Algoritmos e Estruturas de Dados

Não existem conhecimentos base recomendados.

De acordo com os objetivos do curso, as suas condições de realização e o público alvo são utilizadas metodologias e estratégias que permitam à turma apreender e compreender os conteúdos lecionados da melhor forma:

1. Método expositivo: exposição oral de conteúdos teóricos com recurso a apresentações multimédia, tal como utilização de programas específicos e recursos;

2. Método interrogativo: através de questões individuais ou direcionadas ao grupo no decorrer das aulas, permitindo obter feedback imediato sobre os conteúdos abordados;

3. Método ativo: será utilizado com recurso a várias técnicas como, realização de discussões/debates sobre as temáticas desenvolvidas, estudos de caso relativamente a factos importantes na área das ciências informáticas, resolução de problemas e desenvolvimento de trabalhos individuais;

4. Método demonstrativo.

Dotar os alunos de conhecimentos fundamentais de algoritmos e das estruturas de dados básicas, como ferramentas essenciais para resolver problemas de forma eficiente.

Depois de frequentar esta unidade curricular espera-se que cada aluno:

• conheça diferentes estruturas para guardar e manipular dados na memória;
• distinga estruturas estáticas de estruturas dinâmicas;
• saiba escolher a estrutura de dados mais adequada para cada problema;
• saiba desenvolver e implementar algoritmos que permitam manipular diferentes estruturas de dados, em C;
• compreenda a noção de complexidade e consiga escolher entre dois ou mais algoritmos para resolver o mesmo problema (tendo em conta o esforço computacional de cada um).

1. Tipos Abstratos de Dados
   a. Pilha (disciplina LIFO)
   b. Fila (disciplina FIFO)
   c. Lista (acesso por posição)
   d. Dicionário (acesso por chave): não ordenado e ordenado
2. Estruturas de Dados
   a. Listas circulares
   b. Listas simplesmente e duplamente ligadas
   c. Tabelas de dispersão
   d. Árvores genéricas
   e. Árvores binárias
   f. Árvores binárias de pesquisa: árvores sem restrições, árvores AVL.
   g. Heaps
3. Introdução ao estudo da eficiência de algoritmos
   a. Complexidade temporal e espacial
   b. Complexidade no melhor caso, no pior caso e no caso esperado
4. Introdução à Recursividade
   a. Divisão e conquista
   b. Função-memória
5. Algoritmos de Ordenação
   a. Ingénuos: insertion sort; selection sort; bubble sort
   b. Eficientes: heapsort; mergesort; quicksort

NAO

Damas, L. (2019). Linguagem C. 24ª edição. FCA.

Rocha, A. A. (2014). Análise da complexidade de algoritmos. FCA.

Rocha, A. A. (2014). Estruturas de dados e algoritmos em C. 3ª edição. FCA.

Vasconcelos, J. & Carvalho, A. (2005). Algoritmia e estruturas de dados: Programação nas linguagens C e java. Edições Centro Atlântico.