Algoritmid ja andmestruktuurid (IFI6012.DT)
Õppeaine kood
IFI6012.DT
vana ainekood
IFI6012
Õppeaine nimetus eesti k
Algoritmid ja andmestruktuurid
Õppeaine nimetus inglise k
Algorithms and Data Structures
Õppeaine maht EAP
3.0
Orienteeruv kontakttundide maht
42
Õpetamise semester
sügis-kevad
Kontrollivorm
eksam
2019/2020 sügissemestri õppejõud
õppejõud on määramata
2019/2020 kevadsemestri õppejõud
õppejõud on määramata
Õppeaine eesmärgid
Aidata kaasa lineaarsete ja mittelineraasete andmestruktuuride tundmise ning nende praktilise rakendamisoskuse kujunemisele. Toetada probleemide analüüsi ja lahendusoskuse arenemist tuginedes erinevatele andmestruktuuridele ning kasutades sobilikke algoritme. Toetada praktilise programmeerimisoskuse kujunemist lihtsas imperatiivses viitade kasutamist lubavas keeles.
Õppeaine sisu lühikirjeldus
Dünaamilised loendid (ahelad). Lineaarsed andmestruktuurid – pinu, järjekord, ringjärjekord ja dekk, nende realiseerimine. Puu. Kahendpuu. Puude realiseerimine. Põhilised algoritmid puudel. Graaf. Graafide realiseerimine. Põhilised algoritmid graafidel - laiuti ja sügavuti otsimine, lühim tee, topoloogiline sorteerimine. Algoritmide keerukuse analüüsimine. Keerukusklassid. Algoritmimise strateegiad: algoritmid jõumeetodil, ahned algoritmid, jaga-ja-valitse, algoritmid tagurdusmeetodil, dünaamiline programmeerimine. O(N^2) ja O(N*log N) sorteerimisalgoritmid. Otsimine. Otsimiskahendpuu. AVL-puu. Puna-mustpuu. B-puu. Paisktabel. Paiskfunktsioonid. Kollisioonid ja nende lahendamine. Iseseisva tööna tuleb lahendada kolm probleemi ning esitada nende kohta programmid.
Iseseisev töö
Iseseisva tööna tuleb enne loengut materjaliga tutvuda ja teha endale selgeks põhimõisted.
Iseseisvate tööna teeb ja esitab üliõpilane 3 programmi, mis täpsemalt fikseeritakse praktikatundide jooksul. Programmide kvaliteet ei mõjuta eksami hinnet.
Õppeaine õpiväljundid
Kursuse läbinud üliõpilane:
Teab algoritmide analüüsimise, hindamise ja keerukusega seotud mõisteid.
Kirjeldab dünaamilisi ja staatilisi andmestruktuure ning nendel rakendatavaid algoritme.
Oskab analüüsida algoritme ja hinnata nende efektiivsust.
Oskab lihtsamate ja tüüpilisemate probleemide korral valida sobivat andmestruktuuri ja algoritmi sõltuvalt lahendamist vajavast probleemist.
Koostab imperatiivses viitade kasutamist lubavas programmeerimiskeeles programmi ülesannete lahendamiseks kasutades käsitletud algoritme.
Hindamismeetodid
Eksam.
Lõpphinne pannakse kirjaliku eksami põhjal. Eksamile pääsemise eelduseks on kodutööde esitamine ja kaitsmine.
Õppejõud
õp Inga Petuhhov
Kohustuslik kirjandus
Õppematerjalid kursuse veebilehel: http://www.cs.tlu.ee/~inga/alg_andm/;
Algoritmid ja andmestruktuurid. Kiho, J. 2003.
Asenduskirjandus
R. Sedgewick, Algorithms in C (Parts 1-5). 2002;
Ain Isotamm, Programmeerimine C-keeles ("Algoritmide ja andmestruktuuride" näiteil), TÜ, 2009.