Konspektai

Diskrečioji matematika - kombinatorika

10   (1 atsiliepimai)
Diskrečioji matematika - kombinatorika 1 puslapis
Diskrečioji matematika - kombinatorika 2 puslapis
Diskrečioji matematika - kombinatorika 3 puslapis
Diskrečioji matematika - kombinatorika 4 puslapis
Diskrečioji matematika - kombinatorika 5 puslapis
Diskrečioji matematika - kombinatorika 6 puslapis
Diskrečioji matematika - kombinatorika 7 puslapis
Diskrečioji matematika - kombinatorika 8 puslapis
www.nemoku.lt
www.nemoku.lt
Aukščiau pateiktos peržiūros nuotraukos yra sumažintos kokybės. Norėdami matyti visą darbą, spustelkite peržiūrėti darbą.
Ištrauka

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: XY. Teorema. Jei |X|=n, |Y|=m, tai visų galimų funkcijų f: XY 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 mmm...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 mn (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: XY 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: XY, |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ą

Daugiau informacijos...

Šį 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!

Detali informacija
Darbo tipas
Lygis
Universitetinis
Failo tipas
Word failas (.doc)
Apimtis
8 psl., (1679 ž.)
Darbo duomenys
  • Kombinatorikos konspektas
  • 8 psl., (1679 ž.)
  • Word failas 111 KB
  • Lygis: Universitetinis
www.nemoku.lt Atsisiųsti šį konspektą

www.nemoku.lt Panašūs darbai

www.nemoku.lt Kiti darbai

Tikimybių teorija egzaminui

Tikimybių teorija egzaminui Kombinatorika Peržiūrėti darbą

Atsitiktiniai vyksmai

Atsitiktiniai vyksmai Kombinatorika Peržiūrėti darbą

Diskrečioji matematika - kombinatorika

Diskrečioji matematika - kombinatorika Kombinatorika Peržiūrėti darbą

Kombinatorikos algoritmai: nedvišalė personalo užduotis

Kombinatorikos algoritmai: nedvišalė personalo užduotis Kombinatorika Peržiūrėti darbą

Kombinatorikos uždaviniai su sprendimais

Kombinatorikos uždaviniai su sprendimais Kombinatorika Peržiūrėti darbą

Įvykių tikimybės. Atsitiktiniai dydžiai ir statistika

Įvykių tikimybės. Atsitiktiniai dydžiai ir statistika Kombinatorika Peržiūrėti darbą

Tikimybių teorijos platus pasiruošimas egzaminui

Tikimybių teorijos platus pasiruošimas egzaminui Kombinatorika Peržiūrėti darbą

Kėliniai. Gretiniai. Deriniai

Kėliniai. Gretiniai. Deriniai Kombinatorika Peržiūrėti darbą

Kombinatorikos ir grafų teorijos medžiaga

Kombinatorikos ir grafų teorijos medžiaga Kombinatorika Peržiūrėti darbą

Atsitiktiniai įvykiai

Atsitiktiniai įvykiai Kombinatorika Peržiūrėti darbą

Galimybių medis ir kombinatorikos daugybos taisyklė

Galimybių medis ir kombinatorikos daugybos taisyklė Kombinatorika Peržiūrėti darbą

Atsitiktiniai įvykiai - teorija

Atsitiktiniai įvykiai - teorija Kombinatorika Peržiūrėti darbą
Privalumai
Pakeitimo garantija Darbo pakeitimo garantija

Atsisiuntei rašto darbą ir neradai jame reikalingos informacijos? Pakeisime jį kitu nemokamai.

Sutaupyk 25% pirkdamas daugiau Gauk 25% nuolaidą

Pirkdamas daugiau nei vieną darbą, nuo sekančių darbų gausi 25% nuolaidą.

Greitas aptarnavimas Greitas aptarnavimas

Išsirink norimus rašto darbus ir gauk juos akimirksniu po sėkmingo apmokėjimo!

Atsiliepimai
www.nemoku.lt
Dainius Studentas
Naudojuosi nuo pirmo kurso ir visad randu tai, ko reikia. O ypač smagu, kad įdėjęs darbą gaunu bet kurį nemokamai. Geras puslapis.
www.nemoku.lt
Aurimas Studentas
Puiki svetainė, refleksija pilnai pateisino visus lūkesčius.
www.nemoku.lt
Greta Moksleivė
Pirkau rašto darbą, viskas gerai.
www.nemoku.lt
Skaistė Studentė
Užmačiau šią svetainę kursiokės kompiuteryje. :D Ką galiu pasakyti, iš kitur ir nebesisiunčiu, kai čia yra viskas ko reikia.
Palaukite! Šį darbą galite atsisiųsti visiškai NEMOKAMAI! Įkelkite bet kokį savo turimą mokslo darbą ir už kiekvieną įkeltą darbą būsite apdovanoti - gausite dovanų kodus, skirtus nemokamai parsisiųsti jums reikalingus rašto darbus.
Vilkti dokumentus čia:

.doc, .docx, .pdf, .ppt, .pptx, .odt