Disciplina: Estruturas de Dados e Algoritmos

Área Científica:

Informática

HORAS CONTACTO:

80 Horas

NÚMERO DE ECTS:

7,5 ECTS

IDIOMA:

Português

Objetivos Gerais:

1 - Incrementar os conhecimentos teóricos e práticos de programação, usando como veículo de implementação a linguagem C++.
2 - Afectação dinâmica de memória e construção e manipulação de estruturas dinâmicas.
3 - Estudo de algumas formas de organização dos dados particularmente úteis e dos principais algoritmos associados.
4 - Estudo dos algoritmos de ordenação e análise da sua eficiência.

Conteúdos / Programa:

1 - Introdução à linguagem de programação C++
2 - Tipos de dados em C++. Afectação dinâmica de memória e construção e manipulação de estruturas dinâmicas. Tipos de dados abstractos mais comuns e implementações variadas para estes (representações sequenciais e encadeadas em vectores, e representações dinâmicas diversas, recorrendo a "apontadores").
3 - Estudo e manipulação de estruturas arborescentes. Árvores, árvores n-áreas e árvores binárias: caracterização formal e implementações diversificadas. Árvores de pesquisa, árvores equilibradas e árvores de Bayer: algoritmos (iterativos e recursivos) de pesquisa, inserção e anulação sobre tais estruturas.
4 - Formas de organização dos dados por dispersão e algoritmos de pesquisa, inserção e anulação associados.
5 - Grafos: sua representação e estudo de alguns algoritmos associados.
6 - Introdução ao estudo da eficiência de algoritmos. Algoritmos de ordenação de vectores: elementares (inserção directa, selecção directa e Bubblesort) e avançados (Shellsort, Heapsort, Quicksort e fusão binária). Ordenação por dispersão. Combinação de métodos de ordenação. Algoritmos de ordenação de ficheiros

Bibliografia / Fontes de Informação:

T.H. Cormen, C.E. Leiserson, R.L. Rivest & C. Stein , 2001 , Introduction to Algorithms , The MIT Press,
Sedgewick, R. , 1998 , Algorithms in C, Parts 1-4 ( Fundamental Algorithms, Data Structures, Sorting, Searching) , Addison-Wesley, 3rd edition
Sedgewick, R , 2002 , Algorithms in C, Part 5 ( Graph Algorithms) , Addison-Wesley, 3rd edition

Métodos e Critérios de Avaliação:

Tipo de Classificação: Quantitativa (0-20)

Metodologia de Avaliação:
A avaliação baseia-se nas seguintes componentes obrigatórias: Teórico/Teórico-Prática (Individual) 70% - 2 Frequências obrigatórias (35% + 35%), com nota mínima de 9,0 valores em cada uma e possibilidade de recuperação no período complementar. Prática (Grupo de 4 elementos) 30% - Projeto (nota mínima 8,0 valores, sem possibilidade de recuperação) 2 datas de entrega (todas obrigatórias) e 2 defesas com todos os elementos. Quem não atingir a nota mínima no projeto reprova a disciplina. Observações: Para efeito de nota mínima a nota do prática não está sujeita a arredondamento. O exame de recurso está dividido em duas partes, cuja matéria corresponde às duas frequências. Os alunos podem optar por fazer uma delas ou ambas. Apenas a nota final é arredondada às unidades.