| Kursa nosaukums | Fundamentālie algoritmi un datu struktūras |
| Kursa kods | InfT6001 |
| Zinātnes nozare | Elektrotehnika, elektronika, informācijas un komunikāciju tehnoloģijas |
| Zinātnes apakšnozare | Sistēmu analīze, modelēšana un projektēšana |
| Kredītpunkti (ECTS) | 6 |
| Kopējais stundu skaits kursā | 162 |
| Studenta patstāvīgā darba stundu skaits | 162 |
| Priekšzināšanas Kursam priekšzināšanas nav nepieciešamas |
|
| Kursa anotācija | |
| Kursa mērķis ir iepazīstināt studentus ar datu tipiem un datu struktūru specifikācijām, ar datu struktūru veidošanas metodēm un attēlošanas paņēmieniem, ar efektīviem algoritmiem darbā ar bieži lietojamām datu struktūrām. Iemācīt studentus izvēlēties visoptimālākās datu struktūras un to algoritmus un lietot tos praksē programmatūras izstrādes procesā. | |
| Kursa saturs(kalendārs) | |
| 1 Masīvi. Specifikācija. Masīvi ar rādītājiem. Masīvi ar funkcijas rādītājiem. Objektu masīvi.
2 Vienkāršsaistīti saraksti. Elementu pievienošana. Saraksta elementa pārjaunošana. Datu meklēšana. 3 Divkāršsaistīti saraksti. Divkāršsaistīto sarakstu konstruēšana. Elementu ielikšana saraksta sākumā. 4 Cikliskie saraksti. Pamatmezgls. Pirmā mezgla ielikšana. Nākamo mezglu ielikšana. Datu atjaunošana. 5 Steka konstruēšana. Elementu ielikšana. Elementu izvilkšana. Pirmā elementa lasīšana. 6 Rindas. Rindas konstruēšana. Elementu ielikšana. Elementu dzēšana. Rindas ar prioritātiem. 7 Divpusējas rindas. Elementu ielikšana divpusējas rindas sākumā un beigās. 8 Meklēšanas algoritmu analīze. Binārā meklēšana. Binārās meklēšanas koki. C valodas mezgla struktūra. 9 Kārtošanas pamatmetodes un algoritmi. Datu klasifikācija. Kārtošanas algoritmu veidi. 10 Koka jēdziens. Koku klasifikācija. Koku salīdzināšana. Koku datu strukturas. Konstruēšana un dzēšana. 11 Boyer – Moore algoritms. Apskate no kreisa puses uz labo. Slikta simbola noteikums. 12 Knuth – Morris – Pratt algorithm. Pārbīdes ideja. Pārbīdes noteikums. Metodes pirmsapstrādāšana. 13 Shift – And metode. Metožu efektivitāte. Metode ar kļūdām. 14 ”Dactylic” methods. Daktilogramas. Gadījuma daktilogramas algoritms. Kļūdu robežas. 15 Sufiksa koki un tas lietojums. Pamat definīcijas. Sufiksa koki būvēšanas vispārīgais apraksts. 16 Simbolu rindas un evolūcijas koki. Saite starp evolūcijām un ultrametriskiem kokiem. Koku testēšana. |
|
| Prasības kredītpunktu iegūšanai | |
| Izstrādāti un aizstāvēti praktiskie darbi, uzrakstīti un aizstāvēti visi patstāvīgie darbi: Darbs ar masīviem; Vienkāršsaistītu saraksts; Divkāršsaistītu saraksts; Cikliskais saraksts; Steks; Rindas; Divpusējas rindas; Koki; Burbuļveidīga kārtošanas; Kārtošanas ieliktos; Šela kārtošanas; Ātrā kārtošana; Piramīdveidīga kārtošana; Kārtošanas metožu salīdzināšana; Boyer – Moore algoritms; Shift – And metode; Daktilogramas; Sufiksa koki; Evolūcijas koki. | |
| Obligātā literatūra | |
| 1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
2. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983. 3. Donald E. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley, 1968. Second edition, 1973. 4. Donald E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, 1969. Second edition, 1981. |
|
| Papildliteratūra | |
| 1. Donald E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, 1973. 2. Хэзфилд Ричард, Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. Издательство «ДиаСофт», 2001. — 736 с. | |
| Periodika un citi informācijas avoti | |
| 1. "IEEE Software" www.computer.org/software/
2. "IEEE Computer" www.computer.org/computer/ 3. "Communication of the ACM" www.acm.org/cacm/ |
|
| Piezīmes | |
| Obligātais studiju priekšmets ITF "Informācijas tehnoloģijas" maģistrantiem pilna un nepilna laika studijās. | |