Probabilidade
Probabilidade
Probabilidade é a linguagem da incerteza, e em computação ela aparece em três papéis distintos que vale distinguir.
Como modelo de entrada: analisar o caso médio de um algoritmo supõe uma distribuição sobre as entradas. Como recurso do algoritmo: algoritmos aleatorizados usam moedas internas para ganhar simplicidade ou desempenho, e sua análise não depende de hipótese sobre a entrada. Como objeto de estudo: aprendizado de máquina e inferência bayesiana têm a probabilidade como assunto.
Ordem sugerida
Comece por espaço amostral e probabilidade condicional; Bayes sozinho já resolve boa parte dos problemas práticos. Depois variáveis aleatórias e distribuições. As desigualdades de concentração e as cadeias de Markov são o ferramental avançado que sustenta a análise de algoritmos aleatorizados.
Referências
- Sheldon M. Ross (2014). A First Course in Probability. Pearson.
- Michael Mitzenmacher; Eli Upfal (2017). Probability and Computing: Randomization and Probabilistic Techniques. Cambridge University Press.
- Rajeev Motwani; Prabhakar Raghavan (1995). Randomized Algorithms. Cambridge University Press.