Conhecimentos de Base Recomendados

Conhecimentos iniciais da linguagem de programação JAVA.

Objetivos

 O aluno deve adquirir e consolidar conhecimentos, aptidões e competências na:

- interpretação, análise, especificação e implementação de algoritmos triviais de computação, e.g., algoritmos de seleção, pesquisa, ordenação; algoritmos iterativos e recursivos; na componente de análise será dado destaque à complexidade temporal dos algoritmos;
- especificação e manipulação de estuturas de dados lineares (estáticas e dinâmicas) e tabelas de dispersão;
- comprensão, uso e implementação dos tipos abstratos de dados (do género coleção) mais comuns, e.g., Stack, Queue, List, Map;
- especificação de novos TAD, escolha de uma estrutura de dados apropriada e sua implementação e uso;
- (paralelamente) aquisição de competências  em programação orientada a objetos e uso de tipos genéricos e exceções na implementação de TADs.

Métodos de Ensino

Aulas  teórico-práticas com proposição de exercícios e projeto prático.

Estágio(s)

Não

Programa

• Algoritmos, complexidade algorítmica e formalização de algoritmos em pseudo-código;


• Algoritmos de pesquisa e seleção;


• Algoritmos de ordenação simples O(n²) - Bubble Sort e Selection Sort;


• Algoritmos recursivos versus iterativos;


• Algoritmo de ordenação complexa, e.g., O(n log n) - Quick Sort;


• Tipos de dados referenciados, tipos genéricos e recapitulação de conceitos de interfaces e exceções.


• Utilização de um TAD dada a sua interface; criação de unidades de teste para validação de implementações de TAD;


• Definição e manipulação de uma estrutura de dados linear estática, e.g. arraylist;


• Especificação e implementação dos tipos abstratos de dados (do género coleção) mais comuns, e.g. Stack, Queue, List e Map, recorrendo a uma estrutura de dados estática;


• Implementação e manipulação de estruturas de dados lineares dinâmicas, e.g. listas ligadas;


• Implementação dos tipos abstratos de dados anteriores, recorrendo a uma estrutura de dados dinâmica;


• Tabelas de dispersão e uso desta estrutura de dados numa implementação do TAD Map (=Hash tables).

Demonstração de conteúdos

-

Demonstração da metodologia

-

Docente(s) responsável(eis)

Bruno Miguel Nunes da Silva - 1.º Semestre

Bibliografia

António Adegro da Rocha; ESTRUTURAS DE DADOS E ALGORITMOS EM JAVA
António Adrego da Rocha; ANÁLISE DA COMPLEXIDADE DE ALGORITMOS