Os principais objetivos desta Unidade Curricular são:

- adquirir conhecimentos sobre algoritmia, em particular algoritmos recursivos, de ordenação e de pesquisa, e análise de complexidade dos algoritmos;

- compreender os conceitos fundamentais associados aos vários tipos de estruturas de dados sequenciais (listas ligadas, pilhas e fila) e não sequenciais (árvores), e dos algoritmos passíveis de aplicação a cada estrutura.

No final da Unidade Curricular o estudante deve ser capaz de

- desenvolver competências de algoritmia, em particular em problemas que envolvam recursividade, ordenação e/ou pesquisa;

- analisar a eficiência dos algoritmos, através da respetiva análise de complexidade, de forma a usar os algoritmos mais eficientes na resolução do problema em questão;

- idealizar, esquematizar e implementar estruturas de dados e respectivos algoritmos com vista à resolução de problemas.

PARTE A - ALGORITMOS

1 - Memória dinâmica

2 - Algoritmos recursivos

3 - Análise de complexidade dos algoritmos

4 - Algoritmos de ordenação

4.1 - Iterativos: por selecção e por troca/borbulhagem (Bubble Sort)

4.2 - Recursivos: por separação (Quick Sort) e por fusão (Merge Sort)

5 - Algoritmos de pesquisa

5.1 - Iterativos: Exaustiva, Sequencial e Binária

5.2 - Recursivos: Binária

6 - Tabelas de Dispersão (Hash).

PARTE B - ESTRUTURAS DE DADOS

1 - Estrutura Abstrata de Dados (EAD)

2 - A EAD "LISTA"

2.1 - Lista ligada simples

2.2 - Pilha

2.3 - Fila

2.4 - Listas com Saltos

3 - A EAD "ÁRVORE"

3.1 - Conceitos gerais

3.2 - Árvore binária

3.3 - Árvore binária de pesquisa

4 - Grafos e redes

"Estruturas de Dados e Algoritmos em C", 2008

António Manuel Adrego da Rocha

FCA - Editora Informática. Coleção:Tecnologias de Informação

ISBN: 9789727222957

"Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms", 3rd Edition, 2001

By Robert Sedgewick

Addison-Wesley Professional

ISBN: 0201756080

"Data Structures and Algorithm Analysis", Edition 3.2 (C++ Version), 2013

Clifford A. Shaffer

Free download in http://people.cs.vt.edu/~shaffer/Book/C++3e20130328.pdf).

"Introdução à Programação Usando C"

António Manuel Adrego da Rocha

FCA - Editora Informática. Coleção: Tecnologias de Informação

ISBN: 9789727225248

"Data Structures in ANSI C", 1991

S. Sengupta

Academic

"Mastering algorithms in C". 1999

Kyle Loudon

O'Reilly

"Programs and Data Structures in C", 2nd edition, 1996

L. Ammeraal

John Wiley & Sons

"Data Structures and Algorithm Analysis in C++", 2nd Edition, 1999

Mark Allen Weiss

Addison-Wesley

A avaliação consiste no seguinte:

- 4 Fichas de Trabalho (realizados nas aulas práticas): 6 valores (valendo 1,5 valores cada ficha)

- 2 Testes Escritos (Frequências): 14 valores (7 valores cada teste)

- Assiduidade: 75%

Aprendizagem = Fichas de Trabalho + Frequências

em que, 

- Assiduidade < 75% ==>  Reprovado e Não Admitido a Exame

- Fichas de Trabalho < 1,5 (em 6)  ==>  Reprovado e Não Admitido a Exame

- Aprendizagem >= 9,5  ==>  Aprovado e Dispensado de Exame

- Outros casos  ==>  Reprovado e Admitido a Exame

Exames = Teste Escrito + Fichas de Trabalho

em que,

- Fichas de Trabalho (realizados nas aulas práticas): 6 valores

- Teste Escrito: 14 valores

Tipo	Data	Salas
Frequência 1	16/04/2019	Aula teórica/prática
Frequência 2	04/06/2019	Aula prática/prática
Ficha Trabalho 1	19/03/2019	Aula prática
Ficha Trabalho 2	09/04/2019	Aula prática
Ficha Trabalho 3	07/05/2019	Aula prática
Ficha Trabalho 4	21/05/2019	Aula prática

Ano letivo 2018/2019 (necessita de senha de acesso)

Trabalhos

Frequência

Aprendizagem (Frequências + Fichas de Trabalho)

Exame Normal (Teste Escrito + Fichas de Trabalho)

Exame Recurso (Teste Escrito + Fichas de Trabalho)

PARTE A - ALGORITMOS

1. Memória dinâmica

2. Algoritmos recursivos

3. Análise de complexidade dos algoritmos

4. Algoritmos de ordenação

4.1. Iterativos: por selecção e por troca/borbulhagem (Bubble Sort)

4.2. Recursivos: por separação (Quick Sort) e por fusão (Merge Sort).  Exemplos.

5. Algoritmos de pesquisa

6. Tabelas de Dispersão (Hash).

PARTE B - ESTRUTURAS DE DADOS

1. Estrutura Abstrata de Dados (EAD)

2. EAD "LISTA"

2.1. Conceitos gerais

2.2. Listas ligadas com ligações simples

2.3. EAD Pilha

2.4. EAD Fila

2.5. Listas com saltos

3. EAD "Arvore"

3.1. Conceitos gerais

3.2. Árvores binárias

3.3. Árvores binárias de pesquisa

4. Grafos e redes

Sebenta de Algoritmos e Estruturas de Dados

Capítulo 1 - Introdução

Capítulo 2 - Estrutura de Dados sequencial com armazenamento sequencial

Capítulo 3 - Estrutura de Dados sequencial com armazenamento não sequencial

Capítulo 4 - Estrutura de Dados não sequencial (EAD "Arvore")

Capítulo 5 - Estrutura de Dados não sequencial (Grafos e redes)

Outros apontamentos

Ficheiros de texto

Estruturas

Apontadores

Exemplos

Exemplo 1: Memória dinâmica + Ordenação

Exemplo 2: Memória dinâmica + Ordenação + Pesquisa

Exemplo 3: Inserção e remoção de um elemento de um vetor ordenado

Exemplo 4: Remover todos os elementos de um vetor ordenado entre E1 e E2

PARTE I - ALGORITMOS

Folha 01 - Memória dinâmica

Folha 02 - Algoritmos recursivos

Folha 03 - Análise de complexidade dos algoritmos

Folha 04 - Algoritmos de ordenação

Folha 05 - Algoritmos de pesquisa

Folha 06 - Tabelas de dispersão (Hash)

PARTE II - ESTRUTURAS DE DADOS

Folha 07 - Listas ligadas simples

Folha 08 - Pilhas

Folha 09 - Filas

Folha 10 - Listas com saltos

Folha 11 - Árvores Binárias

Folha 12 - Árvores Binárias de Pesquisa

Folha 13 - Grafos e redes

Outras folhas práticas

Estruturas

Apontadores

Ficheiros de Texto

Exercícios resolvidos das folhas práticas

Listas ligadas simples + Listas Ligadas (todas as funções estudadas nas aulas teóricas)

Pilhas

Filas

Árvores Binárias

Árvores Binárias de Pesquisa

Funções implementadas fornecidas:

LerVector (lê de um ficheiro de inteiros - um valor em cada linha)

LerVectorALUNO (lê de um ficheiro com elementos do tipo ALUNO)

Ficheiros de texto fornecidos:

dados.txt

dados1.txt

dados2.txt

dados3.txt

dados4.txt

dados5.txt

discos.txt

multiplos.txt

texto.txt

medicoes01.txt

medicoes02.txt

medicoes03.txt

medicoes04.txt

medicoes05.txt

Inteiros.txt

InteirosPositivos.txt

Reais.txt

ReaisPositivos.txt

ReaisNegativos.txt

InteirosSemRepetidos.txt

InteirosComRepetidos.txt

Matriculas.txt

Outras folhas práticas

Instruções condicionais e ciclos

Ficheiros de texto

Testes de anos anteriores

2014/2015:

Frequência - Resolução

Exame Época Normal - Resolução

Entrada no sistema

Usar Conta UNIX

Acesso através de computadores das salas 6.14 e 6.19

Plataforma de Avaliação

Acesso através de outros computadores

Plataforma de Avaliação

Horas	Segunda	Sala	Terça	Sala	Quarta	Sala	Quinta	Sala	Sexta	Sala
8
9
10
11					ATEND	G4.2
12					ATEND	G4.2
13
14			PL	6.14
15			PL	6.14
16			TE	6.03
17			TE	6.03
18