Algoritmi ajaline keerukus (0)

Lõik failist

Sarnased õppematerjalid

80

pdf

Algoritmid ja andmestruktuurid eksamiks kordamine

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. • Kindlalt piiritletud sisendi korral vastab ta järgmistele kriteeriumitele: o lõpetab töö piiratud aja jooksul; o kasutab piiratud hulka mälu; o annab probleemile õige vastuse. • Parameetrid, mille järgi hinnata algoritmide headust: o vastava mälu hulk; o töötamise kiirus ehk vajatava aja hulk.

Informaatika

22

docx

Algoritmid ICD0001 - kordamisküsimused

kiirmeetod Radix sort, O(n) O(n) Stabiilne. positsioonimeetod Merge sort, O(n logn) O(n logn) On enamasti ühildusmeetod stabiilne. Paisktabel, hash O(1) O(1) table Heap sort, O(n logn) O(n logn) kuhjameetod 1. Algoritmi omadused. Algoritmide asümptootiline analüüs: relatsioonid "suur- O", "väike-o", teeta, "suur-oomega" ja "väike-oomega"; nende definitsioonid ning põhiomadused. Mida miski täpselt tähendab. Algoritm on täpne (üheselt mõistetav) juhis antud ülesande lahendamiseks. Algoritm koosneb lõplikust arvust sammudest, millest igaüks on täidetav lõpliku aja jooksul lõplikke ressursse kasutades. Algoritmi rakendatakse teatavale lähteandmete komplektile (sisend)

Algoritmid ja andmestruktuurid

24

pdf

Rekursiooni ja keerukusteooria eksami konspekt

2) kaotame kõik A → ε. Kui T → Aa ja A → ε, siis kustutame A → ε ja lisame T → a (sama mis T → εa) 3) kaotame kõik A → B. Kui T → A ja A → a, siis asendame T → A kohe produktsiooniga T → a. 4) sobitame muud reeglid, kasutades abi-mitteterminaale. Nt S→aTb muudame S→AC, lisame A→a, C→TB, B→b. 10 KV-keelte süntaksanalüüsi ülesanne. CKY-algoritm. Cocke-Kasami-Younge’i algoritmi abil saame teada, kas sõne kuulub KV keelde L. antud: KV grammatika Chomsky normaalkujul ja sõne w=w1…wn tulemus: accept, kui w selle grammatikaga keelde. Else, reject. tehakse püramiidikujuline tabel, mille alumisse ritta pannakse etteantud sõne kõik osad ja igasse tabeli lahtrisse kuidas neid kombinatsioone saada. Produktsiooni X → a korral pannakse “a saamise lahtrisse” X. Esimeses reas vaadatakse, kuidas saada 1 täht, teises reas, kuidas saada 2 tähte jne


Informaatika

55

pdf

Algoritmid kokkuvõte

Algoritmid ja andmestruktuurid Ülevaades sellest kuhu oleme jõudnud Ja kuidas edasi minna 1/55  Eksamid ja konsultatsioonid Eksamid ⚫ 18. detsember kell 14 ⚫ 11. jaanuar kell 14 ⚫ 20. jaanuar kell 14 2/55  Mis on algoritm? Probleem Algoritm Andmed Programm Tulemus 3/55  Algoritmide loomise paradigmasid ⚫ jaga ja valitse – lahendame väiksemateks ülesanneteks jagamisega ⚫ ahne algoritm – lokaalne valikukriteerium annab globaalse tulemuse – taandame ülesande ühele väiksemale alamülesandele ⚫ dünaamiline planeerimine – paneme alamülesannete lahendustest kokku suurema ülesande

Algoritmid ja andmestruktuurid

16

pdf

Algoritmid

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. Algoritmi iga samm peab olema rangelt ja ühemõtteliselt määratud iga juhu jaoks. 3. Sisend. Algoritmil on sisendandmed, mille hulk võib olla null. 4. Väljund. Algoritmil on vastus(ed), millel on täpselt määratud seos sisendandmetega. 5. Efektiivsus (tulemuslikkus). Algoritm peab olema nii lihtne, et on lõpliku ajavahemiku jooksul pliiatsi ja

Analüütiline geomeetria

230

pdf

Programeerimise algkursus 2005-2006

..........................................................................14 Esimese teema kokkuvõte.........................................................................15 TEINE TEEMA: PÕHIMÕISTED. OMISTAMISLAUSE. .............................................16 Sissejuhatus...............................................................................................16 Programmeerimise mõisted.......................................................................16 Algoritm..................................................................................................16 Programmeerimiskeel.............................................................................17 Lause......................................................................................................18 Võtmesõna..............................................................................................18 Andmeobjekt........................................

Programmeerimine

17

doc

Algoritmide ja andmestruktuuride praktikum

Algoritmide ja andmestruktuuride Praktikum Sügis 2009 Koostas: Elli Kopli Juhendas: Ain Isotamm Praktikum 2 (14.09.2009) Ülesanne 1 Koosta programm, mis küsib kasutjalt lause ja siis pöörab selle ümber. Programmi ajaline keeukus on O(n). Lahendus #include #include #include int main(){ char jutt[100]; char a,b; int i,n,m; printf("Palun sisesta oma tekst.n"); memset(jutt,'',100); //Täidab listi sümpolitega 0 gets(jutt); //küsib stringi if(strlen(jutt)==0){ //Kui string on tühi printf("Sisestatud string on tühi!n"); return(0); }else{ printf("jutt :",jutt);

Algoritmid ja andmestruktuurid

13

doc

Matemaatiline analüüs 1 kordaisküsimuste vastused

1. Muutuvad suurused. Def. 1 *Suurusi, mis omand erinevaid väärtusi(vaadeldavas protsessis) nim muutuvateks suurusteks. *Suurusi, mis omand. konstantseid püsivaid väärtusi nim jäävateks suurusteks e. konstantideks. *Tähistus: x,y,z...u,v,w,t *NT ühtlane liikumine-> kiirus konstantne v, teepikkus ja aeg muutuvad *Muutuvad suurused on tavaliselt reaalarvud-> geom võime esitada sirgel *absoluutsed konstandid- mistahes protsessis vaadeldavad suurused: =3,14..., e =2,71 1. väärtused on diskreetsed x: x1,x2,x3 (arvjada) 2. väärtused omand pideva alamhulga reaalteljel (+joonised!): *X={x IR|axib} lõik * X={x IR|a0 (joonis) 2. Funktsiooni mõiste Olgu antud 2 suurust x-muutumisp. X, y-muutumisp. Y *Def.1 Me nim funktsiooniks kujutust, mis seab igale x väärtusele piirkonnas X vastavusse suuruse y kindl

Kõrgem matemaatika

Kommentaarid (0)