Duomenų struktūros ir algoritmai
paskaitų medžiaga

Paskaitų skaidrės

Nr.	Temos pavadinimas	Skaidrės
1.	Duomenys, duomenų struktūros, abstraktūs duomenų tipai
2.	Tiesiniai duomenų struktūros: sąrašas, stekas, eilė, dekas
3.	Binariniai medžiai, BST
4.	AVL medžiai, Bayer medis, piramidė (heap)
5.	Algoritmai, jų tipai, atvaizdavimas
6.	Rekursija
7.	Rūšiavimo algoritmai (įterpimo, išrinkimo, burbulo)
8.	Greitieji rūšiavimo algoritmai (Šelo, suliejimo, spartusis)
9.	Greitieji rūšiavimo algoritmai (Piramidės, Radix)
10.	Paieška: nuosekli, šuoliuojanti, dvejetainė, interpoliacinė

Savarankiškų darbų užduotys

Dieninio skyriaus studentams

Kiekvienas studentas iki semestro galo privalo atlikti ir atsiskaityti tris savarankiško darbo užduotis. Pirmos ir antros užduoties atlikimui reikia parašyti  programą C++ kalba su funkcijomis. Naudokite komentarus. Trečiosios užduoties atlikimui reikia nubraižyti struktūrinę schemą. Savarankiško darbo užduočių numeris pasirenkamas pagal studento numerį grupės sąraše. Programavimo užduotys vertinamoss po 1,5 balo, o struktūrinės schemos darbas vertinamas 1 balu. Savarankiškų darbų užduotys dieninio skyriaus studentams.

Neakivaizdinio skyriaus studentams

Kiekvienas studentas privalo atlikti ir atsiskaityti tris savarankiško darbo užduotis. Pirmoji užduotis susijusi su duomenų struktūromis, antroji su rūšiavimo ir paieškos algoritmais. Trečiosios užduoties atlikimui reikia nubraižyti struktūrinę schemą. Užduotys atliekamos raštu pateikiant kiekvieną žingsnį, naudojamą realizuonat algoritmą ar duomenų struktūrą. Kiekviena užduotis vertinamas po 1 balą. Savarankiškų darbų užduotys neakivaizdininkams.

Dirbtinio intelekto ir ekspertinių sistemų medžiaga

Paskaitų skaidrės atsisiuntimui

Baigiamųjų darbų temos

Siūlomos baigiamųjų darbų temos yra preliminarios ir gali būti modifikuojamos ir derinamos pagal studento kvalifikaciją ir gebėjimus. Studentai taip pat patys gali siūlyti savo temas.

Pratybų užduotys

Nr.1

• Duotas masyvas, kurio elementai: { 2; 23; 15; 5; 9; 28 }. Parašykite programą, kuri suformuotų statinį masyvą iš nurodytų elementų; ištrintų elementą, kurio reikšmė 15; pridėtų naują elementą su reikšme 17; pakeitų elemento reikšmę iš 23 į 44.
• Duotas sąrašas, kurio elementai: { 45; 18; 10; 73; 6; 19 }. Parašykite programą, kuri suformuotų dinaminį masyvą iš nurodytų elementų; ištrintų elementą, kurio reikšmė 45; pridėtų naują elementą su reikšme 17 į sąrašo galą; pakeistų elemento reikšmę iš 73 į 8.
• Parašykite funkciją, kuri sujungtų du tiesinius sąrašus.
• Tegul Q netuščia eilė, S tuščias stekas. Parašykite alogritmą, kuris kopijuotų elementus iš Q į S.

• Sudarykite binarinį paieškos medį iš duotų elementų { 12; 54; 34; 69; 73; 8; 95; 51; 44 }. Koks tai binarinis medis?
• AVL medis turi tokius mazgus {1; -1; 2; -2; 3; -3; ... }. Sudarykite AVL medį. Ištrinkite mazgus 3 ir -3. Kiek posūkių buvo atlikta?
• Iš atsitiktinių skaičių sudarykite krūvos duomenų struktūrą.

• Parašykite programą, kuri iteracinius ir rekursiniu būdu surastų didžiausią bendrą dviejų skaičių daliklį.
• Suprogramuokite išrinkimo, iterpties ir burbulo rūšiavimo algoritmus ir palyginkite jų vykdymo laiką. Naudokite atsitiktinių skaičių generatorių. Elementų skaičius ~ 10⁶.
• Masyvas A(n) sudarytas iš įvairių skirtingų skaičių. Inversija tai atvejis, kai masyvo elementai atitinka tokią sąlygą: jei i < j, tai A(i) > A(j). Suskaičiuokite, kiek masyve A yra inversijos atvejų.

Literatūra

1. R.Čiegis. Duomenų struktūros, algoritmai ir jų analizė. Vilnius, Technika 2007.
2. T.Cormen, etc. Introduction to Algorithms. MIT, 2009.
3. W.Collins. Data structures and standart template library. McGraw Hill, 2003.
4. K.Baniulis, B.Tamulynas. Duomenų struktūros. Kaunas, Technologija, 2003.
5. A.Juozapavičius. Duomenų struktūros ir algoritmai. Vilnius, VU. 1997.
6. Clifford A. Shaffer. A Practical Introduction to Data Structures and Algorithm Analysis. Virginia Tech Blacksburg, VA 24061, 2011.
7. www.academictutorials.com/data-structure/
8. cprogramminglanguage.net
9. www.techmat.vgtu.lt/konspektai