Algoritmos e Estruturas de Dados
Correção, análise de custos, estruturas de dados e algoritmos em C++17.
Encontrar um máximo, retirar o pedido mais antigo e visitar as cidades alcançáveis exigem operações diferentes. AED estuda como provar esses algoritmos e escolher representações com custos adequados à dimensão da entrada. Os exemplos usam C++17, por isso precisas de funções, classes, referências, apontadores e memória dinâmica de Programação.
Se a sintaxe dos vetores ou das referências ainda te prende, começa pelos fundamentos de C++ para AED. Depois segue o percurso pela ordem, porque cada capítulo usa os contratos e as contagens dos anteriores. O programa atual é o de 2026/27. Os materiais posteriores de 2025/26 servem para ver profundidade e tipos de exercícios, e as provas de janeiro de 2025 e 2026 para tipos de raciocínio; nenhum deles confirma as regras de avaliação atuais.
Percurso
- Correção e complexidade: contratos, invariantes, somas, recorrências e custos amortizados.
- Pesquisa e ordenação: intervalos, repetidos, pesquisa da resposta, estabilidade e limites do modelo de comparação.
- Tipos abstratos e estruturas lineares: escolher a representação, manter ligações e analisar sequências de operações.
- Envolvente convexa: orientação geométrica, Graham e a escolha entre pilha e lista circular.
- Árvores binárias, árvores de pesquisa e equilíbrio: percursos, remoções, AVL e vermelho-pretas.
- DFS e BFS e aplicações em grafos: caminhos mínimos sem pesos, ciclos, ordem topológica, componentes fortes, pontes e articulações.
- Dispersão e heaps: acesso por chave ou prioridade, colisões e construção linear.
Cada capítulo termina com exercícios que pedem uma decisão, um traço ou uma justificação. Tenta resolver antes de abrir as pistas. A Cheat sheet reúne condições e custos para revisão; as provas e os exemplos ficam nos capítulos.
Trabalho prático
Começa por uma entrada pequena e escreve o estado depois de cada operação. Declara os casos vazios, a política de duplicados e as convenções de índices e altura. Depois programa, compila com avisos e compara com uma referência simples. Testa também uma entrada crescente, uma inversa, muitos iguais e os limites numéricos.
Nos grafos, testa vértices isolados, componentes desconexas e ciclos. Nas estruturas com nós, testa alterações da cabeça, da raiz e do último elemento. Antes de submeter no Mooshak, confirma o formato de entrada e saída e retira mensagens de depuração. Os programas destas páginas ensinam os algoritmos; não são soluções completas dos trabalhos da cadeira.
Avaliação de 2026/27
As aulas de introdução e a página de avaliação definem:
NP: soma das notas de dois testes práticos de programação, cada um com 10 valores, total de 0 a 20.E: nota do exame escrito da época normal ou de recurso, de 0 a 20.- Classificação final ; aprovação com .
Por exemplo, E=12 e NP=16 dão 13,4 pela primeira ponderação e 13 pela segunda; é usada 13,4. Os testes práticos de 2026/27 não podem ser repetidos. Para primeira inscrição nesse ano, a melhoria incide na componente de exame.
Para obter frequência, não podes exceder 25% de faltas às aulas teórico-práticas. Quem cumpriu a assiduidade no ano anterior tem dispensa, embora a frequência das aulas seja aconselhada. Quem não aprovou em 2025/26 e realizou a componente prática pode pedir para conservar essa nota, informando os regentes no início do ano. As condições de melhoria de notas práticas de estudantes já aprovados exigem contacto com os regentes. Consulta a ficha e os anúncios da tua edição para datas e situações individuais.
Fontes e âmbito
O programa de referência é a ficha preenchida de AED da LEIC, ocorrência 586989, 2026/27. As ferramentas indicadas são GCC com C++17, VSCode e Mooshak.
A base docente é a página pública de Ana Paula Tomás e Pedro Ribeiro, 2026/27. Em 2 de outubro de 2026 estavam disponíveis quatro apresentações, da introdução à pesquisa, e as duas primeiras aulas práticas. Para os tópicos posteriores, o percurso foi cruzado com as quinze apresentações e as fichas práticas públicas de 2025/26, mantendo o âmbito confirmado no programa atual. O exame-modelo público de 2024/25 ajudou a identificar tipos de raciocínio; as questões destas páginas usam exemplos próprios, exceto as adaptações docentes identificadas nos seus metadados.
Foram também consultados enunciados e uma resolução disponibilizados como contribuições na página de AED do Accio: o exame de 17 de janeiro de 2025, com cabeçalho 2024/25, e o de 13 de janeiro de 2026, com cabeçalho 2025/26. Estes materiais permitiram completar a prática de invariantes de janelas, manipulação de listas por ligações, propriedades recursivas de árvores e contagens em grafos. O alojamento de uma cópia não comprova a autoria de uma resolução; os resultados e custos usados aqui foram conferidos de forma independente. O Moodle de 2025/26 e restantes materiais protegidos continuam sem acesso confirmado. Os Resumos AED de SofiaViP são um suplemento histórico de estudante, sem uma edição atual identificada.
A bibliografia obrigatória indicada na ficha é:
- Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, ISBN 0-201-36122-1.
- Robert Sedgewick, Algorithms in C++, ISBN 0-201-35088-2.
- Thomas H. Cormen e coautores, Introduction to Algorithms, 3.ª ou 4.ª edição; a ficha indica ISBN 978-0-262-53305-8.
Para contratos da biblioteca, foram consultadas as secções do projeto público do padrão C++ sobre operações em listas, ordenação, pesquisa binária, invalidação em vetores, containers associativos ordenados e containers não ordenados. Esse projeto acompanha a evolução da linguagem; os programas publicados usam apenas C++17.