Tölvunarfræði 2 - Vor 2012


Lokapróf


Lokaprófið verður haldið mánudaginn 7. maí kl. 09:00-12:00.

Engin hjálpargögn verða leyfileg í lokaprófinu (closed book exam).

Á lokaprófinu verða 17 dæmi og 10 bestu gilda. Öll dæmin hafa sama vægi.

Efni sem er ekki til prófs: Bottom-up mergesort, Shunting-Yard, Knuth Shuffle, make, gdb, aukaverkefni 4, dæmi 4 í V10 (forgangsbiðröð byggð á hrúgu með hlekkjum)

Helsta efni til prófs:

  1. Grunnatriði í C og Java

    Munurinn á minnismeðhöndlun í C og Java. Bendar í C.

  2. Öll heimaverkefni

  3. Rökstudd forritun

    Notkunarlýsingar. Forskilyrði. Eftirskilyrði. Fastayrðingar fyrir lykkjur. Fastayrðingar gagna fyrir gagnamót.

    Lesefni: Glærur, öll verkefni og sýnidæmi.

  4. Reiknirit fyrir röðun

    Selection sort. Insertion sort. Quicksort. Skipting í Quicksort. Quickselect og miðgildi. Top-down mergesort. Heapsort. Radix sort. Counting sort.
    Fastayrðingar og tímaflækjur fyrir allar aðferðirnar.

    Lesefni: Glærur, kaflar 2.1, 2.3 og 2.4 í kennslubókinni

  5. Reiknirit fyrir leit í fylki

    Línuleg leit í fylki. Helmingunarleit í fylki. Fastayrðingar, útfærslur og tímaflækjur.

    Lesefni: Glærur og kafli 1.4 í kennslubókinni.

  6. Fylki og tengdir listar

    Fylki. Eintengdir listar. Tvítengdir listar. Hringtengdir listar. Aðgerðir og tímaflækjur.

    Lesefni: Glærur, verkefni og kóði.

  7. Hlaðar og biðraðir

    Hugræn (abstract) skilgreining þeirra. Mögulegar útfærslur og fastayrðingu gagna fyrir þær. Tímaflækja aðgerða í mismunandi útfærslum.

    Lesefni: Glærur og kaflar 1.2 og 1.3 í kennslubókinni.

  8. Forgangsbiðraðir

    Hugræn (abstract) skilgreining. Útfærsla með fylki í engri röð. Útfærsla með fylki í röð. Útfærsla með fylki í hrúgu röð. Tímaflækja aðgerða í hverri útfærslu.

    Lesefni: Glærur og kafli 2.4 í kennslubókinni.

  9. Leitartré

    Tvíleitartré. Leitartré í jafnvægi. 2-3 tré. Rauð-svört tvíleitartré (útgáfuna sem við fórum yfir, þ.e. left leaning red-black trees). Aðgerðir í tvíleitartré. Fastayrðingar, útfærslur og tímaflækjur.

    Lesefni: Glærur og kaflar 3.1, 3.2 og 3.3 í kennslubókinni.

  10. Tætitöflur

    Tæting. Tætitafla með keðjum. Tætitafla með línulegri könnun. Tímaflækja aðgerða.

    Lesefni: Glærur og kaflar 3.4 og 3.5 í kennslubókinni.

  11. Tries

    R-way tries. TST. Aðgerðir í tries og hagnýting þeirra.

    Lesefni: Glærur, kóði og kafli 5.2 í kennslubókinni.

  12. Skopplistar

    Skilgreining skopplista og grunnatriði í útfærslu. Fastayrðing. Tímaflækja aðgerða.

    Lesefni: Glærur og kóði.

  13. Net

    Hugtök um net. Aðferðir til að geyma net, sem fylki eða sem lista. Depth first search (DFS). Breadth first search (BFS). Þáttun (Connected Components).

    Lesefni: Glærur og kafli 4.1 í kennslubókinni


Við undirbúning fyrir prófið getur verið gagnlegt að reikna gömul próf:

Ofangreind próf eru frá öðrum kennara (Snorra) og áherslurnar eru því ekki endilega þær sömu. Við undirbúning er því rétt að velja sérstaklega dæmi úr prófunum sem tengjast því efni sem er á listanum yfir námsefni til prófs.