Õppeaine 'Algoritmid ja andmestruktuurid'

Aasta:   2017/2018    2018/2019    2019/2020    

Tallinna Tehnikaülikool, ainekava TTÜ ÕIS-is: https://ois2.ttu.ee

Aine eesmärkideks on:
• teha üliõpilastele selgeks põhilised ideed, millede järgi andmekirjed on organiseeritud erineva ülesehitusega struktuuridesse ja salvestatud arvuti mällu;
• kirjeldada ja selgitada põhilisi algoritme, mida kasutatakse erinevates andmestruktuurides paiknevate andmetega teostatavates tüüpoperatsioonides (kirjete lisamine ja eemaldamine, soovitud kirje otsimine, sortimine jne.);
• tutvustada andmetöötlusega seotud teoreetilisi probleeme (abstraktsed tüübid, algoritmide keerukus jne.);
• parandada üliõpilaste praktilise programmeerimise oskust keeles C.

Eksami edukalt läbinud üliõpilased peaksid:
• tundma kõiki põhilisi andmetöötluses kasutatavaid andmestruktuure;
• tundma nende andmestrukuuridega töötamisel kasutatavaid põhilisi andmetöötlusalgoritme;
• teadma põhjusi, mis mõjutavad andmetöötluse kiirust;
• suutma valida mingi konkreetse probleemi lahendamiseks kõige sobivamad andmestruktuurid;
• suutma valida mingi konkreetse probleemi lahendamiseks kõige sobivamad andmetöötlusalgoritmid;
• suutma kirjutada C-keelseid programme, mis opereerivad keerukate andmestruktuuridega.

1. Täiendavat materjali C-keelest.
2. Andmestruktuurid ja andmetöötluse põhilised operatsioonid. Massiiv. Lingitud struktuurid.
3. Mõningad spetsiifilised andmestruktuurid: hõre maatriks, ringpuhver jne.
4. Abstraktsed andmetüübid: loend, magasin, järjekord, sõnastik.
5. Algoritmide efektiivsuse hindamine.
6. Rekursioon ja rekursiivsed algoritmid.
7. Järjestikotsimine ja kahendotsimine.
8. Kahendpuud. Puu tasakaalustatuse probleem. AVL-puud.
9. Iseorganiseeruvad puud.
10. B-puud ja puna-must puud. B*-puud.
11. Välismälus olevate andmetega seotud probleemid. B+ puud.
12. Digitaalne puu ja trie-puu. Eksistentsitabelid ja kolmikpuu.
13. Prioriteetidega järjekord ja kuhi. Vasakule kaldus puu. Binoompuu ja binomiaalne kuhi.
14. Paiskepaigutus. Paigustusfunktsioonide koostamise meetodid. Aheldamine ja avatud adresseerimine. Laiendatav paiskepaigutus.
15. Lihtsamad sortimise algoritmid. Shelli meetod. Sortimine mestimisega. Kiirsortimine. Sortimine kuhja abil. Jaotamisega sortimine.
16. Tekstist otsimise probleem. Boyer-Moore’i ja Rabin-Karpi meetodid.
17. Andmete pakkimine. Huffmani kood. Lempel-Zivi meetodi alused.
18. Algoritmide tüübid. "Jaga-ja-valitse" algoritmid. Dünaamilise programmeerimise põhimõtted. Ahned algoritmid. Randomiseeritud algoritmid.

2017: CNS*  

* Valikaine