Vídeos das Aulas Teóricas e de outro temas
Para usufruto dos alunos estão aqui os vídeos usados para as aulas teóricas das edições anteriores que foram dadas remotamente por causa da pandemia.
 | Playlist com todos os vídeos |
| #01 - Introdução ao Java: história e um primeiro programa (43m03s) | |
| Slides incluídos: 1 a 8 | |
 |
Introdução ao Java: contexto histórico; versões; vantagems: portabilidade, segurança e ferramentas; live-coding de um primeiro programa; uso da shell e emacs; chavetas e comentários. |
| #02 - Variáveis e operadores; instruções condicionais e de ciclo (1h23m33s) | |
| Slides incluídos: 9 a 28 | |
 |
Tipos de dados: limites, operadores, identificadores, âmbito, conversões e precedências; Instruções de controlo de fluxo: condicionais (if, operador ternário) e de ciclo (while, for, do-while, break, continue). |
| #03 - Classes e Programação Orientada a Objectos (53m49s) | |
| Slides incluídos: 29 a 38 | |
 |
Fundamentos de programação orientada a objectos; conceitos e terminologia: classes, referências, objectos, métodos construtores, atributos; operadores new e ponto; variáveis e métodos estáticos; exemplos de classes e conceitos associados com livecoding. |
| #04 - API do Java: Strings, Arrays, I/O (1h22m38s) | |
| Slides incluídos: 39 a 61 | |
 |
API do Java e documentação; classe String e seu métodos principais; uso de arrays; conceito de package; package utilitário Arrays, I/O em Java e a classe System; classe Scanner e seus métodos principais; escrita formatada com printf; regras de etiqueta nos nomes de métodos e atributos. |
| #05 - Programação Estruturada (1h24m06s) | |
| Slides incluídos: 1 a 12 | |
 |
Regras metodológicas para resolução de problemas; conceitos de programação estruturada; exemplo de boas práticas com a implementação da resolução de um problema relacionado com um jogo do galo generalizado. |
| #06 - TADs e Princípios de Programação Orientada a Objectos (1h13m20s) | |
| Slides incluídos: 1 a 14 | |
 |
Princípios de Programação Orientada a Objectos: abstração, encapsulamento, modularidade; conceito de Tipo de Abstracto de Dados (TAD); TAD vector: conceito, operações e sua implementação; palavras-chave "this" e "private"; override do método "toString". |
| #07 - Interfaces e TAD Conjunto (1h29m41s) | |
| Slides incluídos: 15 a 34 | |
 |
Conceito e uso de interfaces; TAD Conjunto: conceito, definição e APIs e possíveis implementações; TAD Conjunto como lista num array: implementação com "live coding" e análise de vantagens e desvantagens; geração de excepções customizadas: TAD Conjunto como array de booleanos: vantagens e desvantagens. |
| #08 - Genéricos e Herança (1h09m36s) | |
| Slides incluídos: 35 a 55 | |
 |
Conceito de genéricos; implementação exemplo de um par genérico; "boxing" e "unboxing" automáticos; herança: conceito, palavras-chave "extends" e "super", subclasses e acesso a atributos e métodos, override; classes e métodos abstractos; exemplo de uso de heranças para implementa progressões. |
| #09 - Listas Ligadas Simples (1h21m54s) | |
| Slides incluídos: 1 a 17 | |
 |
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. |
| #10 - Listas Ligadas Circulares e Listas Duplamentes Ligadas (55m01s) | |
| Slides incluídos: 18 a 38 | |
 |
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". |
| #11 - Pilhas, Filas e Deques (58m19s) | |
| Slides incluídos: 35 a 55 | |
 |
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. |
| #12 - Resolução de Exercícios de Listas (1h22m24s) | |
| (livecoding) | |
 |
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). |
| #13 - Padrões Geométricos (1h33m05s) | |
| (livecoding) | |
 |
Explicação e implementação com "live coding" do problema de desafio "[ED249] Padrões Geométricos". |
| #14 - Fundamentos de Correção e Eficiência Algorítmica (1h04m23s) | |
| Slides incluídos: 1 a 22 | |
 |
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. |
| #15 - Análise Assintótica (1h05m47s) | |
| Slides incluídos: 23 a 40 | |
 |
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. |
| #16 - Complexidade de programas: ciclos e recursão (57m06s) | |
| Slides incluídos: 41 a 64 | |
 |
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). |
| #17 - Recursividade (1h24m12s) | |
| Slides incluídos: 1 a 19 | |
 |
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. |
| #18 - Árvores Binárias: Conceito e Implementação (1h08m22s) | |
| Slides incluídos: 1 a 16 | |
 |
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. |
| #19 - Árvores Binárias: Pesquisas em Profundidade e Largura (1h16m45s) | |
| Slides incluídos: 17 a 33 | |
 |
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. |
| #20 - Árvores Binárias de Pesquisa (1h27m04s) | |
| Slides incluídos: 34 a 71 | |
 |
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 |
| #21 - Árvores Binárias: Dicionários (57m03s) | |
| Slides incluídos: 72 a 82 | |
 |
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. |
| #22 - Resolução de Exercícios com Árvores Binárias (1h05m30s) | |
| (livecoding) | |
 |
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 - Filas de Prioridade e Heaps (1h14m10s) | |
| Slides incluídos: 1 a 30 | |
 |
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. |
| #24 - Resolução do Exame Modelo (1h38m48s) | |
| Exame Modelo | |
 |
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. |