IAS0090 Algoritmid ja andmestruktuurid

Nädalavaade

• Üldine
  • 

    Sissejuhatus kursusele IAS0090 "Algoritmid ja andmestruktuurid" Lehekülg
  • 

    Ainekava (ÕIS) URL
  • 

    Laiendatud ainekava Fail
  • 

    Õppejõu teadaanded Foorum
  • 

    Kursusel osaleja foorum (küsi nõu õppejõult või teistelt osalejatelt)
  • 

    Tagasiside
  • 

    Praktikum Fail

    Praktikumiks saab iga üliõpilane eritüübilisi objekte sisaldava ning viitadega ühendatud  andmestruktuuri skeemi, *.h failid kõigi vajalike  deklaratsioonidega ja  *.obj failid lähtestruktuuri genereerivate funktsioonidega. Üliõpilase ülesandeks on kirjutada 6 etteantud prototüübiga C funktsiooni, mis võimaldavad andmete otsimist ja  lähtestruktuuri modifitseerimist. Töövahendiks on Microsoft Visual Studio.

    Üksikasjaline kirjeldus, tulemuste arvestamine ja nende mõju eksamil on toodud lisatud failis.
    

• Nädal 1: eeltest

  Eeltesti eesmärgiks on välja selgitada kursuset osavõtjate teadmiste ja praktiliste oskuste tase C-keelse programmeerimise alal. Õppejõud vajab neid andmeid selleks, et näha, milliseid lünki tuleb täita. Üliõpilastel tuleb kirjalikult vastata 10-le küsimusele ja kirjutada lühike kuid keskmise raskusastmega C funktsioon. Testi tulemusi ei hinnata ja neil ei ole mitte mingit mõju eksamile. Nii küsimused kui ka ülesande tekst esitatakse õppejõu poolt loengu algul. Osavõtt on kohustuslik.
  

• Nädalad 2, 3 ja 4

  1. Kursuse eesmärkide selgitus.
  2. Põhilised terminid.
  3. Ülevaade andmestruktuuridest ja andmetöötluse põhilistest operatsioonidest.
  4. Eeltesti käigus ilmenud teadmiste ja oskuste lünkade täitmine, kusjuures  rõhk on sellel, mis on vajalik praktikumi edukaks läbiviimiseks.  Sõltuvalt eeltesti tulemustest  on võimalikeks teemadeks:
  • Muutujate nähtavus ja eluiga
  • Viidad ja dünaamiline mälujaotus
  • Viitade aritmeetika
  • Stringid
  • Kirjed (C terminoloogias struct ja union)
  5. Massiivid ja operatsioonid nendega
  6. Ahelloendid ja operatsioonid nendega
  7. Mõningad spetsiifilised andmestruktuurid (hõre maatriks, ringpuhver, jne.)

  Nädalal 4 jaotatakse välja individuaalsed praktikumi ülesanded ja algab nende lahendamine.

  Vajalikud õppematerjalid on lisatud pdf-failis.

  
  

  
  

  
  

  Fail: 1

• Nädal 5
  1. Abstraktse andmetüübi mõiste
  2. Lineaarsed abstraktsed andmetüübid: loend. magasin, järjekord, sõnastik.
  3. Algoritmide efektiivsuse hindamine
  • Keskmise juhu analüüs
  • Halvima juhu analüüs
  • Kasvukiiruse mõõtmine

  
  

  Vajalikud õppematerjalid on lisatud pdf-failis
  

  Fail: 1

• Nädal 6
  1. Rekursioon ja rekursiivsed algoritmid
  2. Lihtsad otsimise algoritmid
  3. Kahendotsimine

  
  

  Vajalikud õppematerjalid on lisatud pdf-failis
  

  Fail: 1

• Nädalad 7 ja 8
  1. Puud ja kahendpuud
  2. Andmetöötluse operatsioonid kahendpuudega
  3. Puu tasakaalustatuse probleem
  4. AVL-puud
  5. Puu pööramise operatsioonid
  6. Iseorganiseeruvad puud

  
  

  Vajalikud õppematerjalid on lisatud pdf-failis
  

  Fail: 1

• Nädal 9

  1. B-puud ja andmetöötluse operatsioonid nendega
  2. Puna-mustad puud
  3. B*-puud  ja andmetöötluse operatsioonid nendega
  4. Opereerimine failides paiknevate kirjetega.
  5. Indekseeritud jadafailid
  6. B+-puud  ja andmetöötluse operatsioonid nendega

  
  

  Vajalikud õppematerjalid on lisatud pdf-failis

  
  

  Fail: 1

• Nädal 10
  1. Võtme dekomponeerimisega ehitatud puud ja andmetöötluse operatsioonid nendega:
  • digitaalne puu
  • trie-puu
  2. Eksistentsitabelid
  3. Kolmikpuu

  
  

  Vajalikud õppematerjalid on lisatud pdf-failis
  

  Fail: 1

• Nädal 11

  Prioriteetidega järjekorra realisatsioonid ja andmetöötluse operatsioonid nendega:

  • ülespoole järjestatud puu
  • kuhi
  • vasakule kaldus puu.
  • binoompuu ja binomiaalne kuhi. .

  
  

  Vajalikd õppematerjalid on lisatud pdf-failis.

  
  

  Viimane võimalus saada täisarv punkte esimese, teise ja kolmanda ülesande eest.

  
  

  Fail: 1

• Nädal 12
  1. Paisksalvestuse põhimõte ja probleemid
  2. Paigustusfunktsioonide koostamise meetodid.
  3. Aheldamine
  4. Avatud adresseerimine:
  • lineaarne proovimine
  • kahekordne paisksalvestus
  5. Laiendatav paisksalvestus

  
  

  Vajalikud õppematerjalid on lisatud pdf-failis
  

  Fail: 1

• Nädal 13

  1. Primitiivsed sortimise algoritmid:
  • jaotamisega sortimine
  • vahelepanekuga sortimine
  • mullmeetod 
  2. Shelli meetod.
  3. Sortimine mestimisega.
  4.  Kiirsortimine.
  5. Sortimine kuhja abil.
  6. Jaotamisega sortimine.

  
  

  Vajalikd õppematerjalid on lisatud pdf-failis

  
  

  Fail: 1

• Nädal 14

  1. Tekstist otsimise probleemid
  2. Boyer-Moore’i meetod
  3. Rabin-Karpi meetod
  4. Sõnade otsingupuu

  
  

  Vajalikud õppematerjalid on lisatud pdf-failis

  
  

  Fail: 1

• Nädal 15
  Lehekülg: 1 Fail: 1

• Nädal 16

  1. Algoritmide tüübid.
  2. "Jaga-ja-valitse" algoritmid.
  3. Dünaamilise programmeerimise põhimõtted.
  4. Ahned algoritmid.
  5. Randomiseeritud algoritmid..

  
  

  Viimane võimalus praktikume kaitsta.