Diskrečioji matematika 8 Kombinatorika Kombinatorikos apibrėžimas Kombinatorika – matematikos sritis, apimanti aibių elementų išrinkimo ir išdėstymo pagal tam tikras taisykles uždavinių sprendimą. Taisyklėmis nurodoma, kaip iš pradinės elementų aibės sukurti tam tikrą konstrukciją – vadinamąją kombinatorinę konfigūraciją. Kombinatorikos, panašiai kaip grafų teorijos, vystymasis kažkuria dalimi buvo skatinamas noro išspręsti galvosūkius. Pvz., Senųjų Rytų galvosūkis apie magiškąjį kvadratą, kurio kraštinės ilgis n, galėtų būti traktuojamas kaip kombinatorikos uždavinys: n2 natūrinių skaičių reikia išdėstyti taip, kad eilučių, stulpelių ir įstrižainių sumos būtų lygios. Pvz, kai n=3 toks kvadratas būtų 4 9 2 3 5 7 8 1 6 Dėstinių skaičiavimas Paruošta pagal В. Липский knygą "Комбинаторика длиа програмистов", Мир, Москва 1988 Šioje paskaitoje nagrinėsime pagrindinius kombinatorikos uždavinius (kurie bus gerokai paprastesni, negu prieš tai pateiktasis magiškojo kvadrato uždavinys). Sakykime duotos dvi aibės: X sudaryta iš n elementų ( |X|=n ) ir aibė Y sudaryta iš m spalvų ( |Y|=m). Spręsime klausimą, keliais būdais galima nuspalvinti aibės X objektus. Tarkime X={, , }, Y={juoda, balta}. Galimi spalvinimo variantai: • • Matematiškai į sprendžiamąjį uždavinį galima žiūrėti taip: duotos aibės X ir Y, |X|=n, |Y|=m. Kiek egzistuoja funkcijų f: XY. Teorema. Jei |X|=n, |Y|=m, tai visų galimų funkcijų f: XY skaičius yra mn. Teorema įrodoma "apmąstant" spalvinimo procesą: • pirmą objektą galime spalvinti bet kuria iš m spalvų; • antrą objektą, nepriklausomai nuo pirmojo, vėl galime spalvinti viena iš m spalvų; • ir t.t. Galimybių iš viso yra mmm...m (iš viso dauginame n kartų) kas lygu mn. Mūsų pavyzdžio atveju yra 23 galimybių. Į kombinatorikos uždavinių sprendimą galima žiūrėti, kaip į vienokių ar kitokių medžių konstravimą. Norėdami rasti kombinacijų skaičių, skaičiuojame medžio "lapus" (t.y. tas šakas, kurios toliau nebesišakoja). Pavyzdžiui su 3 objektais ir dviem spalvom medis būtų toks: Nagrinėtosios kombinacijos vadinamos dėstiniais. Galite šį pavadinamą sau susieti su kita to paties uždavinio interpretacija: n elementų reikia išdėstyti į m dėžių, ir klausiame, keliais skirtingais būdais tai galima padaryti. Perstatymų skaičiavimas Spręskime kitą uždavinį. Tarkime įvedamas ribojimas, jog į kiekvieną dėžę galima dėti tik po vieną objektą. Klausiama, kiek ir kokių skirtingų sprendinių gali turėti šis uždavinys. Taip kaip ir pirmajame uždavinyje, |X|=n, |Y|=m, tačiau šiuo atveju turi būti mn (t.y., dėžių turi būti daugiau, nei objektų), jei norime, kad uždavinys apskritai turėtų sprendinių. Skaičiuokime sprendinius: • pirmąjį objektą galime dėti į bet kurią iš m dėžių; • antrąjį objektą galime dėti į bet kurią iš likusių tuščių m–1 dėžių; ... • paskutinįjį objektą galime dėti į vieną iš m–n+1 dėžių. Uždavinio sprendinius vadinsime perstatymais, o sprendinių skaičių žymėsime [m]n. Jis apskaičiuojamas: [m]n=m(m–1)(m–2)...(m–n+1)=m!/(m–n)! Ar tas skaičius yra didesnis, ar mažesnis už prieš tai nagrinėtą dėstinių skaičių? mn>m(m–1)(m–2) ... (m–n+1). Imkime pavyzdį. Ar tiks ankstesnis pavyzdys su 3 figūrom ir 2 spalvom? – netiks. Tarime turime figūrų aibę X={, , } ir 3 spalvas: balta, pilka, juoda. Galimos tokios kombinacijos: Kombinatorinis medis: Uždavinio sprendiniai, kai m=n, vadinami perstatymais. Pavadinimas susijęs su dėstymo į dėžes interpretacija. Tarkime turime n objektų, ir n vietų objektams padėti (dėžių). Sprendžiamas klausimas, keliais skirtingais būdais objektus galima sudėti į dėžes. Pvz., objektai "a", "b", "c", o vieta – eilės numeris sekoje. Galimos 6 sekos: abc acb bac bca cab cba Matematiškai uždavinys gali būti formuluojamas, kaip visų abipus vienareikšmių funkcijų f: XY radimas. Kuriam iš nagrinėtųjų NPC uždavinių tinka toks perrinkimo būdas? • Hamiltono ciklo radimui; • Keliaujančiojo prekeivio uždaviniui. Kiek yra galimų perstatymų, jei turime n objektų? – n! (n faktorialas). Ne visus kombinatorikos uždavinius įmanoma išspręsti, sukuriant trumpą gražią išraišką kombinacijų skaičiui. Jei trumpa išraiška neegzistuoja – tada konstruojame loginių galimybių medį ir skaičiuojame "lapus". Loginių galimybių medžio konstravimas – universalus būdas kombinatorikos uždavinių sprendimui. Nereguliarūs kombinatorikos uždaviniai. Kombinatoriniai medžiai Specialiai paimkime nereguliarų uždavinį, kuriam trumpa kombinacijų skaičiaus išraiška neegzistuoja. Į šalies rinktinę kviečiami 7 nauji nariai: 4 jų iš klubo A ir 3 iš klubo B. Nauji nariai į komandą įtraukiami po vieną, ir tik tokia tvarka, kad klubo A atstovų rinktinėje visada būtų daugiau, nei klubo B atstovų. Kiek galimybių yra rinktinei plėsti (turima mintyje visos pagal nurodytus ribojimus galimos "A" ir "B" sekos)? Tvarkingas objektų išdėstymas į dėžes Grįžtame prie "lengvai" (trumpa išraiška) išsprendžiamų kombinatorikos uždavinių – tvarkingo objektų išdėstymo į dėžes skaičiaus radimo. Teorema. tarkime X – objektų aibė, Y – dėžių aibė, |X|=n, |Y|=m. Objektus tvarkingai išdėstyti į dėžes galime [m]n=m(m+1)...(m+n–1) skirtingais būdais. Įrodymas, vėlgi, susijęs su dėjimo į dėžes proceso modeliavimu: • Pirmą objektą galime dėti į m skirtingų dėžių; • Antrą objektą galime dėti į m–1 tuščią dėžę, arba į dėžę, kurioje yra pirmasis objektas, prieš tą objektą ar po jo; iš viso yra m+1 galimybė; ... Čia pateikta tik įrodymo idėja, pilnas įrodymas nepateikiamas. Ar tvarkingo išdėstymo variantų daugiau, nei netvarkingo išdėstymo variantų? Turėtų būti daugiau, pagal sveiką protą, o ir matematika sako tą patį: m(m+1)...(m+n+1)>mn Šis uždavinys būtų dar pasunkintas, jei kiekvienos dėžės tūris būtų ribotas. Galimų kombinacijų būtų mažiau, tačiau suskaičiuoti, kiek tokių kombinacijų egzistuoja būtų sudėtingiau (reikėtų sudėtingesnės formulės). Deriniai A. Dydžio m deriniu vadinamas bet koks m elementų poaibis iš n elementų aibės. n elementų aibės visų m elementų poaibių skaičius žymimas . Matematikoje skaičiai dažnai sutinkami, ir kitaip dar vadinami binominiais koeficientais, nes kaip tik tokie koeficientai atsiranda, skleidžiant n-ojo laipsnio binomą: . Iš kur tokie koeficientai skleidinyje atsiranda? Turime n sumų, o skaičiuodami sandaugą iš kiekvienos galime rinktis x arba jo nesirinkti, t.y. rinktis y. Kiek kartų iš n skirtingose sumose esančių x-ų galime pasirinkti, sakykime, 3 x-us, tiek ir bus narių x3yn–3. Arba, kitaip interpretuojant, į pirmą dėžę dedame tuos daugiklius, iš kurių imame x, į antrą tuos, iš kurių imame y. Teorema. Priimkime be įrodymo. Galime pastebėti, kad derinių iš n po m yra mažiau, nei vienareikšmių funkcijų f: XY, |X|=n, |Y|=m. Binominiai koeficientai turi daug įdomių savybių: – visų poaibių n elementų aibėje skaičius; ; – kiekvienam k elementų poaibiui vienareikšmiškai atitinka n–k elementų poaibis; . Paskutinioji lygybė paaiškinama taip: visi poaibiai susikirstomi į tuos, kuiuose nėra kažkurio elemento x (jų skaičių nurodo pirmas sumos dėmuo) ir tuos, kuriuose elementas x yra (jų skaičių nurodo antrasis dėmuo). Paskutinioji lygybė yra rekurentinė išraiška, pagal kurią galima apskaičiuoti binominius koeficientus, pradedant nuo pradinių koeficientų: ; ; . Koeficientus galima skaičiuoti, naudojantis Paskalio trikampiu. n=0 1 k=0 (įstrižai) n=1 1 1 k=1 (įstrižai) n=2 1 2 1 k=2 (įstrižai) n=3 1 3 3 1 k=3 (įstrižai) . . . Koši lygybė: Interpretacija – k žmonių išrinkimas iš m vyrų ir n moterų grupės. Tarkime s – išrinktų vyrų skaičius, k–s išrinktų moterų skaičius. Be poaibių iš k elementų išrinkimo, dar svarbus kombinatorikos uždavinys yra n elementų skaidymas į daugiau negu 2 poaibius. Spręsti tokį uždavinį prireiktų, pavyzdžiui, randant (x+y+z)n skleidinio koeficientus. Poaibių generavimas Iki šiol tik skaičiavome, kiek yra vienokių ar kitokių kombinacijų. Toks skaičiavimas gali būti naudingas, nagrinėjant algoritmų sudėtingumą arba skaičiuojant tikimybes (pvz, tikimybę išmesti skaičių seką 1,2,3,4,5,6, metant kauliuką šešis kartus). Tačiau dažniau reikia ne tik rasti kombinacijų skaičių, bet ir pageidaujamas kombinacijas išvardinti. Tarkime turime aibę |X|=n. Visų jos poaibių skaičius 2n. Reikia išvardinti visus poaibius. Pirmiausia įsitikinkime, kad visų poaibių skaičius tikrai 2n. Išrikiuokime aibės elementus kuria nors tvarka. Kiekvieną aibės poaibį Y atitiks dvejetainė seka b1, b2, ..., bn, tokia, kad Jau įrodėme, kad dvejetainių n ilgio sekų skaičius bus 2n (|Y|=n, m=2), taigi, tiek pat bus ir aibės poaibių. Beje, aibės poaibius kompiuteryje yra patogu vaizduoti dvejetainėmis sekomis. Vaizdavimo metodas "pasiūlo" ir visų aibės poaibių išvardinimo mechanizmą. Ar turėjome uždavinį NPC uždavinių tarpe, kurio sprendimui reikėtų perrinkti visus aibės poaibius? – Poaibio sumos uždavinys; kuprinės uždavinys. Algoritmas poaibių išvardinimui būtų toks: pradėjęs nuo nulio suki ciklą iki 2n–1, kiekvieną kartą pridėdamas 1. Gautą skaičiuką kiekviename ciklo apsisukime pervedi į dvejetainį vaizdavimo būdą ir pagal gautąją dvejetainę eilutę nustatai, kurie elementai įeina į poaibį, kurie neįeina. k elementų poaibių iš n elementų aibės generavimas Tarkime aibė yra X={1,2,...,n}. Algoritmo darbinis kintamasis bus masyvas A, tačiau aibės X jis pilnai neatstovaus, jo elementai algoritmo bėgyje keisis. poaibių_generavimas(k) begin for i=1 to k do A[i]=i; //inicializavimas p=k; while p>=1 do begin write(A[1],A[2],...A[k]); if A[k]=n then p=p–1 else p=k; if p>=1 then for i=k downto p do A[i]=A[p]+i–p+1; end end end. Algoritmo veikimo esmė: tarkime turime seką
Šį darbą sudaro 1679 žodžiai, tikrai rasi tai, ko ieškai!
★ 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!
Norint atsisiųsti šį darbą spausk ☞ Peržiūrėti darbą mygtuką!
Mūsų mokslo darbų bazėje yra daugybė įvairių mokslo darbų, todėl tikrai atrasi sau tinkamą!
Panašūs darbai
Kiti darbai
Atsisiuntei rašto darbą ir neradai jame reikalingos informacijos? Pakeisime jį kitu nemokamai.
Pirkdamas daugiau nei vieną darbą, nuo sekančių darbų gausi 25% nuolaidą.
Išsirink norimus rašto darbus ir gauk juos akimirksniu po sėkmingo apmokėjimo!