Planificação
NOTA: irei muito brevemente atualizar esta parte do site e atualizá-la regularmente para ser mais fácil para todos perceber quais são as matérias que estão a ser lecionadas.
Calendário
Esta planificação serve para dar uma ideia resumida das aulas planeadas e/ou dadas:
- Teóricas:
- (T01) 11/02: Apresentação da UC; Introdução ao Java I
- (T02) 18/02: Introdução ao Java II
- (T03) 23/02: Introdução ao Java III
- (T04) 26/02: Introdução ao Java IV
- (T05) 02/03: Programação Estruturada
- (T06) 05/03: TADs I
- (T07) 09/03: TADs II
- (T08) 12/03: TADs III
- (T09) 16/03: Listas Ligadas I
- (T10) 19/03: Listas Ligadas II
- (T11) 23/03: Listas Ligadas II
- (T12) 26/03: Revisões I (live coding)
- (T13) 30/03: Revisões II (live coding)
- (T14) 06/04: Revisões III (apoio)
- (T15) 09/04: Complexidade Algorítmica I
- (T16) 04/05: Complexidade Algorítmica II
- (T17) 07/05: Complexidade Algorítmica III
- (T18) 11/05: Recursividade
- (T19) 14/05: Árvores Binárias I
- (T20) 18/05: Árvores Binárias II
- (T21) 21/05: Árvores Binárias III
- (T22) 25/05: Árvores Binárias IV
- (T23) 28/05: Revisões IV (live coding)
- (T24) 01/06: Filas de Prioridade e Heaps
- (T25) 04/06: Revisões V (preparação para o exame)
- Práticas laboratoriais:
- (PL01) 15/02 a 19/02: Introdução ao Java
- (PL02) 22/02 a 26/02: Input/Output e Mooshak
- (PL03) 01/03 a 05/03: Introdução a Classes
- (PL04) 08/03 a 12/03: Programação Estruturada
- (PL05) 15/03 a 19/03: Tipos Abstractos de Dados
- (PL06) 22/03 a 26/03: Listas Ligadas Simples
- (PL07) 29/03 a 02/04: Listas, Pilhas e Filas
- (PL08) 05/04 a 09/04: Consolidação de Conhecimentos (Listas, Pilhas e Filas)
- (PL09) 03/05 a 07/05: Revisões/Preparação para o 1º Teste Prático
- (PL10) 10/05 a 14/05: Complexidade Algorítmica
- (PL11) 17/05 a 21/05: Recursividade
- (PL12) 24/05 a 28/05: Árvores Binárias
- (PL13) 31/05 a 04/06: Árvores Binárias de Pesquisa, Conjuntos e Dicionários
- (PL14) [aula extra opcional]: Filas de Prioridade
Sumários
- Aula Teórica #01: 16/02/2021
- #01 - Apresentação da unidade curricular
Apresentação da unidade curricular: recursos, modelo de funcionamento das aulas práticas e teóricas; frequência e fórmula de cálculo de avaliação; estatísticas do passado e presente; bibliografia; efeito "super mario".
- #02 - Introdução ao Java: história e um primeiro programa
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.
- #01 - Apresentação da unidade curricular
- Aula Teórica #02: 19/02/2021
- #03 - Variáveis e operadores; instruções condicionais e de ciclo
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 - Variáveis e operadores; instruções condicionais e de ciclo
- Aula Teórica #03: 23/02/2021
- #04 - Classes e Programação Orientada a Objectos
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 - Classes e Programação Orientada a Objectos
- Aula Teórica #04: 26/02/2021
- #05 - API do Java: Strings, Arrays, I/O
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 Sacnner e seus métodos principais; escrita formatada com printf; regras de etiqueta nos nomes de métodos e atributos.
- #05 - API do Java: Strings, Arrays, I/O
- Aula Teórica #05: 02/03/2021
- #06 - Programação Estruturada
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 - Programação Estruturada
- Aula Teórica #06: 5/03/2021
- #07 - TADs e Princípios de Programação Orientada a Objectos
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 - TADs e Princípios de Programação Orientada a Objectos
- Aula Teórica #07: 9/03/2021
- #08 - Interfaces e TAD Conjunto
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 - Interfaces e TAD Conjunto
- Aula Teórica #08: 12/03/2021
- #09 - Genéricos e Herança
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 - Genéricos e Herança
- Aula Teórica #09: 16/03/2021
- #10 - Listas Ligadas Simples
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 Simples
- Aula Teórica #10: 19/03/2021
- #11 - Listas Ligadas Circulares e Listas Duplamentes Ligadas
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 - Listas Ligadas Circulares e Listas Duplamentes Ligadas
- Aula Teórica #11: 23/03/2021
- #12 - Pilhas, Filas e Deques
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 - Pilhas, Filas e Deques
- Aula Teórica #12: 26/03/2021
- #13 - Resolução de Exercícios de Listas
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 - Resolução de Exercícios de Listas
- Aula Teórica #13: 30/03/2021
- #14 - Padrões Geométricos
Explicação e implementação com "live coding" do problema de desafio "[ED249] Padrões Geométricos".
- #14 - Padrões Geométricos
- Aula Teórica #14: 06/04/2021
- Revisões de matéria anterior e apoio aos estudantes.
- Aula Teórica #15: 09/04/2021
- #15 - Fundamentos de Correção e Eficiência Algorítmica
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 - Fundamentos de Correção e Eficiência Algorítmica
- Aula Teórica #16: 04/05/2021
- #16 - Análise Assintótica
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 - Análise Assintótica
- Aula Teórica #17: 07/05/2021
- #17 - Complexidade de programas: ciclos e recursão
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 - Complexidade de programas: ciclos e recursão
- Aula Teórica #18: 11/05/2021
- #18 - 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.
- #18 - Recursividade
- Aula Teórica #19: 14/05/2021
- #19 - Árvores Binárias: Conceito e Implementação
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: Conceito e Implementação
- Aula Teórica #20: 18/05/2021
- #20 - Árvores Binárias: Pesquisas em Profundidade e Largura
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: Pesquisas em Profundidade e Largura
- Aula Teórica #21: 21/05/2021
- #21 - Árvores Binárias de Pesquisa
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 de Pesquisa
- Aula Teórica #22: 25/05/2021
- #22 - Árvores Binárias: Dicionários
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 - Árvores Binárias: Dicionários
- Aula Teórica #23: 28/05/2021
- #23 - Resolução de Exercícios com Árvores Binárias
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 - Resolução de Exercícios com Árvores Binárias
- Aula Teórica #24: 01/06/2021
- #24 - 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.
- #24 - Filas de Prioridade e Heaps
- Aula Prática #01: 15/02 a 19/02
Um primeiro programa em Java; ciclos, instruções condicionais, procedimentos e funções; Strings. - Aula Prática #02: 22/02 a 26/02
Classe Scanner e leitura de input; uso de arrays; plataforma Mooshak para avaliação automática de código; classes String e Character; resolução de problemas. - Aula Prática #03: 01/03 a 05/03
Uso de classes em Java: métodos, atributos, construtores; referências e conceito de null; atributos e métodos estáticos; classes para representar objectos geométricos simples: pontos e retângulos; classe para representar uma matriz. - Aula Prática #04: 08/03 a 12/03
Noções de programação estruturada; resolução de problemas: implementação de um verificador para um jogo do galo genérico, implementação do jogo da vida, implementação de um verificador de sopa de letras. - Aula Prática #05: 15/03 a 19/03
Tipos Abstractos de Dados, interfaces e suas implementações; implementação de conjuntos de números inteiros usando um array como lista e um array de booleanos como "dicionário" e métodos associados; implementação de números arbitratriamente grandes. - Aula Prática #06: 22/03 a 26/03
Exploração da implementação de listas ligadas dada nas aulas teóricas; resolução de problemas com implementação de vários métodos sobre listas ligadas. - Aula Prática #07: 29/03 a 02/04
Exploração das implementações de listas circulares, listas duplamente ligadas, pilhas, filas e deques dadas nas aulas; resolução de problemas usando os conceitos de listas, pilhas, filas e deques. - Aula Prática #08: 05/04 a 09/04
Consolidação de conhecimentos de listas, pilhas e filas com resolução e implementação de problemas. - Aula Prática #09: 03/05 a 07/05
Resolução de exercícios de treino para o 1º teste prático: fundamentos de java (variáveis, arrays, ciclos), listas ligadas (métodos internos e uso da API), problemas envolvendo eficiência. - Aula Prática #10: 10/05 a 14/05
Notação assintótica; complexidade do TAD Conjunto; previsão do tempo de execução; problema do subarray contíguo de soma máxima; exercícios extra para consolidação de conhecimentos sobre complexidade temporal. - Aula Prática #11: 17/05 a 22/05
Exercícios envolvendo recursividade: soma de um array, capicuas, flood fill, subconjuntos, permutações. - Aula Prática #12: 24/05 a 28/05
Exercícios envolvendo árvores binárias.