ITT0030 Diskreetne matemaatika II - eksamikonspekt (1)

Diskreetne matemaatika II
Suulise eksami konspekt
IABB 2011
[1]. Hulgad. Alam- ja ülemhulgad. Tehted hulkadega.
[2]. Hulga võimsus. Kontiinumhüpotees.
[3]. Järjendid. Permutatsioonid. Kombinatsioonid.
[4]. Binoomi valem. Pascali kolmnurk .
[5]. Liitmis - ja korrutamisreegel kombinatoorikas.
[6]. Kordustega permutatsioonid. Multinoomkordajad.
[7]. Elimineerimismeetod (juurde- ja mahaarvamise valem).
[8]. Korratused ja subfaktoriaalid.
[9]. Dirichlet ‘ printsiip.
[10]. Arvujadade genereerivad funktsioonid. Jadade ja genereerivate funktsioonide teisendamine .
[11]. n objekti jaotamine k gruppi.
[12]. Rekurrentsed võrrandid. Rekurrentsi lahendamine ad hoc meetodil ja iteratsioonimeetodil.
[13]. Tasandi tükeldamine n sirgega ja n nurgaga .
[14]. Lineaarsed rekurrentsed võrrandid.
[15]. Rekurrentsete võrrandite lahendamine genereerivate funktsioonide meetodil.
[16]. Fibonacci arvud. Üldliikme valem ja rakendused.
[17]. Lucas ‘ arvud.
[18]. Catalani arvud.
[19]. Sündmused ja tõenäosus. Statistiline tõenäosus. Bernoulli suurte arvude seadus.
[20]. Sõltuvad ja sõltumatud sündmused. Sündmuste summa ja korrutis.
[21]. Täistõenäosuse valem. Bayesi reegel.
[22]. Bernoulli valem (k katse õnnestumine katsete üldarvu n korral).
[23]. Kord- ja algarvud . Algarvude jaotus, algarvulisuse kontroll, Eratosthenese sõel.
[24]. Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne.
[25]. Fermat teoreem . Pseudoalgarvud ja Carmichaeli arvud.
[26]. Eukleidese algoritm .
[27]. Lineaarsed diofantilised võrrandid.
[28]. Täisarvude kongruentsid. Kongruentsi omadusi.
[29]. Moodularitmeetika.
[30]. Algarvulisuse Fermat‘ test. Miller -Rabini test.
[31]. Graafid ja graafide omadused. Ahelad ja tsüklid graafis.
[32]. Euleri graafid. Hamiltoni tsüklid.
[33]. Puud. Puude omadused.
[34]. Graafi vähima kaaluga aluspuud.
[35]. Märgendatud puud. Puude esitamine arvuti mälus.
[36]. Prüferi kood. Märgendatud puude loendamine . Cayley teoreem.
[37]. Märgendamata puude arv.
[38]. Kooskõlad graafis. Berge ’i teoreem.
[39]. Kooskõlad kahealuselises graafis. Halli teoreem.
[40]. Tasandiline graaf . Euleri valem: seos tasandilise graafi tippude, servade ja tahkude arvude vahel. Eulri valemi rakendusi.
[41]. Graafi tasandilisuse kriteeriumid. Kuratowski teoreem.
[42]. Graafi tippude värvimise ülesanne. Brooksi teoreem (tõestuseta).
[43]. Tasandilise lihtgraafi värvimine 6 ja 5 värviga. Neljavärviprobleem ja kaartide värvimine.
I. OSA
[1]. Hulgad. Alam- ja ülemhulgad. Tehted hulkadega.
Hulk on koosvaadeldavate objektide kogum.
*Eristatakse kaht erinvat hulgateooriat:

Naiivne hulgateooria - Naiivses hulgateoorias puudub kindel tugev aksiomaatika, ent ta on piisavalt efektiivne väga paljude lihtsamate vajaduste rahuldamiseks. Sageli õpetatakse matemaatikas esmalt naiivset hulgateooriat, kuna ta võimaldab inimesel paremini mõista hulga kontseptsiooni ning seda, miks aksioomid vajalikud on. Ka meie kasutasime kursuse raames naiivset hulgateooriat. Loojaks loetakse George Cantorit(19.saj.)
Aksiomaatiline hulgateooria- Kuna on teada, et naiivne hulgateooria jookseb väga paljudel juhtudel ummikusse (nt. Russeli „habemeajaja“ paradoks ), hakati alates 1908. hulgateooriat palju normeerima, mille tulemusel tekkiski aksiomaatiline hulgateooria. Aksiomaatilist hulgateooriat kasutatakse seal, kus on äärmiselt oluline vältida erinevaid hulgateoreetilisi paradokse või uurida teatavate matemaatiliste probleemide põhimõttelist lahenduvust/ mittelahenduvust.

*Võrdsed hulgad- Kahte hulka loeme võrdseks, kui nad koosnevad täpselt samadest elementidest. Elementide järjekord hulgas ei ole oluline.
*Alamhulk/ülemhulk- Hulka A nimetatakse hulga B alamhulgaks (e. osahulgaks), kui kõik hulga A elemendid sisalduvad ka hulga B koossesisus. Sellisel juhul on hulk B ka muuseas hulga A ülemhulk. Tähistaktakse:
ning .
Tehted:
Hulkade ühend- Kahe hulga ühendiks on „kõik hulga A elemendid + kõik hulga B elemendid“. (Tähistatakse ∪)
Hulkade ühisosa- Kahe hulga ühisosaks on „kõik elemendid, mis sisalduvad samaaegselt nii hulgas A kui ka hulgas B“. (Tähistatakse ∩)
Hulkade vahe- Kahe hulga vahe A/B on defineeritud kui „hulk, mis koosneb kõigist niisugustest elementidest, mis kuuluvad hulka A ent ei kuulu hulka B“ (Tähistatakse /)
Hulkade sümmeetriline vahe- Kahe hulga sümmeetriliseks vaheks on „kõik hulga A elemendid + kõik hulga B elemendid ilma nende ühise osata“ (Tähistatakse ∆)
[2]. Hulga võimsus. Kontiinumhüpotees.
Hulga võimsus- Lõpliku hulga võimsus on tema elementide arv. Hulga võimsust tähistavat sümbolit nimetatase ka hulga kardinaalarvuks.
*Lõpliku hulga kardinaalarv on selle hulga elementide arv, lõpmatute hulkade puhul kasutatakse aga eritähiseid: ℵ0 tähistab loenduvat võimsust, ℵ1 aga tähistab kontiinumvõimsust. (loendamatu)
*Võrdvõimsad hulgad- Kui kahes hulgas on ühepalju elemente ning nende elementide vahel saab luua üksühese vastavuse, on need kaks hulka võrdvõimsad. (Tähistatakse |A|=|B|)
* Loenduv hulk- Kui hulk on sama võimsusega nagu naturaalarvude hulk N, peetakse teda üldiselt loenduvaks. Loenduv hulk võib seega olla ka lõpmatu.
*Loendamatu hulk- Kui hulk on sama võimsusega nagu reaalarvude hulk IR, peetakse teda loendamatuks. Tänu komakohtadele pole elemente lihtsalt võimalik ammendavalt loetleda.
Kontiinumhüpotees- Kontiinumhüpotees on hüpotees, mille arendajaks oli George Cantor (aastal 1877 ) ning see puudutab lõpmatute hulkade võimalikke suurusi.
*Hüpoteesis eristatakse nö. „väiksema võimsusega lõpmatut hulka“, milleks on naturaalarvude hulk N ning „suurema võimsusega lõpmatut hulka“, milleks on reaalarvude hulk R.
*Hüpotees väidab, et ei leidu ühtki sellist lõpmatut hulka, mis oma võimsuse poolest jääks nende „väikse lõpmatu hulga“ ning „suure lõpmatu hulga“ vahele.
Lisaks: Hulga astmehulgaks nim. hulga kõikide alamhulkade hulka. Hulga astmehulga võimsus on |P(A)|=2n
*Hiljem on märgitud, et aksiomaatilise hulgateooria baasil ei ole Cantori väidet võimalik ei tõestada, ega ka ümber lükata.
[3]. Järjendid. Permutatsioonid. Kombinatsioonid.
Järjendid e. korteezid e. ennikud- n-elemendilise hulga elementidest moodustatud k-kohalist järjestatud loendit nimetatakse järjendiks.
*Kaks järjendit on võrdsed vaid siis, kui nad on sama pikad ning nende vastavates positsioonides on samad väärtused. Järjendi puhul on oluline temas sisalduvate elementide järjestus. (Nt. hulk [3] järjendeid on 9: 11,12,13,21,22,23,31,32,33)
Permutatsioonid-
n-permutatsioonideks nimetatakse järjendeid, mis on mingi lõpliku hulga A kõikkide elementide n kõikvõimalikud ümberpaigutused. (n!)
k-permutatsioonideks nimetatakse järjendeid, mis on mingi lõpliku hulga A teatud alamhulga elementide kõikvõimalikud ümberpaigutused. k-permutatsioone nim. ka variatsioonideks. (Nt. hulk[3] 1-permutatsioonid: 1,2,3)
*Arvutada saab: n-permutatsioone Pn = n! ning k-permutatsioone
Kombinatsioonid-
k-kombinatsiooniks nimetatakse hulga A igat k-elemendilist alamhulka. (Nt. hulk[3] 2-kombinatsioonid: {12,13,23}).
*Arvutada saab:
[4]. Binoomi valem. Pascali kolmnurk.
*Kombinatsioonide arvu tähist nimetatakse sageli ka binoomkordajaks. See tulenebgi aga (Newtoni) binoomivalemist.
Binoomi valem-Valem, mis esitub kujul , ning sisuliselt kujutab ta endast „summa ruudu valemit“ astmel n. Selgub aga, et binoomivalemi sulgude avamisega saame sellise üksliikmete summa, kus iga liikme kordaja e. binoomkordaja vastab sisuliselt kombinatsioonide arvule , kus k on konkreetse üksliikme x’i aste ning n on algse sulgavaldise aste. Näiteks:
Toetused aga multinoomvalemile, saaksime binoom -koefitsente välja arvutada ka valemi abil, kus k1 on üksliikme esimese kordaja aste, k2 aga teise kordaja aste.
Omadusi:
* Binoomkordajad on sümmeetrilised alumise indeksi suhtes:
Pascali kolmnurk- Pascali kolmnurk on prantsuse matemaatiku Blaise Pascali poolt loodud matemaatiline element, mis kujutab endast binoomkordajate massiivi, kus viimased on kõik seatud kolmnurksesse paigutusse. Kolmnurga tipuks on binoomkordaja kohal n = 0, allapoole minnes n’i väärtus aga aina kasvab.
Pascali kolmnurga omadusi:
*Ta on sümmeetriline vertikaaltelje suhtes.
*Iga arv Pascali kolmnurgas võrdub tema kohal olevate arvude summaga . (Seetõttu on mõningatel juhtudel teda väga mugav ülesannete lahendamisel kasutada).
* Ehkki binoomkordajate kolmnurkset asetust kirjeldas ametlikult esimesena Pascal , arvatakse, et ka paljud varasemad matemaatikud teadsid selle olemasolust.
[5]. Liitmis- ja korrutamisreegel kombinatoorikas.
Liitmisreegel - üks kahest kombinatoorika põhipostulaadist. Ta ütleb, et kui ühte objekti saab valida m erinval viisi ja teist objekti saab valida n erinval viisil, kusjuures esimese ja teise objekti valikud on teineteist välistavad, siis kas esimese või teise objekti valmiseks leidub täpselt m + n erinevat võimaust.
Korrutamisreegel- teine kombinatoorika põhipostulaat. Ta väidab, et kui ühte objekti saab valida m erineval viisil ja teist objekti saab valida n erineval esimesest valikust sõltumatul viisil, siis nii esimese kui ka teise objekti valimiseks on täpselt m*n erinvat võimalust kokku.
[6]. Kordustega permutatsioonid. Multinoomkordajad.
Kordustega permutatsioonid on sellised n-permutatsioonid, kus mingit hulga elementi a esineb n korda, kusjuures n > 1. (Tähistame )
Anagrammid:
*Nagu ka L.Lovasz’i õpikus näidatud oli, leiavad kordustega permutatsioonid sageli rakendust näiteks juhul, kui meil on vaja arvutada mingi sõna anagrammide arv.
*Et sageli ei ole mingis sõnas sisalduvad tähed kõik erinevad, ongi meil anagrammide leidmisel tegu kordustega permutatsioonidega.
*Sellisel juhul saame sõna anagrammide arvu leida järgneva valemi abil: Pnr = .
*Viimasest järeldub muuseas, et sõnal on enim anagramme, kui kõik tema tähed on erinevad, ning vähim anagramme, kui kõik tema tähed kattuvad.
*Eesti keeles kutsutakse seda valemit ka nö. Raamatupidaja reegliks.
Multinoomkordajad- Tuleks ära märkida, et sümbol
tähistab matemaatikas multinoomkordajat: see tähendab, et ta on multinoomi (X1 +.......+ Xk)n arenduses (sulgude avamisel) üksliikme e. mononoomi kordajaks. (analoogselt binoomi valemile).
Multinoomkordaja leidmine: Oletame et meil on valem (a + b + c)3 ning vaja on leida liikme a1b1c1 koefitsienti väärtust. Üheks võimaluseks on lahti korrutada avaldis (a + b +c)(a + b +c)(a + b +c), ning leida vastava kordaja väärtus. Lihtsam on aga kasutada multinoomi teoreemi, mis annab meile palju mugavamalt kätte mistahes liikme koefitsiendi, näiteks:
ning .
Binoomiteoreem ning binoom-koefitsiendid on sisuliselt vaid multinoomi valemi erijuht.
[7]. Elimineerimismeetod (juurde- ja mahaarvamise valem).
Elimineerimismeetod- Elimineerimismeetod on hulkade võimsuse notatsioonil põhinev, äärmiselt mugav vahend leidmaks mitme, üksteisega ühisosa omava hulga ühendit või ühisosa.
*Ilma konkreetse valemita oleks suure hulga ühisosa omavate hulkadega arvutamine äärmiselt tülikas. (Venni diagramme kasutades kaob ülevaade juba näiteks 4 hulga puhul). *Elimineerimismeetod on aga rakendatav praktiliselt kuitahes suure koguse hulkade korral.
*Elimineerimismeetodi valem avaldub üldkujul järgmiselt:
*Elimineerimismeetodil on rakendusi ka arvuteoorias: näiteks võimaldab ta meil lahendada ülesannet kujul: Kui palju on arve 1-2500, mis ei oma 2500’ga ühiseid tegureid? (e. on relatiivselt algarvulised 2500 suhtes).
*Vahetevahel on elimineerimismeetodit kirjanduses nimetatud ka Grassmanni valemiks (ka DM I kursuse raames).
[8]. Korratused ja subfaktoriaalid.
*Korratus on püsipunktideta permutatsioon. Püsipunktideta permutatsiooni puhul ei jää pärast elementide ümberjärjestamist ükski element oma endisele kohale.
(Nt. hulk[3] korratused on {312,231}).
*Muuseas nimetatakse n-korratuste arvu dn ka arvu n subfaktoriaaliks, ning seda tähistatakse sümboliga !n.
*Mingi arvu korratuste arvu dn on võimalik leida mitme keeruka valemi abil, ent neist kõige optimaalsem on tegelikult järgmine: dn = n! =
*Valemis leitakse esmalt avaldisest korratuste ligikaudne arv. Et aga tulemus pole täisarvuline, liidetakse sellele veel 0,5 ning siis rakendatakse floor funktsiooni. (E. taandatakse tulemus täisarvuni, „alumise“ väärtuseni).
[9]. Dirichlet‘ printsiip.
Dirichlet’ printsiip väidab, et kui n hulgas sisaldub rohkem kui n elementi, peab leiduma vähemat üks selline hulk, milles sisaldub enam kui 1 element.
*See, esmapilgul naeruväärselt triviaalne reegel, osutub sageli äärmiselt rakenduslikuks keeruliste väidete tõestamisel või ümberlükkamisel (nt. Eestis elavate inimeste juuksekarva probleem, püssilaskude omavahelise kauguse probleem märklauas jne.)
*Dirichlet’ printsiip leiab laia kasutust ka arvuteoorias.
*Dirichlet’ printsiipi tuntakse veel kui tuvipesaprintsiipi, laekaprintsiipi või Dirichlet’ sahtliprintsiipi. (Heal lapsel mitu nime )
[10]. Arvujadade genereerivad funktsioonid. Jadade ja genereerivate funktsioonide teisendamine.
Genereerivad funktsioonid on sellised astmeread, mille kordajad e. koefitsendid sisaldavad informatsioonina mõnda arvujada an.
Genereerivad funktsioonid on harilikult esitatud nö. suletud kujul(vastandina lahtisele astmereale): näidatud on vaid avaldis, mis defineerib rea saamiseks teatud tehete hulga (nende tehete sooritamisel saamegi astmerea, mille kordajateks on meile vajalikud väärtused). Tehniliselt on suletud kuju valem tuletatud geomeetrilise summa valemi järgi.
Suletud kuju kasutamine on kasulik selleks, et siis on vaade avaldisest palju ülevaatlikum ning veelgi enam, genereerivatele funktsioonidele defineeritud tehete rakendamine lihtsustub väga oluliselt (jadade liitmine , lahutamine, korrutamine jne).
*Astmereale defineeritud tehete hulgas võivad leiduda nii aritmeetilised operatsioonid nagu korrutamine, liitmine ja lahutamine, kuid ka differentseerimine: näiteks tuletised x’i suhtes. Samuti võib näiteks leiduda asendamisi teistesse funktsioonidesse.
Mõningaid näiteid genereerivatest funktsioonidest:
a).
(„võtme tähtsusega