Algoritmid ja andmestruktuurid (IFI6228.DT)
Õppeaine kood
IFI6228.DT
vana ainekood
Õppeaine nimetus eesti k
Algoritmid ja andmestruktuurid
Õppeaine nimetus inglise k
Algorithms and Data Structures
Õppeaine maht EAP
6.0
Orienteeruv kontakttundide maht
56
Õpetamise semester
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 mittelineaarsete 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 C 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 lõpuni lahendada praktikatundides poolelijäänud ülesanded ning nõudmisel esitada need kontrollimiseks. Samuti tuleb enne loengut läbi töötada vastavad loengumaterjalid.
Õppeaine õpiväljundid
Kursuse läbinud üliõpilane:
Tunneb 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.
Lahendab ülesandeid, tuginedes käsitletud algoritmidele ja kasutades imperatiivset viitade kasutamist lubavat programmeerimiskeelt (keel C).
Hindamismeetodid
Eksam.
Lõpphinne kujuneb kirjaliku eksami põhjal. Eksamile pääsemise eelduseks on kontrolltöö sooritamine. Kontrolltööga kontrollitakse üliõpilase programmeerimisoskust ja programmeerimiskeele tundmist ning töö on arvestatud, kui selle eest kogutakse vähemalt 50% punktidest.
Õppejõud
Inga Petuhhov
Kohustuslik kirjandus
Õppematerjalid kursuse veebilehel: http://www.cs.tlu.ee/~inga/alg_andm/;
V. Leppikson, Programmeerimine C keeles. 1997
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.