XKCD: 1337 Parte 2

Quiz: Elaine è il suo secondo nome in realtà.

Il primo nome di Elaine è spiegato nel testo di questa vignetta. Il fratello è infatti Robertino Tabelle! Lei si chiama quindi ‘Help I’m Trapped In A Driver’s License Factory’ (HITIADLF – ‘Aiuto sono intrappolato in una fabbrica di patenti di guida’) Elaine Roberts.

In questo episodio si parla di Donald Knuth, e dell’efficienza degli algoritmi citando l’algoritmo di ricerca A* e dell’algoritmo di Dijkstra.
Donald Knuth è famoso soprattutto per essere il “padre” dell’analisi degli algoritmi (ecco spiegato perchè Elaine è andata da lui), per i suoi libri sull'”Arte della Programmazione” (TAoCP) e per aver inventato TeX, IL linguaggio di typesetting di cui si è già parlato sulla lega.
L'Algoritmo A* e l'Algoritmo di Dijkstra sono algoritmi di ricerca su grafi, differenti sull’uso dell’euristica -in soldoni, usare un’euristica vuol dire stimare una misura da utilizzare in una decisione-: il primo usa infatti una stima sul costo del percorso che passa da un dato nodo, il secondo non ne usa.
Per altre informazioni vedere questo tutorial sull’A*.

Vignetta originale su XKCD.