is Íslenska en English

Lokaverkefni (Bakkalár)

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

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

Titill: 
  • Titill er á ensku Wilf-classification of mesh patterns of short length
  • Wilf-flokkun möskvamynstra
Námsstig: 
  • Bakkalár
Útdráttur: 
  • Útdráttur er á ensku

    This B.Sc. project deals with mesh pattern avoidance in permutations. A mesh pattern is a pair P=(p,R), where p is a permutation of length k and R is a subset of [0,k]x[0,k]. The elements of R denote filled boxes in a mesh pattern. For a permutation u to contain a mesh pattern, it has to contain the underlying classical pattern p, and no points in u can be located in the shaded boxes. In this paper we begin the study of Wilf-classifying mesh patterns by classifying 776 out of the 1024 mesh patterns of length 2. Two mesh patterns P and Q are said to be equivalent if for any permutation u, u avoids P if and only if u avoids Q. The paper introduces a new operation that preserves pattern equivalence and provides rules determining which additional boxes in a mesh pattern P can be shaded. This is useful to lower the number of patterns one needs to look at in the process of Wilf-classifying patterns. We also have some observations on the only non-trivial interval pattern of length 3.

  • Í þessu B.Sc. verkefni vinnum við með mynstraforðun möskvamynstra í umröðunum. Möskvamynstur er par P=(p,R) þar sem p er umröðun af lengd k og R er hlutmengi í [0,k]x[0,k]. Stökin í R tákna skyggða ferninga í möskvamynstrinu. Umröðun u er sögð innihalda möskvamynstrið P ef hún inniheldur grunnmynstrið p og engir punktar u eru inn í skyggðu ferningum mynstursins P. Í þessu verkefni hefjum við Wilf-flokkun möskvamynstra, þar með hafa 776 mynstur af 1024 verið Wilf-flokkuð. Tvö möskvamynstur P og Q eru sögð vera jafngild ef fyrir sérhverja umröðun u gildir að u forðast P ef og aðeins ef u forðast Q. Verkefnið kynnir nýja aðgerð sem varðveitir jafngildi mynstra og gefur reglur um hvaða ferninga í mynstri P má skyggja aukalega í möskvamynstri. Þessi aðgerð er hentug til að minnka fjölda þeirra mynstra sem þarf að skoða við Wilf-flokkun mynstra. Einnig höfum við skoðað eina bilamynstrið af lengd 3 sem er ekki augljóst, og setjum fram athugasemdir um það.

Athugasemdir: 
  • Heildartexti lokaskýrslu. Prentuð útgáfa og öll fylgi gögn á CD eru varðveitt í bókasafni HR
Samþykkt: 
  • 9.6.2011
URI: 
  • http://hdl.handle.net/1946/9181


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
Wilf-classification of mesh patterns of short length - post-mortem.pdf204 kBOpinnFylgiskjölPDFSkoða/Opna
Wilf-classification of mesh patterns of short length.pdf708,97 kBOpinnHeildartextiPDFSkoða/Opna