Estruturas de Dados

Programação

Linguagem JAVA.

(unidades curriculares Introdução à Programação, Programação, Programação Avançada)

Nas aulas teóricas, são apresentadas, analisadas e discutidas as estruturas de dados mais relevantes e representativas,  via zoom, conforme instruções superiores

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.

Conforme o número de alunos, de acordo com instruções superiores, poderão ocorrer diversos cenários de funcionamento, a determinar aquando do arranque das aulas de dependendo do número de alunos por turma:

• Todas as turmas funcionarem em regime síncrono alternado;
• Regime presencial em todas as turmas laboratoriais.
• Algumas turmas da UC funcionarem em regime presencial e outras em regime síncrono alternado (este último regime poderá funcionar, por exemplo, apenas numa turma, dependendo do número de alunos e do seu horário);

Desenvolver as competencias relativas ao programa da UC, incluindo:

– Compreender o conceito de complexidade algoritmica

– Conhecer as diversas estruturas de dados e o perfil de complexidade das várias operações que estas suportam

– Escolher entre várias alternativas a melhor estrutura de dados a aplicar conforme o perfil de utilização pretendido.

– Compreender o funcionamento de diversas estruturas de dados e os algoritmos que lhes estão associados

– Desenvolver competências de programação genérica e recursividade

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ásicos
     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 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 – Heaps
4.2 – Splay Tree
4.3 – Estruturas de dados para informação espacial e multidimensional
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

Goodrich, Michael T. ; Tamassia, Roberto, 2011- Data structures and algorithms in Java. 5th ed.. Hoboken, NJ : John Wiley & Sons, cop. 2011. 710 p.. ISBN 978-0-470-39880-7 (1A-1-429 (ISEC) – 16300)
Weiss, Mark Allen, 1992 – Data structures and algorithm analysis. Redwood City, California : Benjamin/Cummings, 1992. 455 p.. ISBN 0-8053-9052-9 (1A-5-26 (ISEC) – 05840)
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L., 1997- Introduction to algorithms. Cambridge [etc.] : The MIT Press, 1997 imp. 1028 p.. ISBN 0-262-53091-0(1A-1-427 (ISEC) – 09849)

Bibliografia Complementar
Weiss, Mark Allen, 2009, Data Structures & Problem Solving Using Java,Pearson; 4th edition
Open data structures in java, 2023 – https://opendatastructures.org/
Material de apoio fornecido.