DUOMENŲ STRUKTŪROS IR ALGORITMAI

Mokomoji priemonė iš dalies apima dėstomas kursų “Duomenų struktūros”, "Inforrmacinės
sistemos”, “Efektyvūs algoritmai ir duomenų struktūrų sintezė” temas. Šie kursai numatyti
Matematikos fakulteto informatikos specialybės studentų bakalauro ir magistro studijų
programose.
Įvadas.
1. Pagrindiniai duomenų struktūrų objektai
1.1. Masyvas (array)
1.2. Stekas (stack)
1.3. Eilės (queue)
1.4. Dekas (dequeue)
1.5. Tiesiniai sąrašai (linked lists)
1.6. Medžiai (trees)
1.7. Medžių dėstymas kompiuterių atmintyje
1.8. Rekursija
1.9. Algoritmų analizė
1.10. Algoritmų diegimas
2. Rūšiavimo metodai
2.1. Elementarūs rūšiavimo algoritmai
2.1.1.Išrinkimo (selection) algoritmas
2.1.2.Įterpimo algoritmas
2.1.3.Burbulo algoritmas
2.1.4.Kevalo (shellsort) algoritmas
2.1.5.Pasiskirstymo skaičiavimas
2.2. Greito rūšiavimo algoritmas
2.2.1.Greito rūšiavimo algoritmo taikymas elementams išrinkti
2.2.2.Greito rūšiavimo algoritmo sudėtingumas
2.3. Skaitmeninis rūšiavimas (radix sort)
2.4. Prioritetinės eilės (priority queues)
2.4.1.Duomenų struktūra heap
2.4.2.Operacijos su heap struktūra
2.4.3.Heapsort algoritmas
2.4.4.Netiesioginė heap duomenų struktūra
2.4.5.Aibės duomenų struktūra
2.4.6.Aibinis heapsort algoritmas
2.5. Sąlajos rūšiavimas (mergesort)
2.6. Išorinis rūšiavimas (external sorting)
2.6.1.Subalansuota daugybinė sąlaja (balanced multiway merging)
2.6.2.Pakeitimo išrinkimas (replacement selection)
3. Paieškos metodai
3.1. Elementarūs paieškos metodai
3.1.1.Nuosekli paieška
3.1.2.Dvejetainė paieška
3.1.3.Dvejetainio medžio paieška
3.1.4.Operacija delete
3.1.5.Netiesioginiai dvejetainės paieškos medžiai
3.2. Subalansuoti medžiai
3.2.1.2-3-4 ir 2-3-medžiai
Duomenų struktūros ir algoritmai
4
3.2.2.Įterpimo operacija 2-3-medžiuose
3.2.3.Išmetimo operacija 2-3-medžiuose
3.2.4.Duomenų struktūros 2-3-medžiams
3.2.5.Raudoni-juodi medžiai
3.3. Dėstymo lentelės
3.3.1.Išdėstymo funkcijos
3.3.2.Atskirti sąrašai
3.3.3.Atviro adresavimo dėstymo metodai
3.4. Skaitmeninė paieška
3.4.1.Skaitmeniniai paieškos medžiai
3.4.2.Skaitmeniniai paieškos indeksai
3.4.3.Daugybiniai skaitmeniniai paieškos indeksai
3.4.4.Patricia algoritmas
3.5. Išorinė paieška
3.5.1.Indeksinė-nuosekli paieška
3.5.2.B-medžiai
3.5.3.Išplėstinis dėstymas
4. Sekų apdorojimas ir kompresija
4.1. Sekų paieška
4.2. Tiesmukiškas (brutalios jėgos) algoritmas
4.3. Knuth-Morris-Pratt’o algoritmas
4.4. Boyer-Moore’o algoritmas
4.5. Rabin-Karp’o algoritmas
4.6. Dviejų sekų bendras ilgiausias posekis
4.7. Sekų ir failų kompresijos metodai
4.7.1.Vienodų simbolių sekų kodavimas
4.7.2.Kintamo ilgio kodavimas
5. Daugiamačių duomenų struktūros ir algoritmai.
5.1. Vidinės atminties struktūros
5.1.1.K-D-medžiai
5.1.2.BSP-medžiai
5.1.3.Ketvirtainiai medžiai
5.2. Antrinės atminties struktūros
5.2.1.Daugiamačiai išplėstinio dėstymo metodai
5.2.2.Daugiamačiai hierarchiniai metodai
5.2.3.Erdviniai kreipties metodai
6. Uždaviniai ir pratimai
6.1. Pirmoji uždavinių grupė
6.2. Antroji uždavinių grupė
6.3. Trečioji uždavinių grupė
6.4. Pratimai tiriamajam darbui
7. Literatūra