Algoritmos: curiosidades e quiz

Um algoritmo é um conjunto de passos claros para resolver um problema, como uma receita. Os computadores seguem algoritmos, e as pessoas também, quando amarram os cadarços.

Ponto-chave
A palavra vem de al-Khwarizmi, um matemático persa do século IX.

Para achar um nome numa lista em ordem, não comece do início: abra no meio, veja em que metade ele está e repita. Isso é a busca binária.

Ponto-chave
A busca binária acha um nome entre um milhão em cerca de 20 passos.

Ordenar é colocar as coisas em ordem. Os métodos simples comparam vizinhos e trocam os dois de lugar; os mais rápidos dividem a lista, ordenam as partes e depois as juntam.

Ponto-chave
Um computador consegue ordenar um milhão de itens em uma fração de segundo.

Apps de streaming e de compras usam algoritmos para adivinhar do que você vai gostar, com base no que você e pessoas parecidas com você escolheram antes.

Ponto-chave
As recomendações podem nos prender numa bolha de mais do mesmo.

Dois algoritmos podem resolver o mesmo problema em velocidades bem diferentes. Conforme a entrada cresce, um método esperto pode ser milhões de vezes mais rápido que um ingênuo.

Ponto-chave
Os cientistas da computação descrevem a velocidade com a notação “Big O”.

Os apps de mapa acham a rota mais rápida com algoritmos de caminho mínimo, como o que Edsger Dijkstra inventou em 1956, dizem que em uns 20 minutos.

Ponto-chave
Dijkstra o criou sem lápis nem papel, num café.

Alguns problemas não têm nenhum algoritmo rápido conhecido. Achar a viagem mais curta que passa por várias cidades, o problema do caixeiro-viajante, fica explosivamente mais difícil a cada cidade.

Ponto-chave
Com 20 cidades, há mais de 60 quatrilhões de viagens de ida e volta possíveis.