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...
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 ...
Seosed Seoseks (ehk vastavuseks, sageli ka relatsiooniks või suhteks) hulkade ja vahel nimetatakse otsekorrutise × mistahes osahulka. Seega, seos hulkade ja vahel on järjestatud paaride (,) hulk, kus ja . Teisiti öeldes, seos on mingi osahulk ×. Paari (,)× korral öeldakse, et elemendid ja on seoses ning tähistatakse ka . Mõnikord öeldakse osahulga kohta, et see on seose graafik. Kui =, ehk kui ×, siis räägitakse seosest hulgal . Näide 1. Olgu ={2,3} ja ={1,2,3,4,5,6}. Siis 1={(2,2),(2,3),(3,1), (3,5)} on binaarne seos hulkade ja vahel. Samade hulkade ja korral võime vaadelda veel palju teisi seoseid, näiteks seost 2, mis on antud tingimusega, et see koosneb paaridest (,), millede korral jagub arvuga . Siis 2={(2,2),(2,4),(2,6),(3,3),(3,6)}. Näide 2. Olgu hulgaks kõigi naturaalarvude hulk ning seoseks osahulk hulgas ×, mis koosneb kõikidest paaridest (,), mille korral arv on arv...
LTMS.00.022 ÜHE MUUTUJA MATEMAATILINE ANALÜÜS Loengukursus Tartu Ülikooli loodus- ja täppisteaduste valdkonna üliõpilastele 2019./2020. õppeaasta Toivo Leiger Joonised: Ksenia Niglas Pisitäiendused 2016–20: Märt Põldvere, Natalia Saealle, Indrek Zolk, Urve Kangro 2 Sisukord 1 Reaalarvud 6 1.1 Järjestatud korpused . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Korpuse aksioomid . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Järjestatud korpus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 Täielik järjestatud ...
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...
Sissejuhatus infotehnoloogiasse 2018 1. Nädal. bitt(b) = 1b, Bait(B) = 8b, kB = 1024 B, MB = 1024 kB jne 2. Nädal. Eksamiks: kreeka loogikud, süllogismid, induktsioon, deduktsioon, 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. Küberkaitse termineid: (turvateater, malware, cookie, phishing, social engineering). Kreeka loogikud:Parmenides, -5. Saj, pikad loogilised põhjendused Zenon Eleast, -5. Saj, apooriad/paradoksid Sokrates, -5. Saj, sofistid Platon, -5,-4. Saj Aristoteles, -4. Saj, süllogismid, stoikud (1. eeldus: iga koer on imetaja. 2. eeldus: mõned neljajalgsed on koerad. järeldus: mõned neljajalgsed on imetajad.), Stoikud uurisid, kuidas saab loo...
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 ...
1. LOENG Sissejuhatus Lausearvutus: Teoreemid sõnastatakse tavaliselt kujul: ,,Kui A, siis B". Teoreemi osa A, mis on seotud sõnaga kui, nimetatakse teoreemi eelduseks, ja osa, mis on seotud sõnaga siis, väiteks. Näide: Kui kaks vektorit on risti, siis nende vektorite skalaarkorrutis on null. Näide: Kui nurgad on kõrvunurgad, siis nende summa on 180o. Teoreemi tõestamine tähendab selle näitamist, et eeldusest A järeldub väide B. Tõestamisel lähtutakse aksioomidest ja varem tõestatud teoreemidest. Vahetades teoreemis ,,Kui A, siis B" eelduse ja väite, saame lause ,,Kui B, siis A". Seda lauset nimetatakse antud lause pöördlauseks. Kui lause kehtib, siis selle lause pöördlause ei pruugi kehtida. Näide: Lause: ,,Kui arv lõpeb nulliga, siis ta jagub viiega" (kehtib). Pöördlause: ,,Kui arv jagub viiega, siis ta lõpeb nulliga" (ei kehti). Näide: Lau...
Aritmeetiline masin- 1640, ainult liitis ja lahutas, Kristlik filosoof Blaise Pascal Leibnizi arvuti 1671, Saksa filosoof Leibniz, arvuti: liitis, lahutas, korrutas, jagas Elektritelegraaf - Morse 1837 Loogika (lausearvutuse) alused 1847-1854 Perfolint - Wheatstone 1857 Frege loob kaasaegse predikaatarvutuse - 1879 Herman Hollerith perfokaartidega masin USA rahvaloenduse andmete töötlemiseks 1890, sellest firmast tekkis IBM Vaakumtoru - 1906, Lee Deforest Artikkel Turingi masinast: universaalsus, mittelahenduvus 1935-1937 Churchi lambda-arvutus, Churchi tees. - 1936,universaalsus, mittelahenduvus Z1 1936 , Konrad Zuse mehhaaniline arvuti MARK I 1939-1944, Harvardi elektriline(releedega) digitaalne arvuti ABC computer 1939-1942 , Atanasoff-Berry esimene elektronarvuti Esimene transistor - 1947 EDSAC 1949, esimene praktiline stored-program arvuti, programmid olid aukudega peberiribadel ERA 1101 1950 ESIMENE KOMMERTS-TOOTMI...
Küsimused: 1.Määratud integraali (Riemanni mõttes) definitsioon. Darbouc ülem- ja alamsummad. Riemanni summa ja Darboux’ summade seos-viimane pilt. ∫ f ( x ) dx st ∫ f ( x ) dx=F ( x ) +C . Määramata integraali tuletis on f (¿ ξi) ∆ xi SΠn n võrdne integreeritava funktsiooniga st ( ∫ f ( x ) dx )’= f(x). Tõestus: ( ∫ f ( x ) dx Riemanni summa lõigul [a,b] (f) = ∑¿ . ...
LAUSEARVUTUS Diskreetne matemaatika ei tegele reaalarvudega ega pidevate funktsioonidega. Verbaalne esitus on mistahes info esitamine lingvistilise keele abil. Formaalne esitus on mistahes info esitamine ilma lingvistilise keele abita ehk esitus kokkulepitud sümbolite abil. Formaalne esitus peab olema üheselt tõlgendatav. Lausearvutus on loogilise mõtlemise matemaatiline mudel. Lausearvutuse lause võib olla iga verbaalne väide, millele saame omistada tõeväärtuse – tõene või vale. Lihtlause on lihtsaim võimalik lausearvutuslause. Lausearvutuslauseid tähistatakse formaalselt suurtähtedega: A, B, P, Q … Lihtlausetest koostatakse kindlate sidesõnade ja loog konstruktsioonide abil liitlauseid. Lausearvutuse lihtlauseid seotakse liitlauseteks 5 loogilise konstruktsiooni ehk loogikatehte abil. Binaarsed loogikatehted seovad kahte lauset (4 tk), unaarne loogikatehe on rakendatav üksikule lausele (1 tk – eitus). Loogiline korrutamine ehk konjunk...
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...
Turingi masin 1937 Universaalne masin suudab arvutada/järeldada kõike Turingi tees: kõike mida saab üldse mingi masinaga järeldada/arvutada, saab ka Turingi masinaga arvutada Parmenides (5 saj. e.m.a) kasutas pikki loogilisi põhjendusi. Zenon Elast (5 saj e.ma) paradoksid Sofistid-Sokrates (470-399 e.m.a), Platon (428/427 - 348/347e.m.a) Aristoteles: väidete struktuur kui iseseisev uurimisobjekt Süllogismi näited:1eeldus:iga koer on imetaja, 2eeldus mõned neljajalgsed on koerad, järeldus: mõned neljajalgsed on imetajad. Süllogism on väitlus, kus mingitest etteantud väidetest järeldub paratamatult uus väide. Aristotelese puhul alati kaks kategoorilist eeldust, üks kategooriline järeldus Stoikud uurisid, kuidas saab loogiliste sidesõnade (ja, ei, või, kui ...siis)abil lihtsamatest lausetest keerulisemaid kokku panna ja kuidas näidata selliselt moodustatud lausete õigsust. Ramon Llull 1235- 1315 müstik Peateos Ars magna, generalis et ultim...
tutvu lausearvutuse keskkonnaga: http://logik.phl.univie.ac.at/~chris/gateway/formular-uk-zentral.html Millistel muutuja väärtustel on lause (Av(B&A))v(-A&(Cv(B&-C))) väär? Panna tuleb results only, 0 on väär 1 on õige Tutvu ajalooga saidis kuni II maailmasõda: http://www.maxmon.com/history.htm Loe läbi jutt ja proovi andmetega mängida: http://math.hws.edu/TMCM/java/DataReps/index.html Kahend süsteemi arvu(101101001) ->kümnend süsteemiks. Nr sisse ja bianarile punkt, ja vaatan base ten integeri kümnendarvudest annab Ecki appletis juuresoleva graafilise kujutise, teen kujundi ja vaatan base integeri mis vastab kahendsüsteemi arvule 1110001 ASCII tabelis? Nr sisse ja punkt bianari, vaatan ...teksti Kümnendsüsteemi arv 33 on kahendsüsteemis? 33 kirjutan ja Base-ten integer, vaatan bianary Loe läbi jutud Atbashi ja Caesari šifri (Caesar cipher) kohta: http://www.wikipedia.org 2 Tutvu ajalooga kuni 1970ndad: http://www.islandnet.com/~...
annaabi.ee 
Sisene Facebook'ga
Sisene Google'ga
Sisene LinkedIn'ga
