Objectivos para o Exame (Época Normal e de Recurso)
Aqui fica uma lista de objectivos para o Exame de DAA.
Podem ver um exame modelo.
Os objectivos marcados com asterisco (*) são de valorização, ou seja, vocacionados para estudantes que queiram ter uma nota acima de 16.
Análise Assintótica
Notação
- Conhecer a notação assintótica (O, Ω e Θ) e o seu significado formal
- Saber comparar funções usando esta notação
- Saber justificar o porquê da relação ser O, Ω ou Θ
- Saber o que significa análise do pior caso e caso médio.
- Conhecer as classes habituais de complexidade (linear, logarítmica, linearítmica, etc)
Análise da Complexidade de um Programa
- Saber analisar o custo temporal de um programa simples com ciclos e sem recursão
- Saber resolver somatórios simples para concretizar o tempo de um ciclo
- Saber analisar uma recursão simples (que use a ideia de dividir para conquistar), escrevendo a recorrência e a árvore de recorrência (*).
Previsão e Comparação
- Saber prever e comparar o tempo de execução de um algoritmo quando: (i) já se sabe quanto tempo demora para um tamanho de input pequeno; (ii) ainda antes de começar a implementar qualquer algoritmo
Ordenação
Conceitos
- Conhecer o problema de ordenação e saber a diferença entre algoritmos comparativos e não comparativos.
- Saber qual o limite para um algoritmo de ordenação comparativo (n log n) e saber porque tal limite não se aplica num algoritmo não comparativo.
- Conhecer algumas aplicações da ordenação (ex: calcular frequência, selecionar k-ésimo número, unir conjuntos, descobrir anagramas).
- Conhecer a definição de ordenação estável (stable sort).
Algoritmos
- Conhecer com algum detalhe o funcionamento do MergeSort.
- Conhecer as principais ideias do algoritmos comparativos do BubbleSort, InsertionSort, SelectionSort e QuickSort.
- Conhecer as principais ideias dos algoritmos não comparativos CountingSort e RadixSort.
Pesquisa Binária
- Conhecer e perceber o conceito de pesquisa binária
- Conhecer e perceber a generalização para o caso de sim/não.
- Conhecer e perceber o método da bisseção
- Saber escrever/completar código/pseudo-código para uma pesquisa binária simples, sim/não ou com bisseção
Algoritmos Greedy
- Conhecer e perceber o conceito de algoritmos greedy, subestrutura ótima e propriedade da escolha greedy
- Conhecer as ideias greedy dos problemas: troco, fractional knapsack, interval scheduling e cobertura mínima. Não é necessário conhecer de cor os enunciados dos problemas, mas é conveniente perceber porque funcionam ou não as estratégias greedy dadas nas aulas.
- Saber descrever (matematicamente e/ou com código/pseudo-código) uma determinada escolha greedy
- Saber aplicar manualmente um algoritmo greedy para um dado input
- Saber encontrar contra-exemplos que provem que uma escolha greedy falha para alguns casos
- Saber provar que uma escolha greedy irá dar sempre resultado correcto. (*)
Programação Dinâmica
- Conhecer e perceber o conceito de programação dinâmica (PD), subestrutura ótima, problemas coincidentes.
- Compreender as estratégias bottom-up e top-down (memoization) para PD.
- Conhecer as ideias de PD dos problemas: pirâmide de números, subsequência crescente, obras na estrada e jogo de pedras. Não é necessário conhecer de cor os enunciados dos problemas, mas é conveniente perceber como funcionam as estratégias de PD dadas nas aulas.
- Saber descrever (matematicamente e/ou com código/pseudo-código) um algoritmo de PD.
- Saber aplicar manualmente um algoritmo com PD para um dado input.
- Compreender a PD do problema da distância de edição. (*)
Árvores Binárias de Pesquisa Equilibradas
Conceitos e aplicações
- Conhecer o conceito de árvores binárias de pesquisa, incluindo procuras, inserções e remoções
- Perceber em que tipo de casos a árvore pode ficar desiquilibrada
- Conhecer algumas aplicações possíveis de árvores binárias de pesquisa
Árvores AVL
- Conhecer o conceito de árvores AVL, suas invariantes, pior caso e altura
- Perceber e saber aplicar o conceito de uma rotação simples
- Compreender os desníveis provocados por inserções/remoções e como podem ser corrigidos com rotações
- Conhecer algumas vantagens e desvantagens de árvores AVL
Árvores Red-Black
- Conhecer o conceito de árvores Red-Black, suas invariantes, pior caso e altura
- Compreender os desníveis provocados por inserções e como podem ser corrigidos
- Conhecer algumas vantagens e desvantagens de árvores Red-Black
Grafos: Conceitos
Introdução e Terminologia
- Saber o que é um grafo (nós/vértices e ligações/arestas/arcos)
- Saber dar exemplos de um grafo e o que representam os vértices e as arestas
- Conhecer a terminologia habitual: grafo dirigido e não dirigido, grau de um nó (de entrada e de saída), nó adjacente, lacete, multigrafo, grafo denso ou esparso, caminho (e custo), ciclo, grafo acíclico, distância entre dois pontos, diâmetro de um grafo, componente conexas, subgrafos, cliques, triângulos, árvores e florestas.
Representação de Grafos
- Conhecer as estruturas de dados Matriz e Lista de Adjacências e saber como elas representam um grafo.
- Saber como implementá-las em código.
- Conhecer as vantagens e desvantagens de cada uma destas estruturas de dados.
Grafos: Pesquisas em Profundidade e em Largura
Conceitos
- Saber o que é uma pesquisa em profundidade (DFS) e uma pesquisa em largura (BFS).
- Dado um grafo, saber por qual ordem os nós são percorridos com DFS ou com BFS.
- Ser capaz de produzir e/ou completar código/pseudo-código para uma DFS e para uma BFS.
Aplicações Simples de DFS
- Saber como descobrir componentes conexas num grafo.
- Saber o que é uma ordenação topológia e como usar DFS para calcular.
- Saber o que é um ciclo e como usar DFS para calcular.
Aplicações Mais avançadas de DFS
- Conhecer e compreender o conceito de árvore de pesquisa de DFS
- Saber classificar as arestas numa visita por DFS: tree, back, forward e cross edges.
- Saber o que são componentes fortemente conexos.
- Conhecer e compreender o algoritmo de Tarjan para descobrir componentes fortemente conexos (*)
- Saber o que são pontos de articulação e pontes.
- Conhecer e compreender um algoritmo linear com DFS para descobrir pontos de articulação (*)
Aplicações de BFS
- Perceber como a BFS pode ser usada para calcular distâncias mínimas em grafos não pesados.
Grafos: Distâncias mínimas
- Saber o que são os problemas SSSP (single-source shortest path problem) e APSP (all-pairs shortest path problem )
- Conhecer e compreender o algoritmo de Dijkstra, sendo capaz de o aplicar manualmente num grafo.
- Conhecer e compreender o algoritmo de Bellman-Ford, sendo capaz de o aplicar manualmente num grafo.
- Conhecer e compreender o algoritmo de Floyd-Warshall, sendo capaz de o aplicar manualmente num grafo.
- Ser capaz de produzir e/ou completar código/pseudo-código para qualquer um dos 3 algoritmos anteriores.
Grafos: Árvores de Suporte de Custo Mínimo
- Conhecer e perceber o conceito de árvore de suporte de custo mínimo.
- Conhecer e perceber o algoritmo de Prim, sendo capaz de o aplicar manualmente num grafo.
- Conhecer e perceber o algoritmo de Kruskal, sendo capaz de o aplicar manualmente num grafo.
- Ser capaz de produzir e/ou completar código/pseudo-código para qualquer um dos 2 algoritmos anteriores.
- Saber o que é uma heap, como funciona, e de que modo poderia melhorar o algoritmo de Prim.
- Saber o que é uma estrutura de dados para Union-Find, como funciona, e como poderia melhorar o algoritmo de Kruskal. (*)
Grafos: Fluxo Máximos
- Conhecer o conceitos de grafo de fluxos e de fluxo máximo grafo residual.
- Conhecer e compreender o método de Ford-Fulkerson e a sua implementação com DFS e BFS (Edmonds-Karp).
- Saber manualmente aplicar uma descoberta de fluxo máximo, descobrindo caminhos de aumento e produzindo os respectivos grafos residuais.
- Conhecer algumas das aplicações de Fluxo Máximo (*)
)