Lietišķie algoritmi: Sākumlapa

1 Lietot un analizēt bezzudumu saspiešanas algoritmus

1.1 Ieviest jēdzienus saistībā ar ziņojumu saspiešanu Description Definējam saspiešanas terminus, kopu teorijas un varbūtiskas sakarības; ieviešam arī informācijas saturu un entropiju ziņojumu telpā. Modulis neietver konkrētus saspiešanas algoritmus.
(CMU:Blelloch2013, pp.1-9)Introduction to Data Compression   (Cambridge:MacKay2014A)Entropy and Data Compression (I): Introduction to Compression, Inf.Theory and Entropy. (Cambridge:MacKay2014B)Entropy and Data Compression (II): Shannon's Source Coding Theorem, The Bent Coin Lottery.
1.1.1. Izskaidrot kursa saturu un tajā izmantotās metodes

1. Izskaidrot sešas satura tēmas jeb priekšmetapgabalus
2. Identificēt algoritmu paradigmas jeb algoritmu veidošanas principus
3. Apspriest kursa mācību virsuzdevumus
4. Skaidrot rīku un metožu piemērotību virsuzdevumu sasniegšanai
5. Skaidrot kursa priekšnoteikumus un tvērumu

1.1.2. Definēt ziņojumus, kodējumus, bezzudumu un zudumradošo saspiešanu Aprakstām saspiešanu klasisku kopu un funkciju līmenī bez varbūtiskiem modeļiem.

1. Pierādīt universāla saspiešanas algoritma neesamību ar Dirihlē principu
2. Definēt ziņojumus un ziņojumu alfabētu
3. Definēt kodējumu kā funkciju no ziņojumiem uz bitu virknītēm
4. Definēt bezzudumu un zudumradošo saspiešanu
5. Dotajam saspiešanas kontekstam noteikt ziņojumu alfabētu un kodējuma funkciju.
6. Dotajam alfabētam un ziņojumu virknes garumam noteikt iespējamo virkņu skaitu (t.sk. ar papildu ierobežojumiem).
7. Atrast varbūtību sadalījumu diskrētam gadījumlielumam (piemēram, ziņojumu kopai) ar nelielu skaitu vērtību, ja zināms ziņojumu ģenerēšanas process.

1.1.3. Definēt varbūtisku ziņojumu modeli, ziņojuma informācijas saturu tajā un vidējo kodējuma garumu. Piedēvējam ziņojumiem varbūtības un ieviešam saistītos jēdzienus - informācijas saturu un vidējo kodējuma garumu.

1. Pamatot saspiešanas metodes saistību ar ziņojumu varbūtisko modeli
2. Aprakstīt n-bitu kodu telpu un tās dalīšanu gabalos
3. Definēt konkrēta ziņojuma informācijas saturu
4. Definēt kodējuma vidējo garumu
5. Atrast viena ziņojuma informācijas saturu.
6. Aprēķināt entropiju dotajām burtu varbūtībām.
7. Dotajam gadījumlieluma vērtību skaitam <span class="math inline">\( n \)</span> atrast entropijas maksimums un minimumus

1.1.4. Definēt diskrēta gadījumlieluma entropiju Ieviešam entropijas jēdzienu un ieskicējam tā saistību ar informācijas saspiežamību.

1. Definēt gadījumlieluma entropiju kā vidējo vērtību informācijas saturiem
2. Definēt nosacīto entropiju.
3. Definēt divu neatkarīgu gadījumu lielumu pāra entropiju.
4. Formulēt (bez pierādījuma) entropijas saistību ar datu saspiežamību

1.1.5. Formulēt entropijas īpašības un izpausmes praktiskās situācijās Nostiprinām entropijas izprašanu, risinot piemērus un teksta uzdevumus,

1. Definēt koda vidējo garumu un saspiešanas attiecību (compression ratio)
2. Aprēķināt entropiju monētu svēršanas uzdevumos
3. Aprēķināt entropiju kartiņu un urnu uzdevumos
4. Aprakstīt funkcijas definīcijas un vērtību apgabalus, raksturot entropiju algoritma ieejā un izejā.

1.2 Formulēt un pamatot apgalvojumus par prefiksu kodiem Description Aplūkojam mainīga garuma prefiksu kodus, to teorētiskās īpašības un Hafmana kodu optimalitāti.
(CMU:Blelloch2013, pp.10-15)Introduction to Data Compression (Thanh2020)Demo Projects: Huffman coding   (Cambridge:McKay2014C)Entropy and Data Compression (III): Shannon's Source Coding Theorem, Symbol Codes. (Cambridge:McKay2014D)Entropy and Data Compression (IV): Shannon's Source Coding Theorem, Symbol Codes.
1.2.1. Definēt prefiksu kodus Aprakstām prefiksu kodus vispārīgajā (ne obligāti Hafmana) veidā. Pieminam “non-prefix-free codes”, bet šādas neparastas lietas kursā neapspriežam.

1. Parādīt kā neprefiksu kodi rada divdomības
3. Aplūkot Morzes kodu kā nedivdomīgu kodu un vai tas ir prefiksu kods

1.2.2. Konstruēt prefiksu kokus, zinot burtu parādīšanās varbūtības.

1. Noskaidrot, kā Hafmana pseidokodā darbojas prioritātes rinda
2. Uzzīmēt Hafmana koku, ja dots ziņojumu varbūtību sadalījums.
3. Pārveidot Hafmana koku kanoniskā formā.

1.2.3. Pamatot atkodēšanas viennozīmīgumu, ja kodēšanai izmantots prefiksu koks (neviens kods nav otram prefikss).

1. Minēt prefiksu koka piemērus (teiksim, UTF-8 kodējums)
2. Minēt kodējumus, kas nav prefiksu kodi (teiksim, Morzes kods)

1.2.4. Aprakstīt vispārīgu prefiksu saspiešanas metodi.
1.2.5. Aprakstīt Hafmana kodu dabīgu valodu burtiem
1.2.6. Ieviest prefiksu koku vispārēju teoriju

1. Ieviest kodu telpas jēdzienu
2. Aprakstīt, kā prefiksu koda garums atšķiras no entropijas.
3. Izskaidrot entropiju kā saspiešanas teorētisko robežu

1.2.7. Šenona informācijas teorēma

1. Krafta-Makmilana teorēma
2. Jensena nevienādība (t.sk. Logaritmu un entropijas novērtējumos)
3. Teorēma par koda garumu, kas nepārsniedz <span class="math inline">\( H(S)+1 \)</span>
4. Definēt vidējā prefiksu koda garumu <span class="math inline">\( M = \sum_{x \in X} p_x\ell_x \)</span>.

1.2.8. Pamatot, kāpēc Hafmana algoritms ir optimāls - vidējais koda garums uz vienu simbolu vismazākais, ja salīdzina ar citām prefiksu metodēm.

1.3 Aprakstīt aritmētisko saspiešanu. Description Aplūkojam aritmētiskās saspiešanas algoritmu un tā optimalitātes īpašības starp citiem “entropijas kodiem”.
(CMU:Blelloch2013, pp.16-21)Introduction to Data Compression (Said2004)Introduction to Arithmetic Coding - Theory and Practice. Amir Said, HP Labs, 2004.
1.3.1. Izklāstīt aritmētiskā koda pamatideju

1. Daļskaitļu pieraksts divnieku sistēmā (aritmētiskajam kodam)
2. Kodēt skaitļu intervālus ar galīgām bitu virknēm
3. Pamatot optimālā koda garuma nesasniedzamību, kodējot ziņojumus pa vienam
4. Izmantot kodu telpu optimāli vairāku ziņojumu virknei
5. Aplūkot metamo kauliņu piemēru aritmētiskai kodēšanai

1.3.2. Piekārtot vārdiem alfabētā intervālus no <span class="math inline">\( [0;1] \)</span>
1.3.3. Pamatot viennozīmīgas atkodēšanas iespēju.
1.3.4. Atrast intervālu garumus un to kodēšanai nepieciešamo bitu skaitu.

1. Iekodēt ziņojumu virkni ar aritmētisko kodu, ja dotas ziņojumu varbūtības.
2. Atkodēt aritmētisko kodu, ja dotas ziņojumu varbūtības.

1.3.5. Lietot un analizēt veselo skaitļu aritmētisko kodējumu

1.4 Lietot LZ77, LZ78 un LZW saspiešanas algoritmus Description Apakšnodaļā aplūkoti tie saspiešanas algoritmi, kuri līdzās saspiešanai veido datu struktūras ar bieži atkārtojošamies fragmentiem. Tie labi saspiež cilvēku valodas tekstus; ir efektīvi un plaši izmantoti.
(CMU:Blelloch2013, pp.32-36)Introduction to Data Compression
1.4.1. Definēt Markova ķēdes

1. Aprakstīt ķēdi kā varbūtisku automātu vai Markova modeli ar kārtu <span class="math inline">\( k \)</span>.
2. Definēt nosacīto varbūtību un nosacīto entropiju
3. Definēt valodas informācijas avota entropiju (source entropy) kā n-grammu entropiju robežu

1.4.2. Definēt LZ77 saspiešanu un atspiešanu

1. Aprakstīt LZ77 datu struktūras
2. Iekodēt un atkodēt ziņojumu virkni ar LZ77 algoritmu, izmantot tā datu struktūru (apzīmēt apakšvirknītes jau iekodētajā apgabalā).

1.4.3. Definēt LZ78 un/vai LZW saspiešanu un atspiešanu

1. Aprakstīt LZ78 un LZW algoritmu atšķirības, to datu struktūras un soļus
2. Iekodēt un atkodēt ziņojumu virkni ar LZ78 algoritmu, izmantot tā datu struktūru (tabulu ar pievienojamo virknīšu vārdnīcu).

1.4.4. Aprakstīt Markova ķēdes modeli un tās ziņojumu saspiežamību
1.4.5. Aplūkot "patentētus" algoritmus un failu formātus, vārda brīvību algoritmu pasaulē.
1.4.6. Raksturot LZ saimes rīkus - `gz`, `WinZIP`, GIF, biroja failu formātus.

1. Arhivēšanas rīku gz/WinZIP, gzip2 u.c. pārskats.
2. PNG saspiešanas līmeņi

1.5 Lietot un analizēt Berouza-Vīlera algoritmu. Description Apakšnodaļā aprakstīts Berouza-Vīlera algoritms un tā variācijas
(CMU:Blelloch2013, pp.37-39)Introduction to Data Compression
1.5.1. Lietot “Move-to-front” iekodēšanu un atkodēšanu
1.5.2. Aprakstīt Berouza-Vīlera transformāciju un tai inverso.
1.5.3. Veidot Berouza-Vīlera transformācijas.

1. Atšķirt leksikogrāfisko, inversi leksikogrāfisko u.c. virkņu sakārtojumus
2. Veikt 1 soli Berouza-Vīlera algoritma iekodēšanā vai atkodēšanā (virknēm garumā līdz 20 simboliem).
3. Veikt pilnu Berouza-Vīlera iekodēšanu vai atkodēšanu (virknēm garumā līdz 8 simboliem).
4. Analizēt Markova procesus u.c. stohastiskas ķēdes LZ77, LZ78 un Berouza-Vīlera algoritmos.

1.5.4. Minēt BW variantu, kur transformācijas rezultāts ir vienādi garš ar sākuma virkni; nav jāiegaumē sākumpozīcija.
1.5.5. Raksturot BW saimes rīkus, piemēram, `bzip2` u.c.
1.6 Salīdzināt saspiešanas metodes darbībā Description Agrākajās apakšnodaļās izklāstīto algoritmu kopsavilkums un apsvērumi, kura saspiešanas metode piemērota katrai situācijai
(Haecky2016, CH11)Understanding Compression (Perry2014)A Fictional Compression Metric Moves into the Real World
1.6.1. Analizēt empīriskus novērojumus par bezzudumu saspiešanu

1. Definēt dabisko valodu entropijas raksturlielumus
2. Izmantot Kalgari u.c. korpusus saspiešanas metožu salīdzināšanai
3. Salīdzināt saspiešanas attiecības pēc algoritma un informācijas veida
4. Definēt “Veismana novērtējumu” saspiešanas algoritmam

1.6.2. Salīdzināt datu saspiešanas scenārijus

1. Aprakstīt saspiešanu, ja datus arhivē bezsaistē, atarhivē uz klienta (video-satura u.c. piegādes scenārijs – failu izmērs vs. kvalitāte)
2. Aprakstīt saspiešanu, ja datus arhivē uz klienta, atarhivē mākonī (soctīklu scenārijs – datu apjoma tarifi vs. mobilās ierīces CPU un akumulators)

1.6.3. Raksturot kombinētus bezzudumu saspiešanas rīkus un formātus

1. Raksturot ZPAQ saspiešanas pakotni
2. Raksturot bezzudumu attēlu saspiešanu (GIF, PNG, WebP)
3. Raksturot *File binder* programmas - pašatarhivējošus izpildāmos failus.

1.6.4. Atpazīt saspiešanas algoritmu lietojumus datoru drošībā

1. Definēt scenārijus, kur “man-in-the-middle” nodarbojas ar atarhivēšanu.
2. Definēt DLP (datu noplūdes novēršanas) scenāriju, kurā jākontrolē izejošais saturs saspiestos datu pārraides kanālos.
3. Paredzēt gaidāmo rezultātu, ja arhīva fails datortīklā nosūtīts ne līdz galam vai arī tajā ir daži sabojāti baiti.
4. Raksturot *polymprhpic engine/polymorphic packer* - kā arhivēties katru reizi citādāk, lai vīrusi kļūtu polimorfi un varētu noslēpties no signatūru skenēšanas ((Mutation Engine, TridenT Polymorphic Engine (MtE), NuKE Encryption Device (NED), Dark Angel's Multiple Encryptor (DAME).)
5. Atšķirt Antivīrusu rīku metodes, kas ir efektīvas parastiem un polimorfiem vīrusiem.

1.6.5. Lietot programmatūras profilēšanas rīkus, mērīt bibliotēku izsaukumu ilgumu.

2 Lietot un analizēt zudumradošās saspiešanas algoritmus.

2.1 Ieviest kvantizācijas un mediju datu apstrādes pamatjēdzienus Description Apakšnodaļa definē dažus zudumradošās saspiešanas jēdzienus un dažas izplatītas noapaļošanas vai kvantizācijas pieejas. Apakšnodaļa definē JPEG algoritma soļus (citiem zudumradošiem attēlu formātiem soļi ir ļoti līdzīgi.
(MIT:Penfield2008, U3)Information and Entropy: Compression (MIT:Polyanskiy2016, CH23)Information Theory: Rate-Distortion Theory (Mozilla2020)Image File Type and Format Guide (Weitz2016)Discrete Cosine Transform   (Weitz2017)Diskrete Kosinustransformation (JPEG-Komprimierung). Die Hochschule für Angewandte Wissenschaften Hamburg.
2.1.1. Vektoru un matricu operāciju atkārtojums; krāsu koordinātes kā vektori

1. Veikt pāreju no RGB uz YIQ un otrādi (vai citām krāsu plaknēm)

2.1.2. Skalāra vienmērīgā un nevienmērīgā kvantizācija
2.1.3. Loida algoritms un Centroid Vornoi Tesselation
2.1.4. Kvantizācija un noapaļošana ar Senlaga un Donta metodēm
2.1.5. Nepārtrauktas funkcijas Furjē pārveidojums
2.1.6. Formulēt Šenona-Naikvista teorēmu
2.1.7. Diskrētais kosinusu pārveidojums

1. Definēt ortogonālas funkciju saimes
2. Aprakstīt rastra attēlu glabāšanai un apstrādei nepieciešamos datus.
3. Uzrakstīt izteiksmes diskrēto kosinusu transformācijai 1D un 2D gadījumos
4. Uzrakstīt izteiksmes “wavelet’ pārveidojumam

2.1.8. Atrast krāsas pēc RGB koordinātēm. Definēt alfa caurspīdību kā rastra attēlu superpozīcijas/pārklāšanas koeficientu.
2.1.9. Aprakstīt zudumradošās saspiešanas uzdevumu.
2.1.10. Definēt JPEG un līdzīgiem algoritmiem iespējamos saspiešanas parametrus.
2.1.11. Aprakstīt JPEG saspiešanas algoritmu.

1. JPEG algoritmā izpildīt plakņu I,Q izretināšanu
2. JPEG algoritmā izpildīt DFT 8x8 blokiem
3. JPEG algoritmā kvantizēt DFT koeficientus
4. JPEG algoritmā savirknēt koeficientus un iegūt starpības
5. Run-length encoding - kodēšana un atkodēšana

2.1.12. Apskatīt dažus attēlu zudumradošo saspiedumu lietojumus

1. Krāsu kodēšana, acīm atšķiramas atšķirības, Raw un JPEG dati foto un video aparatūrā.
2. Pirkstu nospiedumu saspiešana ar “wavelet” pārveidojumu

2.2 Apskatīt skaņas un video saspiešanas algoritmus Description Apakšnodaļā aplūko skaņas un video saspiešanas metodes un arī zudumradošos algoritmus darbībā.
(Raissi2002)The Theory behind MP3.
2.2.1. Definēt cilvēka dzirdes matemātisko modeli, kuru lieto MP3
2.2.2. Lietot un analizēt MP3 skaņas saspiešanas pamatsoļus

1. Aprēķināt MP4 formāta datu saspiežamību, ja zināms, cik tajā ir katra veida freimu, cik kadru sekundē un cik labi katru no tiem var saspiest.
2. Aprēķināt MP3 formāta datu saspiežamību, ja zināms paraugā esošo frekvenču diapazons un iesaistīto "filterbank" skaits, un bitraide (bit/s).

2.2.3. Lietot un analizēt video saspiešanas algoritmus
2.2.4. Identificēt praktiskai video failu sagatavošanai piemērotus konteineru formātus.
2.2.5. Pārspriedumi par DRM

1. Patenti saistīti ar saspiešanas algoritmiem
2. Redzamās un neredzamās ūdenszīmes mediju failos (*watermarking algorithms*); to robustums atkarībā no saspiešanas veida.
3. Identificēt lietojumus steganogrāfijai (informācijas paslēpšanai ar to nesaistītā failā; t.sk. JPEG).
4. Skaidrot steganogrāfijas un tās pazīšanas tehnoloģiju iespaidu uz datu noplūdes novēršanas rīkiem (Data Leak Prevention, DLP).

3 Lietot un analizēt kļūdu korekcijas algoritmus

3.1 Pazīt un risināt kļūdu identificēšanas uzdevumus Description Apakšnodaļā apskatām kļūdu identificēšanas paņēmienus (bez apņemšanās kļūdu lokalizēt vai izlabot)
(Modiano2009, L15)Communication Systems Engineering: Cyclic Codes and Error Detection
3.1.1. Lietot un analizēt CRC32 algoritmu un apskatīt tā īpašības
3.1.2. Lietot un analizēt Lūna pārbaudes (Luhn check) algoritmu un līdzīgus kontrolsummu algoritmus
3.1.3. Aplūkot dažus droša hešinga algoritmus (MD5, SHA256 u.c.) un to lietojamību, lai pamatotu, ka datu vai programmatūras fails nav korumpēts.
3.2 Aprakstīt un analizēt Heminga un citus lineārus kļūdu labošanas kodus Description Apakšnodaļa aplūko tos kodus, kam var izlabot tikai vienu kļūdu, toties tie balstās uz matricu algebru un to optimalitāte ir pierādāma.
(MIT:Polyanskiy2016, CH16)Information Theory: Linear Codes   (MacKay2014E)Noisy Channel Coding (I): Inference and Information Measures for Noisy Channels. (MacKay2014F)Noisy Channel Coding (II): The Capacity of a Noisy Channel. (MacKay2014G)Noisy Channel Coding (III): The Noisy-Channel Coding Theorem.
3.2.1. Definēt trijstūra nevienādību virkņu atšķirību metrikai un tās sekas kļūdu labošanā

1. Definēt bitu virkņu attālumu (kļūdu jeb atšķirību skaitīšana)
2. Pamatot, ka attālums starp <span class="math inline">\( 2 \)</span> ziņojumiem ir vismaz <span class="math inline">\( 2c+1 \)</span>

3.2.2. Definēt n-dimensiju kubus ar kodavārdiem virsotnēs

1. Definēt, kas ir [n,k,d] kļūdu korekcijas kodi
2. Kombinatoriski pamatot <span class="math inline">\( [n,k,d] \)</span> kodu (ne)esamību noteiktiem parametriem <span class="math inline">\( n,k,d \)</span>.

3.2.3. Definēt [7,4,1] Heminga kodu

1. Izveidot Heminga kodu (saskaitāmās izteiksmes pēc mod 2) vienas kļūdas labošanai un iekodēt.
2. Izlabot kļūdu saņemtā <span class="math inline">\( [7,4,1] \)</span> Heminga koda ziņojumā un atkodēt
3. Aprakstīt <span class="math inline">\( [7,4,1] \)</span> Heminga kodu ar matricas operāciju

3.2.4. Formulēt Heminga kodu optimalitātes teorēmu (ja koda garums ir <span class="math inline">\( 2^n-1 \)</span>).

1. Atkodēt 7-bitu un 15-bitu Heminga kodus
2. Sakārtot Heminga ziņojumu/kontroles bitus inversi leksikogrāfiski

3.2.5. Definēt vispārīgu lineāru kodu.

1. Lietot lineāra koda ģeneratormatricu
2. Lietot lineāra koda pareizības pārbaudes matricu.

3.3 Lietot Rīda-Solomona kodus un polinomu interpolāciju. Description Aplūkot algoritmu saimi, kas rodas no polinomu aplūkošanas un var izlabot lielāku skaitu kļūdu nekā Heminga kodi.
(Kak2020, L6)Computer and Network Security: Polynomial Arithmetic (Kak2020, L7)Computer and Network Security: Finite Fields of the Form $GF(2^n)$ (Khan2017)Building polinomials over the field $GF(2^8)$
3.3.1. Definēt galīgus laukus un formulēt to īpašības

1. Lauku jēdziens un piemēri
2. Lauks <span class="math inline">\( GF(p) \)</span>, kur <span class="math inline">\( p \)</span> ir pirmskaitlis
3. Veikt aritmētiskas darbības galīgos laukos <span class="math inline">\( GF(p^n) \)</span>
4. Veikt četras aritmētiskas darbības galīgos laukos <span class="math inline">\( GF(2^n) \)</span>.
5. Veikt darbības ar polinomiem pār galīgiem laukiem
6. Veikt aritmētiskas darbības galīgos laukos <span class="math inline">\( GF(p) \)</span> (atlikumi pēc pirmskaitļa moduļa)

3.3.2. Definēt algebras pamatteorēmu

1. Formulēt algebras pamatteorēmas sekas par divu polinomu sakņu sakrišanu
2. Konstruēt polinomu ar dotajām saknēm
3. Rakstīt Lagranža interpolācijas polinomu formulas

3.3.3. Apskatīt Rīda-Solomona kodus kā algebriskas interpolācijas uzdevumus
3.3.4. Saistīt Solomona-Rīda polinoma pakāpi, vērtību un kļūdu skaitu
3.3.5. Apskatīt Rīda-Solomona kodus, veidojot polinomus virs Galuā laukiem
3.4 Aprakstīt un analizēt citus kļūdu labošanas algoritmu veidus Description Apakšnodaļā aplūkoti daži moderni kļūdu labošanas algoritmi un esošo pieeju kombinācijas
(Noisternig2006)An Introduction to Tornado Codes: Introduction to Error-Correcting Codes by Michael Noisternig. University of Darmstadt.
3.4.1. Izmantot kļūdu atjaunošanas kodējumu divdaļīgā grafā.
3.4.2. Aprakstīt Tornado kodu vispārējo darbību
3.4.3. Pazīt kļūdu detekcijas un labošanas metodes darbībā

1. Nosaukt OSI un arī TCP/IP protokolu steku līmeņus, kur labo kļūdas
2. Aprakstīt Etherneta freimu kļūdu labošanas metodi
3. Aprakstīt kļūdu detekcijas un labošanas metodes kompaktdisku datos.

4 Lietot un analizēt lineārās programmēšanas algoritmus

4.1 Definēt LP pamatēdzienus un formalizēt teksta uzdevumus par LP. Description Apakšnodaļā definēti lineārās optimizācijas uzdevumu pamatjēdzieni un vienkāršākie secinājumi par to risināmību kā arī visāda veida dualitātes rezultāti.
(MIT:Goemans2008, L9)Advanced Algorithms: Linear Programming (Vempala2003; L12)Combinatorial Optimization: Linear Programs
4.1.1. Ieviest lineārās programmēšanas pamatjēdzienus

1. Risināt nelielas lineāru vienādojumu sistēmas ar mainīgo izslēgšanu
2. Definēt un noteikt taisnstūrveida matricas rangu
3. Veikt Gausa izslēgšanas soļus matricās

4.1.2. Ieviest lineārās programmēšanas ģeometrisko interpretāciju

1. Interpretēt ģeometriski LP uzdevuma nosacījumus un papildmainīgos
2. Attēlot plaknē pieļaujamo apgabalu 2 brīvo mainīgo LP uzdevumam.
3. Atzīmēt 2D vai 3D pieļaujamā apgabala robežai mainīgo, kurš ir 0.

4.1.3. Ģeometriskā intuīcija par optimālā risinājuma esamību un eksponenciāls “naivais algoritms”
4.1.4. Veikt LP uzdevumu pārrakstīšanas un manipulācijas

1. Pārveidot mērķa funkcijas minimizēšanu par maksimizēšanu
2. Izteikt vienādības ar nevienādībām
3. Izteikt nevienādību ar nenegativitāti un nokares mainīgo
4. Aizstāt ar zīmi neierobežotus mainīgos ar diviem nenegatīviem mainīgajiem

4.1.5. Aprakstīt problēmas kā veselo skaitļu programmēšanas uzdevumus

1. Formulēt teksta uzdevumus kā veselo skaitļu LP uzdevumus.
2. Reducēt Hamiltona ciklu uz veselo skaitļu LP uzdevumu.
3. Reducēt SAT problēmu uz veselo skaitļu LP uzdevumu.

4.2 Lietot un analizēt simpleksu metodi lineārās programmēšanas uzdevumu risināšanai Description Apakšnodaļa apskata vecāko un arvien populārāko LP risināšanas metodi ar simpleksu metodi. Vienlaikus pamatots neapmierinošs konverģences ātrums dažos īpašos gadījumos.
(MIT:Goemans2008, L10)Advanced Algorithms: Sketch of the Simplex Method (MIT:Demaine2015, L15)Design and Analysis of Algorithms: Linear Programming (Chutong2019)Statistical Analysis of Four Pivot Rules for the Simplex Method (Vempala2003, L13)Combinatorial Optimization: The Simplex Algorithm
4.2.1. Pārveidot LP uzdevumus simpleksu standartformā, t.sk. Ieviešot papildmainīgos.
4.2.2. Izvēlēties sākotnējo tuvinājumu simpleksu algoritmā
4.2.3. Veikt simpleksa algoritma soļus
4.2.4. Analizēt simpleksu algoritma ārtrdarbību un sliktākos gadījumus.

4.3 Lietot un analizēt rezultātus par LP dualitāti. Description Šajā apakšnodaļā ieviešam teorijas rezultātus un algoritmus, kas izmanto lineāro programmu dualitāti.
(MIT:Goemans2008; L10)Advanced Algorithms: LP Duality (MIT:Goemans2008; L11)Advanced Algorithms: Complexity of LP (Cornell:Williamson2008; L7)Mathematical Programming I (MIT:Vempala2003, L16)Combinatorial Optimization: The Primal-Dual Algorithm (CMU:Sleator2018, L15)Algorithms: Linear Programming – Duality
4.3.1. Formulēt un pierādīt Farkasa lemmu

1. Formulēt Farkasa lemmu dažos ekvivalentos veidos
2. Pierādīt Farkasa lemmu
3. Formulēt Farkasa lemmas secinājumus

4.3.2. Pārveidot primāro LP uzdevumu par duālo

1. Minēt duālās problēmas fizikālo interpretāciju ar bumbiņu
2. Pārveidot (nestandartformas) LP uzdevumu par tam duālo.
3. Teksta uzdevumos interpretēt gan primāros, gan duālos mainīgos.
4. Izmantot dualitātes teorēmu un aprēķināt dualitātes atstarpi
5. Sastādīt LP modeli optimizācijas veida teksta uzdevumam.
6. Sastādīt LP modeli maksimālās plūsmas uzdevumam grafā.

4.3.3. Primārā-Duālā metode LP uzdevumos
4.3.4. LP uzdevumu izmērs un sarežģītība
4.3.5. Analizēt dualitātes izpausmes teksta uzdevumos

1. Izmantot dualitāti grafu plūsmas uzdevumos
2. Izmantot dualitāti krājumu vadības uzdevumos
3. Izmantot dualitāti matricu spēļu uzdevumos

4.4 Izmantot elipsoīda metodi LP risināšanā Description Apakšnodaļa apskata iteratīvu (skaitlisko metožu iedvesmotu) LP risināšanas metodi – elipsoīdu metodi un tās ģeometrisko interpretāciju.
(MIT:Goemans2008, L12)Advanced Algorithms: Ellipsoid Algorithm (MIT:Goemans2009, L7)Combinatorial Optimization: Ellipsoid Algorithm (MIT:Vempala2003; L17)Combinatorial Optimization: The Ellipsoid Algorithm
4.4.1. Izklāstīt Elipsoīda algoritma soļus
4.4.2. Formulēt Hačijana elipsoīda algoritma tilpumu novērtējumu.

4.5 Izmantot iekšējā punkta metodes un afīno mērogošanu Description Apakšnodaļā virspusēji aprakstītas vairākas iekšējā punkta metodes un viena no tām (afīnās mērogošanas atsevišķs variants) izklāstīts detalizēti.
(MIT:Bertsimas2009, L21)Optimization Methods: Affine scaling algorithm
4.5.1. Ieviest nepārtrauktu funkciju optimizācijā pazīstamus jēdzienus

1. Definēt izliektas kopas
2. Nepārtrauktas un diferencējamas funkcijas maksimumi
3. Formulēt teorēmu par lineāras funkcijas lielāko vērtība uz sfēras
4. Rakstīt izteiksmi <span class="math inline">\( n \)</span>-dimensiju vektora projicēšanai hiperplaknē.

4.5.2. Lietot un analizēt afīnās mērogošanas metodi LP risināšanā

1. Izpildīt afīnās mērogošanas metodes koordinātu pārveidojumus.
2. Atrast afīnās mērogošanas metodes maksimālā pieauguma virzienu.
3. Projicēt afīnās mērogošanas metodes virzienu dotajā plaknē
4. Atrast afīnās mērogošanas kārtējo tuvinājumu un atgriezties sākotnējos apzīmējumos

4.5.3. Apskatīt LP modeļu izmantošanu Ieteikumu sistēmās (recommender systems) – tsk. Netflix vai grāmatu ieteikumos.
4.5.4. Reducēt dažas NP-pilnas problēmas uz lineāras optimizācijas (t.sk. Integer programming) uzdevumiem.
4.5.5. Identificēt citus iekšējā punkta metožu variantus

5 Lietot un analizēt virkņu meklēšanas algoritmus

5.1 Ieviest virkņu meklēšanā izmantotos jēdzienus Description Šajā apakšnodaļā apskatām pamatjēdzienus un naivo algoritmu.
(RajputJi2016)Wildcard Pattern Matching
5.1.1. Definēt terminus – virkne, apakšvirkne, apakšstrings, apakšstringa indekss

1. Novērtēt apakšvirkņu un apakšstringu skaitu dotajā virknē
2. Pamatot dažas stringu prefiksu/sufiksu īpašības
3. Aprakstīt virkņu meklēšanas uzdevumus (jā/nē testēšana, pirmais indekss, visi indeksi)
4. Aprakstīt garākās kopīgās apakšvirknes uzdevumu.

5.1.2. Lietot un analizēt naivo apakšstringa meklēšanas algoritmu.

1. Novērtēt naivā virkņu meklēšanas algoritma ātrdarbību sliktākajā gadījumā.
2. Novērtēt naivā virkņu meklēšanas algoritma ātrdarbību “nejaušām” virknēm.

5.1.3. Aplūkot algoritmiskus risinājumus rediģēšanas attālumam

1. Definēt Levenšteina (rediģēšanas) attālumu
2. Lietot un analizēt dinamiskās programmēšanas algoritmu rediģēšanas attālumam
3. Pārveidot rediģēšanas attālumu par īsāko ceļu grafā un Dijkstras algoritmu
4. Izmantot dinamisko programmēšanu, meklējot paraugus ar aizstājējzīmēm (wildcards)

5.2 Lietot hešinga paradigmas virkņu meklēšanas algoritmos. Description Šajā apakšnodaļā apspriesti slīdošā loga (sliding window jeb rolling hash) algoritmi.
(MIT:Devadas2009, L6)Introduction to Algorithms: Rolling Hash (MIT:Demaine2011, L9)Introduction to Algorithms: Table Doubling, Karp-Rabin
5.2.1. Manipulēt ar skaitļiem dažādās skaitīšanas sistēmās

1. Pārveidot skaitļus no vienas skaitīšanas sistēmas citā
2. Aprēķināt polinomu vērtības ar Hornera shēmu
3. Aprēķināt pozicionāli pierakstītu skaitļu vērtības ar Hornera shēmu.
4. Rakstīt formulas “ritinošā hešinga” efektīvai aprēķināšanai

5.2.2. Lietot un analizēt Rabina-Karpa algoritmu

1. Apskatīt optimāla modulārā hešinga funkciju parametru izvēli
2. Ja doti parametri, novērtēt viltus trāpījumu varbūtību Rabina-Karpa algoritmā.
3. Veikt Rabina-Karpa soli, ja doti parametri un pārbaudāmais teksts

5.2.3. Definēt Blūma filtrus – varbūtiskas datu struktūras ar hešingu.

1. Formulēt Blūma filtra abstrakto datu tipu, iespējamās kļūdas atbildēs
2. Aplūkot praktiski izraudzītus parametrus, lai Blūma filtrs sniegtu vietas ietaupījumu

5.3 Veidot datu struktūras Knuta-Morisa-Prata algoritumam Description Apakšnodaļa apraksta parauga meklēšanu ar galīga automāta palīdzību, kura stāvokļu pārejas iekodē prefiksu funkcija.
(CMU:Kingsford2017, L9)Design & Analysis of Algorithms: String Matching (Berkeley:Patrascu2009, HW5)Computability and Complexity: Pattern Matching
5.3.1. Aplūkot galīgo automātu jēdzienus stringu analīzei.

1. Izveidot automātu apakšstringu meklēšanai
2. Izveidot automātu regulāru izteiksmju meklēšanai

5.3.2. Parādīt ievades papildināšanas (input enhancement) pieeju virkņu meklēšanas algoritmos.
5.3.3. Definēt prefiksu funkciju meklējamam paraugam un tās algoritmu
5.3.4. Definēt KMP algoritmu, kas optimizē nobīdes palielinājumus

1. Dotajam meklējamajam paraugam P izveidot KMP prefiksu funkcijas tabulu.
2. Pamatot dažas prefiksu funkcijas īpašības
3. Saskaitīt simbolu salīdzināšanas, meklējot apakšvirknes ar KMP algoritmu.

5.3.5. Salīdzināt KMP ar stāvokļu automātu

1. Definēt stāvokļa automātu stringu meklēšanas uzdevumiem.
2. Aplūkot prefiksu funkcijas saistību ar pārejām stāvokļu automātā
3. Dotam paraugam <span class="math inline">\( P \)</span> izveidot galīgu automātu tā meklēšanai.

5.4 Veidot datu struktūras Bojera-Mūra algoritmam Description Apakšnodaļa apraksta otra veida stringu meklēšanas algoritmus, kuri sāk pārbaudes no parauga beigām.
(UCDavis:Gusfield2011)String Algorithms: Notes on Boyer-Moore (Lang2001)Boyer-Moore-Algorithmus (Mangal2017)Boyer Moore Algorithm: Good Suffix heuristic
5.4.1. Aprakstīt Bojera-Mūra algoritmu

1. Aprakstīt sliktā simbola heiristiku un funkciju <span class="math inline">\( \lambda(n) \)</span>
2. Aprakstīt labā sufiksa heiristiku un gammas funkciju <span class="math inline">\( \gamma(n) \)</span>
3. Dotajam meklēšanas paraugam <span class="math inline">\( P \)</span> izveidot labā sufiksa tabulu
4. Dotajam meklēšanas paraugam <span class="math inline">\( P \)</span> izveidot sliktā simbola tabulu.

5.4.2. Analizēt pilna BM algoritma ātrdarbību caurmēra un sliktākajā gadījumā.
5.4.3. Lietot un analizēt Bojera-Mūra-Horspola algoritmu caurmēra un slikākajā gadījumā
5.5 Veidot sufiksu koku un lietot to virkņu uzdevumos Description Šajā nodaļā apskatītas tās pieejas, kas nav radniecīgas RK, KMP, BM algoritmiem un virkņu algoritmu lietojumi dzīvē.
(CMU:Kingsford2017, L10)Algorithms: Suffix Trees and Arrays (MIT:Karger1999, Handout 8)Advanced Algorithms: Problemset 3 Solutions (Allison)Suffix Trees (Stanford:KayA)Suffix Trees (Stanford:KayB)Suffix Trees: Notes on Ukkonen's Algorithm   (MIT:Demaine2012)Advanced Data Structures: Strings
5.5.1. Minēt garākā kopīgā apakšstringa meklēšanas algoritmus
5.5.2. Apskatīt stringu meklēšanas lietojumus datoru drošībā

1. Apskatīt slīdošā hešinga lietojumus plaģiāta noķeršanā; pārskatīt rīkus un pakalpojumu veidus.
2. Izskaidrot datu noplūdes novēršanas lietojumus (DLP); heštabulu un Blūma filtru lietojumus tajos.
3. Pazīt algoritmus leksikonu (nelielu vārdnīcu) meklēšanu DLP rīkos
4. Pazīt algoritmus regulāru izteiksmju meklēšanu DLP rīkos

5.5.3. Iepazīties ar sufiksu kokiem

1. Definēt sufiksu koku datu struktūras.
2. Lietot un analizēt Ukonena algoritmu sufiksu koku veidošanai.
3. Izmantot sufiksu kokus dažiem meklēšanas uzdevumiem.