IFI6228.DT Algoritmid ja andmestruktuurid

EAP: 6.0
Hindamisviis: Eksam
Õppejõud: õpetaja Inga Petuhhov
Toimumisaeg: kevadsemester 2024
Eeldusaine: Programmeerimise alused (kui aine sooritamata, siis vähemalt teadmised programmeerimise põhimõtetest)

Soovitused

Lõpeta kodus see, mis tunnis pooleli jäi. Vajadusel küsi konsultatsiooni.
Arvesta, et loengus kuuldut või harjutustunnis läbitehtut läheb varem või hiljem praktikumis vaja.
Soovitav on loengute materjalid (slaidid ja pikem tekst) enne loengut läbi lugeda, et kergem jälgida oleks.
Kuid hiljemalt peale loengut või harjutust tuleb vastav info läbi töötada, mõtelda läbi mõisted ja lahendada lõpuni ka paberil tehtud ülesanded.
C-keelt me ei näri lause haaval läbi. Eeldan, et Programmeerimise alustes läbivõetud põhitõed ning ka teistest programmeerimise kursustest omandatud on selged ning Sa oled võimeline neid teadmisi uue keele kontekstis rakendama.
Ja seda rohkem tuleb pingutada uutest asjadest arusaamisega, näiteks viitmuutujad, uued algoritmid, erilisemad andemstruktuurid.
Saada oma lahendusi vaatamiseks-kommenteerimiseks!

Kontrolltöö

Eksamile pääsemise eelduseks on kontrolltöö edukas sooritamine. Tööga kontrollitakse arusaamist C-keelest ja viitmuutujatest.
Kontrolltöö on kohustuslik kõigile üliõpilastele. Ka korduskuulajatele!!
Kontrolltöö toimub 22. ja 24. aprillil praktikumi ajal.

Eksam

Eksam toimub eksamisessioonil. Eksamiga kontrollitakse arusaamist uuritud algoritmidest ja andmestruktuuridest ja nendega seotud mõistetest.

Tunnid ja materjalid

Nädal	Teemad ja materjalid	Tunnitööd
Praktika 5., 7.02.24	Sissejuhatus kursusele. Keel C ja tema süntaks. Lihtsamate (tuttavate) programmide koostamine.	Slaidid Tunnitöö Palun jätka kindlasti kodus!
Loeng 8.02.24	Viidad C-s. Dünaamiline mäluhaldus. Loend, ahelloend. Pinu. Järjekord. Loenditele pühendatud loengumaterjal Pinu, järjekord jt lineaarsed struktuurid. Loengumaterjal	Slaidid
Praktika 12., 14.02.24	Lahendame ülesandeid C-keeles. Massiivid.	Tunnitöö Sissejuhatus Vim'i kasutamisse
Harjutus 15.02.24	Viitmuutuja mõiste. Ahelloendite algoritmid. Ülesanded pinu ja järjekorraga. Linked List Basics (lisalugemist loenditest)	Harjutus
Praktika 19., 21.02.24	Viitmuutujad. Viitmuutujate kasutamine ahelloendite ehitamiseks	Tunnitöö
Loeng 22.02.24	Algoritmide keerukus. Loengumaterjal	Slaidid Paar ülesannet
Praktika 26., 28.02.24	Ülesanded ahelloenditega. Märgid ja stringid. Pinu.	Tunnitöö
Loeng 29.02.24	Puud üldiselt. Põhilised algoritmid puudel. Loengumaterjal	Slaidid Ülesanne
Praktika 4., 6.03.24	Pinu. Järjekord. Ringjärjekord.	Tunnitöö
Harjutus 7.03.24	Puuülesannete arutelu.	Ülesanded Programm loomad on kompileeritud Linuxis.
Praktika 11., 13.03.24	Puuülesanne.	Tunnitöö Morsekood 1 ja Morsekood 2
Loeng 14.03.24	Graaf. Graafide realiseerimine. Põhilised algoritmid graafidel. Loengumaterjal	Slaidid
Praktika 18., 20.03.24	Puu. Ülesanded	Tunnitöö Meenutus harjutustunnist: loomapuu selgitus.
Harjutus 21.03.24	Graafiülesannete arutelu. Graafi esitamine. Laiuti otsing.	Harjutustunni ülesanded Nimetatud tööfailid on siin
Praktika 1., 3.04.24	Graaf. Ülesanded.	Tunnitöö
Harjutus 4.04.24	Graaf. Süviti otsing, toesepuu	Tunnitöö Nimetatud tööfailid on siin Dijkstra algoritmi ingliskeelne kirjeldus ja lühem eestikeelne kirjeldus Dijkstra algoritmi animatsioon
Praktika 8., 10.04.24	Graaf. Ülesanded.	Tunnitöö Eesti teede kaart
Loeng 11.04.24	Otsing. Kahendotsingupuu. AVL-puu. Puna-mustpuu. B-puu. Loengumaterjal	Slaidid
Praktika 15., 17.04.24	Graaf	Tunnitöö
Harjutus 18.04.24	Kahendotsingupuu. AVL-puu.	Ülesanded Puna-musta puu animatsioon
Praktika 22., 24.04.24	Kontrolltöö C-keelest (eksami eeldus).	Kontrolltöö - viitade joonistamise näide: programm ja joonis. Programmi lähteülesande näidis.
Loeng 25.04.24	Algoritmimise strateegiad Strateegiate materjal	Ülesanded Kassa testid Valimiste testid
Praktika 29.04.24	Dünaamiline planeerimine ja teised algoritmimise strateegiad.	Ülesanded
Loeng / harjutus 2.05.24	Paiskadresseerimine otsingumeetodina. Paisketabel. Paiskefunktsioonid. Kollisioonid ja nende lahendamine. Loengumaterjal	Slaidid Ülesanded harjutamiseks
Praktika 6., 8.05.24	Sorteerimine. Loengumaterjal	Tunnitöö Uurimiseks: Sorting Algorithm Animations Mõned sorteerimised tantsuvormis
Loeng / harjutus 9.05.24	Paiskadresseerimine otsingumeetodina.	Jätkame sealt, kus nädal tagasi pooleli jäi. Vt eelmise nädala faile!
Praktikum 13, 15.05.24	Paiskadresseerimine.	Tunnitöö
16.05.24	Konsultatsioon

C näited.

Lahendusi

Kõik ülesanded saavad olema siin.

Loengumaterjalid (PDF-formaadis)

Loendid, ühe ja kahe viidaga ahelloendid
Pinu ja järjekord
Üldiselt puudest
Rekursioon
Graaf
Algoritmide keerukus
Sorteerimisalgoritmid
Eelistusjärjekord
Otsing. Kahendotsingupuu
Paiskmeetod
Stringide otsimine (beeta)
Algoritmimise strateegiad

Lingikogu

Järgnev raamat sobib C-ga tutvumiseks eesti keeles: Programmeerimiskeel C (Veiko Sinivee)

Ingliskeelne õpetus, sisaldab ka meie kursuse spetsiifilist materjali.

Ingliskeelne C Programming wikibook

Ingliskeelne raamat: Tim Bailey, An Introduction to the C Programming Language and Software Design
A. Isotamm Programmeerimine C-keeles: algoritmide ja andmestruktuuride näidetel
J. Kiho Algoritmid ja andmestruktuurid

Inglisekeelsed rohkete näidetega töölehed C keelest
Jaagup Kippari koodinäited
The C Library Reference Guide

Õppematerjal viitadest ja massiividest C-s by Ted Jensen A TUTORIAL ON POINTERS AND ARRAYS IN C

Erinevatest teksti kodeeringutest (UTF-8 kasutamine)

Viitadest, ahelatest ja puudest Stanfordi ülikooli veebis. Lõbusad animatsioonid viitmuutujatest (pointer) (keeled: C, Java ja Pascal).

Algoritmide ja andmestruktuuride materjal Aucklandi ülikooli veebist
Dictionary of Algorithms and Data Structures
Algoritmide keerukusest eesti keeles
Lineaarsetest struktuuridest eesti keeles

Tarkvara

Programmeerimiseks kasutame C keelt (plussideta) ja gcc kompilaatorit. Töökeskkonnana võib kasutada CodeBlocks'i. NB! Windowsi jaoks laadi alla codeblocks-20.03mingw-setup.exe, mis sisaldab ka C kompilaatorit.
Oleme kasutanud ka DevCpp'd.
Õige C-fänn kirjutab aga koodi Linuxis (näiteks greeny's) vim-iga. ;)