Facebook Like

Teoreetilibe informaatika kordamisküsimused (0)

5 VÄGA HEA
Punktid
 
Säutsu twitteris

Teoreetiline informaatika


Kordamisküsimuste vastused
Eero Ringmäe
  • Hulkade spetsifitseerimine, tehted hulkadega, hulgateooria paradoksid.
    Hulk:
    Korteezh – järjestatud lõplik hulk.
    Hulk – mingi arv elemente, mille vahel on leitav seos – klassifitseeritud elementide kogum.
    Hulk – samalaadsete objektide järjestamata kogum.
    Hulga esitamine:
    elementide loeteluna A = {2;3;4}
    predikaadi abil A = {x | P(x)}
    Tühihulk on iga hulga osahulk .
    Iga hulk on iseenda osahulk.
    Hulga boleaan – kõigi osahulkade hulk.
    H boleaan on 2H. 2H = {x | x on osahulgaks H-le}. Boleaani võimsus |2H| = 2|H|
    Tühja hulga boleaani võimsus on 1.
    Tehted:
    Hulkade võrdsus = A on B osahulk AND B on A osahulk. Ekvivalentsiseose definitsioon ((A => B) && (B => A)) – hulgas sisaldavad samu elemente.
    Hulga osahulk – võib võrduda hulgaga .
    Hulga pärisosahulk – ei või võrduda.
    Hulkade ühend – C = {x | x kuulub A && x kuulub B}
    Hulkade lõige e ühisosa C = {x | x kuulub A OR x kuulub B}
    Hulkade vahe C = {x | x kuuulub A XOR x kuulub B}
    Hulga A täiend A* = {x | x kuulub universaalhulka AND x ei kuulu A}
    A x B hulkade ristkorrutis e otsekorrutis e Descartes ' korrutis
    A x B = {(a,b) | a kuulub A, b kuulub B}
    Paradoksid:
    Russelli ehk habemeajaja paradoks (hulga esitamine predikaadi abil):
    P(X) = true, kui argumendina esitatud hulk pole iseenda elemendiks .
    P(X) = false , kui argumendina esitet hulk on iseenda elemendiks.
    Kontrollime hulka
    Y = {X | P(X)}
    Eeldades, et Y kuuluks hulka Y, saame P(Y) = false => Y ei kuulu hulka Y
    Eeldades, et Y ei kuulu hulka Y, saame P(Y) = true => Y kuulub Y
    Paradokside elimineerimine hulkade hierarhia ja klassifitseerimisega.
  • Relatsioonid. Ekvivalentsi- ja järjestusseosed.
    Relatsioon ehk seos hulkade A ja B vahel on alamhulk A x B-le.
    Seos hulgal A on alamhulk A x A-le.
    Pöördrelatsioon R-1 on relatsiooni täiend.
    aRb -> Elemendid a ja b on seoses R
    Refleksiivsus - iga a korral aRa (a on iseendaga seoses)
    Sümmeetria – iga a korral aRb => bRa (kõik seosed on vastastikused)
    Transitiivsus – iga a korral aRb && bRc => aRc (põhimõtteliselt järjestusseos)
    Ekvivalentsiseoseks nimetatakse seost, mis on refleksiivne, sümmeetriline ja transitiivne .
    Elemendiga a (A element) ekvivalentsete elementide hulka nimetatakse a ekvivalentsiklassiks (hulgal A).
    Elemendiga a ekvivalentsete elementide hulka tähistatakse [a] = {b | aRb}, kus R on ekvivalentsiseos .
    Teoreem 1:
    Ekvivalentsiseos R hulgal A. Iga elemendipaari a ja b korral kehtib seos [a] = [b] või [a] ühisosa [b] on tühihulk.
    Tõestus:
    Kuna R on sümmeetriline ja transitiivne, näitame, et kui aRb ja suvaline element [a]-st on z, siis sümmeetria tõttu bRa ja aRz – transitiivsuse järgi bRz ehk siis z kuulub [b].
    Siit nähtub, et [b] on alamhulgaks [a]-le.
    Analoogselt tõestame, et [a] on alamhulgaks [b]-le.
    Kui not(aRb), eeldame vastuväiteliselt, et eksisteerib y, mis kuulub korraga nii [a] kui [b]. – ehk aRy ja bRy. Sümmeetria tõttu yRb, millest transitiivuse alusel aRb, mis on vasutolus esialgse väitega.
    Voila!
    Relatsiooni aste:
    R on seos hulgal A. R aste Rk on (aR1b = aRb; aR2b, kui aRcRb)
    aRkb (k>1) on selline relatsioonide järjestus, et (kui c kuulub A) aRc = cRk-1b.
    Suhete ahel. Tee pikkus elementide vahel graafis.
    Relatsiooni transitiivne sulund:
    R on seos hulgal A. R transitiivne sulund on seos R+ hulgal A nii, et aR+b kehtib parajasti siis, kui eksisteerib i >= 1 nii, et aRib.
    Transitiivne sulund on R-le lisatud vähima paaride arvuga seos, mis on transitiivne.
    Relatsiooni refleksiivne transitiivne sulund:
    R on seos hulgal A. R refleksiivne transitiivne sulund on seos R*, mille korral:
    • iga a puhul aR*a
    • aR*b kehtib, kui kehtib aR+b
    • R* sisaldab parajasti nii palju elemente, kui eelmised tingimused ette näevad

    R* on seos, mis on saadud R-le minimaalse arvu paaride lisamisel nii, et saaksime refleksiivse ja transitiivse seose.
    Järjestusseosed:
    • osalise järjestuse seos (kõigile saab leida ülem- ja alamelemendid, kuid kõik pole järjestusse seatud):
      • transitiivne
      • irrefkeksiivne

    (näiteks alamhulgaks olemise seos kõigi osahulkade hulgal)
    • refleksiivne osaline järjestus (seos R)
      • määrab lineaarse järjestuse – kehtib kas aRb, bRa või a = b

    Hulgal A on määratud järjestusseos – tähistuseks (A, R)
    Näiteks (N, b=c.
    Tähistus: M: A -> B
    Asjaolu, et (a,b) kuulub M, tähistatakse M(a) = b.
    Kujutuse M: A -> B
    • muutumispiirkond Dom(M) = {a | a kuulub A AND eksisteerib b, mille jaoks b = M(a)}
    • määramispiirkond Ran(M) = {b | b kuulub B AND eksisteerib a, mille jaoks M(a) = b}

    Liigid:
    • osaline kujutus -> Dom(M) on A pärisosahulk (osadele A elementidele on vastavus seatud)
    • täielik kujutus -> Dom(M) = A (kõigile A elementidele on vastavus seatud)
    • pealekujutus e sürjektsioon -> Dom(M) = A ja Ran(M) = b (osalevad kõik mõlema hulga elemendid)
    • üks-üheseks kujutuseks e injektsiooniks kui iga A elemendipaari a,a' ning iga B elemendi b korral kehtib seos:

    (f(a) = b AND f(a') = b) => a = a'
    (igale elemendile vastavuses vid üks kindel element)
    • bijektsiooniks -> kui kujutus on samaaegselt sürjektsioon ja injektsioon

    Idee poolest on kujutus teatud tüüpi vastavus hulgast A hulka B.
    Hulgad A ja B on võrdvõimsad, kui leidub bijektiivne vastavus (M:A  B) nende vahel (ehk siis kõik elemendid mõlemast hulgast on haaratud ja igaühele vastab vaid 1 kindel element).
    Lõpmatut hulka nimetatakse loenduvaks, kui see on võrdvõimas naturaalarvude hulgaga.
    |H| on hulga võimsus ehk lõpliku hulga korral elementide arv hulgas. Lõpmatu hulga võimsus leitakse, seades tema elemendid bijektiivsesse vastavusse (üks-ühesesse) mõne tuntud võimsusega hulga (näiteks naturaalarvude hulga) elementidega.

  • Graafid . Puude esitused. Programmide esitamine puuna
    Mittejärjestatud ja mitteorienteeritud graaf on paar G = (A,R), kus A on tippude hulk ja kaarte hulk R on seos hulgal A.
    Graafi saab esitada paaride hulgana (A + R analüütiliselt, või predikaadina) või joonisena.
    Graafide võrdsus:
    Graafid G1 = (A1, R1) ja G1 = (A2, R2) on võrdsed ehk isomorfsed, kui leidub selline bijektiivne kujutus f: A1  A2 nii, et aR1b = f(a)R2f(b)
    Kui igale tipule a G1-st leidub tipp b G2-st, millele saab vastavusse seada samade tippude kaared ja kõik G2 tipud saavad ka kaetud.
    Kui kaar R1 järgi on esimese graafi tippude vahel, siis on see ka samade teise graafi tippude vahel ja kui seda pole, pole kummaski.
    Graafi märgendus:
    Graafi G = (A, R) märgenduseks nimetatakse funktsioonide paari f,g, kus
    f: A  M – tippude märgendus
    g: R  L – servade märgendus
    Ühesõnaga pannakse igale tipule ja igale servale vastavusse mingid arvud
  • 80% sisust ei kuvatud. Kogu dokumendi sisu näed kui laed faili alla
    Vasakule Paremale
    Teoreetilibe informaatika kordamisküsimused #1 Teoreetilibe informaatika kordamisküsimused #2 Teoreetilibe informaatika kordamisküsimused #3 Teoreetilibe informaatika kordamisküsimused #4 Teoreetilibe informaatika kordamisküsimused #5 Teoreetilibe informaatika kordamisküsimused #6 Teoreetilibe informaatika kordamisküsimused #7 Teoreetilibe informaatika kordamisküsimused #8 Teoreetilibe informaatika kordamisküsimused #9 Teoreetilibe informaatika kordamisküsimused #10 Teoreetilibe informaatika kordamisküsimused #11 Teoreetilibe informaatika kordamisküsimused #12 Teoreetilibe informaatika kordamisküsimused #13 Teoreetilibe informaatika kordamisküsimused #14 Teoreetilibe informaatika kordamisküsimused #15 Teoreetilibe informaatika kordamisküsimused #16 Teoreetilibe informaatika kordamisküsimused #17 Teoreetilibe informaatika kordamisküsimused #18 Teoreetilibe informaatika kordamisküsimused #19 Teoreetilibe informaatika kordamisküsimused #20 Teoreetilibe informaatika kordamisküsimused #21 Teoreetilibe informaatika kordamisküsimused #22 Teoreetilibe informaatika kordamisküsimused #23 Teoreetilibe informaatika kordamisküsimused #24 Teoreetilibe informaatika kordamisküsimused #25 Teoreetilibe informaatika kordamisküsimused #26 Teoreetilibe informaatika kordamisküsimused #27 Teoreetilibe informaatika kordamisküsimused #28 Teoreetilibe informaatika kordamisküsimused #29 Teoreetilibe informaatika kordamisküsimused #30 Teoreetilibe informaatika kordamisküsimused #31 Teoreetilibe informaatika kordamisküsimused #32 Teoreetilibe informaatika kordamisküsimused #33 Teoreetilibe informaatika kordamisküsimused #34 Teoreetilibe informaatika kordamisküsimused #35 Teoreetilibe informaatika kordamisküsimused #36 Teoreetilibe informaatika kordamisküsimused #37
    Punktid 50 punkti Autor soovib selle materjali allalaadimise eest saada 50 punkti.
    Leheküljed ~ 37 lehte Lehekülgede arv dokumendis
    Aeg2008-01-12 Kuupäev, millal dokument üles laeti
    Allalaadimisi 81 laadimist Kokku alla laetud
    Kommentaarid 0 arvamust Teiste kasutajate poolt lisatud kommentaarid
    Autor Rain Ungert Õppematerjali autor

    Lisainfo

    Mõisted


    Meedia

    Kommentaarid (0)

    Kommentaarid sellele materjalile puuduvad. Ole esimene ja kommenteeri


    Sarnased materjalid

    54
    doc
    Süsteemiteooria kordamisküsimused
    38
    docx
    Arvutid kordamisküsimused
    16
    docx
    Keeleteaduse kordamisküsimused 2013
    24
    pdf
    Rekursiooni ja keerukusteooria eksami konspekt
    13
    pdf
    Majandusmatemaatika IIE eksami kordamisküsimused
    24
    docx
    Biokeemia I kordamisküsimuste vastused
    30
    docx
    TÜ Keeletüpoloogia kordamisküsimused-2016
    575
    docx
    Nimetu



    Faili allalaadimiseks, pead sisse logima
    Kasutajanimi / Email
    Parool

    Unustasid parooli?

    UUTELE LIITUJATELE KONTO MOBIILIGA AKTIVEERIMISEL +50 PUNKTI !
    Pole kasutajat?

    Tee tasuta konto

    Sellel veebilehel kasutatakse küpsiseid. Kasutamist jätkates nõustute küpsiste ja veebilehe üldtingimustega Nõustun