1. Algoritm. Algoritmi omadused. Keerukus. Ajalise keerukuse asümptoodiline hinnang. Erinevad keerukusklassid. Algoritm on mingi meetod probleemi lahendamiseks, mida saab realiseerida arvutiprogrammi abil. Algoritm peab olema määratud nii täpselt, et seda suudaks täita isegi arvuti. Täidetavaid samme ei tohi olla liiga palju. Algoritm peab lahendama ülesande õigesti erinevate sisendandmete korral. Algoritmi 5 olulist omadust: 1. Lõplikkus. Algoritmi töö peab lõppema peale lõpliku arvu sammude läbimist. 2. Määratletus
1. Algoritm. Algoritmi keerukus. Ajalise keerukuse asümptootiline hinnang. Erinevad keerukusklassid: kirjeldus, näited. 1.1 Algoritm • Mingi meetod probleemi lahendamiseks, mida saab realiseerida arvutiprogrogrammi abil. • Algoritm on õige, kui kõigi sisendite korral, mis vastavalt algoritmi kirjeldusele on lubatud, lõpetab ta töö ja annab tulemuse, mis rahuldab ülesande tingimusi. Öeldakse, et algoritm lahendab arvutusülesande. • Selline programm, mis annab probleemile õige vastuse piiratud aja jooksul.
Iga mitme lindiga Turingi masinal ajalise keerukusega O(t(n)) töötava programmi jaoks leidub ekvivalentse funktsionaalsusega programm ühe lindiga Turingi masinal, nii et tema ajaline keerukus on O(t2(n)). Teoreem: Olgu t(n) > n. Iga ühe lindiga mittedeterministlikul Turingi masinal ajalise keerukusega O(t(n)) töötava programmi jaoks leidub ekvivalentse funktsionaalsusega programm ühe lindiga deterministlikul Turingi masinal, nii et tema ajaline keerukus on 2O(t(n)). 29 Ülesannete keerukusklassid. Deterministlik vs mittedeterministlik keerukus O-notatsioon näitab keerukuse kasvamist andmete kasvasmisel. g(n) on funktsiooni f (n) (ülemine) asümptootiline hinnang. Ülesande keerukus on teda lahendava efektiivseima algoritmi keerukus (1 lindiga TM korral). Teoreem: Iga mitme lindiga TM-l ajalise keerukusega O(t(n)) töötava programmi jaoks leidub sama tööd tegev programm ühe lindiga TM-l, nii et tema ajaline keerukus on O(t2(n)).
KV-keelte ühesus: Moodustame hulga C alusel grammatika G = ( U I, {S,A,B},P,S), kus produktsioonide hulk evib kolme liiki prod: S A, S B, A xiAi B yiAi A xii (i on siis number), B yii Keeled Lc ja Mc on ühesed. Keel L(G) pole ühene, kui sõnale x eksisteerib vähemalt 2 vasaktuletust. Selline situatsioon on võimalik ainult siis, kui see sõna kuulub nii Lc kui Mc parajasti siis, kui Posti vastavuse probleem pole lahenduv. 33. Algoritmide keerukuse hindamine. Ülesannete keerukusklassid. Turingi masina ajaline keerukus T(M) n mitu takti kulub, kus |x| = n. Turingi masina mahuline keerukus S(M) n mitu pesa kulub Magasinmäluga masina ajaline keer üleminekute arv Mahuline magasini täituvus. Ajaline keerukus algoritmi n-astmelise sisendi jaoks tehtav sammude arv f(n). Asümptootilised hinnangud sisendandmete mahu piiramatul kasvamisel. Polünomiaalse keerukusega algoritmid: O(nd)
•Keerulised algoritmid kasutavad vahetulemuste hoidmiseks ja nendega opereerimiseks andmestruktuure •Keerukuse analüüs annab aimu algoritmi headusest ja parema algoritmi olemasolust ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 16 O notatsioon •O-notatsiooni abil määratakse funktsioonide keerukuse klassid. •Abstraheeritakse konstantsed kordajad ja väiksema keerukusega liidetavad O( 1000 n3log n+28n3+ 34 n+ 1000000 ) = O(n3log n) •Spetsiaalsed keerukusklassid: .logaritmiline:O(log n) .lineaarne:O(n) .ruutkeerukus:O(n2) .polünomiaalne:O(nk), k . 1 .eksponentsiaalne:O(an), n > 1 ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 17 C:My DocumentsalgoritmidImage1_3.jpg ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 18 Mis on suur ja mis on väike? .Minimaalsedsuurused: .Elektroniraadiusca 2.82 x 10-15m .Minimaalsedajad: .Aeg, misvõtabvalguselelektroniraadiuseläbimine: .Valgusekiirus: 300.000.000 m/s = 3*108m / s
annaabi.ee 
