| dbo:abstract
|
- Das Pfannkuchen-Sortierproblem ist ein Problem aus dem Bereich der diskreten Mathematik bzw. der theoretischen Informatik, bei dem es anschaulich darum geht, einen Stapel Pfannkuchen der Größe nach zu sortieren. Der Stapel besteht aus Pfannkuchen unterschiedlicher Größe und soll so sortiert werden, dass am Ende der größte Pfannkuchen an unterster Stelle ist, der zweitgrößte darüber bis zum kleinsten ganz oben. Dazu darf in jedem Schritt ein von der aktuellen Spitze des Stapels ausgehender Teilstapel ausgewählt und als ganzer umgekehrt werden. Gefragt ist nach der kleinsten Anzahl an Schritten dieser Art, die benötigt werden, um unabhängig von der Ausgangslage den gesamten Stapel zu sortieren. Erstmals veröffentlicht wurde das Problem 1975 von unter dem Pseudonym Harry Dweighter (gleicht in der Aussprache harried waiter, „gestresster Kellner“) in der Zeitschrift American Mathematical Monthly. Seitdem wurden zahlreiche ernsthafte Forschungsergebnisse zum Thema veröffentlicht. Anwendung findet das Problem unter anderem bei Mutationen in der Genetik. (de)
- El ordenamiento de panqueques (panecillos, arepas...) es el término coloquial para el problema matemático de ordenar una pila desordenada de panqueques por orden de tamaño utilizando una espátula que puede ser insertada en cualquier punto en la pila para voltear todos los panqueques encima de ella. Un número de panqueque es el número máximo de volteos requeridos sin repetir para ordenar un número dado de panqueques. Este problema fue presentado de esta forma por el geómetra americano Jacob E. Goodman. Es una variación del problema de ordenamiento en que la única operación permitida la de invertir los elementos de algún prefijo de la secuencia.A diferencia de un algoritmo de ordenación tradicional, que intenta ordenar con el menor número de comparaciones posible, su objetivo es ordenar la secuencia en el menor número posible de inversiones.Una variante del problema se ocupa de panqueque quemados donde cada uno de estos tiene un lado quemado y todos los panqueques deben además, acaba con este, en la parte inferior. (es)
- Le tri de crêpes (de l'anglais pancake sorting) est un problème mathématique. Il s'agit de trier une pile de crêpes afin que les crêpes soient empilées de la plus grande à la plus petite (au sens de leur diamètre). La seule opération autorisée pour arriver à ce résultat est de retourner la partie supérieure de la pile. On peut considérer d'une part le problème algorithmique, où le but est d'arriver à la configuration finale, comme pour un algorithme de tri, et d'autre part des questions mathématiques. Une question classique est d'évaluer le nombre minimum de mouvements nécessaires, pour toute pile d'une certaine taille. (fr)
- Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. In this form, the problem was first discussed by American geometer Jacob E. Goodman. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom. All sorting methods require pairs of elements to be compared. For the traditional sorting problem, the usual problem studied is to minimize the number of comparisons required to sort a list. The number of actual operations, such as swapping two elements, is then irrelevant. For pancake sorting problems, in contrast, the aim is to minimize the number of operations, where the only allowed operations are reversals of the elements of some prefix of the sequence. Now, the number of comparisons is irrelevant. (en)
- Penyortiran panekuk adalah variasi masalah penyortiran yang satu-satunya operasi yang diperbolehkan adalah membalikkan elemen sejumlah prefiks urutan. Tidak seperti algoritme penyortiran lama, yang berusaha mengurutkan dengan perbandingan sesedikit mungkin, tujuan penyortiran ini adalah mengurutkan sebuah urutan dengan pembalikan sesedikit mungkin. Operasi ini dapat divisualisasikan dengan membayangkan tumpukan panekuk dan seseorang dibolehkan mengambil panekuk k di atas dan membalikannya. Ada satu varian masalah ini yang berkaitan dengan panekuk gosong, yaitu ketika setiap panekuk memiliki sisi gosong dan semua panekuk harus berakhir dengan sisi gosong di atasnya. (in)
- 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. (it)
- Pancake sorting (letterlijk: pannenkoekensorteren) is een variatie op het sorteren van een rij getallen, waarbij het alleen toegestaan is de volgorde van een zeker prefix van de rij om te keren. Een prefix bestaat uit een aantal getallen aan het begin van de rij; dat aantal mag men zelf kiezen. De methode wordt daarom ook sorting by prefix reversal genoemd (sorteren door omkeren van een prefix). Het is de bedoeling om de rij te sorteren van klein naar groot met zo weinig mogelijk omkeringen of flips. (nl)
- Блинная сортировка (от англ. pancake sorting) — алгоритм сортировки. Единственная операция, допустимая в алгоритме — переворот элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить как стопку блинов, которую тасуют путём взятия нескольких блинов сверху и их переворачивания. (ru)
- 煎饼排序（英語：Pancake sorting）指的是将大小不同的一摞煎饼按大小排序的数学问题，其中每次只能从任意位置铲起上方全部煎饼并翻面。“煎饼数”（英語：pancake number）是指给定煎饼的张数时，最坏情况下需要的最少翻面次数。这个问题最早由美国几何学家提出。它属于排序问题的变种。煎饼排序的目标和传统排序算法最小化比较次数不同，因为它每次操作只允许反转序列的，所以需要最小化反转前缀次数。焦煎饼排序是煎饼排序的变种问题，每张煎饼都有一面是烤焦的，最终除了按照大小排序以外还要让所有焦面向下。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 21604 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:title
| |
| dbp:urlname
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Le tri de crêpes (de l'anglais pancake sorting) est un problème mathématique. Il s'agit de trier une pile de crêpes afin que les crêpes soient empilées de la plus grande à la plus petite (au sens de leur diamètre). La seule opération autorisée pour arriver à ce résultat est de retourner la partie supérieure de la pile. On peut considérer d'une part le problème algorithmique, où le but est d'arriver à la configuration finale, comme pour un algorithme de tri, et d'autre part des questions mathématiques. Une question classique est d'évaluer le nombre minimum de mouvements nécessaires, pour toute pile d'une certaine taille. (fr)
- Penyortiran panekuk adalah variasi masalah penyortiran yang satu-satunya operasi yang diperbolehkan adalah membalikkan elemen sejumlah prefiks urutan. Tidak seperti algoritme penyortiran lama, yang berusaha mengurutkan dengan perbandingan sesedikit mungkin, tujuan penyortiran ini adalah mengurutkan sebuah urutan dengan pembalikan sesedikit mungkin. Operasi ini dapat divisualisasikan dengan membayangkan tumpukan panekuk dan seseorang dibolehkan mengambil panekuk k di atas dan membalikannya. Ada satu varian masalah ini yang berkaitan dengan panekuk gosong, yaitu ketika setiap panekuk memiliki sisi gosong dan semua panekuk harus berakhir dengan sisi gosong di atasnya. (in)
- Pancake sorting (letterlijk: pannenkoekensorteren) is een variatie op het sorteren van een rij getallen, waarbij het alleen toegestaan is de volgorde van een zeker prefix van de rij om te keren. Een prefix bestaat uit een aantal getallen aan het begin van de rij; dat aantal mag men zelf kiezen. De methode wordt daarom ook sorting by prefix reversal genoemd (sorteren door omkeren van een prefix). Het is de bedoeling om de rij te sorteren van klein naar groot met zo weinig mogelijk omkeringen of flips. (nl)
- Блинная сортировка (от англ. pancake sorting) — алгоритм сортировки. Единственная операция, допустимая в алгоритме — переворот элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить как стопку блинов, которую тасуют путём взятия нескольких блинов сверху и их переворачивания. (ru)
- 煎饼排序（英語：Pancake sorting）指的是将大小不同的一摞煎饼按大小排序的数学问题，其中每次只能从任意位置铲起上方全部煎饼并翻面。“煎饼数”（英語：pancake number）是指给定煎饼的张数时，最坏情况下需要的最少翻面次数。这个问题最早由美国几何学家提出。它属于排序问题的变种。煎饼排序的目标和传统排序算法最小化比较次数不同，因为它每次操作只允许反转序列的，所以需要最小化反转前缀次数。焦煎饼排序是煎饼排序的变种问题，每张煎饼都有一面是烤焦的，最终除了按照大小排序以外还要让所有焦面向下。 (zh)
- Das Pfannkuchen-Sortierproblem ist ein Problem aus dem Bereich der diskreten Mathematik bzw. der theoretischen Informatik, bei dem es anschaulich darum geht, einen Stapel Pfannkuchen der Größe nach zu sortieren. Der Stapel besteht aus Pfannkuchen unterschiedlicher Größe und soll so sortiert werden, dass am Ende der größte Pfannkuchen an unterster Stelle ist, der zweitgrößte darüber bis zum kleinsten ganz oben. Dazu darf in jedem Schritt ein von der aktuellen Spitze des Stapels ausgehender Teilstapel ausgewählt und als ganzer umgekehrt werden. Gefragt ist nach der kleinsten Anzahl an Schritten dieser Art, die benötigt werden, um unabhängig von der Ausgangslage den gesamten Stapel zu sortieren. (de)
- El ordenamiento de panqueques (panecillos, arepas...) es el término coloquial para el problema matemático de ordenar una pila desordenada de panqueques por orden de tamaño utilizando una espátula que puede ser insertada en cualquier punto en la pila para voltear todos los panqueques encima de ella. Un número de panqueque es el número máximo de volteos requeridos sin repetir para ordenar un número dado de panqueques. Este problema fue presentado de esta forma por el geómetra americano Jacob E. Goodman. Es una variación del problema de ordenamiento en que la única operación permitida la de invertir los elementos de algún prefijo de la secuencia.A diferencia de un algoritmo de ordenación tradicional, que intenta ordenar con el menor número de comparaciones posible, su objetivo es ordenar la (es)
- Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. In this form, the problem was first discussed by American geometer Jacob E. Goodman. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom. (en)
- 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. (it)
|
| rdfs:label
|
- Pfannkuchen-Sortierproblem (de)
- Ordenamiento de panqueques (es)
- Penyortiran panekuk (in)
- Tri de crêpes (fr)
- Ordinamento delle frittelle (it)
- Pancake sorting (en)
- Pancake sort (nl)
- Блинная сортировка (ru)
- 煎餅排序 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
