{"id":6525,"date":"2008-11-10T12:12:48","date_gmt":"2008-11-10T12:12:48","guid":{"rendered":"http:\/\/xmau.com\/wp\/notiziole\/2008\/11\/10\/bill_gates_e_le\/"},"modified":"2008-11-10T12:12:48","modified_gmt":"2008-11-10T12:12:48","slug":"bill_gates_e_le","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2008\/11\/10\/bill_gates_e_le\/","title":{"rendered":"Bill Gates e le frittelle"},"content":{"rendered":"

\"[qualcheNon so se avete presente le frittelle che gli americani si mangiano a colazione (i pancakes, per la precisione): quelle robe pi\u00f9 o meno spesse e tonde che gi\u00e0 non sono dietetiche di loro ma poi vengono completate con generose dosi di sciroppo d’acero. Qua per\u00f2 le frittelle le uso solo come spunto per un problema matematico. Supponiamo di avere un certo insieme di frittelle, tutte di dimensioni diverse, e volerle mettere in ordine di diametro, con la pi\u00f9 piccola in alto e la pi\u00f9 grande in fondo. L’unica operazione che ci \u00e8 concessa fare, per\u00f2, \u00e8 prendere una spatola, infilarla in un punto qualsiasi della pila di frittelle, sollevarne alcune e lanciarle in aria, riprendendole rovesciate. Detto in maniera meno cuciniera, se abbiamo la stringa abcdefghijk<\/i> possiamo scegliere un punto qualunque (ad esempio, e<\/i>) e rovesciare la sottostringa che termina l\u00ec, ottenendo cos\u00ec edcbafghijk<\/i>. Al crescere del numero n <\/i>di frittelle, come varia il numero minimo P(n<\/i>), il pancake number<\/i>, di operazioni da fare nel caso peggiore?
\n\"[giriamoCon una sola frittella non occorre fare nulla, quindi P(1)=0. Con due frittelle, i casi sono due: o sono gi\u00e0 in ordine oppure basta rovesciarle entrambe in un colpo, quindi P(2)=1. Con tre frittelle la cosa si inizia a fare un po’ complicata: per\u00f2 si pu\u00f2 vedere che partendo dalla disposizione 132, entrambe le mosse iniziali possibili (girare le prime due frittelle arrivando alla disposizione 312, oppure girarle tutte arrivando a 231) richiedono altre due operazioni: insomma, P(3)=3. Al crescere delle frittelle, la cosa diventa molto<\/b> complicata: \u00e8 abbastanza semplice vedere che aggiungendo una frittella il numero minimo di operazioni cresce almeno di 1 (aiutino: se la configurazione peggiore nel caso di n-1 frittelle \u00e8 C, immaginate la configurazione nC’, dove C’ \u00e8 la configurazione ottenuta invertendo C), \u00e8 abbastanza semplice vedere che P(n<\/i>) ≤ 2n<\/i>-3 (aiutino: va’ a leggere la pagina relativa di Wikipedia, da cui tra l’altro ho preso il disegno). Che una formula non sia cos\u00ec semplice da trovare, lo si pu\u00f2 notare anche guardando la tabella dei valori di P(n<\/i>) per n<\/i> che va da 1 a 13:<\/p>\n\n\n\n\n
n<\/i><\/td>\n 1 <\/td>\n 2 <\/td>\n 3 <\/td>\n 4 <\/td>\n 5 <\/td>\n 6 <\/td>\n 7 <\/td>\n 8 <\/td>\n 9 <\/td>\n 10 <\/td>\n 11 <\/td>\n 12 <\/td>\n 13 <\/td>\n<\/tr>\n
P(n<\/i>)<\/td>\n0<\/td>\n1<\/td>\n3<\/td>\n4<\/td>\n5<\/td>\n7<\/td>\n8<\/td>\n9<\/td>\n10<\/td>\n11<\/td>\n13<\/td>\n14<\/td>\n15<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

e i valori computati negli ultimi anni da un gruppo di informatici giapponesi usando cluster di computer:<\/p>\n\n\n\n\n
n<\/i><\/td>\n 14 <\/td>\n 15 <\/td>\n 16 <\/td>\n 17 <\/td>\n<\/tr>\n
P(n<\/i>)<\/td>\n16<\/td>\n17<\/td>\n18<\/td>\n19<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Se non si sa andare pi\u00f9 avanti di cos\u00ec, significa che c’\u00e8 davvero qualcosa di complicato. E in effetti, i limiti teorici trovati nel 1975 e pubblicati nel 1979 – che 5(n<\/i>+1)\/3 inversioni sono sempre sufficienti, e nel caso peggiore ne servono almeno 17n<\/i>\/16 – sono rimasti imbattuti fino al 1997, quando Mohammad H. Heydari e I. Hal Sudborough alzarono il limite inferiore a 15n<\/i>\/14, e a quest’ultimo settembre, dove Sudborough e un gruppo di suoi studenti ha abbassato il limite inferiore a (18\/11)n<\/i>.<\/p>\n

Che c’entra tutto questo con Bill Gates, mi staranno chiedendo i pochi pazzi che sono arrivati fin qua? Semplice. L’articolo del 1979, Bounds for Sorting by Prefix Reversal<\/i>, \u00e8 stato scritto da nientemeno che William Henry Gates III, insieme al suo allora professore Christos Papadimitriou. Un lato inaspettato del multimiliardario, insomma!
\nBibliografia:<\/b>
\n♦ http:\/\/it.wikipedia.org\/wiki\/Ordinamento_delle_frittelle
\n♦ http:\/\/www.maa.org\/mathtourist\/mathtourist_10_9_08.html
\n♦ http:\/\/www.npr.org\/templates\/story\/story.php?storyId=92236781<\/p>\n","protected":false},"excerpt":{"rendered":"

Non ci crederete, ma c’\u00e8 una connessione matematica!<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":3,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[214],"tags":[],"class_list":["post-6525","post","type-post","status-publish","format-standard","hentry","category-matematica_light"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-1Hf","jetpack-related-posts":[{"id":23948,"url":"https:\/\/xmau.com\/notiziole\/2022\/04\/06\/il-vero-rientro-in-ufficio\/","url_meta":{"origin":6525,"position":0},"title":"il vero rientro in ufficio","author":".mau.","date":"2022-04-06","format":false,"excerpt":"Quelli di questo autunno non valgono","rel":"","context":"In "io"","block_context":{"text":"io","link":"https:\/\/xmau.com\/notiziole\/category\/io\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":25865,"url":"https:\/\/xmau.com\/notiziole\/2023\/02\/21\/superbonus-superstop\/","url_meta":{"origin":6525,"position":1},"title":"Superbonus: superstop","author":".mau.","date":"2023-02-21","format":false,"excerpt":"La fine del superbonus \u00e8 stata come spesso capita brutale. Ma forse il problema era a monte.","rel":"","context":"In "pipponi"","block_context":{"text":"pipponi","link":"https:\/\/xmau.com\/notiziole\/category\/pipponi\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1979,"url":"https:\/\/xmau.com\/notiziole\/2002\/04\/18\/meno_tasse_per_tutti\/","url_meta":{"origin":6525,"position":2},"title":"Meno tasse per tutti!","author":".mau.","date":"2002-04-18","format":false,"excerpt":"Oggi faccio una scappata a Torino per l'assemblea della CAMLC, la cooperativa che gestisce la mensa Tilab e alla quale sono sempre affezionato. Leggendo il bilancio, ho visto che l'utile \u00e8 pi\u00f9 o meno quello dell'anno scorso, un milioncino di vecchie lire in meno: nulla di male, visto che tanto\u2026","rel":"","context":"In "2001-02"","block_context":{"text":"2001-02","link":"https:\/\/xmau.com\/notiziole\/category\/varie\/varie-2001-02\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":7955,"url":"https:\/\/xmau.com\/notiziole\/2010\/07\/02\/o_punto_o_virgo\/","url_meta":{"origin":6525,"position":3},"title":"o punto o virgola","author":".mau.","date":"2010-07-02","format":false,"excerpt":"Capisco l'indecisione nelle notazioni, ma a distanza di una riga...","rel":"","context":"In "italica_stampa"","block_context":{"text":"italica_stampa","link":"https:\/\/xmau.com\/notiziole\/category\/italica_stampa\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":3892,"url":"https:\/\/xmau.com\/notiziole\/2006\/01\/11\/fenomenologia_delle_sottomarche\/","url_meta":{"origin":6525,"position":4},"title":"Fenomenologia delle sottomarche","author":".mau.","date":"2006-01-11","format":false,"excerpt":"Non \u00e8 affatto un caso che le sottomarche siano cos\u00ec brutte.","rel":"","context":"In "y2006_curiosita'"","block_context":{"text":"y2006_curiosita'","link":"https:\/\/xmau.com\/notiziole\/category\/y2006_curiosita\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":4782,"url":"https:\/\/xmau.com\/notiziole\/2007\/02\/28\/sempre_sulle_pensioni\/","url_meta":{"origin":6525,"position":5},"title":"Sempre sulle pensioni","author":".mau.","date":"2007-02-28","format":false,"excerpt":"Un articolo di lavoce.info","rel":"","context":"In "link"","block_context":{"text":"link","link":"https:\/\/xmau.com\/notiziole\/category\/link\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/6525","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/comments?post=6525"}],"version-history":[{"count":0,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/6525\/revisions"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=6525"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=6525"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=6525"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}