This post originated from an RSS feed registered with .NET Buzz
by Adrian Florea.
Original Post: Bill Gates e il pancake problem
Feed Title: Web Log di Adrian Florea
Feed URL: /error.aspx?aspxerrorpath=/adrian/Rss.aspx
Feed Description: "You know you've achieved perfection in design, not when you have nothing more to add, but when you have nothing more to take away." Antoine de Saint-Exupery
Pochi forse sanno che il nostro amato chief software architect è anche il coautore di un davvero bellissimo risultato di combinatorica sul cosìdetto problema delle frittelle :-) (in inglese "pancake problem") insieme al vincitore del Premio Knuth per 2002 (una specie di Nobel per l'informatica teorica), il Prof. Christos H. Papadimitriou. Insieme, sono riusciti all'inizio del 1978 (Bill aveva appena compiuto 22 anni) a dimonstrare che per fare il sorting di una permutazione di ordine n ci vogliono non più di (5*n+5)/3 flip (o prefix reversal) e non meno di 17*n/16 flip. Vale la pena di scaricare (e leggere) il PDF della fotocopia dell'articolo originale (sono quasi 5 MB):
Il limite inferiore è stato fratempo migliorato, nel 1992, a 15*n/14, grazie a David S. Cohen (non mi crederete però ha scritto anche The Simpsons!) e al Prof. Manuel Blum (quest'ultimo, vincitore del Premio Turing per 1995 - il premio è la più alta onorificenza in computer science).
Il problema originale è stato proposto dal Prof. Jacob E. Goodman nel 1975 (si è firmato però Harry Dweighter) e suscita tuttora interesse, dopo 30 anni, soprattutto per le sue varie applicazioni pratice. Il nostro Bill, nello stesso articolo, oltre al risultato sopra menzionato, propone e risolve un altro problema, leggermente modificato: quello delle frittelle bruciate ("burnt pancake problem"). Lascio adesso a voi il piacere di gustarle :-)
P.S.: Sembra che il valore del limite magiore, (5*n+5)/3, sia stato ottenuto indipendentemente, sempre nel 1978, anche da due ungheresi:
E. Györi, G. Turán, "Stack of pancakes", Studia Sci. Math. Hungar., 13 (1978),133-137
Previous Topic
