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 - Ficheiros binários

3 - Algoritmos recursivos

4 - Análise de complexidade dos algoritmos

5 - Algoritmos de ordenação

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

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

6 - Algoritmos de pesquisa

6.1 - Iterativos: Exaustiva, Sequencial e Binária

6.2 - Recursivos: Binária

7 - Tabelas de Dispersão (Hash).

PARTE B - ESTRUTURAS DE DADOS

1 - Estrutura Abstrata de Dados (EAD)

2 - A EAD "LISTA"

2.1 - Conceitos gerais

2.2 - Lista ligada simples

3 - A EAD "ÁRVORE"

3.1 - Conceitos gerais

3.2 - Árvore binária

3.3 - Árvore binária de pesquisa

"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 < 5,5 => 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	21-04-2020	Aula prática
Frequência 2	26-05-2020	Aula teórica
Ficha Trabalho 1	10-03-2020	Aula prática
Ficha Trabalho 2	24-03-2020	Aula prática
Ficha Trabalho 3	05-05-2020	Aula prática
Ficha Trabalho 4	02-06-2020	Aula prática

Testes do ano lectivo 2019-2020 (atual):

Frequência 1 [16-04-2019]  ==>  Enunciado  +  Resolução

Frequência 2 [04-06-2019]  ==>  Enunciado  +  Resolução

Exame - Época Normal [19-06-2019]  ==>  Enunciado

Exame - Época Recurso [03-07-2019]  ==>  Enunciado

Testes do ano lectivo 2018-2019:

Frequência 1 [16-04-2019]  ==>  Enunciado  +  Resolução

Frequência 2 [04-06-2019]  ==>  Enunciado  +  Resolução

Exame - Época Normal [19-06-2019]  ==>  Enunciado

Exame - Época Recurso [03-07-2019]  ==>  Enunciado

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

Fichas de Trabalho

Frequência 1

Frequência 2

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. Ficheiros binários

3. Algoritmos recursivos

4. Análise de complexidade dos algoritmos

5. Algoritmos de ordenação

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

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

6. Algoritmos de pesquisa

7. 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

3. EAD "Arvore"

3.1. Conceitos gerais

3.2. Árvores binárias

3.3. Árvores binárias de pesquisa

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")

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 A - ALGORITMOS

Folha A.1 - Memória dinâmica

Folha A.2 - Ficheiros binários

Folha A.3 - Algoritmos recursivos

Folha A.4 - Análise de complexidade dos algoritmos

Folha A.5 - Algoritmos de ordenação

Folha A.6 - Algoritmos de pesquisa

Folha A.7 - Tabelas de dispersão (Hash)

PARTE B - ESTRUTURAS DE DADOS

Folha B.1 - Listas ligadas simples

Folha B.2 - Árvores Binárias

Folha B.3 - Árvores Binárias de Pesquisa

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)

Á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:

Pessoas.txt

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