Planificação

Calendário

Esta planificação serve para dar uma ideia resumida das aulas planeadas e/ou dadas:

 

Sumários

Aula Teórica #01: 25/09/2020
Apresentação da unidade curricular: frequência, avaliação, objectivos, programa, funcionamento das aulas.

Aula Teórica #02: 25/09/2020
Previsão do tempo de execução de um algoritmo: com acesso a implementação e tempo de execução numa instância e antes mesmo de ter implementação; alguns exemplos e regras práticas.

Aula Teórica #03: 02/10/2020
O modelo de Random Access Machine (RAM) para contagem de operações simples num programa; 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, Ω Θ e regras práticas; funções mais comuns: nomes, relações de dominância e exemplos de algoritmos. Previsão do tempo de execução de um algoritmo com acesso a uma implementação (alguns exemplos e regras práticas).

Aula Teórica #04: 02/10/2020
Previsão do tempo de execução de um algoritmo antes de ter uma implementação (alguns exemplos e regras práticas). 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 recorrências; outras recorrências (máximo com dividir para conquistar ou tail recursion; pesquisa binária).

Aula Teórica #05: 09/10/2020
A ordenação como passo fundamental de muitos algoritmos; esboço de prova do "lower bound" de n log n para algoritmos de ordenação no modelo comparativo; algoritmos comparativos: bubblesort, selectionsort, insertionsort, mergesort e quicksort (naive e aleatorizado); algoritmos não comparativos: counting sort e radixsort.

Aula Teórica #06: 09/10/2020
Exemplos de aplicação de ordenação; algoritmo de pesquisa binária direto num array ordenado; variantes de pesquisa binária; "binary search the answer" como pesquisa binária indireta, no espaço de soluções; problema da partição equilibrada; método de bisseção.

Aula Teórica #07: 16/10/2020
Algoritmos greedy (ávidos/gananciosos/gulosos); o problema do troco de moedas; propriedades de um algoritmo greedy: subestrutura ótima e escolha greedy.

Aula Teórica #08: 16/10/2020
Algoritmos greedy para problemas práticos: fractional knapsack, planeamento de intervalos, cobertura mínima.

Aula Teórica #09: 23/10/2020
Motivação para programação dinâmica (PD): números de fibonacci e pirâmide de números; propriedades de um algoritmo de PD: subestrutura ótima e subproblemas coincidentes; metodologia para resolução de um problema com PD: caracterizar, definição recursiva, cálculo da solução de todos os problemas e eventual reconstrução da solução ótima.

Aula Teórica #10: 23/10/2020
Aplicação de PD em problemas: maior subsequência crescente, mínimo troco de moedas, contagem de caminhos, jogos para 2 jogadores, distância de edição.

Aula Prática #01: 28/09 a 02/10
Introdução e uso prático do Mooshak como sistema de avaliação automático. Resolução de problemas introdutórios (ciclos, manipulação de dígitos, manipulação de strings).

Aula Prática #02: 05/10 a 09/10
Exercícios sobre análise assintótica: notação, previsão e complexidade de programas. Resolução de problemas envolvendo somas acumuladas e paradigma de dividir para conquistar.

Aula Prática #03: 12/10 a 16/10
Exercícios práticos sobre ordenação e pesquisa binária; bibliotecas para ordenação customizada, pesquisa binária directa a indirecta.

Aula Prática #04: 19/10 a 23/10
Exercícios práticos sobre algoritmos greedy.

Aula Prática #05: 26/10 a 30/10
Exercícios práticos sobre programação dinâmica.