A. Juozapavičius: "Duomenų struktūros ir algoritmai"

Dalyko turinys:

Šis dalykas yra apie algoritmus – algoritmus, kaip jie yra konstruojami ir naudojami kompiuterinių skaičiavimų praktikoje. Algoritmai reiškia aibę instrukcijų, kurias taikant kokiam nors procesui pradiniai duomenys yra perdirbami ir paverčiami baigtiniais duomenimis.
Algoritmo sąvoka, iš pradžių gana abstrakti ir universali, iškilusi daugiausia matematinėse disciplinose, labai pasikeitė, atsiradus kompiuteriams. Pasikeitė ir algoritmų svarba, jie tapo kompiuterių valdymo ir darbo pagrindu, algoritmai išsiliejo į teoriją, sudarančią atskirą tyrimų ir praktinės veiklos sritį. Ši sritis formaliai aprašo platų svarbių ir vis labiau plintančių procedūrų spektrą, naudojant algoritmų teoriją lingvistikoje, ekonomikoje, smegenų fiziologijoje, gamtos moksluose, o taip pat kompiuteriu sprendžiant inžinerijos, kompiuterinės grafikos, informacijos valdymo, skaitmeninių ir simbolinių skaičiavimų, telekomunikacijų, kitus uždavinius. Algoritmų teorija jungia įvairius matematinės logikos, kombinatorikos, diskrečiosios matematikos, programavimo, kompiuterinės technikos konstravimo, geometrijos ir algebros metodus.
Algoritmų konstravimas, panaudojant duomenų struktūras, yra efektyvus ir populiarus įvairiuose taikymuose (duomenų bazėse, geografinėse informacinėse sistemose, kompiuterinėje grafikoje ir regoje, skaičiavimo uždaviniuose, kitose srityse). Dalyke nagrinėjama, kaip taikomieji uždaviniai apsprendžia algoritmų formalizavimą ir jų sudėtingumo analizę. Detaliai pateikiami įvairūs algoritmų konstravimo metodai, algoritmų analizė, intervalinė paieška, indeksavimas.

2009/2010 m.m. rudens semestre dalykas yra skaitomas informatikos bakalauro programos II-o kurso studentams: 1 - 5 grupėms

Paskaitos ir kolokviumai numatomi tokiu grafiku:

• 2009.09.07 - įvadas, abstrakti kompiuterio veikimo schema, von Neumano principai, ADT, baziniai duomenų tipai, pavyzdžiai
• 2009.09.14 - elementarios struktūros: stekas (dėklas), eilutės, prioritetinės ir atsitiktinės eilutės, heap struktūra, programavimas masyvo ir rodyklės pagrindu
• 2009.09.21 - sąrašai, jų programavimas masyvo pagrindu, elementarios hierarchinės struktūros (medžiai), medžių traverso (apėjimo) algoritmai
• 2009.09.28 - dvejetainiai paieškos medžiai, AVL medžiai, medžių dėstymas atmintyje
• 2009.10.05 - subalansuoti medžiai, 2-3-4 medžiai, raudoni-juodi medžiai
• 2009.10.12 - B-medžiai
• 2009.10.19 - Huffman'o algoritmas
• 2009.10.26 - vidinio rūšiavimo algoritmai, greitas rūšiavimas ir ranginė statistika
• 2009.11.02 - išorinio rūšiavimo algoritmai
• 2009.11.09 - dėstymo metodai (hashing)
• 2009.11.16 - išplėstinis dėstymas, žodynai, dinaminės aibės, paieška
• 2009.11.23 - kolokviumas (rūšiavimas, elementarios struktūros, hierarchinės struktūros)
• 2009.11.30 - skaitmeninis rūšiavimas ir skaitmeniniai paieškos algoritmai
• 2009.12.07 - tekstų apdorojimo algoritmai, ilgiausias posekis
• 2008.12.14 - kolokviumas (dėstymas, skaitmeniniai algoritmai, paieška)
• 2008.12.21 - algoritmų analizė, indeksai

Dalyko temų konspektai:

• Duomenų struktūros, abstraktūs duomenų tipai, baziniai algoritmai, sąrašai, heap, prioritetinės eilutės
• Duomenų struktūros, abstraktūs duomenų tipai, baziniai algoritmai, sąrašai, dėklai, eilutės, medžiai - konspektas lietuvių kalba
• Vidinio ir išorinio rūšiavimo algoritmai
• Vidinio ir išorinio rūšiavimo algoritmai - tekstas lietuvių kalba
• Medžiai, paieškos medžiai, subalansuoti medžiai, Huffman'o kodas
• Skaitmeniniai paieškos algoritmai
• Dėstymo (hashing) algoritmai
• Išplėstinio dėstymo algoritmai, lietuvių kalba
• Sekų apdorojimo algoritmai
• Algoritmų sudėtingumas ir jo įvertinimas

Dalyko reikalavimai informatikos studentams

Dalyko žinios yra vertinamos egzaminu. Egzamino balą sudaro iš praktinių užsiėmimų užduočių vertinimas - iki 5 balų, dviejų kolokviumų vertinimas - iki 2 balų (po 1 balą kiekvienas), ir teorinių žinių egzamino metu vertinimas - iki 3 balų.

Kolokviumai:

• pirmas kolokviumas numatomas lapkričio 23 d., paskaitų metu: 1-a, 2-a grupės ir 5-os grupės pirmieji 15 studentų rašo 12.00 - 12.50 val., o 3-a, 4-a grupės ir 5-os grupės likusieji studentai rašo 13.00-13.50 val. Kolokviumo temos: ADT, rūšiavimas, medžiai
  
  
• antras kolokviumas numatomas gruodžio 14 d., paskaitų metu: 1-a, 2-a grupės ir 5-os grupės pirmieji 15 studentų rašo 12.00 - 12.50 val., o 3-a, 4-a grupės ir 5-os grupės likusieji studentai rašo 13.00-13.50 val. Kolokviumo temos: skaitmeniniai algoritmai, paieška, dėstymo (hashing) algoritmai
  
  
• Kolokviumų perlaikymai tiems studentams, kurie praleido pirmą ar antrą kolokviumus dėl pateisinamos priežasties, vyks gruodžio 21 d., 18.00 val., rinktis prie 103 auditorijos
  

Praktinės užduotys. Praktinių užsiemimų dėstytojai formuluoja užduotis, nustato jų vykdymo ir atsiskaitymo tvarką, vertina užduočių atlikimą, keldami joms tokius reikalavimus:

• teisingai suformuluoti užduotį, gerai ją suprasti, pasiūlyti savo arba įsisavinti esamą algoritmą, mokėti jį paaiškinti, suprogramuoti algoritmą, mokėti paaiškinti (mokėti skaityti) programą, atlikti testinius skaičiavimus, mokėti paaiškinti ir analizuoti gaunamus rezultatus,
• papildomi balai gali būti pridedami už kūrybingas ir kokybiškai atliktus užduočių papildymus arba esmines modifikacijas

Egzamino perlaikymas. Egzamino perlaikymas vyks tokia pat tvarka ir tokia pat forma, kaip ir egzaminas, egzamino perlaikymui pateikiami klausimai ir užduotys bus panašios. Į egzamino metu surinktus balus bus atsižvelgta, kai vertinamos egzamino žinios perlaikymo atveju. Perlaikymo data skelbiama dekanato skelbimuose, MIF tinklapyje.

Vadovėliai:

• Robert Sedgewick. AlgorithmsAddison-Wesley, Inc., New York, 1992
• Robert Sedgewick. Algorithms in C (parts 1-4). 3^rd edition. Addison-Wesley, Inc., New York, 1999
• Algimantas Juozapavičius. Duomenų struktūros ir algoritmai, Vilniaus Universitetas, Vilnius, 1997
• Algimantas Juozapavičius. Duomenų struktūros ir efektyvūs algoritmai, Vilnius, TEV, 2007
• Gregory L. Heileman. Data Structures, Algorithms, and Object-Oriented Programming. The McGraw-Hill Companies, Inc., New York, etc., 1996
• Leendert Ammeraal. Algorithms and Data Structures in C++. John Wiley & Sons, Chichester, England, 1996
• Horowitz E., Sahni S., Anderson-Freed S. Fundamentals of Data Structures in C. Computer Science Press, New York, 1993.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms. The MIT Press, Cambridge, MA, 1990