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.
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.
ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 20 Loe juurde! •http://www.itil.org/en/ •www.isaca.org/cobit/ •http://builder.com.com/5100-6315-1046507.html •http://agilemanifesto.org/ •http://www.agilealliance.org/home •http://www.paulgraham.com/bronze.html •http://www.paulgraham.com/start.html •http://www.joelonsoftware.com/articles/fog0000000245.html •http://www.joelonsoftware.com/articles/fog0000000074.html ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 21 Keerukusteooria ja lahenduvus Millest räägime •Keerukusteooria mõiste •Kasutusvaldkonnad •Lahenduvusest ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 2 Matemaatikast –Vanad “vist ekslikud” oletused: 1.Mathematics isconsistent. Roughly this means that we cannot prove a statement and its opposite; we cannot prove something horrible like 1=2. 2.Mathematics is complete. Roughly this means that every true mathematical assertion can be proven i.e. every mathematical
annaabi.ee 
