Notas finais sobre o funcionamento da disciplina.

Inclusão da classe P em NP.
Alguns exemplos de problemas NP-completos.
Alguns exemplos de problemas não-computáveis: Halting e Correspondência de Post.

Avaliação do ensino ministrado.

Classes de problemas: a classe P.

Algoritmos não-determinísticos e a classe NP.

Noção de redução e a classe NP-completo.

Propriedade de sub-problema óptimo como garantia de correcção de algoritmos greedy.
Contra-exemplo: pesos negativos nos algoritmos de Dijkstra e Prim.

Motivação da classificação de problemas. Definições informais das classes P e NP.

Algoritmo de Kurskall para calcular a árvore geradora de custo mínimo.
Pormenores de implementação: uso de heaps para armazenamento das arestas e estruturas de find&union para detecção de ciclos.

Árvore geradora de custo mínimo: algoritmo de Prim como exemplo de algoritmo greedy.

Representação de uma árvore geradora através do vector de ascendentes.

Join 2007.

Algoritmos de procura em grafos: estratégia global de procura.
Análise de alguns exemplos.
Travessias de um grafo a partir de um vértice: Breadth-first e Depth-first.

Outras implementações de grafos: listas duplamente ligadas e vector de adjacências.

Grafos: motivação e definições.
Implementações das arestas de um grafo como matrizes ou listas de adjacência.
Análise informal da complexidade de algumas operações básicas sobre grafos nestas duas implementações (existência de uma aresta, cálculo dos sucessores e cálculo dos sucessores).

No próximo dia 2 de Maio vai haver uma aula extra para compensar o reduzido número de Terças-feiras.
Será no DI-A2 das 8:00 às 10:00.

Análise das recorrências dos algoritmos merge-sort e quick-sort.
Identificação do melhor e pior casos para o algoritmo de quick-sort.

Determinação do limite inferior para o pior caso dos algoritmos de ordenação baseados em comparação de elementos.

Algoritmo de counting-sort como alternativa (linear) aos algoritmos baseados em comparações.

Estratégia divide-and-conquer e recorrências associadas.
Aplicação aos algoritmos de ordenação de vectores (merge-sort e quick-sort)

Propriedades das notações O, Ω e Θ.
Classificação de funções polinomiais.

Já se encontra disponível (ver Material de Apoio) o enunciado do trabalho prático.

Definição do tempo de execução de um dado algoritmo usando relações de recorrência (exemplo: pior caso da procura binária).
Análise assimptótica: notações O, Ω, Θ.

Cálculo do número de operações do algoritmo de merge usado na ordenação merge-sort.

Cálculo do número de operações atómicas de um algoritmo de ordenação.

Introdução à análise da complexidade de algoritmos.
Máquina abstracta, tamanho do input, estado do input como parâmetros da simplificação da análise.

Exemplificação destes conceitos para o algoritmo de ordenação de um vector de inteiros por troca directa.

Aula de demonstração do uso de ferramentas aplicadas à verificação de programas.

Uso de invariantes como forma de descrever algoritmos cíclicos. Exemplos: procura num vector ordenado, algoritmo de Euclides, partição de um vector.

Outros exemplos de correcção de programas com ciclos: divisão inteira.

Derivação da multiplicação de inteiros à custa da multiplicação e divisão por 2.

Fortalecimento de especificações (fortalecimento da pré-condição e enfraquecimento da pós-condição).
Exemplo de prova de um programa com ciclos (multiplicação por somas sucessivas).

Correcção das condicionais e da atribuição.
Correcção da sequenciação.
Exemplo de prova de correcção: swap.
Correcção parcial de ciclos: noção de invariante.
Prova da terminação de um ciclo: noção de variante.

Apresentação da disciplina: objectivos, programa, equipa docente e métodos de avaliação.
Introdução à análise da correcção de algoritmos. Noções de pré e pós-condições. Exemplos.