Kombinatorikos teorija

Kombinatorika 1. Bendrieji kombinatorikos dėsniai: sumavimo, sandaugos, priskirties ir išskirties (pagal pvz.). Sumavimo dėsnis Jei kokiam nors objektui A pasirinkti yra m būdų, o kitam objektui B pasirinkti yra n būdų, tai pasirinkti “arba A, arba B” yra m + n būdų. Pastaba. Taikant taip suformuluotą sumavimo dėsnį, reikia žiūrėti, kad nei vienas objekto A pasirinkimo būdas nesutaptų su kuriuo nors objekto B pasirinkimo būdu. Jei tokių sutapimų yra k, tai susidaro m + n – k pasirinkimo būdų. Pavyzdys. Pintinėje yra 12 obuolių ir 10 apelsinų. Jonukas pasirenka arba obuolį, arba apelsiną, o paskui Onutė ima ir obuolį, ir apelsiną. Keliais būdais Jonukas gali paimti vaisių ir kada Onutei didesnė pasirinkimo laisvė: ar kai Jonukas paima obuolį, ar kai apelsiną? Aišku, kad Jonukas obuolį gali pasirinkti 12 skirtingų būdų, o apelsiną – 10 skirtingų būdų. Vadinasi, pasirinkti arba obuolį, arba apelsiną galima 12 + 10 = 22 būdais. Į antrą klausimo dalį atsakysime po sandaugos dėsnio. Sandaugos dėsnis Jei objektui A pasirinkti yra m būdų, o po kiekvieno tokio pasirinkimo objektą B galima pasirinkti n būdais, tai porą (A, B) pasirinkti nurodytąja tvarka galima m  n būdais. Pavyzdys. Panagrinėkime aukščiau pateiktą pavyzdį. Tarkime, Jonukas pasirinko obuolį. Tada Onutei galimų pasirinkimo būdų yra 11  10. Jei Jonukas būtų pasirinkęs apelsiną, tai Onutei paimti ir obuolį, ir apelsiną būtų galima 12  9 būdais. Kadangi 11  10 > 12  9, tai Onutei didesnė pasirinkimo laisvė bus tada, jei Jonukas pasirinks obuolį. Priskirties ir išskirties dėsnis Sakykime, kad kai kuriems iš N turimų daiktų būdingos savybės . Simboliu pažymėkime skaičių daiktų, turinčių savybes (į kitas tų daiktų savybes nekreipiame dėmesio). Jei reikės pabrėžti, kad imami tik tie daiktai, kurie neturi kurios nors savybės, tai tą savybę rašysime su brūkšneliu. Pavyzdžiui, žymi skaičių daiktų, turinčių savybes ir , bet neturinčių savybės (į kitas jų savybes nekreipiame dėmesio). Tada priskirties ir išskirties dėsnis bus užrašomas taip: Įrodymas. Šį dėsnį įrodysime pilnosios matematinės indukcijos metodu. Dėsnis teisingas, kai kiekvienas daiktas turi savybę . Tada . Tarkime, kad dėsnis teisingas, kai savybių skaičius lygus : (1) Įrodysime, kad dėsnis teisingas, kai savybių skaičius yra n. (1) formulę taikykime daiktų aibei. Gausime: (2) Iš (1) lygybės atėmę (2), gausime (3) (3) formulės kairiosios pusės skirtumas yra lygus , nes iš skaičiaus daiktų, kurie neturi savybių atimame skaičių daiktų, neturinčių tų pačių savybių ir turinčių savybę . Vadinasi, atėmus liks skaičus daiktų, neturinčių savybių . Pavyzdys. Pasinaudodami priskirties ir išskirties formule, apskaičuokime, kiek tarp natūraliųjų skaičių nuo vieneto iki 100 yra skaičių, kurie nesidalo nei iš 2-jų, nei iš 3-jų, nei iš penkių. Tarkime, – tai skaičiaus savybė dalintis iš 2-jų, – tai skaičiaus savybė dalintis iš 3-jų, o – tai skaičiaus savybė dalintis iš 5-ių. Tada Norint sužinoti, kiek skaičių nuo 1 iki N dalijasi iš n, reikia N padalinti iš n ir imti gautojo dalmens sveikąją dalį į mažesniąją pusę. Todėl , , , , , , . Vadinasi, . 2. Junginių generavimo algoritmai: bendra junginių generevimo algoritmo schema, derinių generavimas leksikografine tvarka (paaiškinti); kėlinių generavimas leksikografine tvarka (per pvz. su teorijos elementais: kaip rasti mažiausią kėlinį (derinį) leksikografiškai didesnį nei duotas). Optimali tokių objektų generavimo algoritmo struktūra yra: begin generuoti pradinį junginį (kombinatorinį objektą); while “generavimo sąlyga” do begin nagrinėti (spausdinti) junginį (kombinatorinį objektą); generuoti junginį (kombinatorinį objektą), gretimą išnagrinėtam (atspausdintam). end; end; Priklausomai nuo pasirinktų objektų bei jų generavimo tvarkos, šiame algoritme turi būti konkretizuoti sakiniai “generuoti pradinį junginį”, “generavimo sąlyga”, “generuoti gretimą junginį”. Derinių generavimas leksikografine tvarka Pirmiausia aptersime derinių generavimo leksikografine didėjimo tvarka algoritmą. Čia priminsime, kad jei į derinį žiūrėsime kaip į skaičių, tai deriniams atitinkantys skaičiai bus išdėstyti didėjimo tvarka. Pavyzdys. Panagrinėkime . Deriniai, surašyti leksikografine tvarka, bus: 123, 124, 125, 134, 135, 145, 234, 235, 245, 345. Derinius nuosekliai talpinsime masyve ir šio masyvo elementai apibrėš derinį. Pradinio derinio generavimas. Aišku, kad pradinis derinys generuojamas taip: for l := 0 to k do c [l] := l; Kaip generuoti patį mažiausią leksikografiškai didesnį derinį nei turimas? Tarkime, – turimas derinys. Leksikografine tvarka pats didžiausias derinys yra: . Vadinasi, , . todėl, norint apskaičiuoti patį mažiausią leksikografiškai didesnį derinį nei nagrinėjamas derinys, elgsimės taip: 1) masyve rasime pirmą iš dešinės elementą cl, , tenkinantį sąlygą ; 2) šį elementą padidinsime vienetu, t.y. ; 3) likusius elementus užpildysime iš eilės einančiais natūraliaisiais skaičiais, t.y. for i := l + 1 to k do ci: = ci-1 + 1; Generavimo pabaigos sąlyga. Jei pirmasis iš dešinės elementas, tenkinantis sąlygą , yra , tai reiškia, kad nagrinėjame derinį: . Vadinasi, jau visi deriniai sugeneruoti. Tuo būdu, derinių generavimo leksikografine tvarka algoritmas yra. Derinių skaičiaus apskaičiavimo algoritmas Duota: n – objektų skaičius, k – objektų skaičius derinyje. Rasti: generuoti derinius leksikografine tvarka. begin { c [0..k] – masyvas, kurio elementai nusako derinį } for l := 0 to k do c [l] := l; { Pradinio derinio generavimas } p := true; { Generavimo sąlyga } while p do begin spausdinti derinį ; { Generuoti leksikografiškai didesnį derinį } l := k; while (l >= 1) and c [l] >= n – k + l do l := l – 1; if l = 0 then p := false else begin c [l] := c [l] + 1; for i := l + 1 to k do c [i] := c [i – 1] + 1; end; end; { while p } end; Kėlinių generavimo leksikografine tvarka algoritmas Aptarsime kėlinių iš n elementų generavimo leksikografine tvarka uždavinį. Spręsdami šį uždavinį, laikysime aukščiau pateiktos (žr. 3.4 paragrafo pradžią) kombinatorinų objektų generavimo algoritmo struktūros. Norėdami išsiaiškinti šio algoritmo pagrindinius momentus, panagrinėkime pavyzdį, kai . Pradinio kodo generavimas. Kėlinį talpinsime masyve , kurio elementai ir nusako kėlinį. Aišku, kad pradinis kėlinys yra . Pavyzdžiu, jei , tai . Paties mažiausio, leksikografiškai didesnio kėlinio nei nagrinėjamas, apskaičiavimas. Tarkime, – nagrinėjamas kėlinys. Pavyzdžiui, . Jei į kėlinį žiūrėsime kaip į skaičių, tai reikia rasti patį mažiausią skaičių, didesnį nei nagrinėjamas. Tam tikslui reikia: 1) rasti pirmą iš dešinės porą tokią, kad , 2) rasti , t.y tarp elementų rasti patį mažiausią elementą, didesnį už , 3) elementus ir sukeisti vietomis, 4) elementus (“uodegą”) surašyti atvirkščia tvarka (“apversti”). Pavyzdžiui, pirmoji iš dešinės pora, tenkinanti 1) punkto reikalavimą, yra , o elementas . Tada, sukeitę 4 su 5, gausime . “Apvertę uodegą”, gausime patį mažiausią leksikografiškai didesnį kėlinį nei duotas: . Generavimo pabaigos sąlyga. Aišku, kad pats didžiausias kėlinys yra (masyvo elementas yra pagalbinis, ir jo reikšmė lygi nuliui). Tada pirma iš dešinės pora , tenkinanti sąlygą yra . Kitaip tariant, jei , tai generavimo pabaiga. Vadinasi, kėlinių generavimo leksikografine tvarka algoritmas gali būti užrašytas taip. begin fo i:= 0 to n do p [i] :=i; t := true; while t do begin spausdinti ; { Leksikografiškai didesnio kėlinio apskaičiavimas } i := n – 1; while p [i] > p [i+ 1] do i := i – 1; if i = 0 then t := false else begin { Rasti } j := n; while p [j] eps and not p do begin c := a+(b-a)/2 ; if F(a) * F(c) 0 then a := c else begin s:= c; p:= true end; end; if not p then s := (a+b)/ 2 end. Pusiaukirtos metodas visada konverguoja, jei tik F(x) intervale yra tolydžioji funkcija ir F(a) * F(b) 0 then xn := b else xn := a; while z > eps do begin xn1 :=xn - F(xn) / FI(xn); z := abs((xn1-xn) / xn1); xn := xn1 end; s := xn1; end. 3. Tiesinis algebros uždavinys: sistemos Ax=b sprendimas Gauso metodu (algoritmas); sąlygotumo skaičius ir jo prasmė; determinanto apskaičiavimas Gauso metodu (algoritmas); A-1 apskaičiavimas Gauso metodu (per pvz.). Tarkime, kad sprendžiame tiesinių lygčių sistemą ; čia A —n-tosios eilės kvadratinė matrica, x ir b — vektoriai stulpeliai. Išskleiskime duotąją sistemą: Gauso metodas susideda iš dviejų etapų: tiesioginio ir atvirkštinio. Tiesioginiame etape sistema perskaičiuojama į trikampę išraišką ; čia — viršutinė trikampė matrica. Atvirkštiniame etape nuosekliai, pradedant n-tąja lygtimi, apskaičiuojami . Tiesioginį etapą sudaro n – 1 žingsnis. k-tuoju žingsniu pirmosios k lygtys nekeičiamos, o iš lygčių pašalinamas kintamasis . Tam tikslui iš i-tosios () lygties atimama k-toji lygtis, padauginta iš tokio dau­giklio s, su kuriuo . Vadinasi, . Kiti i-tosios lygties koeficientai bei laisvasis narys perskaičiuojami pagal formules . Perskaičiuojant ir , apvali­ni­mo paklaidos mažiausios esti tada, kai s yra kuo mažesnis. Vadinasi, kiek­vie­na­me žingsnyje turi būti k-tojo stulpelio didžiausio modulio elementas, t. y. . Tai vadinamasis pagrindinio elemento parinkimo būdas. Tiesioginis etapas k-tasis žingsnis Atlikę k – 1 žingsnį, gauname lygčių sistemą 1) Randame k-tojo stulpelio didžiausio modulio elementą . l := k; for i := k to n do if abs(a[l,k])

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!