katmiseks on mul # võimalust. 3) Kolmandat varianti pole. Seega kokku võimalusi: # = + #, mida tuligi näidata. Saadud rekurrentne seos erineb Fibonacci jadast üksnes algväärtuste poolest(# = 1 ja $ = 2), $ vastab % -le ja # $ -le. Järelikult W = ÜLESANNE 5 Hulgal {1,2, ..., n} on W = W + W + W sellist alamhulka, milles ei leidu kolme järjestikust arvu, kusjuures W = , W = , W = Põhjendus: Katsetan 1 3 J 3 5 korral. Tähistan sobivate alamhulkade arvu -ga. Vaatan ka " -i, sest teda on vaja rekurrentse seose kasutamisel. Diskreetne matemaatika II Kodused ülesanded 2 Olga Dalton 104493 IAPB21
Vastus: V V V 3. Väide $ $ $ on VÄÄR Põhjendus: Üldjuhul sisaldab A B rohkem elemente, kui igas hulgas on eraldi. Arvutades võrduse vasakut poolt saame omavahel paaridesse kombineerida ka hulga A elemente hulga B elementidega, mis annab rohkem eri kombinatsioone. Arvutades paremat poolt saame omavahel paaridesse kombineerida üksnes ühe hulga elemente ning lõpuks leiame nende alamhulkade hulkade ühendi. St võrreldes vasaku poolega kaotame sellised kombinatsioonid, kus üks element on pärit esimesest hulgast ja teine teisest. Diskreetne matemaatika II Kodused ülesanded 1 Olga Dalton 104493 IAPB21
ka 6 loengut topoloogia p˜ohim˜oistetest. K¨aesolev loengukons- pekt ongi nende kuue loengu u ¨mbert¨o¨otatud ja t¨aiendatud variant. Vormistatud on see eesm¨argiga, et tulevikus on se- minaride jaoks allikmaterjal, kust vajaduse korral tutvuda v˜oi tuletada meelde vajaminevaid topoloogia m˜oisteid. Autor 1 TOPOLOOGILINE RUUM 1.1 Topoloogilise ruumi definitsioon Olgu X mis tahes hulk ja P(X) tema k˜oigi alamhulkade hulk. Definitsioon 1.1 Hulga X alamhulkade hulka T ⊂ P(X) nimetatakse topoloogiaks hulgal X, kui T rahuldab j¨argmisi tingimusi: 10 ∅ ∈ T , X ∈ T ; 20 mis tahes koguses hulgast T v˜oetud hulga X alamhulkade ¨hend kuulub samuti hulka T (st T on kinnine u u ¨hendi v˜otmise suhtes); 30 l˜opliku arvu hulgast T v˜oetud hulga X alamhulkade u ¨his-
· Loenduva hulga iga lõpmatu osahulk on samuti loenduv. Cantor-Bernsteini teoreem Definitsioon Ütleme, et hulga A võimsus ei ületa hulga B võimsust, kui leidub injektsioon f : A B. Teoreem (Cantor-Bernsteini teoreem.) Kui hulga A võimsus ei ületa hulga B võimsust ja hulga B võimsus ei ületa, hulga A võimsust, siis hulgad A ja B on sama võimsusega. Teoreemi teine sõnastusvariant. Kui A B C ja A C, siis A B C. Teoreem Naturaalarvude hulga alamhulkade hulk on sama võimsusega nagu reaalarvude hulk, st P(N) R. Tõestuse idee. Piisab tõestada, et P(N) [0, 1). a) Naturaalarvude hulga igale alamhulgale A seame vastavusse reaalarvu 0,i0i1i2 . . . , kus ik = 1 või ik = 0 vastavalt sellele, kas k A või k 6 A. b) Reaalarvule x [0, 1) seame vastavusse alamhulga, mis sisaldab / ei sisalda 5
Deterministlik lõplik automaat on viisik: M = (Q(olekud), Σ(tähestik), δ(üleminekufunktsioon), q0(lähteolek), F(lõppolekud)). δ : Q × Σ → Q (mingi olek + sümbol tähestikust = uus olek) Mittedeterministlik lõplik automaat on viisik: M=(Q(olekud), Σ(tähestik), δ(üleminekufunktsioon), Q0(lähteolekud), F(lõppolekud)) δ : Q × Σε → P(Q) ükskõik mis tähe puhul või ka ilma sisendita (ε) läheb ühte Q kõigi alamhulkade hulgast. (üleminekufunktsiooni asemel on hoopis relatsioon) Olgu . Siis hulga A alamhulkade hulk on järgmine: Teoreem: Iga mittedeterministik automaat N=(Q, Σ, δ, Q0, F), mis aktsepteerib keelt A, on teisendatav sama keelt aktsepteerivaks deterministlikuks lõplikuks automaadiks M = (Q’, Σ, δ′, Q0′, F′). Kui mittedeterministlikul on k olekut, siis talle vastaval deterministlikul võib olla kuni 2k olekut. T: eeldame, et N-is pole ε-üleminekuid.
siis ei saa olla täisarvude ja reaalarvude vahel üks ühest vastavust. Seega reaalarvude lõpmatus on suurem kui täisarvude lõpmatus. Kontiinumhüpotees- Kas täisarvude ja reaalarvude vahel on veel lõpmatusi. Ei saa öelda, kas hüpotees on õige või vale. Cantori teoreem: reaalarvude hulk on suurem (võimsam) kui positiivsete täisarvude hulk. Hulgad on sama võimsad: Kui saad panna üksühesesse vastavusse. Igale A elemendile vastab täpselt üks B element ja vastupidi. Kõigi alamhulkade hulk on suurem kui hulk ise. Reaalarvude alamhulkade hulk on suurem kui reaalarvude hulk. Peatumisprobleem, selle lahendamatuse idee: Kontrollime, kas etteantud programm jääb seisma. Kui while ega rekursiooni pole, siis peatub. While korral interpretaator käima, lihtsamate korral saame teada, raskemate puhul ei tea, kas peatubki. 3n + 1 Collatz conjecture: Alati on peatunud, aga kuna arve on lõpmatult palju, siis ei saa kindel olla, et pole olemas olukorda, kus ta ei peatuks
Uuritakse lahendumise struktuuri, mis on kirjeldamatult keeruline Uuritakse loogikaklasside lahendumise taandumist muudele ülesannetele Kuidas lahendamatust näidata (plaan): Näitame, et algoritme on sama palju, kui täisarve (lihtne) Näitame, et probleeme on vähemalt sama palju, kui reaalarve (veidi keerulisem) Näitame, et reaalarve on lõpmatult rohkem kui täisarve (Cantori üks teoreeme) Cantori teoreem ütleb üldisemalt, et mingi hulga H kõigi alamhulkade hulk on suurema võimsusega kui see hulk H. Poollahenduvus Olgu ülesandeks tuvastada, kas täisarv X kuulub mingisse lõpmatusse täisarvude alamhulka H. Mõne H jaoks on ülesanne lahenduv: näiteks, kui H on paarisarvude hulk, kui H on algarvude hulk jne, Mõne H jaoks ülesanne ei ole lahenduv: näiteks, kui H on arvude hulk, millele vastavad programmid peatuvad. Poollahenduvus tähendab, et kui X juhuslikult kuulub hulka H, siis me saame seda algoritmiga alati näidata
väiksemvõrdne b). Seega pakub suurt huvi ka vähim sigma algebra, mis sisaldab kõiki osalõike. 3. Tõenäosuse aksiomaatiline definitsioon. Tõestada aksioomide põhjal, et tühja hulga tõenäosus on null. Tuletada liitmislause 2 sündmuse (liidetava) puhul Def: Olgu Ω mingi hulk, mille element ω me nimetame elementaarsündmuseks. Olgu S hulga Ω mingi alamhulkade hulk. Hulga S elemente nimetame juhuslikeks sündmusteks ja hulka Ω elementaarsündmuste ruumiks. Hulka S nimetame hulga Ω hulkade algebraks, kui 1) Ω∈ S 2) A∈S ja B∈S => AUB ∈ S ja AÜB ∈S ja A/B ∈S Tühja hulga tõenäosuse tõestamine: 1) P(∅) = 0 tõestus: on ilmne, et ∅+∅=∅ ja ∅*∅=∅. Seega P(∅) = P(∅+∅) = P(∅) + P(∅) => P(∅) = 0. Liitmislause: on selge, et A+B = AB + BA + AB ja (AB)AB = ∅; (BA)AB = ∅; (AB)(BA) = ∅
enesesarnaselt foo calls foo: * int foo(int x) { if (x>0) return 1+foo(x-1) else return 1} Salesman travel - 6 linna puhul 5*4*3*2*1=120 erinevat teed(N-1)! Reaalarvude hulk on suurem (võimsam) kui positiivsete täisarvude hulk. Reaalarvude hulk on suurem (võimsam) kui täisarvude hulk. N: 0 1 -1 2 -2 3 -3 4 -4 ... Z: 0 1 2 3 4 5 6 7 8 ... Tegelikult on murdarvud vs pos täisarvud üksküheses vastavuses Cantori teoreem ütleb üldisemalt, et mingi hulga H kõigi alamhulkade hulk on suurema võimsusega kui see hulk H. GNU ideoloogia: vabadus: primaarne on tarkvara vabadus, sekundaarne tasuta kättesaadavus ausus: ausam on kasutada vabavara kui piraatkopeerida teadmiste vabadus: teadmised, tarkvara tahab olla vaba,on loomu poolest vaba - teadmiste ja tarkvara kopeerimine laiendab ühiskonna majanduslikku võimsust, kaotajaid (rumalamaks jääjaid) pole raha saab teenida ka tarkvara toetades ja installeerides ja
+ lihtne, valikuraam pole piiritletud - varjatud perioodilisuse oht 3. Kihtvalim • Kiht – üldkogumi alajaotus • Üldkogum jagatakse üksteist välistavateks alamhulkadeks, millest võetakse lihtjuhuvalim, näit. vanuse, soo, tegevusvaldkonna järgi + eraldi tulemused iga kihi kohta + andmete kogumine lihtsam + suurem täpsusaste - eeldab rohkem ettevalmistust, infot iga kihi kohta 4. Klastervalim • Üldkogum jaotatakse alamhulkadeks ja valitakse alamhulkade juhuvalim. • Erinevus kihtvalimiga – kihtvalikuga võetakse igast alamrühmast ühikute valim; klastervalikuga alamrühmade valim. + pole vaja täielikku valikuraami teiseste valikuühikute jaoks - muutujad võivad varieeruda klastrite vahel ja täpsus väheneb Replication – kordusuuring Kordusuuring, sarnaste tulemuste kontroll; Skoobi ja piirangute laiendamine. Hüpotees: Hüpoteesid on varasema kirjanduse kokkuvõte, mis juhib andmete kogumist ja analüüsi.
hulgad pole sugugi kõik sama ``suured'' ehk ühesuguse võimsusega, vaid et lõpmatus peidab endas kirjeldamatult keerulist struktuuri erineva ``suurusega'' lõpmatustest. 19. sajandi viimastel aastatel märkas Cantor, et tema näiliselt selge ja vastuvaidlematu hulgateooria lubab tuletada vastuolulisi väiteid ehk paradokse. Cantori paradoks on järgmine: Vaatleme kõigi hulkade hulka ja tähistame selle tähega M. Cantori teoreemi järgi on suvalise hulga X kõigi alamhulkade hulga võimsus (see tähendab lõpmatu hulga puhul tema `suurust'') suurem kui X-i võimsus. Seega on ka M-i kõigi alamhulkade hulga võimsus suurem kui M-i võimsus. Teisest küljest aga, kuna M on kõigi hulkade hulk, peab M sisaldama elemendina iga oma alamhulka, seega ei saa M-i võimsus olla väiksem kui tema kõigi alamhulkade hulga võimsus (sest viimase kõik elemendid on ka M-i elemendid). Paradoksi põhjuseks on meie hüpotees, et eksisteerib abstraktne kõigi hulkade hulk M
Tavaliselt on soovitatav, et iga x-i väärtus omaks kuuluvust vähemalt ühes hägusas hulgas. x X , i, µ Ai ( x) > 0 , (12) elik S (13) x X : µ Ai ( x) > 0 , s =1 1.3 Hägus tükeldus 8 kus S on hägusate alamhulkade arv (antud juhul 3), millest tükeldus koosneb. Öeldakse, et tükeldus, mis rahuldab tingimust (13), katab muutujat x. IGA Lingvistiline muutuja noor keskealine vana Lingvistilised märgendid 1.0 0.8 µA(x) 0.6 Liikmesfunktsioonid 0.4 0.2 0
Meie kursuses käsitletakse lõplikke hulki, mõnikord ka lõpmatuid loenduvaid hulki. Hulgateoreetilised operatsioonid · Hulkade ühend AB={x |(xA)V (xB)} · Hulkade ühisosa (lõige) AB={x |(xA)& (xB) · Hulga täiend A = { x | ( x I ) & ( x A ) }, kus I on nn. universaalhulk. · Hulkade vahe AB={x |(xA)& (xB)} · Hulkade sümmeetriline vahe A B = { x | (( x A ) & ( x B )) V (( x A ) & ( x B )) } Hulga A astmehulgaks 2A nimetatakse hulga A kõigi alamhulkade hulka. Hulgateoreetiliste operatsioonide omadused · Kommutatiivsusseadused AB=B A B = B · Assotsiatiivsusseadused A(BC)=(AB)C 1 A(BC)=(AB)C · Distributiivsusseadused A(BC)=(AB)(AC) A(BC)=(AB)(AC) · De Morgani seadus seadused A B = A B AB = AB · Idempotentsusseadus A=AA=A · Välistatud kolmanda seadused A A = I A A = · Topelttäiendi seadus A =A · = AI=A A=A AI=I · Neeldumisseadused
Hulgateoreetilised operatsioonid Hulkade ühend A B = { x ( x A) V ( x B ) } Hulkade ühisosa (lõige) A B = { x ( x A) & ( x B ) Hulga täiend A = { x ( x I ) & ( x A ) }, kus I on nn. universaalhulk. Hulkade vahe A B = { x ( x A) & ( x B ) } Hulkade sümmeetriline vahe A B = { x (( x A ) & ( x B )) V (( x A ) & ( x B )) } Hulga A astmehulgaks 2A nimetatakse hulga A kõigi alamhulkade hulka. Hulgateoreetiliste operatsioonide omadused Kommutatiivsusseadused A B = B A B = B Assotsiatiivsusseadused A ( B C ) = ( A B ) C A ( B C ) = ( A B ) C Distributiivsusseadused A ( B C ) = ( A B ) ( A C ) A ( B C ) = ( A B ) ( A C ) De Morgani seadus seadused A B A B A B A B Idempotentsusseadus A= A A= A Välistatud kolmanda seadused A A = I
(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
10.2011 Tõenäosuslikud valimid (4) (Tambur) Replication 4. Klastervalim · Replication on kordusuuring · Üldkogum jaotatakse alamhulkadeks ja valitakse · Kordusuuring, sarnaste tulemuste kontroll. ,,A alamhulkade juhuvalim. replication is defined as "a duplication of a previously published empirical study that is · Erinevus kihtvalimiga kihtvalikuga võetakse concerned with assessing whether similar findings
Vahetu kontroll näitab, et kehtib järgmine lause. Lause 1.7 Q on järjestatud korpus. Iga täisarvu n samastame ratsionaalarvuga [(n, 1)]. Kontroll näitab, et see samastamine on kooskõlas tehete ja järjestusega. Niisiis Z ⊆ Q. 1.2.2 Täieliku järjestatud korpuse konstruktsioon Nüüd saame asuda täieliku järjestatud korpuse konstrueerimisele. Teoreem 1.8 On olemas täielik järjestatud korpus F . Tõestus. Olgu F kõigi ratsionaalarvude hulga Q selliste alamhulkade A hulk, mis rahuldavad tingi- musi (a) kui q ∈ A ja p < q, siis p ∈ A, (b) hulgas A ei ole suurimat elementi, (c) A 6= ∅, A 6= Q. Iga q ∈ Q puhul tähistame q := {p ∈ Q : p < q}, vahetu kontroll näitab, et q ∈ F ning kujutus T : Q → F, q 7→ q, on üksühene. Seega Q ⊆ F , selle sisalduvuse all mõistame tegelikult sisalduvust {q : q ∈ Q} ⊆ F.
annaabi.ee 
