Programmi töö aeg kujul c*f(n) Lahendamise aja suhteline kasv f(25)/f(5)
c1*log(n) 2
c2*n2 25
c3*n3 125
c4*2n 1048576
Et kõik funktsioonid kujul c*f(n) kasvavad ühetaoliselt, siis on nad sama
asümptootilise hinnanguga. Seda tähistatakse kujul O(g(n)) . Näiteks O(n2) .
Def. Olgu f ja g naturaalarvuliste argumentidega ja positiivsete väärtustega
funktsioonid. Siis f on O(g(n)) parajasti siis kui leidub c>0 ja N>0 nii, et
f(n)
log 0, 5 tan arccos( - 0,5) - 3 2 B-5 On antud funktsioon y = f ( x ) joonisel on y = f ( x ) graafik. Leia argumendi väärtus, mille korral on funktsiooni väärtus minimaalne. y = f ( x ) ( ) B-6 Leia funktsiooni y = log 8 48 x - 2 x + log 8 x argumendi naturaalarvuliste väärtuste 3 5 summa. 4 - x + 4 x + x - 4 + ( 4 x - 18 2 x + 32) = 0 lahend või 3 2 2 B-7 Leia võrrandi tan x -3 lahendite summa. ( )
Järeldus: Pole olemas algoritmi, mis etteantud Gödeli numbrite a ja b põhjal tunneks ära, kas f.-nid a ja b ühtivad või mitte Järeldus: Pole olemas algoritmi, mis suvalise arvutatava f.-ni f korral teeks kindlaks, kas võrrand f(x) = 0 on arvutatav või mitte. 32. Posti vastavuse probleemi mittelahenduvus. Mittelahenduvate ülesannete näited. A = {x1,..,xn} f: A A on ühskohaline kõikjal määrat' naturaalarvuline f.-n. f on Nn tükki. Kõigi ühekohaliste naturaalarvuliste f.-nide arv aga on |N| |N| - kontiinumi võimsus. Kõigil arvutatavatel f.-nidel on Gödeli numbrid need aga on naturaalarvud seega ei saa kõik f.-nid olla lahenduvad. · Turingi masina peatumine (kas A(x) = lõpmatus?) · Hiberti kümnes probleem kas täisarvuliste kordajatega polünoomi P(x1,..,xn) korral on võrrandil P(x1,..,xn) = 0 naturaalarvulisi lahendeid? · Posti vastavuse probleem Posti vastavuse probleem: korteezhid tähestikus :
vuliste astmetega hätta, rääkimata siis irratsionaalarvulistest astmetest. Praktikas võime irratsionaalarvuliste astmetega käituda samamoodi nagu astme null korral – otsime lihtsalt mõne ratsionaalarvulise astendaja, mis on meie irrat- sionaalarvule piisavalt lähedal. Täpselt nii käituvad ka arvutid – irratsionaalarve nad nagunii salvestada ei oska. Efektiivne astendamine Naturaalarvuliste astmete võtmine on üpriski igapäevane tegevus (kui mitte isikli- kult Sulle, siis kindlasti mõningatele teadlastele ja ka arvutitele). Näiteks arvutamiseks on vaja 2 korrutamistehet ning . Mitme tehtega saaks aga arvutada arvutada ? Kas tõesti läheb selleks 99 tehet või on võimalik leida mõni kiirem viis? Selgub, et on olemas ka kiirem viis. Selle kiirema viisi tabamiseks tuleb märgata, et
annaabi.ee 
