Objetivos e resultados da aprendizagem

Algoritmos e Estruturas de Dados

 

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

 

Programa

Algoritmos e Estruturas de Dados

 

PARTE I - ALGORITMOS

1 - Algoritmos recursivos

2 - Algoritmos de ordenação

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

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

3 - Algoritmos de pesquisa

3.1 - Iterativos: Exaustiva, Sequencial e Binária

3.2 - Recursivos: Binária

4 - Tabelas de Dispersão (Hash).

5 - Análise de complexidade dos algoritmos

PARTE II - ESTRUTURAS DE DADOS

1 - Estrutura Abstrata de Dados (EAD)

2 - A EAD "LISTA"

2.1 - Lista ligada simples

2.2 - Pilha

2.3 - Fila

3 - A EAD "ÁRVORE"

3.1 - Conceitos gerais

3.2 - Árvore binária

3.3 - Árvore binária de pesquisa

 

Bibliografia

Algoritmos e Estruturas de Dados

 

"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

 

Avaliação

Algoritmos e Estruturas de Dados

 

A avaliação consiste no seguinte :

- 12/10 Mini-Testes (realizados nas aulas práticas e teóricas): 10 valores (correspondentes aos 10 melhores)

- 1 teste escrito/frequência: 10 valores

- Assiduidade: 50%

Aprendizagem = Mini-Testes + Frequência

em que,

- Assiduidade < 8 Mini-Testes  ==>  Reprovado e Não Admitido a Exame

- Mini-Testes < 4 (em 10)  ==>  Reprovado e Não Admitido a Exame

- Frequência < 2 (em 10)  ==>  Reprovado e Não Admitido a Exame

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

- Outros casos  ==>  Reprovado e Admitido a Exame

Nota Final Exame = Mini-Testes + Exame

em que,

- Mini-Testes (realizados nas aulas práticas e teóricas): 10 valores

- Exame: 10 valores

 

Datas dos testes

Algoritmos e Estruturas de Dados

 

Tipo

Data

Salas

Frequência

18-05-2016, 14:00h

6.18

 

Resultados obtidos nos vários tipos de avaliação

Algoritmos e Estruturas de Dados

 

Ano letivo 2014/2015 (necessita de senha de acesso)

Bioengenharia

Trabalhos

Frequência

Aprendizagem

Exame Normal

Exame Recurso

 

Apontamentos

Algoritmos e Estruturas de Dados

 

PARTE I - ALGORITMOS

1 - Algoritmos recursivos

2 - Algoritmos de ordenação

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

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

3 - Algoritmos de pesquisa

3.1 - Iterativos: Exaustiva, Sequencial e Binária

3.2 - Recursivos: Binária

4 - Tabelas de Dispersão (Hash). Mais sobre Tabelas de Hash.

5 - Análise de complexidade dos algoritmos

PARTE II - ESTRUTURAS DE DADOS

1 - Estrutura Abstrata de Dados (EAD)

2 - A EAD "LISTA"

2.1 - Conceitos gerais

2.1 - Lista ligada simples

2.2 - Pilha

2.3 - Fila

3 - A EAD "ÁRVORE"

3.1 - Conceitos gerais

3.2 - Árvore binária

3.3 - Árvore binária de pesquisa

 

Outros apontamentos

Estruturas

Apontadores

Memória dinâmica

Ficheiros de texto

Ficheiros binários

 

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

 

Folhas práticas

Algoritmos e Estruturas de Dados

 

PARTE 1 - ALGORITMOS

Folha 1 - Algoritmos recursivos

Folha 2 - Algoritmos de ordenação

Folha 3 - Algoritmos de pesquisa

Folha 4 - Tabelas de dispersão (Hash)

Folha 5 - Análise de complexidade dos algoritmos

PARTE 2 - ESTRUTURAS DE DADOS

Folha 6 - Listas ligadas simples

Folha 7 - Pilhas

Folha 8 - Filas

Folha 9 - Árvores Binárias

Folha 10 - Árvores Binárias de Pesquisa

 

Apontamentos em MATLAB

Programação em MatLab

Tutorial de MatLab

MatLab 1

MatLab 2

 

Outras folhas práticas

Estruturas (struct)

Apontadores

Memória dinâmica

Ficheiros de texto

Ficheiros binários

 

Exercícios resolvidos das folhas práticas

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

Listas ligadas duplas

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

ReaisPositivos.txt

InteirosSemRepetidos.txt

InteirosComRepetidos.txt

 

Outras folhas práticas

Instruções condicionais e ciclos

Cadeias - vetores e matrizes

Carateres e strings

 

Horário

Algoritmos e Estruturas de Dados

 

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

 

 

 

 

TE

6.18

PL

6.19

 

 

15

   

 

 

TE

6.18

PL

6.19

 

 

16

 

 

 

 

 

 

 

 

 

 

17

 

 

 

 

 

 

 

 

 

 

18