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
docstxt/128766409089.txt
Esimene leiab uue lahtri valides tabelis lihtsalt järgmise. Teine algoritm liigub tabelis edasi vastavalt etteantud sammule. Kolmas arvutab vastavalt valemile (s = (h mod (T-2) +1)) eraldi sammu igale sõnale. Sõnade paigutamiseks on üldse ülesandes kokku neli algoritmi. Viimane võimalus ei kasuta lineaarset tabelit, nagu eelmised kolm, vaid jaotab selle kolme sõnalistesse pakkettidesse. Kokku on tabelis 11 paketti, seega 33 lahtrit sõnade paigutamiseks. ALGORITMIDE EFEKTIIVSUSE HINNANG Katsete graafikute uurimisel selgus, et kui paiskadresseerimist kasutada mõne suure reaalse tarkvara väljatöötamisel, tuleks paisktabel võtta võimalikult suur (umbes 60% - 70% suurem, kui tegelikult andmete hoidmiseks vaja oleks). See tagaks andmetele kiire juurdepääsu, kuna kollisioonide arv on seda väiksem, mida suurem on paisktabel. 3
TALLINNA TEHNIKAÜLIKOOL Siduteooria ja disaini õppetool Kodutöö nr 3 aruanne aines LAC5700 OPERATSIOONISÜSTEEMID autor: Eero Ringmäe 010636LAP juhendaja: Vello Kukk Tallinn 2002 Üldine suunitlus Katsetamisel osutus, et otstarbekas oli jälgida algoritmide käitumist piisavalt erinevate taktide arvude korral. Haldusstrateegiate headus tuli paremini esile, kui võrdlesin neid vaid 100, 400 ja 800 taktiste simulatsioonide korral. Valisin kriteeriumiteks peale protsessori ning ressursside kasutamise oote- ja täiteaegade ka maksimaalsed ooteajad protsessori ning ressursside järjekorras, kuna kasutajaprogrammide juures on üheks põhikriteeriumiks protsesside täitmise sujuvus (näiteks meedia taasesitamine arvutis, kopeerimine, salvestamine).
tähtsamaid uurimistulemusi avaldatakse tihti raamatutena. Kõige selle põhjuseks on ilmselt just nende arvude lai rakendatavus ja üldistatavus. Nimelt põhineb suur osa looduslikest protsessidest kas eksponentfunktsioonil (ex) või siis just diskreetsetel rekurrentsetel jadadel, millistest lihtsaimaks ehk ongi Fibonacci jada. Siiski on imestamisväärne, et siiani leitakse uusi viise nende arvude rakendamiseks, nii börsi liikumiste ennustamiseks, õnnemängudes võitmiseks ning algoritmide keerukuse hindamiseks. Huvi pakuvad kindlasti ka puhtalt arvuteoreetilised tulemused, mida arvude pikast ajaloost hoolimata siiski pidevalt juurde avastatakse. Niisiis on Fibonacci arvude näol tegu vägagi unikaalse nähtusega matemaatikas. 3 1. Fibonacci arvud ja nende üldistused 1.1 Fibonacci arvud Fibonacci arvude nime all tuntakse tanapäeval jada 0, 1, 1, 2, 3, 5, 8, 13, . . . ,
..............3 Programmi disaini kirjeldus.........................................................9 Katsed: 1. katse listing........................................................................10 2. katse listing........................................................................11 3. katse listing........................................................................12 4. katse listing........................................................................13 Kommentaarid ja arvamused algoritmide omaduste kohta.....................14 2 ÜLESANDE TINGIMUSED 1) mälu maht 64 või rohkem ühikut; valida nii, et oleks võimalik printida iga olek ühte ritta (kasutada püsilaiusega fonti) 2) protseduurid: 1. mälu eraldamine (reserveerimine) get (maht, tunnus), 2. mälu vabastamine free (tunnus). 3) mudeleerimis- (test-)programm reserveerib-vabastab mälu vähemalt 60 korda;
Tallinna Tehnikaülikool Arvutid I KAUGÕPE 2.kodutöö Jelizaveta Vavilkina Mat.nr. 124226 Rühm: IASB Ülesanne: Protsessori juhtautomaadid ja nende realiseerimine. Protsessori juhtautomaadid on mitte ainult protsessorite juhtimise algoritm , vaid iga tööpingi juhtimisi algoritm mingi kindla algoritmi järgi. Algoritmide realiseerimine toimub kristallpinna peal transistorite ja loogika elementide kaudu. Juhtautomaat koosneb: Sisendite hulk Z(f) Väljundite hulk W(y) hulk siseolekuid a(e) Üleminekute funktsiooni defineerimine a(s) = g (a(m), Z(f)) Automaatide mudelid (Mealy, Moore) Struktuurne skeem: Mealy automaadi ehitus: W(y) = Ʊ( a(m), Z(f) ) Automaadi väljund sõltub üleminuketest ja olekutest, kus ollakse algoritmi täitmisel.
Mis on andmebaasid ja mis on sql. Detailseid sql- küsimusi ei tule. Sql näidet tuleks ära tunda (et on sql keeles). 12. Nädal Eksam: lahenduvus teoreetilises ja tavamõttes, mis on lahenduvad ülesanded. Positiivsete täisarvude, positiivsete/negatiivsete ja murdarvude võimsuse võrdlemine ja tõestamine. Reaalarvude suurem võimsus kui täisarvude võimsus (Cantori teoreem): tõestuse idee. Mis on peatumisprobleem, selle lahendamatuse tõestuse idee. Keerukusest: mis on algoritmide keerukus ja mis on O-notatsioon. Mis on sorteerimise parim keerukus halvimal juhul. 13. 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.
põhimälust vahemällu ja on sealt edaspidistel vahemälu otsingutel kättesaadav. Seda nimetatakse vahemälu möödalask (cache miss). Vahemälust leitud tulemuste protsenti võrreldes päringutega nimetatakse cache tabamuse tasemeks või tabamuse koefitsiendiks. Kui vahemälu maht on piiratud, siis möödalase puhul võib olla vastu võetud otsus loobuda mõnest salvestusest vaba ruumi tekitamiseks. Väljajäetava salvestuse valikuks kasutatakse erinevaid algoritmide väljasurumiseid. Kui modifitseeritakse vahemälu andmete osasid, toimub nende ajakohastamine põhimälus. Viivitust ajas vahemälu andmete muutmise ja põhimälu uuendamise vahel kontrollib niinimetatud "kirjete poliitika". Write-through vahemälus kutsub iga muudatus esile sünkroonse andmete uuendamise põhimälus. Write-back vahemälu uuendamine toimub
hoitakse üsnagi lühikest aega. Kõik portfelli allokatsiooniotsused teeb arvuti vastavalt kvantitatiivsetele mudelitele. Tihti on nende masinate edukus sõltuvuses samaaegses võimes analüüsida inimestele hoomamatuid andmemahte. Sellest tulenevalt on ka neil arvutitel spetsiifilised algoritmid, mida tuntakse „algode“ all. Tänapäeval pole tihti enam oluline uute tuulte ega murrangute toomine algoritmide maailma, vaid et kelle arvuti suudab kõige kiiremini arvutada algoritmide tulemusi. Arvutuskiirusest tulenevalt kasutatakse ka väga erinevaid strateegiaid: 1. Market makers – kasum teenitakse täiesti tavalise ostu-müügi vahega. Lisaks pakuvad nad likviidsust oma firma klientidele, mille eest võetakse komisjonitasu. Selliseid tehinguid teevad väga kiired arvutid kasutades algoritme. [9] 2
käskude jada) esineb programmis kahes või enamas kohas. Sellega me taotleme, et programm tuleks võimalikult lühikene. Kuid see ei ole ainus põhjus. Tihti on otstarbekas jagada programm loogilisteks üksusteks parema loetavuse huvides. Kui kogu programmi pikkuseks on tuhat rida ja see kõik paikneb põhiprogrammis, siis selle programmi tekst on äärmiselt raskesti loetav. Selline loogilisteks üksusteks eraldamine käib harilikult käsikäes ülesande lahendamiseks vajalike algoritmide valimise ja kombineerimisega. Oletame, et ülesande lahendamine eeldab andmete sisestamist, töötlemist ja vastuse väljastamist. Seetõttu võiks programmi ülesehitus olla järgmine: Programm (Põhiprogramm) Andmetesisestus (see on alamprogramm) Andmetöötlus (see on alamprogramm) Väljastamine (see on alamprogramm) Lõpp (Põhiprogramm) Mis on programmitsükkel? Korduvate operatsioonide puhul kasutatakse programmeerimises tsükleid
· comp.ai.fuzzy : ilma selga teemata..
'General Knowledge Machine' (Konstantin Mgolubev)
Autor annab viite uude põnevasse andmebaasi aadressil
http://gkm-ekp.sourceforge.net
· comp.ai.games : arvutimängud..
'Maximums and balance' (Jonathan Wooldridge)
Arutelu, kas arvutimängudes peaksid mängija virtuaalsete vastaste
võimed arenema ettemääratud piiritletud kirjelduste järgi või vabalt,
piiritlemata algoritmide järgi
· comp.ai.philosophy : filosoofia
'Americans Are Now Psycho-Brainwashing' (George ?)
Minu subjektiivse arvamuse kohaselt pisut kollektivistlik, hipi-ideoloogiline
või lausa vasakäärmuslilk käsitlus maailma naftapoliitikast ning
terrorismivastasest buumist.
5.2 Võrgulehekülgede külastamine
Käsk: lynx kuvab samanimelise tekstipõhise html-sirvija abimenüü
Käsk: lynx
Delay2 clrwdt ;valveloenduri nullimine nop ;viivitus no operation nop nop nop nop nop nop nop nop nop nop nop nop nop nop nop nop nop nop decfsz Pause_tmp,1 goto Delay2 goto Delay1 end Kokkuvõte: Algoritmide joonistel ei ole programmi lõpp ühendatud ühegi elemendiga, kuna see on ainult tinglik lõpp – programm ei jõua selleni kunagi. Antud juhul oli viimases programmis kasutatud natuke pikemat moodust, et LEDid „jooksma” saada, tegelikkuses on võimalik see kood palju lühemalt ja kompaktsemalt koostada, kuid hetkel puudub teadmine kuidas kasutada Assembleris matemaatilisi funktsioone. Mõlemad programmid töötavad ja vastavad ülesande püstitusele. Programmeerimine Assembleris ei ole
JAH LÕPP Käesolevale aruandele on lisatud selle ülesande programmifail kitt.asm, mis on etteantud näidisprogrammi2 täiendatud versioon. Seadme juhtimisprogrammis on võrreldes eelnevatega üks muudatus on defineeritud ,,taimer", ,,taimer2" ja ,,taimer3" mälualad. Programmi tööpõhimõte on algoritmide plokkskeemidel esitatud. Sisenditeks on määratud registri PORTA bitid (ühendatud nupuga) ja väljunditeks registri PORTD bitid (ühendatud valgusdioodidega). Viivitamiseks antakse kolmele mälupesale (taimer, taimer2, taimer3) kindlad väärtused ja seejärel neid kahandatakse vastavalt joonisele 1.4 kuni kõigi mälupesade väärtused on jõudnud nulli. Selle protsessi ajalise kestuse arvutasin välise taktsageduse allika taktsageduse 20Mhz kaudu üheks toiminguks kulub ligikaudu 200ns
(Vikipeedia, 2014) Küberneetika aluseks on idee ühtse lähenemisviisi võimalikkusest erineva iseloomuga juhtimisprotsesside uurimisel. Selle idee jõud on selles, et ta võimaldab lisaks ühisele metodoloogialisele käsitlusele luua võimsa matemaatilise aparaadi protsesside kvantitatiivseks kirjeldamiseks ja keeruliste ülesannete lahendamiseks. See aparaat rajaneb informatsiooniteooria, dünaamiliste süsteemide teooria, algoritmide teooria ja tõenäosusteooria meetoditel. Küberneetika üheks põhiliseks iseärasuseks on see, et ta ei vaatle juhitavaid süsteeme staatilistena, vaid nende liikumises ja arengus. Süsteemide uurimine liikumises muudab põhjalikult nende käsitlust, võimaldab nii mõnigi kord avastada seaduspärasusi ja teha kindlaks fakte, mis muidu oleksid jäänud avastamata. Küberneetika ei käsitle süsteeme üksteisest isoleerituna, vaid uurib nende teatud ühendust, milleks kõige
tasuta (priivarana). 2. Mis on Linux? Linux on vabavarana levitatav (GNU alla kuuluv) ja avatud lähtekoodiga (Open Source) unixilaadne operatsioonisüsteem. Operatsioonisüsteem on kogumik põhilisi programme ja utiliite, mis on vajalikud arvuti tööks. Operatsioonisüsteemi tuumaks on kernel (programm, mis on kõige aluseks ning mis lubab käivitada teisi programme). 3. Mis on linuxi failisüsteem? Failisüsteem on andmestruktuuride, algoritmide ja tarkvara kogum, mille eesmärk on salvestusseadme peale andmete organiseeritud paigutamine, et need hiljem leitavad ja kättesaadavad oleksid. Failisüsteem määrab failide paiknemise ja struktuuri füüsilisel kettal, seab piirangud failinimedele ja nende suurustele. Failisüsteem võimaldab faile salvestada, kustutada, nimetada, organiseerida, pakkida ning määrata failidele ligipääsuõigusi. 4. Mis on distributsioon?
uurimistulemusi avaldatakse tihti raamatutena. Kõige selle põhjuseks on ilmselt just nende arvude lai rakendatavus ja üldistatavus. Nimelt põhineb suur osa looduslikest protsessidest kas eksponentfunktsioonil (ex) või siis just diskreetsetel rekurrentsetel jadadel, millistest lihtsaimaks ehk ongi Fibonacci jada. Siiski on imestamisväärne, et siiani leitakse uusi viise nende arvude rakendamiseks, nii börsi liikumiste ennustamiseks, õnnemängudes võitmiseks ning algoritmide keerukuse hindamiseks. Huvi pakuvad kindlasti ka puhtalt arvuteoreetilised tulemused, mida arvude pikast ajaloost hoolimata siiski pidevalt juurde avastatakse. Niisiis on Fibonacci arvude näol tegu vägagi unikaalse nähtusega matemaatikas. Ja kes teab, ehk see jada on vastuseks paljudele rasketele ja selgitamata küsimustele, mis tekitab universium.
Algoritmi formaalsed (matemaatilised) esitused (samaväärsed): Turingi masin, 1936-37 lambda-arvutus (Church), 1941 Posti süsteemid, 1943 Markovi algoritmid, 1951 Chomsky 0-tüüpi grammatikad, 1959 programmeerimiskeeled, Sammet, 1969 Page 4 2.2 ERNINEVAD ANDMESTRUKTUURID JA NENDE OMADUSED Abstraktne andmestruktuu- on abstraktne andmetüüp koos keerukushinnanguga vajalik algoritmide loomisel ja keerukuse hindamisel. Massiiv - Massiivi kui andmestruktuuri iseloomustavad järgmised omadused: Massiivi suurus on tavaliselt fikseeritud. Keeltes, kus massiivi suurust pärast massiivi loomist üldse muuta saab, on see üsna ajamahukas operatsioon (oluliselt ei peta ettekujutus, et selleks tehakse uus massiiv, kopeeritakse vana massiivi kõik elemendid uude ümber ja kustutatakse vana massiiv mälust ära)
negatiivne) Vale ümberpööramine: kõik A on B = kõik B on A (vale) osa A on B= osa B on A (õige) Ootuste mõju Sisulise - kõige suurem mõju on rõhutamisel. 3. Mispärast teevad inimesed Wasoni valikuülesande lahendamisel nii sageli vigu? Mis tingimustel on samalaadsete ülesannete lahendamine lihtsam? Reegli ümberpööramist ei kontrollita. Eeltingimuste täitmise kontrollimine muudab lahendamise lihtsamaks. 4. Millised on algoritmide ja heuristikute abil mõtlemise puhul kummagi plussid ja miinused? · Algoritm on protseduur, kus kõik operatsioonid, mis eesmärgi saavutamiseks on vajalikud, läbitakse samm-sammult. Algoritm garanteerib õige lahenduse leidmise, kuid selleni jõudmine võtab aega Lolli kindlad. Heuristikud on lihtsustatud mõtlemise skeemid, trikid ja rusikareegleid, mis on varem töötanud ja edule (eesmärgile) viinud. Heuristiku kasutamine ei garanteeri edu, kuid tavaliselt siiski eemärk saavutatakse
Algoritmi formaalsed (matemaatilised) esitused (samaväärsed): Turingi masin, 1936-37 lambda-arvutus (Church), 1941 Posti süsteemid, 1943 Markovi algoritmid, 1951 Chomsky 0-tüüpi grammatikad, 1959 programmeerimiskeeled, Sammet, 1969 Page 4 2.2 ERNINEVAD ANDMESTRUKTUURID JA NENDE OMADUSED Abstraktne andmestruktuu- on abstraktne andmetüüp koos keerukushinnanguga vajalik algoritmide loomisel ja keerukuse hindamisel. Massiiv - Massiivi kui andmestruktuuri iseloomustavad järgmised omadused: Massiivi suurus on tavaliselt fikseeritud. Keeltes, kus massiivi suurust pärast massiivi loomist üldse muuta saab, on see üsna ajamahukas operatsioon (oluliselt ei peta ettekujutus, et selleks tehakse uus massiiv, kopeeritakse vana massiivi kõik elemendid uude ümber ja kustutatakse vana massiiv mälust ära)
mille täitmise kontrollimine on efektiivsem kaugseire kui in situ meetodite abil. Samas annab iseseisev kaugseire võimekus Eestile võimaluse kaitsta ennast ka alusetute süüdistuste eest. Näiteks on võimalik, et rannikumere seisundi parandamise edukust hakatakse Euroopa tasemel kontrollima kaugseire meetodeid (GMES teenuseid) kasutades. See võib kaasa tuua poliitilisi komplikatsioone kui hinnangud põhinevad kaugseire algoritmide kasutamisel, mis ei sobi Läänemere oludesse. (Kutser, T. 2008) 5 4. Rannikumere kaugseire aruanded 2005. aastal teostati riikliku seireprogrammi raames uuringuid selgitamaks välja kas ja kuivõrd on erineva ruumilise ja spektraalse lahutusega satelliidid sobilikud kaardistamaks põhjataimestikku Eesti rannavetes. Esialgsetele tulemustele tuginedes julgeti väita , et kolm fütobentose rühma: pruun-, puna-, ja rohevetikad on üksteisest,
· jadatsükkel - etteantud tegevust korratakse etteantud lõpliku jada kõigi elementide jaoks · jätkamistingimusega tsükkel - etteantud tegevust korratakse niikaua, kui nn. jätkamistingimus on tõene · katkestiga tsükkel - etteantud tegevust korratakse niikaua, kuni nn. väljumistingimus muutub tõeseks Seni oleme vaadelnud korraga üht algoritmi/programmi - programming in small. Kui tekivad algoritmide/programmide kogud, mida on tarvis hallata, siis muutub meie ülesanne keerukamaks - programming in large.
Ta elas XIII ja XIV sajandi vahetusel. Tema "Arvutamise raamatus" on kuulus küülikute paljunemise ülesanne: Mitu küülikupaari tekib ühest paarist aasta jooksul, kui (1) iga paar annab ühes kuus ühe paari järeltulijaid, (2) iga uus paar saab suguküpseks ühekuuseks saamisel, (3) küülikud ei sure kunagi? Selle ülesande lahendamine viib Fibonacci arvudeni. Fibonacci arvudel on teadusajaloos tähtis koht. Muu hulgas on nad aparatuuriks algoritmide keerukuse hindamisel. Fibonacci arvude iteratiivne algoritm Fibo(n) leidmiseks: IF (N = 0) OR (N = 1) THEN Fibo := N Eelmine := 0 Järgmine := 1 FOR I := 2 TO N Abi := Eelmine Eelmine := Järgmine Järgmine := Abi + Eelmine END FOR Fibo := Järgmine Rekursiivne definitsioon: ¦ n, kui n = 0 vôi n = 1 Fibo(n) = ¦ Fibo(n - 2) + Fibo(n - 1), kui n > 1 Protsess n = 5 puhul: F5 = F3 + F4 = F1 + F2 + F4 = ...............
praktilised). Algoritmi formaalsed (matemaatilised) esitused (samaväärsed): Turingi masin, 1936-37 lambda-arvutus (Church), 1941 Posti süsteemid, 1943 Markovi algoritmid, 1951 Page 4 Chomsky 0-tüüpi grammatikad, 1959 programmeerimiskeeled, Sammet, 1969 2.2 Erinevad andmestruktuurid ja nende omadused Abstraktne andmestruktuu- on abstraktne andmetüüp koos keerukushinnanguga vajalik algoritmide loomisel ja keerukuse hindamisel. Massiiv - Massiivi kui andmestruktuuri iseloomustavad järgmised omadused: Massiivi suurus on tavaliselt fikseeritud. Keeltes, kus massiivi suurust pärast massiivi loomist üldse muuta saab, on see üsna ajamahukas operatsioon (oluliselt ei peta ettekujutus, et selleks tehakse uus massiiv, kopeeritakse vana massiivi kõik elemendid uude ümber ja kustutatakse vana massiiv mälust ära). Paljudes
lehepinnaindeksi hindamist. Hoolimata tänapäevase kaugseire mitmesugustest võimalustest saada metsade takseerkirjeldusi nii tabelitena kui ka kaartidena, ei tähenda see, et vajadus metsataksaatorite järele kaob. Pigem vastupidi: kuigi kosmosepilte või 3D-punktiparvi saab lihtsasti teisendada metsade takseerkirjeldusteks, siis on alati vajalik protseduuri sisendis kasutada kvaliteetseid metsa struktuuriandmeid mudelite koostamiseks või algoritmide õpetamiseks. 10 Kasutatud kirjandus Heritage, G.L., Large, A.R.G. 2009. Principles of 3D Laser Scanning – Laser Scanning for the Environmental Sciences, 21-34. Holmgren, J., Persson, A. 2004. Identifying species of individual trees using airborne laser scanner - Remote Sensing of the Environment 90, 415–423. Korhonen, L., Korpela, I., Heiskanen, J., Maltamo, M. 2011. Airborne discrete- return
7 5.2 2016.aasta olulisemad uuringud ja arendusvaldkonnad Uttegaasist bensiinifraktsiooni regenereerimise projekt - modelleerimine ja tasuvusanalüüsi täpsustamine; Petroter seadmete töökindluse tõstmine; Petroter seadmete põlevkivi ümbertöötlemisvõime ja netoõlisaagise tõstmine; Varahalduse juurutamine; Matemaatilise mudeli ja tootmise optimeerimise algoritmide täiustamine; MARPOL merekütuse kvaliteedinõuete muutumise mõjuanalüüs, kohandumise strateegia. 5.3 Reklaam VKG Grupp tegeleb nii palju heategevuse ja ürituste korraldamisega, et reklaami sellele ettevõtele küll pole vaja. VKG põhitähelepanu on suunatud regioonile, kus ta tegutseb. Nii räägivad oma ettevõtte kohta VKG Gruppi töötajad: “Meie toetustegevus laieneb eelkõige Kohtla-Järve linna ja ümberkaudsetes
indirectly. That is, the subroutine is used in its own definition. Important to check that recursion terminates. Code should contain: One or more base cases (no recursion involved!) One or more recursive cases. Arguments of the recursive call must be "simpler" according to some measure. NB! The "simplicity" measure may be arbitrarily complex. Imperatiivsed keeled sobivad samm-sammult, kindlas järjekorras täidetavate algoritmide esitamiseks. Programmid kujutavad endast arvutile antavate käskude jada. Tuntumad imperatiivsed keeled on C, Basic, Pascal, Java, objektorienteeritud keeled ja assemblerkeeled. Imperatiivsete keelte peamiseks eeliseks on arvuti tegevuse täpse kontrollimise ja suunamise võimaldamine, mis enamasti tagab maksimaalse töökiiruse. Miinusteks on programmeerimise suur töömahukus - lahenduskäigu kõik detailid tuleb süsteemile esitada - ning suured
toimuvad üheaegselt. Sekveneerimisprotsess on muudetud kiiremaks, odavamaks ja täpsemaks. Pärast genoomi sekveneerimist on järgmiseks etapiks koostute (assembly) ülesehitamine. Kui genoomi sekveneerimine andis informatsiooni nukleotiidse järjestuste kohta, siis koostute arvutiprogrammid proovivad rekonstrueerida erinevaid pikemaid biopolümeeride järjestusi kasutades selleks sekveneeritud järjestuste joondamist mitmesuguste algoritmide alusel. Assemblerid tööpõhimõte eeldab, et kui kahel lugemil esineb nukleotiidiline ühisosa, siis pärinevad nad tõenäoliselt genoomi samast kromosoomi piirkonnast. Kui selline kattuvus on tuvastatud, siis joondab programm lugemid vastavalt kontiigideks. Kontiig ehk piirnevaid järjestusi moodustavad komplekt ülekattuvaid DNA segmente (lugemid), mis üheskoos moodustavad ühe DNA regiooni konsensuspiirkonna.
dokumentatsiooni osadest. Kitsamalt peetakse tehnilise dokumentatsiooni all silmas dokumente, mis on abiks süsteemi hooldamisel, töös ja ajakohasena hoidmisel (nt kuidas installeerida uuendusi). Dokument kirjeldab tarkvarasüsteemi ülesehitust (koodi ja muude failide loetelu). Võimalik on ka kommenteeritud lähtekood. Seega võib osa tehnilisest dokumentatsioonist paikneda tarkvara enda sees. Lisaks veel andmestruktuuride ja keerulisemate algoritmide kirjeldused, Dokumentatsioon võib sisaldada mitmeid jooniseid, mida saab näiteks esitada modelleerimiskeeles UML. Tehnilise dokumentatsiooni koostamisel võib olla abi spetsiaalsetest dokumendigeneraatoritest. Näiteks oskab selline generaator kokku korjata kõigi moodulis olevate funktsioonide päised ning päisele järgnevad kommentaarid ning moodustada sellest eraldi dokumendi. Ja ongi olemas dokumenteeritud ülevaade sellest, mida moodul sisaldab ja mida selles
Teine võimalus on kasutada kokkuleppelise koodi loomisel krüptograafilisi võtteid. Krüptograafia on IT maailmas üheks peamiseks tööriistaks, mis tagab andmete kaitsmise. Muuhulgas pakub krüptograafia niiöelda ühesuunalise funktsiooni teenust. Lühidalt seisneb põhimõte selles, et näiteks suurus A ja B, kus suurusest A saab suurust B arvutada, kuid B põhjal A leidmine ehk taastamine on praktikas võimatu. Ehk see põhimõtteliselt võimaldab nimest ja isikukoodist kindlate algoritmide abil leida kokkuleppelise koodi, aga seda koodi ei saa tagasi nimeks ega isikukoodiks arvutada. Teele Vits Ühesuunaline 14bfhK847gjdW578 funktsioon 49102066034 jshh6790GLW23dfp IT maailmas on mõlemad eeltoodud variandid teoreetiliselt lahendatavad. Nende praktiline lahendatavus sõltub huvigruppide tahtest säärased IT-teenused üles ehitada. Isikuandmete töötlemine
2 n
1 3 1
et - iga n>=1 korral siis valime C2 suurema arvu kui ½
2 n 2
1 3 1
et - iga n>=1 korral siis valime C1 väiksema arvu kui 1/4
2 n 4
Näiteks C1=1/8 ja C2=1 on täiesti sobivad.
tähistus- kasutatakse alumise piiri korral
Etteantud funktsiooni g(n) korral tähistame f(n)= ( g( n )) , kui funktsioonid f ja g
täidavad tingimusi (s.t. leiduvad sellised C1 ning N)
C1 g ( n ) f ( n ) kõigi n>=N korral
Ül 419.
2.2. Mõnede lihtsate algoritmide koostamine
Otsingu algoritmid
Lineaarne otsing
Probleemi püstitus: Otsime massiivist etteantud arvuga võrdset elementi. Etteantud
elementi võrreldakse järjest kõigi massiivi elementidega kuni leitakse võrdsus.
Tagastatakse vastava massiivi elemendi indeks või siis 1, kui massiivis pole vastavat
elementi. Skeemprogramm tsükli realiseerimiseks (mitte kogu lahenduse) on:
* i=0,1..N-1
x=a[i]?
vastav C++ kood:
for (i=0; i
nähtavat seost, seega pole meil strateegiat ning me ei saa sellega hästi hakkama. Mõlemate tõlgenduste kohaselt sõltub arutluse käik mentaalsetest representatsioonidest, mille üle arutleme. Lisaks rõhuavad mõlemad pragmaatilisi kaalutlusi- ühel juhul on tarvis õigesti arutleda valetamise ja petmise puhul (Wason), teisel aga lubamise ja kohustamise puhul (lihtsustatud). 4. Millised on algoritmide ja heuristikute abil mõtlemise puhul kummagi plussid ja miinused? Kas inimesed ja arvutid lahendavad probleeme sarnaselt? Newell & Simon (1972) eristasid 2 probleemilahendusstrateegi : Heuristikud ja Algoritmid. Algoritm on protseduur, kus kõik operatsioonid, mis eesmärgi saavutamiseks on vajalikud, läbitakse samm-sammult. Algoritm garanteerib õige lahenduse leidmise, kuid selleni jõudmine võtab aega.
RAKENDUSSTATISTIKA ARVUTUSGRAAFILINE TÖÖ Osa A Valim A mahuga N=25 variatsioonirida: 1 2 17 81 97 75 22 21 94 62 81 73 74 52 79 45 14 70 2 71 48 79 77 39 19 1. Leida keskväärtuse, dispersiooni, standardhälbe, mediaani ja haarde hinnangud. Keskväärtus: = 51,8 Dispersioon: s x² = 968,58 Standardhälve: s x = 31,12 Mediaan: Mediaan on variatsioonirea keskmine element paarituarvulise valimi korral või kahe keskmise elemendi poolsumma paarisarvulise valimi korral. Me = 62 Haare: R = 91 – 1 = 96 2. Leida keskväärtuse ja dispersiooni usaldusvahemikud (eeldades üldkogumi normaaljaotust ning võttes olulisuse nivooks α = 0.10). Kes...
PROGRAMMEERIMISE MÕISTED ALGORITM on täpne ja üheseltmõistetav eeskiri mingi ülesande lahendamiseks. Algoritmi esitusviisid: Pseudokoodis, kus kasutatakse programmeerimiskeele võtmesõnu, lauseid. Graafiliselt - blokk-skeemid. PROGRAMMEERIMISKEEL on tehiskeel algoritmide kirjapanekuks arvutitele "arusaadaval" kujul. Programmeerimiskeeles kirja pandud algoritmi nimetatakse PROGRAMMIKS või, kui veelgi täpsem olla, PROGRAMMI TEKSTIKS. Programmeerimiskeele süntaks on range eeskiri, mis sätestab väga üksikasjalikult, kuidas tohib programmi kirja panna nii, et see oleks arvuti poolt vastuvõetav. Vastasel juhul on tekstis süntaksivead. Programmi süntaks võib olla õige, kuid sellegipoolest see programm ei tööta arvutis nii, nagu soovisime. Siis on
M-i sisendiks. Siis M-i väljund on A karakteristlik funktsioon. Teoreem: KV grammatikate ühesuse probleem pole lahenduv. T: selle saab redutseerida Posti vastavuse probleemile. Oletame, et grammatika G on ühene. Keel L (G) on kahe ühese keele La (G) ja Lb (G) ühend. Kui L(G) pole ühene, siis sõnedel, mis kuuluvad La ja Lb ühisossa, on kaks erinevat tuletuspuud (vasaktuletust). Kas aga neil keeltel on ühisosa? See on Posti vastavuse probleem, mis pole lahenduv. 28 Algoritmide keerukuse hindamine. Algoritmi keerukuse sõltuvus arvutamismudelist. DEF: Algoritmi keerukus on funktsioon f : N → N, mis seab sisendandmete mahule n vastavusse algoritmi sammude arvu (ajaline keerukus) või kasutatava mälu mahu (mahuline keerukus). ajaline keerukus – taktide / konfiguratsioonide arv; mahuline keerukus – kasutatud lindipositsioonide arv. Teoreem: Olgu t(n) > n. Iga mitme lindiga Turingi masinal ajalise keerukusega O(t(n)) töötava programmi
Krüptoprotseduuri valik jaguneb kahe järgneva ülesande vahel: - krüptograafilise algoritmi väljavalimine ning - tehniliste lahenduste väljavalimine. Enne kui kasutaja seob ennast ühe või teise protseduuriga, peaks tal olema täpne ettekujutus sellest, millised on tema nõuded töödeldavate andmete konfidentsiaalsusele ja autentsusele igas informatsiooni töötleva süsteemi ,,punktis". Krüptograafiliste algoritmide valimine Krüptograafiliste algoritmide valimisel tuleb esmalt selgeks teha, milliseid krüptograafilisi protseduure soovitakse kasutada, ehk siis kas sümmeetrilisi, asümmeetrilisi või hübriidprotseduure ning seejärel tuleb langetada valik sobiva, st vastava mehhanismitugevusega algoritmi kasuks. Krüpteerimisprotseduur - Sümmeetriline krüpteerimine: sümmeetriliste protseduuride eelised ja puudused on kokku kogutud meetmesse M 3
sum = sum + i; (internetis) ja (XML) keeltevahelisi seoseid. Soovitav tulemus: saab teha tarkvara, mille abil XML-datat saab ühest return sum; programmist teise saata, nii et info kaduma ei lähe. } Imperatiivsed keeled sobivad samm-sammult, kindlas järjekorras täidetavate algoritmide esitamiseks. Programmid kujutavad endast arvutile antavate käskude jada. Tuntumad imperatiivsed keeled on C, Basic, Pascal, Java, Modula-2 objektorienteeritud keeled ja assemblerkeeled. Imperatiivsete keelte peamiseks eeliseks on arvuti tegevuse täpse
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
läheb ja kummale poole pea liigub. · Töö lõpeb, kui masin siirdub passiivsesse seisundisse q0 või kui täitmisjärg jõuab tühja lahtrisse. Turingi masina omadused: · Vastab hästi meie intuitiivsele arusaamale algoritmist. · Lihtsuse ja elementaarsuse tõttu võib tabel olla üsna mahukas, kuid praktilise kasutatavusega seotud küsimused on antud juhul teisejärgulised. · Samas on hõlpus tõestada Turingi masinate kohta üldisi teoreeme, mh algoritmide mitteleidumist. · Taktide arv sobib hästi algoritmi keerukuse mõõduks. Arvude ja arvujärjendite esitamine lindil: Turingi masinate kompositsioon ja hargnemine. Definitsioon 3. Turingi masinat M nim masinate M1 ja M2 konpositsiooniks, kui iga algkonfiguratsiooni X korral kehtib võrdus M(X)=M2(M1(X)) 6 Teoreem 1
pääsemata ligi kaitsmist vajavatele andmetele Praktikas tegelvad sellega küll kitsa eriharidusega inimesed-krüptoloogid-, kes on reeglina eriteadmistega matemaatikud Kaasaja krüptograafia kasutab eranditult matemaatikute (krüptograafide) poolt koostatud tüüpalgoritme,ise oma kasutamiseks välja töötatavad unikaalsed algoritmid on ajalugu Nende algoritmide koostamine krüptograafia (matemaatika) alaseid eriteadmisi Mida kauem on krüptoalgoritm avalikus kasutuses olnud, seda väiksem on tõenäosus, et tal leidub efektiivseid murdmisvõtteid. Kaasaja krüptograafia kasutab eranditult arvutustehnikat, käsitsi paberil arvutamine on jäädavalt ajalugu Krüptoanalüüil on oluline tehete kiirus: aruvit taktsagedus GHZ-des, käsitsi arvutamisel heal juhul mõni Hz
Soovitav tulemus: saab teha tarkvara, mille abil XMl-datat saab 0hest 1950 - ERA ll0l ) proqrammist leise saala, hii et info kaduma ei ldhe. I Modula-2 lmperatiivsd keeled sobivad sammammult, kindlas jerjekorras taidetavate algoritmide esitamiseks. Programmid PROCEDURE *mto(n:INTEGER):INTEGER; l95t - uNIvAc I kujutavad endast arvutile aniavate keskude Jada
Platvorm? (Platvorm mis? Saapad? Käi mööda mu selga nendega) Liidesed Liidesed olemasolevate süsteemidega Kasutatavad/toetatavad protokollid Toimimine (Operation) Kes juhib töötavat süsteemi? Pakendamine (Packaging) Kes installeerib süsteemi? Erinevate installeerimiste arv? Juriidika (Legal) Litsensid? Vastutuse küsimused? Litsensitasud või kohustused, mis tulenevad kolmandate osapoolte komponentide või algoritmide kasutamisest? Nõuded omavad seoseid: Funktsionaalne - mittefunktsionaalne Vastuolu seos Sisalduvusseos Hästidefineeritud nõue on (SWEBOK, SE2004 järgi (tra mart ei pane enam mingi keerulise triipkoodiga küsimust)) - korrektne, täielik, selge, kooskõlaline, verifitseeritav, jälgitav, tostatav, modulaarne, disainist sõltumatu 7. Elementaarne äriprotsess Nõuete analüüsis konkreetse arvutirakenduse jaoks keskenda use case-id elementaarsete
Tõendab, et sõnum pärineb sõnumi saatjalt ja ei ole muudetud. Vajalik on kolmas osapool, mis väljastab ja verifitseerib digitaalseid sertifikaate. 28. Nimeta erinevaid andmeallikaid organisatsioonis. - Organisatsiooni dokumendid, andmebaasid, töötajate arvamused,avalikud andmebaasid, lingid. blogid, pildid, videod, märkmed. 29. Kirjelda traditsioonilist failisüsteemi. Millised probleemid on traditsioonilisele failisüsteemile omased? - Failisüsteem on andmestruktuuride, algoritmide ja tarkvara kogum, mille eesmärk on salvestusseadme peale andmete organiseeritud paigutamine, et need hiljem leitavad ja kättesaadavad oleksid. Probleemid: informatsiooni keeruline või võimatu erinevate valdkondade vahel vahetada; nimed, aadressid muutuvad, tegevusalad muutuvad; andmekandjad vananevad,erinevad riigiti ja muutuvad ajas. 30. Mis on ja kuidas seostuvad bitt, bait, väli, kirje, tabel ja andmebaas? - Bitt väikseim andmeühik
Eelkontrolliga kordus Harjutused "Auto_3" ja "Autod_4". Iseseisvalt Fuktsioonide nullkohad. Iseseisvalt Do...Loop- kordused. Demod For ... Next-lause Funktsiooni värtuste keskmise ja maksimumi leidmine Lahtrite värvid. Demo For...Each-lause Harjutus "Ufod" Rakendus "Ufod". Iseseisvalt Lahtriploki keskmised Protsesside modelleerimisest algoritmid protsesside juhtimine Programmeerimine - protsesside modelleerimine Peamine pole keel, vaid protsesside mudelite ja algoritmide loomine Protsesside liigid Järjestikune protsess ehk jada tegevus_1 tegevus_2 tegevus_1 tegevus_2 ... tegevus_n ... Paralleelne protsess
automatiseeritud andmete sisestamiseks ja vigade leidmiseks, andmete arendustööks, andmete ühildamiseks, keerukateks analüüsideks ja keeruliste andmete kuvamiseks ning kaardi komponeerimiseks. Saadaval on ka programmeerimiskeeled koos programmeerimistööriistadega, mis võimaldavad spetsiifilisi laiendusi lisada ise tehtud programmidele, ning programmi teegid lubamaks GeoMedia algoritmide modifitseerimist eri- eesmärkidega tarkvara loomiseks. GeoMedia on eriti võimekas integreerimaks andmeid erinevatest allikatest, formaatidest ning platvormidelt. Tundub, et Integraph on suuresti pühendanud OpenGIS algatusele, komplekt standardeid hõlbustamaks platvormide- ja tarkvara vahelist andmete jagamist. Ükskõik millises tavalises kommerts andmebaasis olevat infot saab integreerida erineva vorminguga ruumiandmetega. Kombineerida võib ka pilt kujutisi, koordinaate ja tekst andmeid
Seoses esmärkidega on tekkinud üks küsimus. Kuidas saab tagada seda, et õpilanetunneksendoma pere liikmena, oma klassi õpilasena? Seda on raske saavutada. See on ideaal. 3.3. Õppe- ja kasvatuse rõhuasetused 3.5. klassis 3.3.1. Õpilaste juhtivaks tunnetusprotsessiks on mälu, hakkab kujunema sisekõne, areneb elementaarne verbaalne mõtlemine. Sisekõne kujunemine võimaldab arendada õpitegevuse kavandamist-reguleerimist: orienteerumine ülesandes, planeerimine, algoritmide valik ja kasutamine, enesekontroll. Õpioskuste seisukohalt on oluline õppeülesannete teadvustamine, st oma tegevuse refleksioon. 3.3.2. Põhitaotluseks on kujundada õpilase roll ja õpioskused, häälestada õpilast suhtuma õppimisse positiivselt. 3.3.3. Õppekavaterviku kujundamise aluseks on suhted MINA/MEIE/KODUKOHT (paikkond). 3.3.4. Lugemine, kirjutamine, arvutamine, orienteerumine tekstis ja tekstiloome, vaatlus- ning võrdlusoskus jne omandatakse tasemel, mis võimaldab neid hiljem
Eelkontrolliga kordus Harjutused "Auto_3" ja "Autod_4". Iseseisvalt Fuktsioonide nullkohad. Iseseisvalt Do…Loop- kordused. Demod For ... Next-lause Funktsiooni värtuste keskmise ja maksimumi leidmine Lahtrite värvid. Demo For…Each-lause Harjutus "Ufod" Rakendus "Ufod". Iseseisvalt Lahtriploki keskmised Protsesside modelleerimisest algoritmid protsesside juhtimine Programmeerimine - protsesside modelleerimine Peamine pole keel, vaid protsesside mudelite ja algoritmide loomine Protsesside liigid tegevus_1 Järjestikune protsess ehk jada Jada tegevus_2 tegevus_1 tegevus_2 ... tegevus_n ...
Eelkontrolliga kordus Harjutused "Auto_3" ja "Autod_4". Iseseisvalt Fuktsioonide nullkohad. Iseseisvalt Do...Loop- kordused. Demod For ... Next-lause Funktsiooni värtuste keskmise ja maksimumi leidmine Lahtrite värvid. Demo For...Each-lause Harjutus "Ufod" Rakendus "Ufod". Iseseisvalt Lahtriploki keskmised Protsesside modelleerimisest algoritmid protsesside juhtimine Programmeerimine - protsesside modelleerimine Peamine pole keel, vaid protsesside mudelite ja algoritmide loomine Protsesside liigid tegevus_1 Järjestikune protsess ehk jada Jada tegevus_2 tegevus_1 tegevus_2 ... tegevus_n ...
Mis on peatumisprobleem, selle lahendamatuse tõestuse idee. - Olgu ülesandeks tuvastada, kas täisarv X kuulub mingisse lõpmatusse täisarvude alamhulka H. paneme X-le vastava programmi käima ja kui ta peatub, siis loomulikult teame, et ta kuulub hulka H. Kui ta aga ei peatu, siis meil ei ole kindlat viisi aru saada, et ta ei kuulu hulka H. Peatumisprobleem on poollahenduv. Keerukusest: mis on algoritmide Eksamkeerukus - Algoritmi keerukus on põhioperatsiooni(de) arvu sõltvusfunktsioon K(n) sisendi(te) suurusest n O-notatsioon. Annab keerukusklassi – millise proportsiooniga suureneb arvutusaeg sõltuvalt sisendi suuruse muutusest Mis on sorteerimise Eksamparim Eksamkeerukus Eksamhalvimal Eksamjuhul. - O(n2) 11 Eksamiks: umbes kuipalju Eksamon Eksamneuroneid Eksamc-elegansil ja inimesel (suurusjärgud) – c-elegans 302 neurons, inimene
GEOINFOSÜSTEEMID Eksamiteemad kaardiraam - kaarti piirav vormikohane joonestik, mille matemaatiliseks tähenduseks on kaardi koordinaatvälja piiramine; vormiliselt kasutatakse kaardiraami ka koordinaatide tähistamiseks. Kartograafiline projektsioon - matemaatiline algoritmide süsteem, mille abil kantakse kumera pöördellipsoidi pinnalt geograafilised koordinaadid tasapinnale. Aluseks on seega ellipsoid, mis määrab ära kõik muu. Hetkel kasutatavad tuntumad ellipsoidid: WGS 84 - World Geodetic System 1984 - sellel tugineb GPS ja kasutatakse üsna laialt (varasemad näiteks NAD27 jm) GRS 80 - Geodetic Reference System 1980 - sellel põhinevad enamus suuremõõtkavalisi Eesti kaarte (viimasest ajast)
annaabi.ee 
