Sumários das aulas teóricas

  Objectivos, programa e método de avaliação.
  Ordens de grandeza.

Aula 02

  Indução, recursão e demonstração da correcção dos algoritmos.
  Funções definidas por recorrências.
  Alguns métodos de resolver recorrências: método directo,
  "tabelar-suspeitar-demonstrar", equação característica homogénea, 
  equação característica não homogénea (alguns casos),
  diferenças finitas de ordem k constantes. 

Aula 03

 Tempo e espaço das computações. 
 Modelos de cálculo: 
    modelo exacto (TM)
    modelo uniforme e máquinas de registos
    modelo com dados externos
    modelo dos circuitos
 Tempo no pior caso e no caso médio.
 

Aula 04

 Custo amortizado
 Função potencial
 Aplicação a uma sequência de operações de "push" num "stack" com
 redimensionamento. 
 Aplicação a uma sequência de operações de incremento num contador
 binário. 

Aula 05

 Análise genérica dos algoritmos baseados no esquema
 "dividir para conquistar".
 Aplicação a algoritmos específicos de ordenação e pesquisa.

Aula 06

 Aplicação do esquema "dividir para conquistar" a
  - multiplicação de inteiros muito grandes; algoritmo de
    Karatsuba. Referência a algoritmos posteriores baseados no FFT.
  - multiplicação de matrizes muito grandes; algoritmo de
    Strassen. Algoritmos ainda mais rápidos (assimptoticamente) e sua
    aplicabilidade prática. 

Aula 07

 Algoritmos aleatorizados. 
 Estatísticas baseadas nas distribuições probabilísticas dos dados e
 nos aletórios utilizados pelos algoritmos. 
 Aplicações a
  - um problema de coloração 
  - o produto de duas matrizes iguala uma terceira?

Aula 08

 O quicksort clássico: análise do pior caso e do caso médio.
 O quicksort aleatorizado: análise do pior caso e do caso médio.

Aula 09

 Primalidade: testemunhos de "composicionalidade", Pequeno Teotera de
 Fermat, teste de de Rabin-Miller (referência à potenciação modular
 eficiente). 

Aula 10

 Computação aleatorizada: classes de complexidade.
 Classes RP, co-RP, BPP.
 Relação com as classes P e NP.

Aula 11

  Estabilidade da ordenação. Algoritmos de ordenação 
  Quando o universo é constituído por inteiros positivos não
  excessivamente grandes. 'Bit-arrays'.

Aula 12

 Representação de conjuntos por indexação nos elementos.
 Operações entre conjuntos.
 Algoritmos de ordenação por contagem. Elementos
 repetidos. Estabilidade.  

Aula 13

 Ordenação de reais uniformemente distribuídos em [0,1).
 Eficiência.
 Estudo do radix-sort. Eficiência. Necessidade da estabilidade da
  ordenação. 
 Referência à estrutura de informação 'trie'.

Aula 14

 Problema da selecção: algoritmo não determinístico (inspirado no
   quick-sort) com tempo médio O(n).

Aula 15

 Algoritmo determinístico de determinação da mediana
 (devido a Blum, Floyd, Pratt, Rivest e Tarjan)
 em tempo O(n).
 Classe de recorrências com solução linear em n.

Aula 16

 Não uniformidade; o modelo de computação dos circuitos.
 Circuitos lógicos.
 Famílias completas de circuitos elementares

Aula 17

 Comparadores.
 Redes de comparadores e redes de ordenação. Princípio 0/1.
 Tempo paralelo (profundidade) e tempo sequênciasl. Número de
  componentes do circuito. 
 Rede elementar de ordenação. Complexidade. 
 Construção de uma rede de ordenação com tempo paralelo baseada no
 merge-sort: 
  - sequências bitónicas
  - circuito HC, ordenador bitónico
  - circuito merge, circuito merge-sort.

Aula 20

 Programação Dinâmica; problemas de optimização, princípio de
 Bellman. Aplicação à determinação da 'parentização' óptima de um
produto de matrizes. Eficiência.

Aula 21

 Aplicação da Programação Dinâmica aos seguintes problemas:
   - Máxima sequência (não necessariamente consecutiva) comum a duas
     "strings" dados. 
   - Problema da mochila ("knapsack problem")

Aula 22

Minorantes de complexidade: princípio da informação necessária  e
modelo externo dos dados.

Aula 23

Estabelecimento de minorantes de complexidade para o problema da
pesquisa, o problema do "merge" e para o problema da
ordenação. Comparação com os melhores algoritmos conhecidos.

Aula 24

Complementos sobre os métodos de "hashing".
"Hashing" aleatorizado, "hashing" universal.

Aula 25

"Hashing" perfeito em espaço O(n2).
"Hashing" perfeito em espaço O(n).