Vídeos das Aulas Teóricas e de outro temas
Antes do dia 13 de Março, todas as aulas teóricas foram presenciais. A partir daí, passaram a ser vídeo pré-gravado por cada aula teórica prevista (a data do vídeo refere-se à data onde a aula seria dada se fosse presencial):
 |
#25 (29/05) - Revisões/Recuperação IV |
| Apresentação e resolução do exame modelo, com passagem pelos vários grupos de perguntas: fundamentos de java; implementação de uma classe simples; tipos abstratos de dados; complexidade algorítmica; listas, pilhas e filas; árvores; árvores binárias de pesquisa; filas de prioridade e heaps |
 |
#24 (26/05) - Revisões/Recuperação III |
| Implementação com "live coding" (e explicações) de várias implementações possíveis de 7 problemas de árvores binárias. Nomeadamente, são resolvidos os problems [ED204] Contando folhas, [ED205] Árvores estritamente binárias, [ED206] Percorrendo caminhos, [ED207] Nós profundos, [ED211] Contando os números pares, [ED212] Soma de todos os níveis e [ED213] Caminho de maior soma. |
 |
#23 (22/05) - Filas de Prioridade e Heaps |
| Motivação, conceito e API de fila de prioridade; custos de implementações naive; conceito e invariantes de heap; correspondência entre um array e heap implícita; implementação de heaps usando arrays; exemplos de uso de heaps com diferentes tipos e comparadores. |
 |
#22 (19/05) - Árvores Binárias IV |
| Motivação, conceito e API de dicionário/mapa/array associativo; implementação de dicionário usando uma árvore binária de pesquisa; aplicação de mapas para contagem de nomes; API do Java para conjuntos e dicionários. |
 |
#21 (15/05) - Árvores Binárias III |
| Conceito de objectos comparáveis e motivação para árvores binárias de pesquisa (BSTs); conceito e propriedades de BSTs; métodos essenciais numa BST: inserir, remover e verificar se existe; visualização de BSTs; complexidade das operações numa BST e relação com altura e equilibrio das BSTs; noções de altura esperada para inserção aleatória; interface comparable; implementação de BSTs; uso de BST como conjunto e comparação com outras alternativas. |
 |
#20 (10/05) - Árvores Binárias II |
| Ordens de travessia de uma árvore: pesquisas em profundidade (DFS) e em largura (BFS); implementação de várias variantes de DFS: preorder, inorder e postorder; implementação de BFS usando filas; uso de pilhas explicitas para obter DFS; leitura de uma árvore e preorder; complexidade temporal dos métodos de árvores. |
 |
#19 (28/04) - Árvores Binárias I |
| Estruturas de dados não lineares; conceito e motivação para o uso de árvores; terminologia de árvores binárias; implementação de árvores binárias usando genéricos; implementação recursiva de alguns métodos: contar número de nós, calcular profundidade e descobrir se elemento existe na árvore. |
 |
#18 (24/04) - Recursividade |
| Recursividade: características principais, metodologias e erros comuns; implementação de várias versões recursivas para o cálculo do máximo; implementação do mergesort; implementação de "flood fill", implementação de geração de subconjuntos; implementação da geração de permutações. |
 |
#17 (21/04) - Complexidade Algorítmica III |
| Análise de ciclos (e somatórios); progressões aritméticas; intuições sobre complexidade de ciclos; análise de funções recursivas (e recorrências); a estratégia de dividir para conquistar; estudo detalhado do algoritmo do mergesort e sua árvore de recorências; outras recorrência (máximo com dividir para conquistar ou tail recursion; pesquisa binária). |
 |
#16 (17/04) - Complexidade Algorítmica II |
| Tipos de análise: pior caso e caso médio; Fundamentos de análise assintótica: conceito de taxa de crescimento e notação O, Ω Θ; funções mais comuns: nomes e exemplos de algoritmos; previsão do tempo de execução de um algoritmo; alguns exemplos e regras práticas. |
 |
#15 (14/04) - Complexidade Algorítmica I |
| Conceitos de algoritmo, instância, correcção e eficiência temporal ou espacial; o problema do caixeiro-viajante (TSP): algumas possíveis heurísticas não optimais e uma solução correta gerando testando todas as hipóteses; estimativas de tempo necessário num computador atual; o modelo de Random Access Machine (RAM) para contagem de operações simples num programa. |
 |
#14 (03/04) - Revisões/Recuperação II |
| Explicação e implementação com "live coding" do problema de desafio "[ONI_PG] Padrões Geométricos". |
 |
#13 (31/03) - Revisões/Recuperação I |
| Implementação com "live coding" (e explicações) de 6 problemas de listas ligadas simples. Nomeadamente, são resolvidos os problems ED188 (get), ED189 (remove), ED190 (copy), ED191 (duplicate), ED192 (count) e ED193 (removeAll). |
 |
#12 (27/03) - Listas Ligadas III |
| TAD Pilha (stack): operações fundamentais (push e pop) e implementação com listas ligadas; TAD Fila (queue): operações fundamentais (enqueue e dequeue) e implementação com listas ligadas; TAD deque (double ended queue); TADs sequenciais na API do Java; interface Iterable e uso da instrução de ciclo simplificada do tipo foreach. |
 |
#11 (24/03) - Listas Ligadas II |
| Motivação para listas circulares; escalonamento "round-robin"; implementação de listas circulares; motivação para listas duplamente ligadas; implementação de listas duplamente ligadas; conceito de "sentinelas". |
 |
#10 (20/03) - Listas Ligadas I |
| Estruturas de dados sequenciais; vantagens e desvantagens de arrays; conceito de listas ligadas; implementação de listas ligadas: classes para um nó e para uma lista, adicionar, remover e aceder a elementos, imprimir conteúdo. |
 |
#09 (17/03) - Tipos Abstractos de Dados III |
| TAD Conjunto como um array de booleanos; implementações de conjuntos da API do Java (TreeSet e HashSet); genéricos; wrappers; auto boxing/unboxing; mecanismo de herança; override. |
 |
#08 (13/03) - Tipos Abstractos de Dados II |
| Modo de funcionamento das aulas não presenciais; TAD conjunto, conceito de interface; implementação de um conjunto como lista num array; geração de erros customizados; vantangens e desvantagens da implementação mostrada. |
Don't Submit Now ("hino" de Estruturas de Dados)