Metraipolis › archive › dc_cef06915e9f2

Ordinamento delle frittelle — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Ordinamento_delle_frittelle
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-08T03:08:56.027Z
SHA-256 of the archived text
db67a21d8cc190496ef29bcf0b51c47361d52f68a5a8181593127bf9b96eef72
Stable URL of this page
https://metraipolis.com/documento/dc_cef06915e9f2

How to cite

Ordinamento delle frittelle — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Ordinamento_delle_frittelle (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_cef06915e9f2 (Metraipolis archive dc_cef06915e9f2, sha256 db67a21d8cc190496ef29bcf0b51c47361d52f68a5a8181593127bf9b96eef72)
BibTeX
@misc{dccef06915e9f2,
  title = {Ordinamento delle frittelle — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Ordinamento_delle_frittelle},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_cef06915e9f2; sha256 db67a21d8cc190496ef29bcf0b51c47361d52f68a5a8181593127bf9b96eef72},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Ordinamento_delle_frittelle. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

L'ordinamento delle frittelle (nella letteratura in lingua inglese, Pancake sorting oppure prefix reversal) è una variante degli algoritmi di ordinamento in cui l'unica operazione ammessa è invertire gli elementi di una parte iniziale (un prefisso) della successione. A differenza di un algoritmo di ordinamento tradizionale, che cerca di ordinare gli elementi della successione nel minor numero di confronti possibile, l'obiettivo in questo caso è di ordinare gli elementi nel numero minore possibile di inversioni. Questa operazione può essere visualizzata pensando a una pila di frittelle (da cui il nome), in cui è possibile prendere le k frittelle più in alto e rovesciarle. Si sa che l'algoritmo più veloce per ordinare n valori ha bisogno di un numero di operazioni compreso tra (17/16)n e (5/3)n, ma non si conosce il valore esatto. Un semplice, ma niente affatto ottimale, algoritmo di ordinamento delle frittelle richiede al più 2n−3 inversioni. L'algoritmo consiste nell'usare un'inversione per portare in cima alla pila la frittella più grande non ancora ordinata, usarne un'altra per metterla al suo posto corretto, e proseguire fino all'ordinamento completo. Non sono noti algoritmi precisi per calcolare esattamente il numero di inversioni richieste: i limiti indicati più sopra risalgono al 1975, e hanno anche un interesse al di fuori della matematica, visto che uno degli autori dell'articolo che li ha dimostrati è il fondatore di Microsoft, Bill Gates, insieme al proprio professore Christos Papadimitriou. Solo nel settembre 2008, un gruppo di ricercatori dell'University of Texas di Dallas ha annunciato di aver trovato un algoritmo più efficiente. Nel 2008, un gruppo di studenti ha costruito un computer batterico che può risolvere un semplice esempio di ordinamento delle frittelle abbrustolite, programmando dei batteri E. coli in modo che invertano segmenti di DNA. Oltre che per le sue applicazioni didattiche, il problema di ordinamento delle frittelle appare anche nelle applicazioni delle reti parallele di processori, perché fornisce un algoritmo ottimale di routing tra i vari processori. Esiste anche un problema correlato, l'Ordinamento delle frittelle abbrustolite (Burnt Pancake Problem), in cui occorre che alla fine dell'ordinamento il lato abbrustolito delle frittelle rimanga in basso.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Ordinamento delle frittelle» — https://it.wikipedia.org/wiki/Ordinamento_delle_frittelle
Wikidata Q2736589: «variante degli algoritmi di ordinamento» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2736589
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Ordinamento_delle_frittelle?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 153234546, consultata il 2026-11-08T03:05:17.915Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: bb4a7f74962b9d769dcc8f621d0e4e0e6630ae92eb3d59e3842e6122dce95ba6