Planificação

Calendário

Esta planificação serve para dar uma ideia resumida das aulas planeadas e/ou dadas. É apenas uma estimativa e pode mudar consoante o decorrer do semestre.

Teóricas:
- (T01) 12/10: Apresentação da UC; Introdução ao Java I
- (T02) 15/10: Introdução ao Java II
- (T03) 19/10: Introdução ao Java III
- (T04) 22/10: Introdução ao Java IV
- (T05) 26/10: Programação Estruturada
- (T06) 29/10: TADs I
- (T07) 02/11: TADs II
- (T08) 05/11: TADs III
- (T09) 09/11: Listas Ligadas I
- (T10) 12/11: Listas Ligadas II
- (T11) 16/11: Listas Ligadas III
- (T12) 19/11: Revisões I (live coding)
- (T13) 23/11: Revisões II (live coding + apoio)
- (T14) 26/11: Complexidade Algorítmica I
- (T15) 30/11: Complexidade Algorítmica II
- (T16) 03/12: Complexidade Algorítmica III
- (T17) 07/12: Recursividade
- (T18) 10/12: Árvores Binárias I
- (T19) 14/12: Árvores Binárias II
- (T20) 17/12: Árvores Binárias III
- (T21) 04/01: Árvores Binárias IV
- (T22) 07/01: Revisões III (live coding)
- (T23) 11/01: Filas de Prioridade e Heaps
- (T24) 14/01: Revisões IV (preparação para o exame)
Práticas laboratoriais:
- (PL01) 13/10: Introdução ao Java
- (PL02) 20/10: Input/Output e Mooshak
- (PL03) 27/10: Introdução a Classes
- (PL04) 03/11: Programação Estruturada
- (PL05) 10/11: Tipos Abstractos de Dados
- (PL06) 17/11: Listas Ligadas Simples
- (PL07) 24/11: Listas, Pilhas e Filas
- (PL08) 01/12: Consolidação/Revisões [não presencial mas com guião]
- (PL09) 08/12: Complexidade [não presencial mas com guião]
- (PL10) 15/12: Recursividade
- (PL11) 05/01: Árvores Binárias
- (PL12) 12/01: Árvores Binárias de Pesquisa, Conjuntos e Dicionários

Sumários

Aula Teórica #01: 12/10/2021
- [slides] 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".
- [vídeo] #01 - 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.
Aula Teórica #02: 15/10/2021
- [vídeo] #02 - 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).
Aula Teórica #03: 19/10/2021
- [vídeo] #03 - 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.
Aula Teórica #04: 22/10/2021
- [vídeo] #04 - 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 Scanner e seus métodos principais; escrita formatada com printf; regras de etiqueta nos nomes de métodos e atributos.
Aula Teórica #05: 26/10/2021
- [vídeo] #05 - 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.
Aula Teórica #06: 29/10/2021
- [vídeo] #06 - 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".
Aula Teórica #07: 02/11/2021
- [vídeo] #07 - 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.
Aula Teórica #08: 05/11/2021
- [vídeo] #08 - 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.
Aula Teórica #09: 09/11/2021
- #09 - 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.
Aula Teórica #10: 12/11/2021
- #10 - 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".
Aula Teórica #11: 16/11/2021
- #11 - 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.
Aula Teórica #12: 19/11/2021
- #12 - 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).
Aula Teórica #13: 23/11/2021
- #13 - Padrões Geométricos
  Explicação e implementação com "live coding" do problema de desafio "[ED249] Padrões Geométricos".
Aula Teórica #14: 26/11/2021
- #14 - 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.
Aula Teórica #15: 30/11/2021
- #15 - 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.
Aula Teórica #16: 03/12/2021
- #16 - 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).
Aula Teórica #17: 07/12/2021
- #17 - 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.
Aula Teórica #18: 10/12/2021
- #18 - Á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.
Aula Teórica #19: 14/12/2021
- #19 - Á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.
Aula Teórica #20: 17/12/2021
- #20 - Á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
Aula Teórica #21: 04/01/2022
- #21 - Á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.
Aula Teórica #22: 07/01/2022
- #22 - 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.
Aula Teórica #23: 11/01/2022
- #23 - 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.
Aula Teórica #24: 14/01/2022
- #24 - Resolução do 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.

Aula Prática #01: 13/10
Um primeiro programa em Java; ciclos, instruções condicionais, procedimentos e funções; Strings.
Aula Prática #02: 20/10
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: 27/10
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: 03/11
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: 10/11
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: 17/11
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: 24/11
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: 01/12 (aula opcional, remota)
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 #09: 08/12
Exercícios envolvendo complexidade algorítmica
Aula Prática #10: 15/12
Exercícios envolvendo recursividade
Aula Prática #11: 05/01
Exercícios envolvendo árvores binárias
Aula Prática #12: 12/01
Exercícios envolvendo árvores binárias de pesquisa, conjuntos e dicionários.

Estruturas de Dados

Planificação

Calendário

Sumários

Regente

Práticas Laboratoriais

Conteúdo:

Último update: