8086-spyrnan 2001

Hin árlega hraðaksturkeppni 8086 forrita


Hin árlega keppni nemenda í Uppbyggingu tölva í að skrifa hraðvirk 8086 smalamálsforrit er nú að hefjast. Að þessu sinni er tengist verkefnið hinu sígilda reikniritaverkefni Union-Find. Verkefnið er fólgið í því að framkvæma tiltekinn fjölda samrunaaðgerða (Union) á mengi til að undirbúa leitun að stökum í menginu (Find). Nánari lýsing á aðferðinni er á Verkefnablaði 2 í Uppbyggingu tölva.

Fallið ykkar fær sem inntak bendi á 16-bita vektorinn id í DS:SI. Fjöldi staka í vektornum er 32000 og það gildi kemur sem viðfang í CX. Þið megið þó gera ráð fyrir því í ykkar kóda að vektorinn hafi 32000 stök. Sömuleiðis er fjöldi samruna 32000 og sú tala kemur niður í fallið í gistinu DX. Fallið má ekki hafa breytt neinum gistum þegar því er lokið. Í aðfalforritinu, sem ykkur verður gefið er 32-bita upphafsgildi slembitölugjafa lesið úr skránni SAEDI.DAT. Einnig er gefið fallið slmb(N) sem skilar slembitölu á bilinu 0 til N-1. Þið verðið að nota þetta fall til að fá slembitölur í keppnisfallinu ykkar. Það má ekki breyta aðalstefinu eða slembitölugjöfunum.

Quick-find er ekki besta aðferðin fyrir Union-Find verkefnið, en í þessari keppni verið þið að nota þá aðferð. Það má ekki nota hinar aðferðirnar sem skoðaðar voru í Tölvunarfræði 2, svo sem Quick-union, viktuðu útgáfuna af Quick-union eða path-compression útgáfuna.

Reglur:

  1. Öll dýrin í skóginum skulu vera vinir. Ekkert dýr má éta annað dýr.
  2. Fallið ykkar má ekki breyta neinum gistum. Ekki má breyta gefna aðalforritinu nema til að skilgreina víðvær minnissvæði. Aðeins má nota 8086 skipanir í forritinu.
  3. Öll vinnan við samruna stakana í vektornum verður að vera samkvæmt Quick-find aðferðinni.
  4. Keppnisstjóri er Hjálmtýr Hafsteinsson og sér hann um að taka tímann á forritunum, sem keyrð verða á Pentium II tölvu í nemendaveri tölvunafræðiskorar. Einnig úrskurðar hann um vafaatriði.
  5. Allir nemendur í Uppbygging tölva haustið 2001 mega taka þátt í keppninni, en aðrir tölvunarfræðinemar geta einnig tekið þátt sem gestir, en þeir geta þó ekki sigrað í keppninni.
  6. Sigurvegari keppninnar telst sá sem samdi forritið sem tekur stystan tíma og hlýtur hann (hún) aðdáun íturvaxinna kvenna (karla).

Tímamælingin fer fram í tölvuveri tölvunarfræðinema í kjallara Tæknigarðs 2 fimmtudaginn 25. október kl. 15:00. Allir sem áhuga hafa eru boðnir velkomnir.

hh@hi.is, október, 2001.