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/33586

Titill: 
  • Titill er á ensku Effective enumeration of permutation classes and their juxtapositions
  • Áhrifarík tölusetning umraðanaflokka og hliðsetningu þeirra
Námsstig: 
  • Meistara
Útdráttur: 
  • Útdráttur er á ensku

    We generalise the idea of greedily gridding permutations, introduced by Brignall and Sliačan, to help enumerate N × 1 grid classes by translating them to the language of tilings developed by Bean. We then use automatic methods to get proofs of the enumeration for several known 2×1 grid classes and some previously unknown ones. We develop an automatic method to obtain recurrence relations from proof trees obtained by CombSpecSearcher (Bean). This gives a polynomial time enumeration algorithm for every proof tree, including those where an explicit generating function has proven hard to find.

  • Við útvíkkum hugmynd Brignall og Sliacan um gráðuga flísalagningu umraðana sem notuð er til að auðvelda talningu á N x1 grindarklösum með því að þýða aðferðina yfir á tungumál flísana sem var hannað af Bean. Við notum síðan sjálfvirkar aðferðir til að sanna talningu á nokkrum þekktum 2x1 grindarklösum og þónokkrum óþekktum. Við þróum síðan sjálfvirka aðferð til að finna rakningarformúlur fyrir sönnunartré fundin af CombSpecSearcher. Þetta gefur margliðutímatalningu fyrir öll sönnunartré, einnig þau þar sem að það hefur reynst erfitt að finna beint framleiðnifall.

Samþykkt: 
  • 12.6.2019
URI: 
  • http://hdl.handle.net/1946/33586


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
msc_unnar_2019.pdf448.07 kBOpinnHeildartextiPDFSkoða/Opna