Licenciatura

Engenharia Informática

Área Científica

Matemática

Duração

Semestral

Unidade Curricular

Algoritmos e Estruturas de Dados

ECTS

6

Horas de Contacto Teórico Práticas

60h

OBJETIVOS DA APRENDIZAGEM

Para concluir com sucesso esta unidade curricular, os alunos deverão demonstrar possuir os seguintes conhecimentos e capacidades:

1. Compreender, saber implementar e manipular estruturas de dados do tipo array;

2. Compreender, saber implementar e manipular pilhas e filas de espera;

3. Compreender e saber implementar técnicas de programação recursivas;

4. Compreender, saber implementar e manipular linked lists (listas encadeadas);

5. Compreender, saber implementar e manipular árvores.

Os algoritmos e estruturas de dados serão implementados usando as linguagens C e C++.

PROGRAMA

1. Introdução à Algoritmia e Estruturas de Dados

2. Vetores – Arrays

2.1 Introdução aos vetores

2.2 Implementação de um vetor

2.3. Adicionar, alterar e remover elementos de um vetor

2.4 Ordenação de um vetor

2.5 Pesquisa sequencial e pesquisa binária ou dicotómica

3. Pilhas e Filas de Espera

3.1. O que são Pilhas

3.2. Implementar uma Pilha

3.3. Adicionar, alterar e remover elementos a uma Pilha

3.7. O que são Filas de Espera

3.8. Implementar uma Fila de Espera

3.9. Adicionar, alterar e remover itens a uma fila de espera

4. Recursividade – Conceitos e técnicas

4.1. Recursividade – Conceitos base

4.2. Função Factorial

4.3. Recursão excessiva – Fibonacci Numbers

4.4. Tail Recursion

4.5. Problemas na utilização de funções recursivas

5. Listas encadeadas

5.1. Listas simplesmente encadeadas

5.2. Criar uma lista simplesmente encadeada

5.3. Percurso e localização de um item

5.4. Adicionar, alterar e remover itens em qualquer ponto de uma lista simplesmente encadeada

5.5 Listas duplamente encadeadas

5.6 Implementar uma lista duplamente encadeada

5.7 Adicionar, alterar e remover itens de uma lista duplamente encadeada

5.8 Listas encadeadas circulares

5.9. Implementar uma lista encadeada circular

5.10. Adicionar, alterar ou remover um conjunto de itens a uma lista encadeada circular

6. Árvores

6.1. Conceitos base

6.2. Representação de árvores

6.3. Árvores binárias

6.4. Árvores de ordenação binária

6.5. Atravessamento de uma árvore

6.6. Localizar e inserir itens em árvores de ordenação binária

6.7. Implementar uma árvore de ordenação binária

6.8. Inserir um nó numa árvore de ordenação binária

6.9. Verificar se existe um dado nó numa árvore de ordenação binária

6.10. Calcular o número de nós da árvore de ordenação binária

DEMONSTRAÇÃO DE COERÊNCIA ENTRE CONTEÚDOS PROGRAMÁTICOS E RESULTADOS DA APRENDIZAGEM

O objetivo 1 é atingido através dos pontos 2.1 a 2.5. Os pontos 3.1 a 3.9 permitem atingir o objetivo 2. O objetivo 3 é atingido através dos pontos 4.1 a 4.5. Os pontos 5.1 a 5.10 permitem alcançar o objetivo 4. O objetivo 5 é atingido através dos pontos 6.1 a 6.10.

METODOLOGIA DE ENSINO E AVALIAÇÃO

As aulas desta unidade curricular são de natureza teórico-prática. Estão previstas 60 horas de contato. O tempo total de trabalho do aluno corresponde a 162 horas. Em todas as aulas, exercícios de aplicação prática dos algoritmos e das estruturas de dados complementam a exposição teórica dos apresentados. Esta metodologia permite que os alunos adquiram, não apenas os conhecimentos teóricos, mas também as necessárias competências para aplicar as estruturas de dados a situações práticas simuladas.

De acordo com o Regulamento de Funcionamento do ISTEC a avaliação é efetuada através de um exame escrito individual e obrigatório. Na classificação final, poderão ser considerados elementos de avaliação contínua, tais como testes, trabalhos individuais ou em grupo, assim como a participação nas aulas presenciais e em recursos de aprendizagem proporcionados por sistemas de e-learning.

DEMONSTRAÇÃO DE COERÊNCIA ENTRE METODOLOGIAS DE ENSINO E RESULTADOS DE APRENDIZAGEM

A obtenção dos objetivos da unidade curricular é assegurada pela natureza teórico-prática das aulas da unidade curricular que são planeadas para permitir a compreensão teórica e prática dos conceitos, partindo das estruturas de dados mais simples para as construções mais complexas.

BIBLIOGRAFIA

Fundamental:
Rocha, António A., Estruturas de Dados e Algoritmos em C, 2014, 3ª. edição, FCA, ISBN 978-972-722-769-3.
Shaffer, Clifford A. Data Structures and Algorithm Analysis in C++, Third Edition (2011)

Complementar:
Goodrich, Michael T.; Tamassia, Roberto e Mount, David M. Data Structures and Algorithms in C++, Second Edition, John Wiley & Sons

INTERNET:
Acesso a publicações da especialidade, gratuitamente, através da rede SPRINGER:
https://link.springer.com/