Algoritmid ja andmestruktuurid. Kordamisküsimused. Kevad 2024

Eksamitöö on kaheosaline - pooled punktid saab vastustest teooriaküsimustele ning pooled punktid paberil ülesannete lahendamisest - nagu oleme harjutustundides teinud. Materjalide kasutamine ei ole ette nähtud kummagi osa tegemisel. 

Teooriaküsimused
----------------
1. Algoritm. Algoritmi keerukus. Ajalise keerukuse asümptootiline hinnang. Keerukusklassid: klassi kirjeldus, näited vastavatest algoritmidest.

2. Algoritmimise strateegiate lühike iseloomustus ja kasutamise näide (dünaamiline programmeermine, tagurdusmeetod / backtracking).

3. Andmestruktuuri mõiste. Andmestruktuuri loogiline tase ja realisatsiooni ehk füüsiline tase. Staatiline ja dünaamiline realisatsioon. Realisatsiooni üldised põhimõtted.

4. Ühe viidaga ahelloendid. Peamised algoritmid ahelloendiga: elemendi lisamine, elemendi kustutamine, ahelloendi läbimine. Algoritmide selgitused tekstina ja joonistena. 

5. Pinu: omadused, operatsioonid. Näited pinu kasutamisest. Pinu realiseerimise (kuidas arvuti mälus üles ehitada) võimalused.

6. Järjekord: omadused, operatsioonid. Näited järjekorra  kasutamisest. Järjekorra realiseerimise (kuidas arvuti mälus üles ehitada) võimalused.

7. Puu. Üldine puu. Järjestatud ja järjestamata puu, puu järk jne - igasugused puuga seotud mõisted, mida siinkohal üles ei loetle.
 
8. Kahendpuu: omadused, operatsioonid. Puu realiseerimise võimalused arvutis (kuidas mälus välja näeb).

9. Graaf. Graafiga seotud mõisted, mida siinkohal kõiki üles ei loetle, näiteks suunatud ja suunamata graaf, atsükliline graaf, kaalutud graaf, tee, tsükkel jne. 

10. Graafi algoritmid: topoloogiline sorteerimine, laiutiotsing, süvitiotsing, lühim tee kaalutud graafis ehk Dijkstra algoritm. Algoritmide tööpõhimõtte kirjeldus koos väikese kasutusnäitega.

11. Kahendkuhi - kahendkuhja (binary heap) reeglid, kuidas kuhi realiseeritakse, milliste ülesannete jaoks sobib kasutada.

12. Sorteerimisülesanne - mis ta on? Lisamissorteerimine (insertion s.), sorteermine kuhjaga (heap s.), kiirsorteerimine (quicks.), ühildusmeetod (merge s.). Nimetatud meetodite kirjeldus, keerukusklass, tugevad ja nõrgad küljed, probleemid kasutamisel jne. Mõtle ka läbi näide algoritmi töö selgitamiseks.

13. Otsimisülesanne - mis ta on?. Jadaotsing. Kahendotsing. Mõlema meetodi kirjeldus, selgitav näide, keerukusklass. Mõtle ka läbi näide algoritmi töö selgitamiseks.

14. Kahendotsingupuu. Andmete lisamine, otsimine ja kustutamine, puuoperatsioonide keerukusklassid.
AVL-puu: mis ta on, omadused, kuidas töötab, milleks kasutatakse.

15. Paisksalvestusmeetod. Paisktabel. Paiskfunktsioon (jäägi meetod). Kollisisoonide lahendamine (ahelloendid väljaspool tabelit, avatud paisksalvestus ja erinevad sondeerimismeetodid). 
Andmete lisamine, otsimine ja kustutamine paiskmeetodil.

NB! Eksamiküsimused ei ole täpselt sel viisil sõnastatud ja on reeglina detailsemad. 

Praktiliste ülesannetena tuleb osata paberil konkreetsete andmetega läbi mängida 
--------------------------------------------------------------------------------
- kahendotsingupuu ehitamine ja sealt otsimine, tasakaalustamise vajaduse märkamine (tasakaalustada ei ole vaja, sest see nõuaks palju sodimist või joonistamisruumi) 
- kahendpuu läbimine kolmel erineval viisil (pre-, post- ja inorder), 
- graafi esitamine joonisena, külgnevus- ehk naabrusmaatriksina, naabrusahelloenditena,
- graafialgoritmid: laiutiosting ning selle pealt lühim tee, topoloogiline sorteerimine, 
- paiskmeetod: paisktabeli koostamine koos erinevate kollisioonilahenduste ja sondeerimistega ning otsing.