Teoreetiline informaatika Kordamisküsimuste vastused Eero Ringmäe 1. 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 ...
1 Lõplikud automaadid ja regulaarsed keeled. DEF: Lõplik automaat on sellise arvuti mudel, millel puudub mälu (või seda on väga vähe). DEF: Automaadi M keeleks nimetatakse sõnede hulka A, mida M aktsepteerib. L(M)=A DEF: Keelt nimetatakse regulaarseks, kui seda aktsepteerib mingi deterministlik lõplik automaat. Reg. keelest saab teha lõpliku arvu sõnesid. Tehted regulaarsete keeltega: A∪B = {x|x ∈ A või x ∈ B} ühend nt good, girl, boy, bad A◦B ={xy|x ∈ A ja y ∈ B} konkatenatsioon nt goodboy, goodgirl, badboy, badgirl A∗ = {x1x2...xk|k>=0 ja iga xi ∈ A} sulund nt ε, good, bad, goodgood, badgood… 2 Regulaarsete keelte omadusi. Regulaarsed avaldised. Teoreem: Regularsete keelte hulk on kinnine ühendi suhtes. T: Aktsepteerigu automaat N1 = (Q1,Σ,δ1,Q10,F1) keelt A1 ja automaat N2 = (Q2,Σ,δ2,Q20,F2) keelt A2. Eeldame, et keeltel pole ühiseid olekuid. Ühendi A1 ∪ A2 aktsepteerib lõplik automaat N=(Q;Σ,δ,Q0,F), kus: • Q = {q0} ∪ Q...
1. nädal • Eksamiks: pead teadma suuruse-numbreid ja mida nad tähendavad: bitt, bait, kilobait, megabait jne; oskad selgitada, kuidas tähti kodeeritakse, mis on algoritm ja mis programm. Ajaloost: Kreeka loogikud, induktsioon, deduktsioon, süllogismid, lausearvutus (pead mh oskama tõeväärtustabelit koostada), Pascal, Leibniz, perfokaardid, kangasteljed, Babbage, Hollerith, colossus ja saksa krüptomasinad, Turing, Shannon, Zuse, esimesed programmeeritavad arvutid. Algoritm – täpne samm-sammuline, kuid mitte tingimata formaalne juhend millegi tegemiseks. Nt toiduretsept, juhend ruutvõrrandi lahendamiseks. Programm – formaalses, üheselt mõistetavas keeles kirja pandud algoritm. Arvutid suudavad täita ainult programme. Bitt – info mõõtmise ühik, tuleb mõistest binary digit – nö kahendarv kahe võimaliku väärtusega 0 ja 1. Saab näidata kahte võimalikku olekut. Nibble - 4 bitti. Bait – arvutite...
Loogika aine ja ajalugu: sissejuhatus T.Tamme, T.Tammeti ja R.Prangi loogikaõpikule "Mõtlemisest tõestamiseni" Tanel Tammet Department of Computer Sciences, University of Göteborg and Chalmers University of Technology, 41296 Göteborg, Sweden email: [email protected] Puhta loogika eesmärk on olla õige kõigis võimalikes maailmades, mitte ainult selles veider-segases vaevarikkas maailmas, kuhu juhus meid on heitnud. Loogik peab eneses alal hoidma teatud annuse jumalikkust: ta ei tohi alanduda selleni, et teha järeldusi...
annaabi.ee 
Sisene Facebook'ga
Sisene Google'ga
Sisene LinkedIn'ga
