xn+1 - x* = g(xn) - g (x*) siis seoste (1.24.5) ja (1.24.6) põhjal saame |xn+1 - x | q |xn - x | . 5 Seega |xn - x | q |xn-1 - x | q2 |xn - x | . . . qn |x0 - x | , st kehtib hinnang |xn - x | qn |x0 - x | . (1.24.7) Kui q < 1, siis hinnangust (1.24.7) järeldub, et Algoritmil (1.24.3) põhinevat võrrandi (1.24.2) lahendamise meetodit nimetatakse harilikuks iteratsioonimeetodiks. 6 Teoreem: Leidugu võrrandi (1) lahendit x* sisaldav vahemik (a, b), milles on täidetud võrratus (3). Olgu funktsioon g(x) selline, et x (a, b) korral g(x) (a, b). Olgu x0 (a, b). Siis koondub hariliku iteratsioonimeetodiga arvutatud lähendite jada xn täpseks lahendiks x*. Lisaks kehtib veahinnang
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 paberi abil täidetav. Algoritmi keerukus on hinnang sellele, kuidas algoritmi poolt esitatavad nõudmised ajale muutuvad näiteks siis, kui probleemi mõõt kasvab
sama salajase võtme kaasabil algsed andmed Ilma ühte sama võtit teadmata on mõlemad tegevused võmatud Salajase võtmega krütoalgoritm: turvalisus Kaasajal loetakse piisavalt tugevaks tavaliselt vähemalt 128 biti pikkuse (erijuhul 80 biti pikkuse) salajase võtmega algoritme DES on seega kaasajal nõrguke, kuna ei vasta selle tingimusele. Hädalahendus oli 3kordse DESi kasutamine (kuni aastani 2005) Lisaks võtmepikkusele ei tohi algoritmil olla tuntavaid efekte andvaid krüptoanalüütilisi ehk murdmisvõtteid. Salajase võtmega krüptoalgoritm: kasutusalad Neid on kaks: · Konfidentsiaalse teabe edastamiseks üle (mitte pealtkuulamiskindlate) võrkude · Konfidentsiaalsete teabekogumite salvestamine avalikus keskonnas sooviga teabe saajate hulka piirata Salajase võtmega krüptoalgoritm: tekkiv probleem Probleem: enne teabe edastamist üle võrgu on vaja kuidagi tagada, et mõlemas
LAHENDUVUS. kas Uldse 0lesannet lahendada saab? Selgub, et iga tdpselt tqmuleeritud probleemi jaoks ei leidugi I 965 - PDP-8 lahendavat algoritmil Saab heidata, et ednevaid probleeme on l6omatuh rohkem, kui erinevaid algoritme I967 - LOGO
joonistatud mingi sümboliga andmebaasis kas pikslite või koordinaatide paari kujul Päring Kaardilugemine Atribuudiinfo on iga piksli või koordinaadi paari juures ja otsin põhineb arvuti algoritmil 4. Analoogne vs digitaalne. Analüüsimine Kartograafia GIS Kartomeetria Joonlaud, planimeeter, Arvuti teeb ise ja automaatselt kompass ja inimene analüüsib Piirangud Kõik see, mis kaardil olemas Andmete muurmine, ümberkvalifitseerimise
o IS-IS (Intermediate system to intermediate süstem)(ISO10589) EGP protokollid o - BGP - (Border Gateway Protocol) (RFC4271) Algoritmi järgi jaotatakse o Distantsvektor-marsruutimisprotokollid (distance vector) RIP,IGRP,EIGRP, BGP o Sideliini-oleku marsruutimisprotokollid (link-state) OSPF, IS-IS Distantsvektor-marsruutimisprotokollid Baseeruvad Bellman-Fordi algoritmil Iga marsruuter kuulutab naabermarsruuteritele välja võrke, mida ta teab o on vahetult ühendatud või o on marsruudi õppinud naabermarsruuteritelt Iga võrgu kohta näidatakse ka meetrika o meetrikaks tavaliselt HOP-de (läbitavate marsruuterite) arv Õpitud marsruudid ununevad mingi (kontroll)aja möödudes, seepärast uuendatakse neid kindla aja tagant ... nõrkused Konvergentsi saavutamine võib võtta aega
listi, andmebaasi suurus) – Sisendparameetri väärtus – Sisendparameetri suurus (bittide/baitide arv) Mis on o-notatsioon? Keerukuse hindamiseks. Annab keerukusklassi – millise proportsiooniga suureneb arvutusaeg sõltuvalt sisendi suuruse muutusest Nt 1/2 (n-1)*n O(n**2) Sorteerimise parim keerukus halvimal juhul: Maksimaalne suhteline aeg, mis võib algoritmil minna O(n2) 12. nädal • Eksamiks: mis on tugev ja mis nõrk AI, mis on turingi test ja mis on eliza. Mis on otsimeetodites minimax ja alpha-beta (tehnilisi detaile ja näiteid ei tule). Mis on masinõpe. Mis on IBM Watson ja Wolfram Alpha. Võib tulla küsimus, et kas mingit sorti ülesannet praegused tehisintellektisüsteemid suudavad ok/väga hästi/väga halvasti lahendada. Andmeanalüüsi kohta küsimusi ei tule.
mooduseid, on eukleidese algoritm nendest optimaalseim: a). Algoritmi programmsel realiseerimisel on välistatud kõiksuguste silmuste tekkimine, st. programm lõpetab ALATI oma töö. b). Ta annab tulemuseks 100%-kindlusega suurima ühisteguri. c). Algoritm käib äärmiselt efektiivselt ümber arvuti ressurssidega nagu ka loengus mainitud sai. Sisuliselt ,,loeb ta vaid korra sisse" kõik ette antud operandid. Algoritmil kulub tulemuse saamiseks aega ülimalt 1 sammu. *Sõnades võib algoritmi tööd esitada järgmiselt: a). Valime b ossa suurema kahest arvust gcd(a,b). b). Jagame b'd a'ga, saame jäägi r ning asendame b selle jäägiga r. c). Pöördume tagasi silmuse algusesse või kui a on 0, siis väljastame b gcd'na. *Lisaks: Eukleidese algoritm on äärmiselt laia kasutust leidnud ka arvuteooria erinvates
protokollidest ei nõua BGP kogu tabeli perioodilist värskendust. Tabel sisaldab küll kõiki võimalikke teid vastava võrguni, kuid värskendusteadetes kuulutatakse ainult optimaalseid teid. Mõõt on BGP-l meelevaldne kaal, mille kinnistab võrguhaldur konfiguratsioonifailide kaudu. Kriteeriume võib olla suvaline arv, muuhulgas AS- ide arv, lüli tüüp (stabiilsus, kiirus, usaldatavus) jms. OSPF (Open Shortest Path First, "Vali lühim tee esimesena"). See protokoll põhineb Dijkstra algoritmil. Ta võeti kasutusele kuna seinine protokoll RIP ei rahuldanud suureneva võrgu vajadusi. OSPF töötab lüli oleku järgi. Kõigile teistele marsruuteritele samal hierarhiaalal saadetakse lüli oleku kuulutused (LSA), mis sisaldavad informatsiooni liideste, kasutatava mõõdustiku ja muude muutujate kohta. Lühim tee iga sõlmeni arvutatakse SPF-algoritmiga. Erinevalt RIP-st saab OSPF töötada hierarhias. Sellest aga oli juttu hierarhilise marsruutimise peatükis.
Kliendi autentimiseks kasutatakse andmebaasi tabelis hoitavaid kasutajanimesid ja paroole. Kliendi kasutajanimi ja parool on tabelis Isik (veerud kasutajanimi, parool). Antud tabelis kehtib kitsendus, mis määrab ära, et kasutajanimi peab olema unikaalne. Paroole ei salvestata avatekstina vaid salvestatakse räsiväärtusena. Räsiväärtuste leidmist tehakse rakenduses, mis on realiseeritud java programeerimis keeles. Räsiväärtuse genereerimiseks kasutatakse sha256-l põhineval algoritmil. Räsiväärtuse leidmist võib realiseerida ka otse andmebaasis enne väärtuse salvestamist kuid see on ebaturvaline kuna andmebaasi ja rakenduse vahel liiguks parool avatekstina. Ründaja võib võrku kuulates saada andmeid parooli kohta. Kasutaja identiteeti kontrollimiseks võrreldakse tema poolt etteantud parooli põhjal genereeritud räsiväärtust andmebaasis oleva räsiväärtusega. Kui need väärtused on
• 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
X1 jne sisendid, millest sõltub, kuidas läbitakse algoritmi. Algoritmi täitmisel määravad tingimuslikud sõlmed erinevate harude valiku. Juhtautomaadis vastavad tingimustele sisendid, mis tulevad protsessori teistest osadest. Y1 jne väljundid, mis aktiveerivad tegevusi protsessoris ja kogu süsteemis, käivitavad mikrooperatsioone ehk elementaartegevusi arvutis. A1 jne olekud, ehk info, kus oleme algoritmi täitmisel. Olek kujutab endast algoritmil märgitud punkti, mis näitab kus ollakse parasjagu. Am=Fü(As,Xi) üleminekute funktsioon,mis määrab millisesse olekusse As me liigume, kui oleme olekus Am ja tuleb sisendväärtuste kombinatsioon Xi. Üleminekute funktsioon määrab algoritmis märgitud punktide vahel liikumise seaduspärasuse. Yj = Fv(As,Xi) väljundfunktsioon Mealy automaadil määrab väljundväärtuste kombinatsiooni funktsioonina olekust As ja sisendite väärtuste kombinatsioonist Xi
perioodilist värskendust. Tabel sisaldab küll kõiki võimalikke teid vastava võrguni, kuid värskendusteadetes kuulutatakse ainult optimaalseid teid. Mõõt on BGP-l meelevaldne kaal, mille kinnistab võrguhaldur konfiguratsioonifailide kaudu. Kriteeriume võib olla suvaline arv, muuhulgas AS- ide arv, lüli tüüp (stabiilsus, kiirus, usaldatavus) jms. OSPF (Open Shortest Path First, "Vali lühim tee esimesena"). See protokoll põhineb Dijkstra algoritmil. Ta võeti kasutusele kuna seinine protokoll RIP ei rahuldanud suureneva võrgu vajadusi. OSPF töötab lüli oleku järgi. Kõigile teistele marsruuteritele samal hierarhiaalal saadetakse lüli oleku kuulutused (LSA), mis sisaldavad informatsiooni liideste, kasutatava mõõdustiku ja muude muutujate kohta. Lühim tee iga sõlmeni arvutatakse SPF-algoritmiga. Erinevalt RIP-st saab OSPF töötada hierarhias. Sellest aga oli juttu hierarhilise marsruutimise peatükis.
kättesaadavaks krüptoanalüütikutele selle turvalisuse hindamiseks vähemalt kaks aastat tagasi. Suletud kirjeldusega krüptovahendid peavad olema läbinud turvaauditi, mille käigus on veendutud nende murdmatuses. Viimasel juhul peab asutuse turvajuht veenduma niisuguse suletud turvaauditi usaldusväärsuses ja seda aktsepteerima. · Sümmeetrilise krüptoalgoritmi (efektiivne) võtmepikkus peab olema vähemalt 192 bitti ja algoritmil ei tohi olla teada olulist võitu (enam kui 8-16 korda ajalist võitu) andvaid krüptoanalüütilisi võtteid. ____________________________________________________________________ HT.63 = HS.52 Sülearvutite krüpteerimine HT.63 Sülearvutite krüpteerimine M 4.29 parametriseering Lisaks M 4.29 nõuetele tuleb juhinduda alljärgnevast: · Kõigil füüsiliselt turvatud tsoonist välja viidavatel (nt kodus töötamiseks
Järgmisena pöördutakse naabri poole, kelleni oli tee kõige odavam. Vaadatakse üle tema otsesed naabrid ning kui mõni tee oli odavam, kui eelmise naabri juurest, siis märgitakse see endale üles ning jäetakse meelde, et selle tipu kaudu oli sinna odavam minna. Kallimaid asju üles ei märgita. Ning jätkatakse samal põhimõttel, kuni on teada odavaimad teed alguspunktist teistesse punktidesse. Link state marsruutimisalgoritm - Baseerub Djikstra algoritmil, eeldusena on kõigile võrguseadmetele teada võrgu topoloogia, kõik seadmed omavad sama infot. Arvutatakse vähima kuluga tee ühest võrgusõlmest kõigisse teistesse, saadakse ruutimistabel selle võrgusõlme jaoks. Iteratiivne pärast k iteratsiooni teatakse vähima kuluga teed k sihtkohta. 29. Distance vector marsruutimisalgoritm Omadused: Iteratiivne (jätkub kuni ükski sõlm infot ei vaheta), ise-lõpetav (ei ole
19 Hajutatud – ruuter teab oma naabreid, ühenduskulu naabriteni; kogu tee maksumuse arvutamine iteratiivne, vahetatakse infot naabrite vahel (Distance vector algoritmid). Kas staatilised või dünaamilised: Staatilised – võimalikud teed muutuvad harva. Dünaamilised – võimalikud marsruudid muutuvad sageli, toimub perioodiline uuendamine. 31. Link state marsruutimisalgoritm Baseerub Djikstra algoritmil, eeldusena on kõigile võrguseadmetele teada võrgu topoloogia, kõik seadmed omavad sama infot. Arvutatakse vähima kuluga tee ühest võrgusõlmest kõigisse teistesse, saadakse ruutimistabel selle võrgusõlme jaoks. Iteratiivne – pärast k iteratsiooni teatakse vähima kuluga teed k sihtkohta. 32. Distance vector marsruutimisalgoritm Igal sõlmel on oma kauguste tabel (Distance Table). Tabelis on nii palju ridu, kui on
annaabi.ee 
