is Íslenska en English

Lokaverkefni (Meistara)

Háskólinn í Reykjavík > Tæknisvið / School of Technology > MSc Tölvunarfræðideild / Department of Computer Science >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/16282

Titill: 
  • Titill er á ensku Sorting operators and their preimages
Námsstig: 
  • Meistara
Útdráttur: 
  • Þessi ritgerð byggir á þeirri vinnu Claessons og Úlfarssonar sem snýr að reikniritum sem finna formyndir mynsturflokka undir staflaröðunarvirkjanum. Við skoðum einnig aðrar röðunaraðferðir, þ.e. röðun með stafla af takmarkaðri dýpt, röðun með biðröð, röðun með togstafla, innsetningarröðun og pönnukökuröðun, og gefum sambærileg reiknirit fyrir þær. Við kynnum einnig til sögunnar yfirmynstur sem gera okkur kleift að samræma framsetningu reikniritanna. Við sýnum jafnframt hvernig reiknirit Claesson og Úlfarssonar, fyrir formyndir staflaröðunar, er hægt að útfæra til þess að finna formyndir ákveðins flokks möskvamynstra. Þannig má sjálfvirknivæða sönnun á lýsingu þeirra umraðana sem hægt er að raða með þremur ítrunum af staflaröðun. Að lokum sýnum við hvernig samskeyting á staflaröðunar- og biðrararöðunarvirkjunum gefur reiknirit sem ákvarðar, á línulegum tíma, hvort umröðun innihaldi klassíska mynstrið 4312.

  • Útdráttur er á ensku

    This thesis extends previous work of Claesson and Úlfarsson (2012) on algorithms for computing the preimage of a pattern class under the stack-sort operator. We consider several other sorting operators, namely stacks of fixed depth, queues, pop-stacks, insertion sort and pancake sort, and find corresponding algorithms for them. We also introduce the notion of meta patterns that allow us to present these algorithms in a uniform way. Furthermore, we consider how Claesson's and Úlfarsson's original algorithm for stack-sort can be extended to find the preimage of a mesh pattern class. This enables us to give an automatic proof of the description of West-3-stack-sortable permutations. Finally we show how the combination of the stack-sort and queue-sort operators can be used to create a linear time algorithm for determining avoidance of the pattern 4312.

Samþykkt: 
  • 28.8.2013
URI: 
  • http://hdl.handle.net/1946/16282


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
HjaltiMagnusson-SortingOperatorsAndTheirPreimages.pdf671.46 kBOpinnHeildartextiPDFSkoða/Opna