Algoritmid ja andmestruktuurid

Algoritmi mõiste, algoritmi omadused. Ajaline ja mahuline keerukus. Funktsioonide asümptootiline hindamine, algoritmianalüüs. Levinumad keerukusklassid.
Otsimine ja järjestamine. Lineaarne otsimine, kahendotsimine, paisktabel. Pistemeetod, kahendpistemeetod, mullimeetod, valikumeetod. Kiirmeetod, ühildamismeetod. Loendamismeetod, positsioonimeetod, kimbumeetod. Järjestamismeetodite võrdlus.
Abstraktsed andmetüübid. Pinu ja järjekord, eelistusjärjekord. Pööratud poola kuju. Ahel, ringahel, topeltseotud ahel. Viidastruktuurid.
Puu. Aritmeetilise avaldise puu. Puu läbimise meetodid (eesjärjestus, lõppjärjestus, keskjärjestus). Puu kujutamisviisid tekstina ja viidastruktuurina. Näited.
Graaf. Suunatud ja suunamata graaf. Multigraaf. Teed ja tsüklid. Lihtgraaf, atsükliline graaf. Tugev ja nõrk sidusus, sidususkomponendid. Maatriksesitused (külgnevusmaatriks ja lühimate teepikkuste maatriks). Graafide korrutamine, liitmine ja sulundid. Graafi kujutusviisid. Algoritmid graafidel: Floyd-Warshalli algoritm, topoloogiline järjestamine, Dijkstra algoritm. Graafi läbimine sügavuti ja laiuti. Sidususkomponentide leidmine, minimaalse toese leidmine.
Rekursioon: Hanoi torn, rekursiooni eemaldamine, sabarekursioon. Ammendav otsing: 8 lipu ülesanne, seljakotiülesanne, harude ja tõkete meetod.
Kahendotsimise puu, AVL puu, värvitud puu. B-puu, binomiaalpuu. Kahendkuhi, kuhjameetod.
Sõnealgoritmid: Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp.
Kodeerimine ja pakkimine. Huffmani ja Shannon-Fano meetodid. Ahned algoritmid.
Dünaamiline kavandamine, pikima ühise osasõne leidmine.
Algoritmide korrektsus: eel- ja järeltingimused, tsükliinvariandid. Nõrgima eeltingimuse meetod (Hoare'i meetod). Osaline ja täielik korrektsus, peatuvuse probleem.

Kursuse lõpetanu tunneb põhilisi andmestruktuure (pinu, järjekord, puu, graaf, paisktabel, jt.), nende omadusi ning nendega seotud algoritme ja tehnikaid (rekursioon, otsimine, järjestamine, andmestruktuuride läbimine, teede leidmine, dünaamiline kavandamine jt. ). Üliõpilane oskab hinnata algoritmide ajalist ja mahulist keerukust.
Üliõpilane tunneb programmeerimiskeelt Java ning sellega seotud töövahendeid ulatuses, mis lubab andmestruktuure ja algoritme efektiivselt realiseerida. Ta on võimeline koostama ja analüüsima algoritme ülesannete lahendamiseks kursusel käsitletud teemade piires. Üliõpilane oskab vormistada tehnilist aruannet oma individuaalülesande teemal, suudab töötada koos teiste programmeerijatega, tunneb koodistiili ja dokumenteerimise põhitõdesid ning on valmis end täiendama.