| | | Objectivos, programa, docente |
Pretende-se que o aluno
- Comprenda a relação entre o desenho, a prova da correcção e a
análise dos algoritmos
- Aprenda algumas técnicas gerais que lhe sejam úteis na
implementação de novos algoritmos.
- Fique a conhecer alguns dos principais algoritmos numa
pequena selecção de domínios específicos
Todo o programa previsto com excepção do Capítulo 09 (transformada discreta de Fourier e FFT)
01 Preliminares: fundamentos da análise de algoritmos
Ordens de grandeza
Solução de recorrências
Um exemplo de análise de um algoritmo
02 Tempo de execução dos algoritmos - complementos
Sobre os modelos de computação
Análise amortizada de algoritmos
03 Sobre o esquema "Dividir para Conquistar"
Uma recorrência associada ao esquema "dividir para conquistar"
Multiplicar mais rapidamente inteiros e matrizes
04 Algoritmos aleatorizados e classes de complexidade aleatorizadas
Um problema de coloração
O produto de duas matrizes iguala uma terceira?
O "quick sort"
Técnica de redução da probabilidade de erro
Outro algoritmo aleatorizado: o algoritmo de Rabin-Miller
Computação aleatorizada: classes de complexidade
05 Sobre a ordenação e a selecção
Quando o universo é pequeno: indexação nos valores
Métodos de ordenação baseados na representação dos valores
"Tries"
Mediana; selecção
06 Introdução aos circuitos; redes de ordenação
Circuitos
Classes de complexidade associadas ao modelo dos circuitos
Redes de comparação e redes de ordenação
07 "Hash" universal e perfeito
"Hash" universal: aleatorização do "hash"
"Hash" perfeito
Contar o número de elementos distintos
08 Programação Dinâmica: complementos
Introdução, princípio de Bellman
Parentização óptima de um produto matricial
Máxima sub-sequência comum
Problema da mochila ("knapsack problem")
09 Transformada discreta de Fourier e FFT
Transformações de representação, generalidades
Polinómios em corpos. Representações
Análise da eficiência do algoritmo FFT
10 Notas sobre minorantes de complexidade 43
Entropia, informação e minorantes de complexidade
Aplicação a algoritmos baseados em comparações:
algoritmos de ordenação, de determinação do máximo
e algoritmo "merge"
Docente:
Armando Matos, email: acm@ncc.up.pt
| | | Objectivos, programa, docente |