Tölvunarfręši 2

Vikublaš 4


Ķ žessari viku (ž.e. 31. jan. - 4. feb.) mun Anna Ingólfsdóttir taka viš fyrirlestrunum. Ķ žeim veršur fjallaš um efni ķ köflum 1 og 2 ķ ašalkennslubók nįmskeišsins, Algorithms in C++ eftir Robert Sedgewick. Ķ kafla 1 veršur undirköflum 1.2 og 1.3 sleppt. Žaš sem eftir stendur er létt kynning sem er aušlesin. Kafli 2 veršur hins vegar ašalefni žessarar viku. Žar er fjallaš almennt um reiknirit og greiningu į žeim.

Ķ nęstu viku veršur sķšan haldiš įfram meš Algorithms-bókina og žį veršur fariš ķ tengda lista (e. linked lists).

Dęmatķmar žessa viku (1. og 2. feb.) verša ķ stofunum sem tilgreindar eru į stundatöflunum ykkar (Tfr. 2: H1: V-258, H2: V-155, Tfr.2a: H1: V-138, H2: V-138).

Skiladęmi 4

Leysiš eftirfarandi dęmi og skiliš ķ hólf dęmatķmakennara ykkar fyrir kl. 12:00 mįnudaginn 7. febrśar. Žeir taka ekki viš dęmum sem koma seinna.

  1. Beriš saman tķmann sem žaš tekur aš kalla į lausbundna (e. virtual) ašferš og fastbundna (ž.e. venjulega ašferš). Smķšiš tvo klasa sem hafa eina lausbundna ašferš og ašra fastbundna. Ef žiš lįtiš ašferširnar gera eitthvaš mjög einfalt, t.d. hękka teljara, žį fįiš žiš raunhęfari męlingu į muninum į žessum tveimur geršum ašferša. Til aš męla tķman getiš žiš notaš falli clock() sem skilgreint er ķ safninu time.h. Hér er dęmi um notkun į žvķ. Žaš er lķklegt aš žiš žurfiš aš kalla a.m.k. 10 milljón sinnum į ašferširnar til aš fį męlanlegan mun, en žaš getur fariš eftir tölvugeršum, gerš ašferšanna og fleiru.

  2. Helstu virkjar sem žaš getur borgaš sig aš yfirhlaša (e. operator overloading) ķ venjulegum klösum eru samanburšarvirkjarnir ( <, <=, >, >=, ==, != ). Yfirhlašiš žessa virkja ķ Cat klasanum (notiš t.d. forriti 6.4 sem grunn) og lįtiš aldur kattanna rįša nišurstöšu samanburšarins. Hér aš nešan er haus eins af sambanburšarvirkjunum:
          bool operator< ( Cat &rhs );
      
    Ķ žessu tilviki į skilagildiš aš vera sanngildi žess aš aldur "okkar" kattar sé minni en kattarins rhs. Setjiš alla sex samanburšarvirkjana ķ Cat klasann.

  3. Dęmi 2.10 į bls. 43 ķ Algorithms-bók.
    [Žżšing: Bętiš dįlkum viš Töflu 2.2 fyrir N(lg(N))2 og N3/2. ]

  4. Dęmi 2.20 į bls. 47 ķ Algorithms-bók.
    [Žżšing: Sanniš aš O(1) er žaš sama og O(2). ]

  5. Sżniš aš log10(n) er O(log2(n))

Žeir sem vilja fį ašeins meiri ęfingu ęttu aš reyna viš eftirfarandi dęmi. Lausnirnar į žeim öllum eru tiltękar, annars vegar į gömlum heimasķšum nįmskeišsins og hins vegar aftast ķ C++ kennslubókinni. Ef žiš viljiš fį nįnari śtskżringar į lausnunum žį getiš žiš spurt um žęr ķ dęmatķmunum.
hh (hja) hi.is, 31. janśar, 2005.