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...
Hulk A on rekursiivselt loenduv, kui A või leidub totaalne arvutataf funktsioon f , nii et A range f . Kas antud hulkade omadused on rekursiivselt invariantsed: 1. Sisaldab vähemalt 3 elementi Olgu f bijektiine ja rekursiivne, kui A sisaldab vähemalt 3 elementi, siis f (A) samuti tänu bijektiivsusele 2. On tühi samuti tänu bijektiivsusele 3. On lõputu 2 Margus Martsepp, Rekursiooni- ja keerukusteooria harjutus 3.nb samuti tänu bijektiivsusele 4. On rekursiivselt loenduv (RL) A on rekursiivselt loendub hulk, ta on kas tühi (siis 3.) või leidub totaalne funktsioon f , nii et A range f . Olgu g suvaline bijektiivne rekursiivne funtsioon B g(a), B range (g f ), kus g f on totaalne arvutatav funktsioon ja annab täpselt B ele- menti. x f (x) annab A elementi, g on totaalne. g saab sisendiks ainult A elemente, seega tulemuseks ainust B elemendid. Millised neljast omadusest:
1.2 Algoritmi keerukus • On hinnang sellele, kuidas algoritmi poolt esitatavad nõudmised ajale muutuvad näiteks siis, kui probleemi mõõt kasvab. Keerukus mõjutab jõudlust, kuid mitte vastupidi. • On põhioperatsioonide arvu sõltuvusfunktsioon sisendi suurusest. • Põhioperatsioon: üks tehe, üks tsüklitingimus või üks rida • Keerukusprobleemidega tegeleb vastav teadus – arvutuslik keerukusteooria. Ajalise keerukuse uurimine Mahulise keerukuse uurimine algoritmi alusel koostatud programi tööaja programmi tööks kasutatava mälu mahu hindamine hindamine • Keerukusfunktsiooni kasvukiirus – kui kiiresti kasvab antud algoritmi järgi koostatud programmi ressursivajadus töödeldavate andmete mahu suurenemisel.
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
