Eksamil tuleb

• teada järgmisi definitsioone:
• Algoritmi ajaline keerukus. Suur O, Teeta ja Oomega.
• Algoritmi amortiseeritud keerukus. Potentsiaali mõiste.
  
• Puu. Kahendpuu. (Suunatud) graaf.
• Puu naturaalesitusele vastav kahendpuu.
• Dünaamiline järjend. Magasin. Järjekord.
• Kahendotsimise puu.
• AVL-puu.
• m-rajaline otsimispuu. B-puu.
• Kuhjaomadus puus.
• Binomiaalpuu. Binomiaalkuhi.
• Sorteerimismeetodi stabiilsus.
• Sõne. Alamsõne. Sõne pikkus. Alamsõne esinemine teatavas positsioonis. Prefiks. Sufiks. Osasõne.
  
• Prefiksfunktsioon.
• Kood. Prefikskood. Koodi kujutamine kahendpuuna. Huffmani kood.
  
• Graafi aluspuu. Graaif minimaalse kaaluga aluspuu.
• Kahe tipu vaheline kaugus graafis.
• Suunatud tsükliteta graaf. Graafi tippude topoloogiline järjestus.
• Tugevalt sidus graaf.
• Graafi tugevalt sidusad komponendid ja komponentgraaf.
  
• detailselt teada järgmisi algoritme ja andmestruktuure:
• Puu ja kahendpuu naturaalesitused.
• Puu läbimine eesjärjestuses ja lõppjärjestuses.
• Kahendpuu läbimine keskjärjestuses.
• Graafi kujutamine mälus tippude ahela ja igast tipust väljuvate servade ahelate abil.
• Graafi läbimine laiuti ja sügavuti.
• Otsimine kahendotsimise puust ja lisamine sinna.
• Otsimine m-rajalisest otsimispuust.
• Kahendkuhi. Esitus massiivina. Mis operatsioone toetab? Operatsioonide realisatsioonid. Operatsioonide keerukused.
• Kahendpuu teisendamine kahendkuhjaks.
• Sorteerimine pistemeetodil.
• Sorteerimine kiirmeetodil.
• Randomiseeritud kiirmeetod.
  
• Sorteerimine ühildusmeetodil.
• Sorteerimine kuhjameetodil.
• Sorteerimine loendamismeetodil ja positsioonimeetodil.
• Mida sorteeritavate elementide kohta eeldavad?
• Rabin-Karpi alamsõne otsimise algoritm.
• Bellman-Fordi algoritmi lühimate teede leidmiseks graafi ühest tipust teistesse tippudesse. Nende teede pikkuste ja nende teede eneste leidmine.
• Dijkstra algoritm lühimate teede leidmiseks graafi ühest tipust teistesse tippudesse.
• Lühimate teede pikkuste leidmine graafi kõigi tipupaaride vahel graafi naabrusmaatriksi korduva ruututõstmise teel.
• Floyd-Warshalli algoritm lühimate teede pikkuste leidmiseks graafi kõigi tipupaaride vahel.
• Graafi tippude topoloogiline sorteerimine.
• Klasside kujutamine. Toetatavad operatsioonid ja nende keerukused.
  
• Operatsioonide keerukushinnangute tõestusi ei ole vaja teada.
• Paisktabel.
  
• Välisahelate meetod põrgete lahendamiseks. Toetatavad operatsioonid ja nende keerukused.
• Lahtise adresseerimise meetod põrgete lahendamiseks. Toetatavad operatsioonid ja nende keerukused.
• Topeltpaiskamine.
  
• teada järgmiste algoritmide ja andmestruktuuride töötamispõhimõtteid:
• Kustutamine kahendotsimise puust.
• AVL-puu muutmisoperatsioonid.
• B-puu muutmisoperatsioonid.
• Sorteerimismeetodi stabiliseerimine.
• Sorteerimine kimbumeetodil.
• Mida sorteeritavate elementide kohta eeldavad?
• k-nda elemendi leidmine n-elemendilisest massiivist randomiseeritud kiirmeetodiga sarnasel viisil.
• Deterministlik kiirmeetod keerukusega O(n log n).
• Knuth-Morris-Pratti alamsõne otsimise algoritm. Prefiksfunktsiooni arvutamine.
• Boyer-Moore'i alamsõne otsimise algoritm. Kasutatavad heuristikad.
• Huffmani koodide leidmine.
• Kahe sõne pikima ühise osasõne leidmine dünaamilise algoritmiga.
• Kruskali ja Primi algoritmid graafi min. kaaluga aluspuu leidmiseks.
• Lühimate teede leidmine graafi ühest tipust teistesse tippudesse, kui on antud nende teede pikkused.
• Johnsoni algoritm lühimate teede pikkuste leidmiseks graafi kõigi tipupaaride vahel.
• Lühimate teede leidmine suunatud tsükliteta graafi mingist tipust teistesse tippudesse.
• Graafi tugevalt sidusate komponentide leidmine.
• Kahe sirglõigu lõikumise kontroll.
• Punktihulga kumera katte leidmine Grahami seiremeetodil ja Jarvise mähkimismeetodil.
• Teineteisele lähima punktipaari leidmine punktihulgast.
• Tuleb ka osata põhjendada, et "keskmise" riba läbivaatamisel piisab, kui kontrollime iga punkti kaugust ainult kuuest talle järgnevast punktist.
• Punkti hulknurka kuulumise kontroll.
• Punkti kumerasse hulknurka kuulumise kontroll.
• Hulknurga pindala leidmine.
  
• teada järgmiste algoritmide ja andmestruktuuride olemasolust ning vastavate operatsioonide keerukusi:
• Binomiaalkuhja toetatavad operatsioonid ja nende keerukused.
• k-nda elemendi leidmine n-elemendilisest massiivist lineaarses ajas.
• Kahe vektori suuna võrdlemine (üks on teisest paremal/vasakul).
• Kontrollimine, kas antud sirglõikude hulgas leidub teineteist lõikavaid lõike.
• Teineteisest kaugeima punktipaari leidmine punktihulgast.
  
• teada järgmisi teoreeme koos tõestustega:
• Sorteerimismeetodite keerukused (halvimal juhul).
• Elementide võrdlemisel põhineva sorteerimise keerukuse alamtõke.
• Kasutatavat arvutusmudelit tuleb osata täpselt kirjeldada.
  
• Vajalike võrdlemiste arv massiivi minimaalse elemendi leidmiseks.
• Knuth-Morris-Pratti algoritmi keerukus.
• Graafi kahe tipu vahelise lühima tee leidmise ülesande optimaalne alamstruktuur.
  
• teada järgmiste teoreemide sõnastusi:
• AVL-puu kõrgus on logaritmiline tema tippude arvu suhtes.
• Kahendpuu kuhjastamise keerukus.
• Randomiseeritud kiirmeetodi keerukus.
• Loendamis- positsiooni- ja kimbumeetodil sorteerimise keerukus.
• Vajalike võrdlemiste arv massiivi minimaalse ja maksimaalse elemendi üheaegseks leidmiseks.
• Graafi komponentgraaf on suunatud tsükliteta.
  
• osata materjale kasutades lahendada järgmist tüüpi ülesandeid:
• Praktikumis tehtud ülesanded...
• Algoritmide keerukuse ja/või amortiseeritud keerukuse leidmine (näide).
• Alternatiivne sõnastus: tõesta, et antud algoritmil on järgmine (amortiseeritud) keerukus.
• Potentsiaali kohta võib olla antud vihjeid.
• Muuhulgas tuleb osata
• suurte O-de, Teetade ja Oomegatega arvutada,
• põhiteoreemi kasutada.
• Teatavate ülesannete lahendusalgoritmide keerukuse alamtõkete leidmine, kui lahenduses tohib kasutada ainult teatud tüüpi operatsioone (näide).
• Vihjeid võib olla antud selle kohta, kuidas oraakel käituma peab, et lahendaja võimalikult palju tööd tegema peaks.
• Dünaamilise programmeerimise ülesannete lahendamine (näide).
• Alamülesannete ruumi kohta võib olla antud vihjeid.
• Ahnete algoritmide koostamine ülesannete jaoks, millel sellised algoritmid leiduvad (näide).
• Ahne valiku kohta võib olla antud vihjeid.
• Tuleb osata tõestada, et tehtud ahne valik korrektse algoritmi annab.
• Ülesannete taandamine loengutes uuritud ülesannetele.
• Näiteks lühimate teede leidmisele mingis graafis.
  
• Programmide korrektsuse formaalne tõestamine.
• Näiteid: minimaalse / maksimaalse elemendi leidmine massiivist, massiivi elementide summa leidmine. Iteratiivsed ja rekursiivsed algoritmid nende jaoks.
• Võib (aga ei pruugi) olla antud vihjeid tsükliinvariantide kuju kohta.