Uzdevums par mugursomu

Uzdevums par mugursomu — ir viens no kombinatoriskās optimizācijas NP-pilnām problēmām. Savu nosaukumu dabūja no uzdevuma nosacījumiem: ielikt mugursomā, kuras ietilpība ir ierobežota, pēc iespējas vairāk vērtīgu mantu. Ir sastopamas vairākas uzdevuma par mugursomu nosacījuma variācijas ekonomikā, lietišķā matemātikā, kriptogrāfijā un loģistikā.

Vispārīgi uzdevuma nosacījumus var noformulēt tā: no dotas priekšmetu kopas ar īpašībām “vērtība” un “svars” ir jāizveido apakškopu ar maksimālu vērtību, ievērojot summāra svara ierobežojumu.

Klasiska uzdevuma nostādne 

Pieņemsim, ka mums ir priekšmetu kopa, kurai ir divi parametri – svars un vērtība. Mums arī ir mugursoma ar noteikto ietilpību. Uzdevums ir savākt mugursomu ar maksimālo priekšmetu vērtību tā,  lai ievērotu tās summāra svara ierobežojumu.

Matemātiski uzdevums tie formulēts sekojoši: dots  svari. Katram -tam svaram ir noteikts svars  un vērtība , . Mugursomas summāra svara robežas noteic ar celtspēju . Ir nepieciešams maksimizēt  ar ierobežojumu  un .

Uzdevuma par mugursomu variācijas 
Eksistē daudz vispārinājumu šai problēmai,atkarīgi no nosacījumiem, kuri virzās uz pašu mugursomu, citiem priekšmetiem vai citu priekšmetu izvēli. Populārākie mugursomas problēmas veidi ir:
 Mugursoma 0-1 (): ne vairāk kā viens eksemplārs katram priekšmietam.
 Ierobežota mugursoma (): ne vairāk par noteikto eksemplāru skaitu katram priekšmietam.
 Neierobežota mugursoma (): patvaļīgais eksemplāru skaits katram priekšmetam.
 Mugursoma ar vairākiem izvēles veidiem (): priekšmeti ir sadalīti grupās un no katras grupas ir iespējams izvēlēties tikai vienu.
 Salikta mugursoma (): ir dažas mugursomas, katras ar savu maksimālo svaru. Katru priekšmetu var vai nu atstāt, vai nu ievietot jebkurā mugursomā.
 Daudzdimensiju mugursoma (): svaru vietā ir doti dažādi resursi, piemērām, svars, tilpums un kraušanas laiks. Katrs priekšmēts tērē iepriekš noteikto resursa summu. Jāizvēlās priekšmētu apakškopu tā, lai katra resursu kopējās izmaksas neparsniedza šī resursa maksimumu, pie tām lai priekšmetu kopēja vērtība būtu maksimāla.
 Kvadrātiskā mugursomas problēma (): kopējā vērtība ir noteikta ar nenegatīvu kvadratīsko formu.

Pielikumi 
Nav zināms, kurš tieši formulēja matemātisko formulu mugursomas problēmai. Viens no pirmiem, kuri to pieminēja, bija Džordžs Ballards Metjūss savā rakstā 1897. gadā. Šīs problēmas intensīva pētīšana iesākas pēc D.B. Danciga 1957. gadā savā grāmatā «». It īpaši 70 – 90 gados, 20. gadsimtā, to sāka pētīt gan teorētiķi, gan praktiķi. Lielu interesi pret uzdevumu izraisa tas, ka nosacījumi bija viegli formulēti, uzdevumam bija varākas variācijas un tā risinājums nebija elementārs. 1972. gadā uzdevums par mugursomu tika iekļauts K.Menninga NP-pilnu uzdevumu skaitā.

Uzskatāma uzdevuma interpretācija veicināja , ka to iesāka izmantot dažadās zināšanu jomās: matemātikā, informātikā un šo zinātņu salaidē – kriptogrāfijā. Vienā no matemātiskas lingvistikas darbiem bija piedāvāta automātiskās tekstu referēšanas uzdevums, kura īpašs gadījums atbilst mugursomas uzdevuma formulējumam.

Balstoties uz uzdevumu par mugursomu tika izveidots pirmais asimetriskās šifrēšanas algoritms.

Mugursomas problēma kriptogrāfijā 
1978. gadā Ralfs Merkls un Martins Hellmans izstrādāja pirmo algoritmu vispārējai šifrēšanai izmantojot  publisko atslēgu - Merkļa-Hellmaņa kriptosistēmu. Viņi uzbūvēja to balstoties uz mugursomas problēmu. Viņi publicēja vienpakāpju (angl. singly-iterated) un daudzpakāpju versijas un algoritmu varēja izmantot tikai šifrēšanai. Tomēr Adi Šamirs pielāgoja to arī digitālo parakstu izmantošanai.

Vēlāk tika izveidoti daudzas Merkļa-Hellmaņa kriptosistēmas modifikācijas, ka arī pavisam jaunie kriptosistēmas, kuri balstījas uz mugursomas problēmu. Starp tiem ir:
 Greihama-Šamira mugursoma.
 Gudmana - Makkolija mugursoma.
 Nakaša-Šterna mugursoma.
 Šora-Rivesta mugursoma.

Šifrēšana izmantojot mugursomas problēmu 
Risinājuma sarēžģitība ļauj šifrēt pārraidāmos ziņojumus kā risinājumu mugursomas problēmai.

Definīcija. Mugursomas vektoru    sauksim par sakārtotu priekšmeta kopu n, kur  - priekšmeta  svars.

Lai nošifrētu tekstu, to sadala blokos  bitu garumā (piemērām, atklāts teksts  atbilst četru priekšmetu klātbūtnei no sešiem iespējamiem). Tiek uzskatīts, ka 1 uzrāda uz priekšmēta klātbūtni mugursomā un 0 uz to prombūtni.

Pēc tam tiek uzskatīts kopējais priekšmetu svars mugursomā un tas tiek padots kā šifrēts teksts.

Piemērs šifrēšanai ar šo algoritmu:

Pieņemsim, ka ir uzdots mugursomas vektors  ar garumu .

Konkrētajām  eksistē skaitļi, kuri nepārsniedz 41, t.i. kopējais priekšmetu svars mugursomas vektorā.

Praksē, šifrēšanai ir nepiecešama pieaugstinoša mugursoma, t.i. sakārtoti mugursomas vektora elementi ir pieaugstinoši. Tādā gadījumā katram atklātam tekstam eksistē tikai viens sašifrēts teksts. Dotajā piemērā mugursoma nav pieaugstinoša - ir iespējams saņemt to pašu sašifrētu tekstu 100010 un 001100 vektoriem.

Kriptogrāfija