Informações

[dd-mm-2026]

--

Objetivos e resultados da aprendizagem

Os objetivos principais desta UC prendem-se com a aprendizagem de conhecimentos sobre algoritmia e estruturas de dados na resolução de problemas computacionais.

Esta unidade curricular tem como objetivos adquirir conhecimentos sobre:

- algoritmia, em particular algoritmos de ordenação e de pesquisa, e de análise de complexidade dos algoritmos,

- estruturas de dados de acesso sequencial, como listas, pilhas e filas,

- estruturas de dados de acesso não sequencial, como árvores não balanceadas e balanceadas, heaps e grafos,

- como selecionar as estruturas de dados apropriadas à resolução de problemas práticos,

- como selecionar os algoritmos apropriados às estruturas de dados definidas.

Após a conclusão da UC, os estudantes deverão ser capazes de:

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

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

- explicar a necessidade de eficiência por parte dos algoritmos e das estruturas de dados,

- implementar programas que utilizam os algoritmos e as estruturas estudadas.

A linguagem C será usada na componente prática da disciplina, apesar dos conceitos nela envolvidos serem independentes da linguagem.

Programa detalhado

Algoritmos

1. Algoritmos

2. Análise de Complexidade dos Algoritmos: Big-O

3. Análise Amortizada de Algoritmos

4. Algoritmos de ordenação em arrays 1D (1 dimensão)

5. Algoritmos de pesquisa em arrays 1D (1 dimensão)

Estruturas Abstratas de Dados

1. Conceitos Gerais

2. Estruturas de acesso sequencial

2.1. Listas Ligadas com ligações simples

2.2. Listas Ligadas com ligações duplas

2.3. Pilhas

2.4. Filas

3. Estruturas de acesso não sequencial

3.1. Árvores Binárias

3.2. Árvores Binárias de Pesquisa

3.2. Árvores N-árias

Árvores de Pesquisa Balanceadas

1. Árvores Binárias

1.1. Adelson-Velskii Landis (AVL)

1.2. Vermelho-Preto (Red-Black)

1.3. Árvore de Intervalos

2. Árvores 2-3

Filas de Prioridade (Heaps)

1. Heap

2. Heap Binário

3. Heap Binomial

Grafos

1. Tipos de grafos

2. Representação Computacional (estrutura de dados) de um grafo

3. Algoritmos de Pesquisa em Grafos

3.1. Pesquisa em Largura Primeiro

3.2. Pesquisa em Profundidade Primeiro

4. Problemas envolvendo grafos

4.1. Árvore Abrangente Mínima: Prim

4.2. Caminho Mais Curto: Dijkstra

4.3. Fluxo Máximo: Ford-Fulkerson

4.4. Emparelhamento Estável ("Stable Matching Problem"): Gale-Shapley

Bibliografia

"Estruturas de Dados e Algoritmos em C", 2008

António Manuel Adrego da Rocha.

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

ISBN: 9789727222957

"Algorithms", 4th Edition, 2011

Robert Sedgewick and Kevin Wayne.

Addison Wesley.

ISBN-13: 978-0321573513

"Linguagem C", 25ª Edição Atualizada e Aumentada, 2025

Luís Damas

FCA-Editora de Informática.

ISBN: 978-972-722-945-1

"Competitive Programmer’s Handbook"

Antti Laaksonen

Draft July 3, 2018

"Introduction to Algorithms", 3rd Edition, 2009

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

MIT Press, ISBN-13: 978-0262033848

"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

Department of Computer Science, Virginia Tech

Critérios de avaliação

A avaliação no período de Aprendizagem consiste no seguinte:

- 2 mini-testes práticos (a realizar nas aulas práticas-laboratoriais): 4.0 valores (2.0 valores cada)

- 2 testes escritos (frequências): 16.0 valores (8.0 valores cada)

- assiduidade às aulas: 50%

Aprendizagem = Mini-testes práticos + Testes escritos

em que,

- Assiduidade às aulas inferior a 50% ==> 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 = Mini-testes práticos + Teste escrito

em que,

- Mini-testes práticos (realizados nas aulas práticas-laboratoriais): 4.0 valores

- Teste escrito: 16.0 valores

Datas das avaliações

Testes do ano letivo de 2024/2025

Frequência 1 »»» Resolução

Frequência 2 »»» Resolução

Exame de Época Normal »»» Resolução

Exame de Época de Recurso »»» Resolução

Classificações obtidas nas avaliações

Ano letivo 2025/2026 (necessita de senha de acesso - fornecida através do Moodle)

Mini-Testes Práticos

Frequência 1 (classificação em percentagem) »»» Resolução (sugestão)

Frequência 2 (classificação em percentagem) »»» Resolução (sugestão)

Aprendizagem (Mini-testes práticos + Frequências)

Exame de Época Normal (Teste escrito + Mini-testes práticos) »»» Resolução (sugestão)

Exame de Época de Recurso (Teste escrito + Mini-testes práticos) »»» Resolução (sugestão)

Apontamentos

Introdução

1. Estruturas

2. Apontadores

3. Gestão Dinâmica da Memória

4. Algoritmos Recursivos

Algoritmos

1. Algoritmos

2. Análise de Complexidade dos Algoritmos: Big-O

3. Análise Amortizada de Algoritmos

4. Algoritmos de ordenação em arrays 1D

5. Algoritmos de pesquisa em arrays 1D

Estruturas Abstratas de Dados

1. Conceitos Gerais

2. Estruturas de acesso sequencial

2.1. Listas Ligadas com ligações simples

2.2. Listas Ligadas com ligações duplas

2.3. Pilhas

2.4. Filas

3. Estruturas de acesso não sequencial

3.1. Árvores Binárias

3.2. Árvores Binárias de Pesquisa

Árvores de Pesquisa Balanceadas

1. Árvores Binárias de Pesquisa Balanceadas

1.1. Adelson-Velskii Landis (AVL)

1.2. Vermelho-Preto (Red-Black)

1.3. Árvore de Intervalos

2. Árvore de pesquisa 2-3

Filas de Prioridade (Heaps)

1. Heaps

2. Heap Binário

3. Heap Binomial

Grafos

1. Conceitos Gerais

2. Representação Computacional (estrutura de dados) de um Grafo

3. Algoritmos de Pesquisa em Grafos

4. Problemas Envolvendo Grafos

Folhas práticas

Introdução

Algoritmos

Listas Ligadas (com ligações simples e duplas)

Pilhas e Filas

Árvores Binárias

Árvores Binárias de Pesquisa

Árvores Binárias de Pesquisa Balanceadas

Heaps (Filas de Prioridade)

Grafos

Compiladores de C recomendados

DEV-C++ (para Windows)

CODE::BLOCKS »»» Manual em Português »»» Manual em Inglês

Visualização de Estruturas de Dados e Algoritmos usando Animação

DATA STRUCTURE VISUALIZATIONS (ORIGINAL)

DATA STRUCTURE VISUALIZATIONS (ATUAL)

Bibliotecas para resolver os exercícios das folhas práticas

(Clicar no nome da folha pretendida para aceder às respetivas bibliotecas)

Avaliação prática

Realização Mini-testes Práticos

Mini-Teste Prático

Plataforma de Avaliação

Acesso através de outros computadores

Horário de atendimento

- Segunda-feira, 16h - 18h (Gabinete 4.2)

- Terça-feira, 11h - 13h (Gabinete 4.2)

- Outro horário (sujeito a marcação com o docente), podendo ser presencial ou através do ZOOM

Horário da disciplina

FM 1208 : Fábrica do Moço (Bloco 12), Sala 12.08