Mis veebilehti külastad? Anna Teada Sulge
Facebook Like
Küsitlus


Algoritmid ja andmestruktuurid eksamiks kordamine (0)

5 VÄGA HEA
Punktid

Esitatud küsimused

  • Milleks kogu probleem jagatakse – milline suurus on paras ?
 
Säutsu twitteris
1.   AlgoritmAlgoritmi   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. 
Omadused: 
1.  Lõpplikkus – töö peab lõppema peale lõpliku arvu sammude läbimist. 
2.  Määratletus – iga samm peab olema nii täpselt määratud ( rangelt ja ühemõtteliselt), et seda 
suudaks täita isegi arvuti. Kui täidetavaid samme on liiga palju, siis algoritm ei ole praktiliselt 
täidetav. 
3.   Sisend  – algoritmil on sisendandmed, mis pärinevad alati kindlat liiki objektide hulgast. Nende 
hulk võib olla ka null. Mida rohkem andmeid, seda rohkem aega kulub nende töötlemiseks. 
4.  Väljund – üks või mitu töötulemust. 
5.  Efektiivsus 
a.   Korrektne  – peab andma õige tulemuse 
b.  Efektiivne – peab leidma vastuse mõistliku  ajaga  
c.  Programmi efektiivsusele hinnangu andmist nim. algoritmi keerukuse uurimiseks 
i.  Ajaline 
ii.  Mahuline 
6.  Korrektsus – lahendab etteantud ülesande õigesti. 
Algoritmi tegelik  tööaeg  ja efektiivsus sõltub andmete hulgast, protsessori kiirusest, arvutist, 
kompilaatorist jne. 
 
 
Algoritmid ja andmestruktuurid 2015 
 
 

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. 
•  Keerukusfunktsiooni leidmiseks on võimalik kokku arvutada kõik sammud, mida arvuti teeb 
ülesande lahendamiseks. Pole võimalik väljendada konkreetse arvuga, vaid andmete hulgast (n) 
sõltuva valemina. 
Algoritmi keerukus halvimal juhul 
Algoritmi keskmine 
Algoritmi keerukus parimal juhul 
keerukus 
Teatud algandmete komplekti juures 
Igasuguste halvemate ja 
Mingi algandmete komplekti 
võib kuluda aega tunduvalt rohkem 
paremate juhuste 
puhul võib algoritm töötada 
keskmisest; selgitakse välja, millised 
keskmine, mis aga 
tunduvalt kiiremini. Need juhused 
on halvimad variandid ja kui tihti 
tavaliselt kipub suvaliselt 
on huvitav väljaselgitada, paraku 
nad esinevad. Kriitilistel juhtudel 
tekkivate andmete puhul 
pakub see enamasti vaid 
peetakse õigeks arvestada ennekõike 
olema halvimale üsna 
teoreetilist huvi, sest kasutada 
just halvima juhu keerukusega. 
lähedal. 
saab seda teadmist harva. 
1.3  Ajalise keerukuse asümptootiline hinnang 
Asümptootiline hinnanguga väljendatakse funktsiooni väärtuse muutumise üldist trendi – funktsiooni 
kasvamise kiirust. Asümptoot on sirge, millele funktsiooni graafik  lõpmatult läheneb, kuid millega ta ei 
lõiku. Suure O tähistust kasutakse algoritmide keerukuse tähistamiseks. Reeglina antakse hinnang 
halvima juhu jaoks ja tegelik tööaeg peaks olema parem. Suure O järgi saab hinnata algoritmi tööaja 
suhtelist kasvu andmehulga suurenemisel. Kuna hinnang on ligikaudne  kaob mõte täpselt kõiki tehteid 
üle lugeda. Oluline on N-i järk (kus N on töödeldavate andmete hulk ehk probleemi mõõt). Hinnangud  
hakkavad kehtima alles N-i suurte väärtuste korral. 
O. def: Funktsioon g(N) on O(f(N)), kui leiduvad konstandid C0 ja N0, nii et g(N)N0 
korral 
•  O(g(n)) on funksioonide hulk, mis ei kasva kiiremini kui g(n). 
Algoritmid ja andmestruktuurid 2015 
 
 

•  g(n) on funktsioon, mis kirjeldab algoritmi saamude arvu ja sellest tulenevalt tööaja seost sisendi 
mahuga (n). Näiteks võib funktsiooniks g(n) olla n, n2 jms  
Konstant C0-ga: 
•  püütakse  likvideerida  vead, mis tekivad matemaatiliselt sammude väljaarvutamisel või programmi 
analüüsides ebaoluliste lausete vahelejätmise tõttu 
•  et võimaldada klassifitseerida algoritmid tööaja ülemise piiri järgi 
1.4  Erinevad keerukusklassid: kirjeldus, näited 
Tööaja hindamiseks on vaja peamist tähelepanu pöörata kasutavatele keelekonstruktsioonidele – st 
algoritmi või programmi struktuurile. 
O(1) 
O(log2n) või O(log n) 
O(n) 
O(n log2n) või O(n log n) 
Konstantne  
Logaritmiline 
Lineaarne 
Linearitmeetiline? 
• Andmehulgast ei 
• Tööaeg kasvab väga 
• Kui N kasvab 2 korda,  • Tavaliselt tähendab seda, et 
sõltu algoritmi 
aeglaselt N-i kasvades. 
kasvab ka tööaeg 2 
lineaarses algoritmis on log2n 
tööaeg. 
• Log n kasvab vaid 2 
korda 
algoritm. 
• Kõiki programmi 
korda kui n2. 
• Iga elementi on vaja 
• Algoritm lahendab probleemi 
lauseid  täidetakse 
• Probleemi lahendakse 
töödelda mingil määral. 
nii, et alguses tükeldab 
üks kord. 
selle järkjärgulisel 
väiksemateks osadeks. 
• Lahendamiseks on 
vähendamisel kordades 
• Kui kõik nn alamprobleemid 
tavaliselt olemas 
või muutmisel 
on lahendatud , siis kogu 
valem. 
väiksemaks probleemiks 
lahenduse saamiseks need 
ühendatakse kokku. 
Paisksalvestus; 
Kahendotsimine – otsitav 
Lineaarne otsimine (leida 
Poolitussortimine, 
tuvastamaks, kas 
piirkond aheneb igal 
kõige väiksem number 
kiirsortimine, mestimisega 
täisarv  on paaris või 
sammul  2 korda, 
massiivis) 
sorteerimine, kuhjaga 
paaritu 
Parallelsed ja jagatud 
Vektorite sisestamine
sorteerimine, timsort 
algoritmid 
väljastamine,  liitmine
lahutamine ja 
skalaarkorrutis 
O(n2) 
O(n3) 
O(2n) 
O(n!) 
Ruutkeerukus 
Kuupkeerukus 
Eksponentsiaalne 
Faktoriaalne 
• Andmehulga kasvamisel 10 korda 
Enamasti 3 tsüklit 
• Kui N=10 on  aeg 1000,   
suureneb tööaeg 100 korda. 
üksteise sees, mis 
• Suurendades N-i 20 
• Enamasti 2 tsüklit üksteise see ja 
kõik sõltuvad 
korda, kasvab tööaeg 
mõlemad sõltuvad algandmete 
algandmete hulgast. 
1000000-ni. 
hulgast. 
• Ebapraktiline algoritm. 
 
Algoritmid ja andmestruktuurid 2015 
 
 

• Sobilik on selline algoritm suhteliselt  •  Sobilik vaid 
Jõumeetodil lahendused, 
n elemendi kõigi 
väikest mõõtu probleemide 
väikeste 
kõigi variantide 
võimalike 
lahendamiseks. 
andmetehulkade 
täisläbivaatused. 
järjestuste leidmine 
• Nullsortimine, valiksortimine, 
korral. 
maatriksite sisestamine, 
•  Maatriksite 
väljastamine, liitmine ja lahuta... 
korrutamine. 
 
Arvuti töökiirus 
Probleemi mõõt 10^6 
( operatsioonid sekundis) 
O(n) 
O(n log n) 
O(n2) 
10^6 
tunnid  
tunnid 
lootusetu 
10^9 
sekundid  
sekundid 
aastad 
10^12 
kohe 
kohe 
nädalad 
 
 
Algoritmid ja andmestruktuurid 2015 
 
 

 
2.  Algoritmimise strateegiate lühike iseloomustus ja kasutamise näide ( Brute -force ehk 
jõumeetod , Greedy  method ehk  ahne  algoritm,  Divide  and Conquer ehk jaga ja 
valitse). 
2.1  Brute-force ehk jõumeetod 
•  Leiab lahenduse ebaefektiivselt, tavaliselt vaadates läbi kõikvõimalikud lahendused ja teed 
•  Kergesti arusaadav ja väljamõeldav 
•  Sõltub lähteandmete iseloomust, hulgast ja sellest, mida otsitakse, kas selline meetod on sobiv 
•  Tuleb läbi proovida kõik võimalused ja valida välja parim 
2.1.1  Nõrgad küljed: 
•  Enamasti on tegemist aeglase meetodiga 
•  Nõuavad paljude sammude sooritamist 
•  Tihti võimatu täita, sest keerukusklass võib kerkida O(N!)-ni 
2.1.2  Tugevad küljed: 
•  Jõumeetodil lahenduse uurimine viib tavaliselt probleemist parema  arusaamise  juurde ehk ta 
on kui mõtlemise strateegia. 
•  Väikeste algandmete hulga juures võib sellist  lahendust  paberil läbi mängida ja muutub 
probleem arusaadavaks 
•  Jõumeetodil töötavad algoritmid on lihtsad, paremini arusaadavad, kergemini realiseeritavada 
ja veakindlamad 
Algoritmid ja andmestruktuurid 2015 
 
 

2.1.3  Näide:  
Valiksorteerimine, mullisosrteerimine, Sequential search 
Leida arvu 625 kõik tegurid. Lahenduskäik: alustatades 1-st ja lõpetades 625 jagada arv läbi kõigi 
arvudega. Kui arv jagub ( jääk on 0), siis on järgmine tegur leitud. 
2.2  Greedy method ehk ahne algoritm 
•  Algoritmitüüp on sobiv optimiseerimisülesannete lahendamiseks
•  Optimiseerimisül. Otsib kõigi kandidaatide hulgast mingit alamhulka (valitute hulka), mis 
rahuldaks teatud tingimusi. Tingimuseks on enamasti mingi max või min väärtuse leidmine ja 
vastavalt on ka tehtud valikufunktsioon. 
2.2.1  Nõrgad küljed: 
•  Ei anna alati vastuseks optimaalset tulemust ja kui tulemus on ka optimaalne, on seda väga 
raske tõestada
2.2.2  Tugevad küljed: 
•  Paljudel juhtudel on teda kergem koostada 
•  Töötab kiiremini kui DP algoritm 
Optimiseerimise juures on vajalikud teatud tingimused: 
1.  Kandidaatide hulk ( graafi   tipud , teede pikkused, rahatähtede suurused...) 
2.  Valitute hulk, mis või kes on juba kasutatud ( sobivaks   tunnistatud , tagasi antud rahatähed, 
läbitud graafi tipud...) 
3.  Eeldatav lahendus, otsitav summa vms, mille järgi saab otsustada, kas välja valitud kandidaadid 
moodustavad lahendused (ei pruugi olla optimaalne) 
4.  Jätkamise näitaja, mille järgi saab otsustada, kas kandidaatide hulka saab suurendada, et 
lahendust  leida. 
5.  Valikufunktsioon, mille abil valitakse uusi kandidaate väljavalitute hulka 
6.  Vastusefunktsioon, mis annab lõpliku väärtuse lahendusele 
2.2.3  Näide kasutamisest: 
Ahnet algoritmi on sobiv kasutada siis,
80% sisust ei kuvatud. Kogu dokumendi sisu näed kui laed faili alla

Logi sisse ja saadame uutele kasutajatele faili TASUTA e-mailile

Vasakule Paremale
Algoritmid ja andmestruktuurid eksamiks kordamine #1 Algoritmid ja andmestruktuurid eksamiks kordamine #2 Algoritmid ja andmestruktuurid eksamiks kordamine #3 Algoritmid ja andmestruktuurid eksamiks kordamine #4 Algoritmid ja andmestruktuurid eksamiks kordamine #5 Algoritmid ja andmestruktuurid eksamiks kordamine #6 Algoritmid ja andmestruktuurid eksamiks kordamine #7 Algoritmid ja andmestruktuurid eksamiks kordamine #8 Algoritmid ja andmestruktuurid eksamiks kordamine #9 Algoritmid ja andmestruktuurid eksamiks kordamine #10 Algoritmid ja andmestruktuurid eksamiks kordamine #11 Algoritmid ja andmestruktuurid eksamiks kordamine #12 Algoritmid ja andmestruktuurid eksamiks kordamine #13 Algoritmid ja andmestruktuurid eksamiks kordamine #14 Algoritmid ja andmestruktuurid eksamiks kordamine #15 Algoritmid ja andmestruktuurid eksamiks kordamine #16 Algoritmid ja andmestruktuurid eksamiks kordamine #17 Algoritmid ja andmestruktuurid eksamiks kordamine #18 Algoritmid ja andmestruktuurid eksamiks kordamine #19 Algoritmid ja andmestruktuurid eksamiks kordamine #20 Algoritmid ja andmestruktuurid eksamiks kordamine #21 Algoritmid ja andmestruktuurid eksamiks kordamine #22 Algoritmid ja andmestruktuurid eksamiks kordamine #23 Algoritmid ja andmestruktuurid eksamiks kordamine #24 Algoritmid ja andmestruktuurid eksamiks kordamine #25 Algoritmid ja andmestruktuurid eksamiks kordamine #26 Algoritmid ja andmestruktuurid eksamiks kordamine #27 Algoritmid ja andmestruktuurid eksamiks kordamine #28 Algoritmid ja andmestruktuurid eksamiks kordamine #29 Algoritmid ja andmestruktuurid eksamiks kordamine #30 Algoritmid ja andmestruktuurid eksamiks kordamine #31 Algoritmid ja andmestruktuurid eksamiks kordamine #32 Algoritmid ja andmestruktuurid eksamiks kordamine #33 Algoritmid ja andmestruktuurid eksamiks kordamine #34 Algoritmid ja andmestruktuurid eksamiks kordamine #35 Algoritmid ja andmestruktuurid eksamiks kordamine #36 Algoritmid ja andmestruktuurid eksamiks kordamine #37 Algoritmid ja andmestruktuurid eksamiks kordamine #38 Algoritmid ja andmestruktuurid eksamiks kordamine #39 Algoritmid ja andmestruktuurid eksamiks kordamine #40
Punktid 100 punkti Autor soovib selle materjali allalaadimise eest saada 100 punkti.
Leheküljed ~ 40 lehte Lehekülgede arv dokumendis
Aeg2015-06-13 Kuupäev, millal dokument üles laeti
Allalaadimisi 207 laadimist Kokku alla laetud
Kommentaarid 0 arvamust Teiste kasutajate poolt lisatud kommentaarid
Autor darben Õppematerjali autor

Lisainfo

IFI6083 Algoritmid ja andmestruktuurid

Väga hea abivahend eksamiks valmistumisel.

EAP: 4.0
Hindamisviis: Eksam
Õppejõud: õpetaja Inga Petuhhov
Toimumisaeg: kevadsemester 2015
Eeldusaine: Programmeerimise alused

Märksõnad

Mõisted


Meedia

Kommentaarid (0)

Kommentaarid sellele materjalile puuduvad. Ole esimene ja kommenteeri


Sarnased materjalid

22
pdf
Algoritmid ja andmestruktuurid-puud-kuhjad
575
docx
Nimetu
6
pdf
Algoritmid ja andmestruktuurid-transfers
3
pdf
Algoritmid ja andmestruktuurid konspekt - puud
555
doc
Programmeerimiskeel
816
pdf
Matemaatika - Õhtuõpik
86
pdf
ARVUTID I-IAF 0041
16
pdf
Algoritmid





Logi sisse ja saadame uutele kasutajatele
faili e-mailile TASUTA

Faili allalaadimiseks, pead sisse logima
või
Kasutajanimi / Email
Parool

Unustasid parooli?

UUTELE LIITUJATELE KONTO MOBIILIGA AKTIVEERIMISEL +50 PUNKTI !
Pole kasutajat?

Tee tasuta konto

Sellel veebilehel kasutatakse küpsiseid. Kasutamist jätkates nõustute küpsiste ja veebilehe üldtingimustega Nõustun