Disciplina Curricular
Algoritmos Probabilísticos AProb
Diploma de Estudos Avançados em Segurança de Informação - DEASegInf2007
Peso
7.5 (para cálculo da média)
Objectivos
Desenvolver algoritmos probabilísticos, caracterizar classes computacionais probabilísticas, e verificar a correcção de programas
Programa
Máquinas de Turing probabilísticas. Máquinas-PP, -BPP-, -R-, e -ZPP. Monte Carlo versus Las Vegas. A hierarquia polinomial. Relação da hierarquia polinomial com as classes probabilísticas. Complexidade de problemas de optimização: classes PO e NPO. Aproximabilidade: classes APX, PAS, e FPAS. Sistemas de prova interactivos (Arthur versus Merlin). Classes IP and DIP. Verificação probabilística de provas. Limites de Chernoff: packet routing. Grafos aleatórios: hashing e circuitos hamiltonianos. Cadeias de Markov em tempo discreto e contínuo. Aplicações a máquinas de Boltzmann e redes neuronais estocásticas. Relativização de relações estruturais entre classes probabilísticas.
Metodologia de avaliação
Fichas (60%) + Exame Final (40%).