Lietišķie algoritmi – 4. mājas darbs Termiņš: otrdiena, 20.decembris. 1. Duālā lineārā programma. Apskatām šādu lineāro programmu. max 3x1+5x2, ar nosacījumiem 2 x1 + x2 17, x1 + x2 10, x1 + 2 x2 17, x1 0, x2 0. a. Uzrakstīt šai programmai duālo lineāro programmu; b. Kombinējot sākotnējo un duālo programmu, uzrakstīt lineāru programmu, kuras jebkurš atrisinājums dod maksimumu sākotnējai lineārajai programmai un minimumu duālajai programmai. 2. Meklēšana ar galīgu automātu. Uzzīmēt galīgu automātu, kas pārbauda, vai ieejas tekstā sastopams vārds abcababc. 3. Bojera-Mūra algoritms. a. Uzrakstīt Bojera-Mūra algoritmā lietotās tabulas, ja meklējamā apakšvirkne P ir bccacc. b. Nodemonstrēt Bojera-Mūra algoritma darbību šīs apakšvirknes meklēšanai tekstā T=acacaccbcbcbccaccabababccacc. 4. Attālums starp simbolu virknēm. Apskatām vispārinātu variantu attāluma meklēšanai starp simbolu virknēm. Tāpat kā parastajā attāluma meklēšanā dotas divas simbolu virknes T un T’. Atļauts ar virkni T veikt šādas operācijas: a. Nomainīt simbolu pret citu – tiek skaitīta kā 1 operācija; b. Izmest vai iespraust simbolu – tiek skaitīta kā 1 operācija; c. Izmest vairākus pēc kārtas esošus simbolus – tiek skaitīta kā 5 operācijas; d. Iespraust vairāku simbolu virkni starp diviem blakus esošiem simboliem – tiek skaitīta kā 5 operācijas. Parādīt, kā jāpārveido lekcijā aprakstītais dinamiskās programmēšanas algoritms, lai tas atrastu mazāko operāciju skaitu, ar kādu iespējams pārveidot T par T’.