[27-04-2025]
Encontram-se disponíveis as classificações obtidas no mini-teste prático 1 em "Classificações". A senha de acesso é fornecida através do Moodle.
Encontra-se também disponível possíveis resoluções dos vários enunciados do mini-teste prático 1, junto às classificações.
As classificações obtidas no teste escrito 1 (frequência 1) serão publicadas durante a próxima semana.
Quaisquer esclarecimentos sobre as classificações obtidas no mini-teste prático 1 e no teste escrito 1 serão dados no período de 5 a 7 de maio.
Objetivos e resultados da aprendizagem
Os objetivos principais desta UC prendem-se com a compreensão por parte dos alunos de estruturas de dados complexas e algoritmia avançada na resolução de problemas computacionais. Os alunos deverão compreender e assimilar:
- As estruturas de dadas mais avançadas relacionadas com árvores balanceadas e não balanceadas, grafos dirigidas e não dirigias, grafos densos e esparsos, processamento de strings.
- Como selecionar as estruturas de dados apropriadas à resolução de problemas práticos.
- Como selecionar os algoritmos apropriados às estruturas de dados definidas.
- Desenvolver competências na utilização de técnicas matemáticas de análise da complexidade computacional espacial e temporal de algoritmos.
No final desta unidade curricular o estudante deve ser capaz de
- Explicar a necessidade de eficiência por parte dos algoritmos e estruturas de dados.
- Analisar a complexidade computacional (temporal e espacial) de programas.
- Implementar programas que utilizam os algoritmos e estruturas estudadas.
A linguagem C será usada na componente prática da disciplina, apesar dos conceitos nela envolvidos serem independentes da linguagem.
COMPLEXIDADE COMPUTACIONAL DOS ALGORITMOS
1. Algoritmos
2. Análise de Complexidade dos Algoritmos: Big-O
3. Análise Amortizada de Algoritmos
ESTRUTURAS ABSTRATAS DE DADOS
1. Conceitos Gerais
2. Lista Ligada (com ligações simples)
3. Pilha
4. Fila
5. Árvore Binária
6. Árvore Binária de Pesquisa
ÁRVORES BINÁRIAS DE PESQUISA BALANCEADAS
1. Inserção Binária
2. Adelson-Velskii Landis (AVL)
OUTRAS ÁRVORES DE PESQUISA BALANCEADAS
1. Vermelho-Preto (Red-Black)
2. Árvore 2-3
3. Árvore de Intervalos
FILAS DE PRIORIDADE (HEAPS)
1. Heaps
2. Heap Binário
3. Heap Binomial
4. Heap de Fibonacci
GRAFOS
1. Conceitos Gerais
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 (de um nó para todos) e Floyd-Warshall (entre todos os pares de nós)
4.3. Fluxo Máximo: Ford-Fulkerson
4.4. Emparelhamento Estável ("Stable Matching Problem"): Gale–Shapley
STRINGS
1. Conjuntos de Strings
2. Ordenação de Strings: Ordenação por Radix
3. Pesquisa de Strings: Pesquisa Binária
4. Pesquisa de uma Substring numa String: Knuth-Morris-Pratt e Boyer-Moore
5. Prefix Tree (Trie), Suffix Tree e Suffix Arrays
"Competitive Programmer’s Handbook"
Antti Laaksonen
Draft July 3, 2018
"Algorithms", 4th Edition, 2011
Robert Sedgewick and Kevin Wayne
Addison Wesley, ISBN-13: 978-0321573513
"Introduction to Algorithms", 3rd Edition, 2009
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
MIT Press, ISBN-13: 978-0262033848
"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 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
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
Tipo
Data
Hora
Salas
Teste escrito 1
07/04/2025
18 h
6.05 - 6.06 - 6.26
Teste escrito 2
26/05/2025
18 h
6.05 - 6.06 - 6.26
Mini-teste prático 1
24-27/03/2025
Aula PL
Aula PL
Mini-teste prático 2
05-08/05/2025
Aula PL
Aula PL
Testes do ano letivo de 2023/2024
Exame de Época Normal ## Resolução (sugestão)
Classificações obtidas nas avaliações
Ano letivo 2024/2025 (necessita de senha de acesso - fornecida através do Moodle)
Mini-Testes Práticos ## Resolução (sugestão)
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 Recurso (Teste escrito + Mini-testes práticos) ## Resolução (sugestão)
INTRODUÇÃO
1. Estruturas
2. Apontadores
COMPLEXIDADE COMPUTACIONAL DOS ALGORITMOS
1. Algoritmos
2. Análise de Complexidade dos Algoritmos: Big-O
3. Análise Amortizada de Algoritmos
ESTRUTURAS ABSTRATAS DE DADOS
2. Lista Ligada (com ligações simples)
3. Pilha
4. Fila
ÁRVORES BINÁRIAS DE PESQUISA BALANCEADAS
2. Adelson-Velskii Landis (AVL)
OUTRAS ÁRVORES DE PESQUISA BALANCEADAS
2. Árvore 2-3
FILAS DE PRIORIDADE (HEAPS)
1. Heaps
2. Heap Binário
GRAFOS
2. Representação Computacional (estrutura de dados) de um Grafo
3. Algoritmos de Pesquisa em Grafos
4. Problemas Envolvendo Grafos
Folha - Introdução
Folha - Complexidade Computacional dos Algoritmos
Folha - Listas Ligadas (com ligações simples)
Folha - Pilhas e Filas
Folha - Árvores Binárias
Folha - Árvores Binárias de Pesquisa
Folha - Árvores Binárias de Pesquisa Balanceadas
Folha - Heaps (Filas de Prioridade)
Folha - Outras Árvores de Pesquisa Balanceadas
Folha - Grafos
Folha - Strings
Compiladores de C
DEV-C++ (versão 5.11) - para Windows
TUTORIALSPOINT (online)
CODECHEF (online)
ONLINEGDB (online)
Algoritmos de Ordenação e de Pesquisa em arrays 1D
Algoritmos de ordenação em listas manipuladas com arrays 1D
Algoritmos de pesquisa em listas manipuladas com arrays 1D
Visualização de Estruturas de Dados e Algoritmos usando Animação
Bibliotecas e Exercícios das folhas práticas
Gerar Números Aleatórios
Listas ligadas simples (exercícios da folha prática - grupo A)
EADLista.h ---> operações básicas sobre a Estrutura Abstrata de Dados Lista
OperacoesBasicasExA.h ---> operações básicas sobre a estrutura de dados do exercício do grupo A
OperacoesExA.h ---> operações a implementar relativas aos exercícios a resolver do grupo A
MainListasExA.c ---> programa prinicipal asociado aos exercícios do grupo A
Pilhas e Filas (grupo A - EAD Pilha)
EADPilha.h ---> operações básicas sobre a Estrutura Abstrata de Dados Pilha
OperacoesBasicasPilhasExA.h ---> operações básicas sobre a estrutura de dados do exercício do grupo A
OperacoesPilhasExA.h ---> operações a implementar relativas aos exercícios a resolver do grupo A
MainPilhasExA.c ---> programa prinicipal asociado aos exercícios do grupo A
Pilhas e Filas (grupo B - EAD Fila)
EADFila.h ---> operações básicas sobre a Estrutura Abstrata de Dados Fila
OperacoesBasicasFilasExB.h ---> operações básicas sobre a estrutura de dados do exercício do grupo B
OperacoesFilasExB.h ---> operações a implementar relativas aos exercícios a resolver do grupo B
MainFilasExB.c ---> programa prinicipal asociado aos exercícios do grupo B
Pilhas e Filas (grupo D - EAD Fila + EAD Pilha)
EADFila.h ---> operações básicas sobre a Estrutura Abstrata de Dados Fila
OperacoesBasicasFilasExD.h ---> operações básicas sobre a estrutura de dados do exercício do grupo D
EADPilha.h ---> operações básicas sobre a Estrutura Abstrata de Dados Pilha
OperacoesBasicasPilhasExD.h ---> operações básicas sobre a estrutura de dados do exercício do grupo D
OperacoesFilasPilhasExD.h ---> operações a implementar relativas aos exercícios a resolver do grupo D
MainFilasPilhasExD.c ---> programa prinicipal asociado aos exercícios do grupo D
Árvores Binárias
Aleatorio.h ==> gerar números aleatórios
==> operações básicas sobre a Estrutura Abstrata de Dados Árvore Binária ==> operações básicas sobre a estrutura de dados dos exercícios propostos ==> operações associadas aos exercícios propostos ==> programa prinicipalMostrar por níveis (adaptada ao exercício da folha prática)
==> operação para mostrar por níveis uma Árvore Binária ==> operações básicas sobre a Estrutura Abstrata de Dados FilaÁrvores Binárias de Pesquisa
Aleatorio.h ==> gerar números aleatórios
==> operações básicas sobre a Estrutura Abstrata de Dados Árvore Binária de Pesquisa ==> operações básicas sobre a estrutura de dados dos exercícios propostos ==> operações associadas aos exercícios propostos ==> programa prinicipalMostrar por níveis (adaptada ao exercício da folha prática)
==> operação para mostrar por níveis uma Árvore Binária ==> operações básicas sobre a Estrutura Abstrata de Dados FilaÁrvores Binárias de Pesquisa Balanceadas (exercícios da folha prática)
A. Inserção Binária
==> operações básicas sobre a Estrutura Abstrata de Dados Árvore Binária de Pesquisa ==> operações básicas sobre a estrutura de dados dos exercícios sobre ABP (Inserção Binária) ==> operações associadas ao método de Inserção Binária ==> programa prinicipalMostrar por níveis (adaptada ao exercício da folha prática)
==> operação para mostrar por níveis uma Árvore Binária de Pesquisa ==> operações básicas sobre a Estrutura Abstrata de Dados FilaB. Árvore de Adelson-Velskii Landis (AVL)
==> operações básicas sobre a Estrutura Abstrata de Dados Árvore Binária de Pesquisa do tipo AVL ==> operações básicas sobre a estrutura de dados dos exercícios sobre AVL ==> programa prinicipalMostrar por níveis (adaptada ao exercício da folha prática)
==> operação para mostrar por níveis uma AVL ==> operações básicas sobre a Estrutura Abstrata de Dados Fila
Realização Mini-testes Práticos
Plataforma de Avaliação
Acesso através de outros computadores
- Terça-feira, 14h - 16h (Gabinete 4.2)
- Quarta-feira, 9h - 11h (Gabinete 4.2)
- Outro horário (sujeito a marcação com o docente), podendo ser presencial ou através do ZOOM
Horas
Segunda
Sala
Terça
Sala
Quarta
Sala
Quinta
Sala
Sexta
Sala
8
9
PL4
FM
1209
10
PL1
FM
1209
PL4
11
PL1
12
13
14
TE
6.03
15
TE
16
PL2
6.14
PL3
FM
1209
17
PL2
PL3
18
FM 1209 -- Fábrica do Moço (Bloco 12), Sala 12.09