Greining algórişma
09.12.55


Lokapróf 4. maí 1994

Allar spurningarnar hafa sama vægi. Einungis şarf ağ svara 6 spurningum af 7. Bestu 6 svörin gilda.
Leyfileg hjálpargögn: Kennslubók (Sara Baase: Computer Algorithms). Fyrirlestranótur og heimadæmi.



1. Sıniğ ağ neğri mörk fyrir fjölda samanburğa til ağ finna samruna (merge) tveggja rağağra lista, a1, ..., an og b1, ..., bk, şar sem n > k eru
şar sem
Einfaldiğ yrğinguna ağ ofan á svipağan hátt og gert var í neğri mörkunum fyrir röğun (ş.e., losna viğ hrópmerkisağgerğina).



2. Gefiğ er graf G, sem er tré (ş.e., fjöldi stika er n-1 og şağ er samhangandi). Sıniğ línulegan algórişma sem finnur şann hnút v, sem gefur tré af minnstri hæğ ef hann er valinn sem rót.



3. Lát a1, ..., an vera heiltölur. Sıniğ algórişma sem finnur mengiğ S, şannig ağ
er lágmarkağ. Notiğ kvika bestun.



4. Í şjöppunaralgórişmanum LZW er haldiğ utan um orğasafn og strengirnir sem bætt er í orğasafniğ hafa formiğ pc, şar sem p er lengsti strengur sem fannst í orğasafninu og passaği viğ forstreng inntaksins og c er næsti stafur inntaksins şar á eftir. Hægt er ağ hugsa sér ağra ağferğ viğ ağ setja strengi inn í orğasafniğ. Strengnum pq er bætt inn, şar sem p er eins og ağ ofan, en q er nú líka lengsti strengur í orğasafninu sem passaği viğ inntakiğ á eftir p.
  1. Sıniğ şjöppun á strengnum "hallamallakalla".
  2. Hvağa kosti og galla hefur şessi útgáfa af LZ78?
  3. Ef viğ gerum ráğ fyrir ağ notağ sé trie gagnagrind fyrir orğasafniğ (eins og í LZW), hvernig verğur ağ ağlaga hana ağ şessari ağferğ?



5. Helmingunarleit í röğuğum n-staka vektor tekur O(log n) tíma, en şağ tekur O(n) tíma ağ setja inn nıtt stak. Viğ getum bætt úr şessu meğ nırri gagnagrind. Viğ notum allt ağ log n vektora, sem hver um sig er rağağur (şó óháğ hver öğrum) og eru allir af lengd, sem er heilt veldi af 2, en enginn şó af sömu lengd! Lısiğ slíkri gagnagrind og
  1. sıniğ hvernig best er ağ leita í slíkri gagnagrind og hver tímaflækjan er.
  2. sıniğ hvernig á ağ setja inn nıtt stak og greiniğ tímaflækju şess, bæği meğ versta-tilfellis greiningu og jafnağargreiningu.



6. Vandamál P er fullkomiğ fyrir flokk C, meğ tilliti til margliğutíma umbreytinga ef P stakí C og P' < P fyrir öll P'.
  1. Sıniğ ağ P < ~P şşaa ~P < P (~P er andhverfa vandamálsins P).
  2. Sıniğ ağ P er fullkomiğ fyrir flokkinn NP (ş.e. NP-complete) şşaa ~P er fullkomiğ fyrir co-NP.



7. Hanniğ samhliğa PRAM útgáfu af Boyer-Moore strengleitar algórişmanum. Nota á n/m gjörva, şar sem n er lengd textans og m er lengd orğsins sem á ağ finna. Geriğ fyrst ráğ fyrir ağ forvinnslan hafi fariğ fram og "charJump" og "matchJump" vektorarnir séu til stağar í gjörvunum. Ræğiğ síğan hvernig hægt sé ağ framkvæma forvinnsluna samhliğa.