Estruturas de Dados

Progrmação em Java, Programação Orientada a Objetos

Nas aulas teóricas, são apresentadas, analisadas e discutidas as estruturas de dados mais relevantes e representativas. Nas aulas laboratoriais, os alunos operacionalizam este conhecimento, realizando fichas de exercícios que englobam análise, implementação, teste e selecção de estruturas de dados.
A realização de testes laboratoriais periódicos permite monitorizar continuamente o desempenho dos alunos, enquanto que a realização de seminários promove a maior integração dos alunos no processo de aprendizagem, através da preparação e realização de apresentações sobre tópicos seleccionados aos seus colegas.
A avaliação inclui os seguintes componentes:
–   Exame (12 valores)
–   Componente Laboratorial (testes a realizar durante as aulas Laboratoriais) – 5 valores
–   Projecto (Investigação e apresentação de uma estrutura de dados) – 3 Valores

Compreender as técnicas de análise de complexidade algoritmica. Conhecer o API de colecções.
Aplicar o API de colecções de forma adequada.
Analisar um algoritmo de forma a descobrir a sua complexidade.
Conhecer um espectro diversificado de estruturas de dados fundamentais e avançadas Escolher as estruturas de dados de acordo adequadas para um dado o problema.
Implementar as estruturas de dados e algoritmos associados de forma correcta.

1   – Introdução
1.1   – Análise de Complexidade
1.2   – Programação genérica
1.3   – API de colecções
2   – Estruturas Fundamentais 2.1- Pilhas, Filas, Árvores
2.1.1   – Conceitos básico
2.1.2   – Aplicações – Árvores de Huffman
2.1.3   – Aplicações – Representação e cálculo de expressões (infix-postfix)
2.2   – Árvores de Pesquisa
2.2.1   – Conceitos Básicos
2.2.2   – Árvores AVL
2.2.3   – Árvores Red-Black
2.2.4   – Árvores AA
2.2.5   – Árvores de aridade superior – B-Trees 3- Tabelas de Hash
3.1   – Conceitos Básicos
3.2   – Pesquisa linear e quadrática
3.3   – Encadeamento separado 4- Estruturas Avançadas
4.1   – Heap binária
4.2   – Splay Tree
4.3   – Conjunto Disjunto
Nas aulas Laboratoriais irão ser implementados, aplicados e testados os algoritmos e estruturas abordados nas aulas teóricas, sendo utilizada a linguagem JAVA.

NAO