ÍslenskaenEnglish

Aðilar að Skemmunni

Leit eftir:


LokaverkefniHáskólinn í Reykjavík>Tölvunarfræðideild>Lokaverkefni, BSc m/rannsóknaráherslu>

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

Titlar
  • en

    Wilf-classification of mesh patterns of short length

  • Wilf-flokkun möskvamynstra

Útgáfa
Maí 2011
Útdrættir
  • en

    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

Tölvunarfræði. Heildartexti lokaskýrslu. Prentuð útgáfa og öll fylgi gögn á CD eru varðveitt í bókasafni HR

Birting
9.6.2011


Skrár
NafnRaðanlegtStærðRaðanlegtAðgangurRaðanlegtLýsingRaðanlegtSkráartegund
Wilf-classificatio... .pdf208KBOpinn Fylgiskjöl PDF Skoða/Opna
Wilf-classificatio... .pdf725KBOpinn Heildartexti PDF Skoða/Opna