Analiza problema sortiranja uz reverzne prefikse

diplomski rad

• Naslov (engleski): Analysis of Sorting Problem by Prefix Reversals
• Autor: Hana Bašić
• Mentor: Tomislav Burić (mentor)
• Član povjerenstva: Tomislav Burić (predsjednik povjerenstva)
• Član povjerenstva: Lenka Mihoković (član povjerenstva)
• Član povjerenstva: Tomislav Šikić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2020-07-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Problem sortiranja uz reverzne prefikse kolokvijalno je poznat kao problem palačinki, a primijenjuje se u raspoređivanju procesa u mrežama paralelnih procesora. U radu je matematički analiziran problem, te je prikazana implementacija programske aplikacije koja vizualno prikazuje različite varijante ovakvih sortiranja. Nedavno je dokazano da je problem sortiranja palačinki NP-težak problem te još uvijek nije poznat minimalni broj koraka potrebnih za sortiranje, tek su nađene gornje ograde za taj broj.

Sažetak (engleski)

The problem of sorting with reverse prefixes is colloquially known as the pancake problem, and it is applied in scheduling processes in networks of parallel processors. The paper mathematically analyzes the problem, and presents the implementation of a software application that visually shows different variants of such sorting. It has recently been proven that the problem of sorting pancakes is an NP-difficult problem and the minimum number of steps required for sorting is still unknown, the upper fences for that number have just been found.

• Ključne riječi: Sortiranje palačinki; sortiranje reverznim prefiksima; permutacije; graf
• Ključne riječi (engleski): Pancake sorting; sorting by prefix reversals; permutations; graph
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:180583
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-15 09:45:38