Algoritmid kokkuvõte (0)

PowerPoint Presentation



1/55 Algoritmid ja andmestruktuurid Ülevaades sellest kuhu oleme jõudnud Ja kuidas edasi minna


2/55 Eksamid ja konsultatsioonid Eksamid ⚫ 18. detsember kell 14 ⚫ 11. jaanuar kell 14 ⚫ 20. jaanuar kell 14


3/55 Mis on algoritm? Probleem Algoritm Programm Andmed Tulemus


4/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 ⚫ tagasivõtmisega algoritm, hargne ja kärbi – otsime lahendust puust ja kärbime seda niipalju kui suudame ⚫ metaheuristikad – võimaldavad leida häid tulemusi ilma headuse garantiita ⚫ lähendavad algoritmid ⚫ paralleelsed algoritmid


5/55 Andmestruktuurid ⚫ annavad andmete töötlemiseks algoritmile 
abstraktse liidese – võimaldab kirjutada algoritmi kõrgemal, andmestruktuuri 
mõistete tasandil 
lisa element (puusse, kuhja), ühenda kaks alamhulka – võimaldavad kasutada erinevaid realisatsiooni  optimiseeritud erinevate operatsioonide tarvis  erinevad valmis realisatsiooni (paketid, teegid) ⚫ peidavad/realiseerivad algoritmi olulise keerukuse – enamus programmi mahust võib olla andmestruktuuride 
realisatsioon ⚫ realiseeritakse lihtsamate andmestruktuuride baasil


6/55 Kompositsiooniline lähenemine ⚫ Algoritmi tehakse abstraktsema andmestruktuuri 
terminites – algoritm on arusaadavam – kasutatakse efektiivseid andmestruktuuride realisatsioone ⚫ Algoritmis kasutatakse teadaolevaid häid algoritme – minimaalse aluspuu leidmine lähendavas TSP-s – sügavuti otsing graafil topoloogiliseks sorteerimiseks ⚫ Andmestruktuuride realiseerimiseks kasutatakse 
lihtsamaid andmestruktuure prioriteetjärjekord - kuhi - binaarpuu - massiiv mittelõikuvad alamhulgad - tagurpidid lingitud puu - massiiv


7/55 Komponendid  optimiseerimisprobleemis Rändkaupmehe ülesanne otsing konfiguratsioonide puus tagasivõtmisega otsing parim-enne otsing ahne otsing dünaamiline planeerimine prioriteet järjekord binaarne kuhi (dünaamiline) massiiv paisksalvestus lähendav lahendamine puu sügavuti  läbimine Minimaalse alus- puu leidmine mittelõikuvad  alamhulgad


8/55 Mis kasu on algoritmidest ja  andmestruktuuridest? ⚫ Üldised algoritmide klassid – võimaldavad mõista probleemi olemust – võimaldavad probleemile ise algoritmi leida ⚫ Andmestruktuurid – võimaldavad mõelda abstraktsemalt – kirjutada koodi kõrgema tasemel – muuta käitumist andmestruktuuri realisatsiooni ja tüübi 
muutmisega (sügavuti - laiuti - parim enne otsing) – lihtsustada algoritmi kasutades sobilikku olemasolevat 
andmestruktuuri implementatsiooni


9/55 Algoritmide keerukus ⚫ Algoritmi keerukus on põhioperatsiooni(de) arvu
sõltuvusfunktsioon K(n) sisendi(te) suurusest n. – Põhioperatsioon ei ole üheselt defineeritav  Üldiselt midagi mis on riistvara tasandil tehtav piiratud arvu
sammudega – Sisendi suurus võib olla defineeritud erinevalt  Sisendandmete maht (massiivi, faili, andmebaasi suurus)  Sisendparameetri väärtus  Sisendparameetri suurus (bittide/baitide arv) ⚫ Tavaliselt hinnatakse halvima juhu (sisendi) 
keerukust


10/55 f(n) = 2n + 6 Funktsioonide f(n) ja
g(n) jaoks on 
olemas konstandid c
ja N, nii et: 
f(n)≤c g(n), kui n ≥ N järeldus:  2n+6 is O(n). Asümptootiline keerukus


11/55 Lahtine probleem ⚫ Arvutuslik keerukus – Käsitleb probleemi – Annab keerukuse alumise raja - sellest piirist väiksema 
keerukusega algoritmi olla ei saa ⚫ Algoritmi keerukus – Analüüsib algoritmi – Annab keerukuse ülemise raja - probleemi keerukus ei 
ole suurem kui seda lahendava algoritmi keerukus ⚫ Probleeme, kus keerukuse alumine ja ülemine raja ei 
lange kokku nimetatakse lahtisteks probleemideks


12/55 Lahtine probleem O(n!) O(Kn) O(n3) O(n12) ? Probleemi P olemuslik keerukus O(Kn) algoritm P lahendamiseks O(n!) algoritm P lahendamiseks Tõestus, et P vajab vähemalt 
O(n12) keerukust  Tõestus, et P vajab vähemalt 
O(n3) keerukust  ülemine raja alumine raja


13/55 NP täielik probleem ⚫ Tähtis ülesannete klass – sisaldab palju praktikas olulisi probleeme – raske leida lahendust - eksponentsiaalse keerukusega – lihtne lahendust kontrollida - polünomiaalse keerukusega – probleemid on omavahel seotud - kui ühe jaoks leitakse 
polünomiaalne lahendusalgoritm, siis on see olemas kõigi 
jaoks ⚫ Mida teha? – defineerida probleem ümber, nii et leiduks vähem-
keerukas algoritm (tihti piisab mingist lisakitsendusest) – kasutada heuristikaid, mis võimaldavad paljudel 
praktilistel juhtudel ülesande ära lahendada – kasutada lähendavat algoritmi


14/55 Kuidas saab veel arvutada ⚫ Juhuslikkuse kasutamine – viskame münti ⚫ Meta-heuristiline lähenemine – matkime loodust ⚫ Paralleelne arvutamine – teeme seda kambaga ⚫ Kvantarvutamine, molekularvutamine – looduse saladuste ärakasutamine, massiivne paralleelsus


15/55 Juhuslikkuse kasutamine On mitmed üldiseid meetodeid probleemide 
ligikaudseks lahendamiseks või kiirendamiseks, mis 
tuginevad juhuslikkusele – deterministlike algoritmide juhuslikustamine  – Monte Carlo meetod, simuleerimine – metaheuristikate kasutamine NP täielike ülesannete 
lahendamiseks


16/55 Algoritmide juhuslikustamine ⚫ Kasutatakse juhul kui  – algoritmi keskmine ja halvima juhu keerukus on erinevad  – halvima juhu realiseerumine on keskmisest tõenäolisem ⚫ Algoritmi tuuakse sisse juhuslikkuse moment, nii et 
halvima juhtumi realiseerumine poleks sõltuv 
sisendandmetest vaid juhuslikkusest ⚫ Iga algoritmi täitmine samade sisendandmete korral 
võib võtta erineva aja


17/55 Juhuslikustatud Quicksort ⚫ Valime teljeks juhusliku elemendi – esimese elemendi teljeks valimisel realiseerub halvima 
juhtumi keerukus, kui andmed on juba sorteeritud ⚫ Sorteerime kõik teljest väiksemad temast vasakule ja 
suuremad paremale ⚫ Sorteerime teljest paremale ja vasakule jääva
massiivi


18/55 Algarvulisuse test ⚫ Kas N on algarv? ⚫ Eksponentsiaalse keerukusega N suuruse (bittide 
arus suhtes) ⚫ Miller-Rabin test on võimalik kontrollida testide arvu 
väljendava sisendparameetri s alusel – kas arv on kordarv – kas arv on algarv tõenäosusega 2-s, ehk 
iga testi tsükliga väheneb algarvuks olemise tõenäosus 2 
korda
s = 50 piisab igaks praktiliseks rakenduseks


19/55 Monte Carlo meetod Stohhastiline simuleerimismeetod paljude 
matemaatiliselt keeruliste probleemide lahenduse 
numbrilise hinnangu saamiseks – kasutab (pseudo)juhuslikke arve probleemi paljukordseks 
läbisimuleerimiseks Näiteid Selgitatakse objekti sisendite statistiline jaotus – Genereeritakse juhuslikke sisendeid vastavalt leitud 
jaotusele – Loendatakse tulemusi – Arvutatakse hälve, et hinnata tulemuse täpsust


20/55 Example:  the area of a circle ⚫ Sample points randomly 
from square surrounding 
circle of radius 5 ⚫ 10,000 sample points ⚫ Acceptance criterion:  
inside circle ⚫ Actual area:  78.54 ⚫ Calculated area:  78.66 2000 4000 6000 8000 10000 78.2 78.4 78.6 78.8 79.2 79.4 79.6 -4 -2 2 4 -4 -2 2 4


21/55 Example:  more complicated  shapes -4 -2 2 4 -4 -2 2 4


22/55 Monte Carlo kasutamine kärpimise  efektiivsuse hindamiseks ⚫ Annab hinnangu kärbitud otsingupuu suurusele ⚫ Iga Monte Carlo simulatsioon on annab puu suuruse 
hinnangu liikudes mööda üht haru nii sügavale kui 
võimalik.  ⚫ Piisava hulga simulatsioonide keskmisena saame 
hinnang kogu puu suurusele. ⚫ On rakendatav kui – kõigil tasemetel kasutatakse sama promising funktsiooni – sama taseme sõlmedel on ühepalju järglasi m i lootustandvate järglaste arv tasemel i t i järglaste arv tasemel i 1 + t 0 + m0 t1 + m0 m1 t2 + ... + m0 … m i-1 t i


23/55 Metaheuristikad ⚫ On mitmeid üldisi metaheuristikaid – geneetilised algoritmid (genetic algorithms) – simuleeritud lõõmutamine (simulated annealing) – tabudega otsing (tabu search) – optimiseerimine sipelgakolooniaga 
(ant colony optimization) ⚫ Aitavad leida optimaalsele lahendusele lähedast 
lahendust olukorras, kus optimaalse lahenduse 
leidmine pole arvutusmahu tõttu realistlik ⚫ Ei anna hinnangut tulemuse “headusele”,  – tulemuse osas pole kindlust kui palju see erineb 
optimaalsest – optimaalse tulemuse leidmisel, ei peatu


24/55 Metaheuristikad Koosnevad tavaliselt kahest osast ⚫ lokaalse optimumi poole liikumine ⚫ hajutamine, et mitte takerduda lokaalsesse optimumi Nende vahel tuleb leida  tasakaal, et mitte: ⚫ koonduda viletsasse
lokaalsesse optimumi ⚫ taanduda juhuslikule
otsingule


25/55 Geneetilise algoritmi idee ⚫ Genereeritaks lahenduseks vormiliselt sobilik 
(juhuslik) isendite (kromosoomide) hulk, ehk 
põlvkond. ⚫ Kontrollitakse iga isendi sobivust lahenduseks ja 
antakse neile sobilikkuse hinnang ⚫ Ühe põlvkonna isendeid kasutatakse järgneva 
põlvkonna loomiseks, püüdes seda teha nii, et need 
oleks keskmiselt paremad ⚫ Jätkatakse kuni arvatakse olevat leitud lahend või 
piisavalt hea lahend.


26/55 Geneetilise algoritmi üldkuju 1. Genereeri juhuslik n isendiga põlvkond (n genoomi) 2. Hinda iga isendi sobilikkust s(n) 3. Loo uus põlvkond kasutades järgnevaid samme a) vali kaks vanemat - suurema tõenäosusega parema 
sobilikkusega isendid b) ristamistõenäosusega rista järglaste tekitamiseks 
vanemate kromosoomid, vastasel juhul kopeeri c) muteerimistõenäosusega muuda mõne geeni väärtust d) lisa tulemus uude generatsiooni 4. Kasuta järgnevalt uut põlvkonda 5. Vastavalt lõpetamistingimusele jätka punktist 2 või 
lõpeta


27/55 Järglaste loomine ⚫ Kromosoomi kodeerimine Näiteks on kromosoomiks (probleemi argumendiks) on 
üks täht ja number 0-7. Kodeerime tähe 5 bitiga, sümboli 3 bitiga:
A5 = 00001101
F2 = 00110010 ⚫ Ristamine lõikame gromosoomid juhuslikust kohast pooleks ja 
vahetame vanemate kromosoomide tagumised osad vanemad: 00001101 (A5) 00110010 (F2) järglane: 00101101 (E5) ⚫ Muteerimine 00101101 (E5) 00101111 (E7)


28/55 Metaheuristilised algoritmid  ⚫ Annavad tihti enamvähem hea lahenduse keerulisele 
probleemile ⚫ Ei anna kunagi kindlust, et leitud lahendus on 
optimaalne optimaalsusülesande lahendamisel ⚫ NP täieliku ülesande lahendamisel saadud “jah” 
vastuse korral on meil lahend käes ⚫ Võimaldavad mitte süveneda probleemi 
matemaatilisse keerukusse ⚫ Pole imerohuks - efektiivsus sõltub oluliselt 
kasutatavast kodeeringust ja operaatoritest


29/55 Parallel computer


30/55 PRAM Parallel Random-Access Machine  • Shared Memory – SMT (Simultaneous Multithreading) – Each processor may have local memory to store local 
results • MIMD  – Multiple Instruction Multiple Data • SIMD  – Single Instruction Multiple Data – Model is MIMD, but algorithms tend to be SIMD  – Each active processor executes same instruction ⚫ SIMT - Single Instruction Multiple Thread (CUDA) • Synchronous • Memory Access – There are different PRAM models depending on the possibility of 
the concurrent read/write


31/55 Memory Access ⚫ Exclusive Read Exclusive Write (EREW) – no simultaneous access to a single shared-memory 
location  ⚫ Concurrent Read Exclusive Write (CREW) – simultaneous reads of a single shared-memory location 
are allowed  ⚫ Concurrent Read Concurrent Write (CRCW) – simultaneous reads and writes are allowed on a single 
shared-memory location are allowed 


32/55 Conventions of the parallel  algorithms ⚫ Each processor can know it’s own index p = index of this processor; ⚫ A variable can be in  – shared memory - accessible to all processors – private memory - each processor has a local copy of the 
variable ⚫ Shared memory is accessed only for reading and 
writing (not for operations) ⚫ Processors do the steps, reads and writes 
simultaneously ⚫ There is unlimited number of procs available


33/55


34/55


35/55 CRCW PRAM algorithm for finding  the largest key


36/55 Complexity of the parallel (finding)  algorithms Algorithm Time complexity Size (Processors) Sequential O(n) 1 CREW PRAM O(lg n) n/2 CRCW PRAM O(1) n(n-1)/2 • Order of magnitude improvement can be achieved  only when the number of processors is unlimited. • Product complexity Time  Size cannot be better  than the complexity of the best sequential algorithm. • Sequential space complexity  parallel time  complexity – Sequential-PSPACE = Parallel-PTIME


37/55 Kvantalgoritmid Kvantarvutid võimaldavad lahendada mõningaid 
ülesandeid eksponentsiaalselt kiiremini kui 
klassikalised arvutid ⚫ Arvude tegurdamine ⚫ Kvantsimuleerimine (molekulaarmudelid) ⚫ Lineaarvõrrandite lahendamine


38/55 Kvantarvutamine ⚫ Tugineb kvantmehaanika nähtustel – Kvantolek on tõenäosuslik – Kvantoleku mõõtmisel olek muutub – Põimolekus kvantnähtused toimuvad sünkroonselt ja
hetkeliselt sõltumata vahemaast


39/55 Kvantolekud


40/55 Kvantbitt ⚫ Matemaatiliselt: |  = |0 + |1 ⚫ Siin on |0  ja |1 baasivektorid kompleksruumis ning  ja  kompleksarvud. ⚫ Füüsikaliselt võivad |0  ja |1 olla näiteks aatomi põhi- ja ergastatud seisund, footoni polarisatsioonitasand, 
spinni suund jm. ⚫ Kvantbitt – on korraga “mingi tõenäosusega” mõlemas olekus – kannab korraga kahte kompleksväärtust


41/55 Kvantbiti mõõtmine ⚫ Kvantbiti |  = |0 + |1 mõõtmisel baasi |0 , |1 suhtes saame tõenäosusega | |2 tulemuse |0 tõenäosusega | |2 tulemuse |1 ⚫ Normeerimistingimus | |2+||2=1.  ⚫ Kvantbitt |  hävib mõõtmisel. – Kui mõõtmise tulemus on 0,
siis on kõigi järgnevate
mõõtmiste tulemus ka 0 Bloch sphere representation of a qubit


42/55 not kvantfunktsioon not (0) = i/2|0> + 1/2|1>
not (1) = 1/2|0> +  i/2|1> 0 → 0 ja 1 → 1 tõenäosusamplituudiga i/2 0 → 1 ja 1 → 0 tõenäosusamplituudiga 1/2 not = kaks  not kvantfunktsiooni järjest : 0 → 0 on summa kahest teest 0 → 0 → 0 ja 0 → 1 → 0 tõenäosus   | (i/2) 2 + (1/2) 2 |2 =  | -1/2 + 1/2 |2  = 0


43/55 Kvantregister ⚫ Kahebitine kvantregister on nelja vektori
superpositsioon:  |  = |00 + |01 + |10 + |11 ⚫ Normeerimistingimus | |2 + ||2 + ||2 + ||2 = 1 ⚫ Üks n-bitine kvantregister sisaldab
2n erinevat kordajat (kompleksarvu).


44/55 Superpositsioon ⚫ Kvantregistri üks teisendus mõjutab kõiki
baasivektoreid. ⚫ Enne: |00 + |01 + |10 + |11 ⚫ Pärast: U|00 + U|01 + U|10 + U|11 ⚫ Loogikatehted korraga kõigi argumentidega


45/55 Superpositsioon


46/55 Arvutamine kvantarvutil ⚫ Algoleku tekitamine: registri sisuks kõigi
baasivektorite ühtlane superpositsioon 1/ 2n (|0000 + |0001 + ... + |1111) ⚫ Tehted unitaarteisendustena: kvantseaduste järgi
peavad kõik tehted olema pööratavad ⚫ Mõõtmine: registri sisu mõõdetakse baasil |0000 , |0001, ..., |1111 ⚫ Arvutamise komplitseeritus n-qbitine arvuti arvutab 2n kompleksväärtust, aga need  väärtused on seotud – ruutude summa = 1 – teisendused muudavad korraga kõiki väärtusi


47/55 Shori algoritm ⚫ Taandab tegurdamise perioodi leidmise ülesandele ⚫ Leiab n-bitise arvu tegurid O(n) keerukusega, 
kasutades 2n qbitist kvantarvutit


48/55 Põimolek ( entangled state) ⚫ Kaks kvantsüsteemi võivad olla ühises olekus, nii et  
ühe mõõtmine mõjutab ka teist isegi suure vahemaa
tagant. ⚫ Näiteks 1/ 2 |00 + 1/2 |11 ⚫ Põimolekute tõttu on kvantsuprepositsiooni kordajad
üksteisest sõltuvad.


49/55 Kvantkrüptograafia ⚫ Printsiip: pealtkuulamine on võimalik ainult signaali
taastamatu rikkumise hinnaga. ⚫ On olemas tõestatavalt turvaline
võtmekehtestusprotokoll (BB84) ⚫ Edastada tuleb vaid polariseeritud footoneid ⚫ Katseid korraldatud mitmete kilomeetrite kaugusele


50/55 Raskused ⚫ Mõõtmine hävitab kvantsuperpositsiooni ⚫ Dekoherents: vastasmõju keskkonnaga, andmete
lugemisel ⚫ Tehnoloogilised raskused


51/55 Ideaalne kvantarvuti ⚫ skaleerub füüsiliselt qbittide osas ⚫ qbitid saab algväärtustada suvalisele väärtusele ⚫ operatsioonid on kiiremad kui dekoherents ⚫ turing-täielik teisenduste komplekt ⚫ qbitte saab lugeda lihtsalt 


52/55 Kvantarvuti v digitaalne arvuti ⚫ Kvantarvuti annab polünomiaalse keerukusega 
tegurdamis- ja diskreetse logaritmi algoritmi ⚫ Mõlemad algoritmid on NP. Pole suudetud näidata, et 
nad oleks NPC ja usutakse, et need pole NPC ⚫ Pole suudetud näidata, et kvantarvuti lahendaks 
polünomiaalses ajas NPC ülesannet, kui pole 
realiseeritavad mittelineaarsed unitaarteisendused. ⚫ Kvantarvuti ei laienda arvutatavate probleemide 
hulka - kvantarvutit saab simuleerida Turingi masinal.


53/55 Turingi masin ⚫ Minimaalne andmestruktuuride esitus – string ⚫ Minimaalne arvutusmasin – Turingi masin – Andmed – lõpmatu pikkusega lint – Käsud – loe, kirjuta, liigu paremale, liigu vasakule – Programm – lõplik olekumasin ⚫ Arvutatavuse
alusformalism


54/55 Church-Turing tees Kõik, mis on efektiivselt (algoritmiliselt) arvutatav, 
on arvutatav Turingi masinaga (1930) Alternatiivsed arvutatavusteooriad – Rekursiivsed funktsioonid (Kleene) – Lambdaarvutus (Church) Need on omavahel ekvivalentsed ⚫ Paraleelarvutus, kvantarvutus jt mudelid ei lisa
midagi arvutatavate funktsioonide hulka


55/55