Ahne algoritm – sobilik optimeerimisülesanneteks, kergem koostada & kiirem kui DP algoritm, ei anna alati tulemuseks optimaalset vastust, vastuse optimaalsust raske tõestada. Sobib kui kõige optimaalsemat vastust polegi vaja & kindlasti siis, kui alamülesannete optimaalsed lahendused annavad tulemuseks kogu probleemi optimaalse lahenduse. Kudos who wrote it!(+1)+1 3. Andmestruktuur. Loogiline tase. Realisatsiooni tase. Andmestruktuur näitab, kuidas paiknevad programmi töö ajal mälus hoitavad andmed. Lihtsaim viis – massiiv ehk tabel (füüsiline struktuur). Loogiline struktuur on andmete jada, elemendid on järjestatud. Keerulisemad struktuurid on kahe- ja mitmemõõtmelised massiivid, kirjed jne. Loogiline tase – kirjeldab struktuuri loogilist ülesehitust. Esitamiseks sobivad kastid & nooled. Operatsiooni selgitamiseks pseudokood.
GIS Teemakaardid 2009 GEOINFOSÜSTEEM Automatiseeritud süsteem geograafilise ruumiga seotud andmete kogumiseks, haldamiseks, säilitamiseks, päringute tegemiseks, analüüsiks ja esituseks. Vaatenurgast GIS-ile sõltub, milliseid võimalusi tema juures oluliseks peetakse Kartograafiline vaatenurk - kaardid Andmebaasilik vaatenurk andmestruktuur- ja baasid Analüütiline vaatenurk ruumiline analüüs TEEMAKAARDID · Kaart maapinna või muu taevakeha üldistatud ja leppemärkidega seletatud matemaatiliselt määratletud vähendatud kujutis. · Kaardiga on keerulist geograafilist sõnumit lihtsam edasi anda kui sõnade või tabelite abil. · Õnnestunud ja kvaliteetne kaart on ise sõnumi kandja ning vajab väga vähe teksti sõnumi täpsustamiseks. TEEMAKAARDID · Teemakaartide kvaliteedinäitajad:
· PostScript-i keel on saanud 2 suurt uuendust, mida eristatakse levelite abil. · 1984 - algne PostScript ehk PostScript Level 1 · 1991 - PostScript Level 2 Parandatud oli kiirust, JPEG lisamist otse PostScript-i, dokumendi osade kordamist. · 1997 - PostScript Level 3 Parandatud oli värvide käsitlust, vea käsitlust, programmi sisu filtreid (pakkimine, formaatide tõlgendamine jms), programmi ülesehitust. Programmeerimiskeel · PostScript on pinu (andmestruktuur, millest loetakse esimesena viimati sisestatu) põhine süsteem. Tavaliselt kirjutavad PostScript programme teised programmid ja mitte inimene. · PostScripti suudavad interpreteerida GhostScript, Acrobat Distiller. Prepressis kasutatakse Acrobat Distillerit. POSTCRIPTFAIL · Postcriptfail on selline fail, mis on genereeritud läbi postcript programeerimiskeele ning see on tehtud selleks, et muutmata kujul saata vajalik dokument printerisse. Laser-, filmi- või
Mõlemat pidi võib. Praegu lisame lihtsalt 61-le viide 37-le, kõik muu jääb paika. Väga lihtne. Füüsiliselt midagi ei liiguta. Mõningaid operatsioone puudel keeruline läbi viia, kuna viidad on alati vaid ühes suunas ülalt alla. Viidad on ainult emadelt tütardele. On olemas ka teistsugune puu läbiõmmeldud puu kuid sellega töötamine on äärmiselt tülikas, kuna iga kord tuleb muuta mitte 1 viita, vaid mitut. Probleem - Mõnus andmestruktuur nt andmebaasi esitamiseks, aga kui tahan saada mingeid andmeid paberil, siis seda puud ikka trükkima ei hakka. Puu läbi käimine - Me peame leidma algoritmid, millega külastatakse puu iga tippu, ükski tipp ei jää vahele ja ühtki tippu ei külastata rohkem kui üks kord. Nt kui tahame puud nimekirja kujul saada. 4 strateegiat. 1) Nivooti probleem selles, et väga raske läbi viia, kuna viidad on meil ainult ülalt alla, aga vasakult paremale puuduvad
Kompileerimine: võtab sisendiks kõrgkeelse programmi ja tõlgib selle täitmisprogrammiks. Kompileeritud täitmisprogrammi saab edaspidi iseseisvalt käivitada, vajamata seal juures keelevahendeid Interpreteerimine: loeb programmi lähtekoodi rida haaval, tõlgib rea kohe masinkoodi ning seejärel täidab String: tähemärkidest koosnev järjestikune jada Massiivid: jada ühetüübilisi väärtusi puud: andmestruktuur Lihtsad andmetüübid: int - täisarv, float - ujukomaarv 7. Nädal Eksamiks:, parsimine, jit, vahekood, programmeerimiskeeled vs kirjelduskeeled, json, html, sql, keelte äratundmine (fortran, cobol, lisp, C, modula/pascal, python). Mis on data warehouse. LISP: FORTRAN: COBOL: C: MODULA2: PYTHON: 8. Nädal
tüüpe. 4. Polümorfism on tehnika, mille puhul on võimalik kasutada sama koodi ja funktsioone erinevate andmetüüpidega, mille tulemuseks on üldisemad ning abstraktsemad implementatsioonid. Kuidas saab liigitada · parameetriline polümorfism, ad-hoc-polümorfism · kompileerimisaegne polümorfism, käivitamisaegne polümorfism Kas üledefineerimine on polümorfismi avaldus? List · Andmestruktuur, milles andmed on kindlas järjekorras. · Saab: 1. elemendi võtta - get 2. elemendi lisada - add 3. elemendi eemaldada - remove · Saab mitut moodi realiseerida, näiteks klassidest ArrayList, LinkedList import java.util.*; import java.util.*; public class Listinäide { public class Listinäide { public static void public static void
pikema elueaga GISi komponent. Loeng 2 Andmemudelid, andmeallikad geoinformaatikas. Andmeallikad geoinformaatikas · Olemasolevad kaardid/andmekogud · Mõõtmine: maa peal (geodeetiline, topgraafiline maamõõtmine), kaugseire (vaatamine ülevalt foto, skanneerimine, aero, satelliit). Andmemudelid · Vektor- ja rasterkuju · Objektorienteeritud mudel · TIN Raster- ja vektroandmete võrdlus Parameeter Raster Vektor Andmestruktuur Enamasti lihtne Tavaliselt kompleksne Andmemaht Enamasti suur (pakkimata) Enamasti väike Koordinaatide teisendus Aeglane, võib vajada Lihtne ümberpakendamist Analüüs Lihtne, lubab kihte Võrgustikul eelistatav, mujal kombineerida keerukam
• Cachemälu kasutamine on efektiivsem 2.3.3 Nõrgad küljed: • Tugevate külgede vastandid 2.3.4 Näide kasutamisest: • Kiirsorteerimine ja mestimisega sorteerimine. Mõlemad algoritmid on rekursiivsed ja jaotavad mingi skeemi järgi kogu ülesannet tükkideks, et need sorteerida ja hiljem osad ühendada. • Jaga ja valitse tüüpi strateegiat kasutavad ka otsimiskahendpuu ja kahendotsimise algoritmis. 3. Andmestruktuur. Andmestruktuuri loogiline tase ja realisatsiooni tase. 3.1 Andmestruktuur • Andmete talletamise ja organiseerimise viis • Vahend suure hulga andmete organiseerimiseks ja salvestamiseks arvutis ning neile efektiivse juurdepääsu tagamiseks • Andmestruktuurid jaotuvad üldise ülesehituse järgi: lineaarsed ja mittelineaarsed. Nad tuginevad arvuti võimetele salvestada ja võtta andmeid mälust aadressi järgi.
suurema lisatööta andmelaadurites. Andmeladu ettevõttes tähendab reeglina erinevate andmelettide (data mart) kogumit. Iga andmelett teenindab teatavat üksust või teatavat juhtimisvaldkonda. Sageli tekkib küsimus, et mis on ikkagi andmelao loomise eesmärk, et võtta andmed ühest andmebaasist ja panna nad teise andmebaasi ? Olulisteks erinevused relatsioonilise andmebaasi ning andmelao vahel on järgmised: 1. Andmelao andmestruktuur on täht-kujuline (star-schema), kus on alati olemas üks nn.faktitabel ehk tehingute register. Selline andmestruktuur garanteerib andmete analüüsil kõigi uuritavate objektide (dimensioonide) omavahelise seostatavuse, sest kõik dimensioonid on omavahel seotud läbi ühise faktitabeli. Näitena olgu meil tegemist ühe hulgifirma müügiandmetega. Andmelao struktuur sellisel puhul näeks välja nii, et meil
lugeda ja kirjutada. NTFS uuendused[11] võrreldes FATga on maksimaalne failinimi kuni 255 tähemärki (salvestatakse UTF-16 kodeeringus), journaling (muudatuste logi, mille abil saab andmekao ohtu oluliselt vähendada), laiendatud failiattribuudid, sisseehitatud failide pakkimise võimalus, kvoodid (kettaruumi jaotamine kasutajate vahel) ning faili-, ja partitsioonisuuruse piirangute kaotamine (piir on 16EB). Kuna NTFS-i kataloogi struktuuri aluseks on efektiivne andmestruktuur – binomiaalpuu, siis failide otsimisaeg ei sôltu lineaarselt nende arvust. Kataloogi struktuuri keerukus ja failide arv kataloogis ei piira samuti töö kiirust. Normaalseks tööks nôuab NTFS vähemalt 64MB operatiivmälu. Samas pidurdavad töökiirust aeglased kettad ja ilma Bus Mastering’ta kontrollerid. Nii nagu Microsoft alguses plaanis FAT-i DOS-i jaoks (mis väljus aga selle operatsioonisüsteemi piirest), nii valmistati ka NTFS tegelikult Windows NT- le
ttu.ee), siis tuleb kõigepealt leida sellenimelise masina IP aadress. DNS serverid: serverid, mis sisaldavad "nimi<->IP aadress" tabeleid ja vastavad päringutele "anna selle nime IP aadress": XML tähendab - eXtensible Markup Language Struktureeritud teksti esitamise formaat XML standard ütleb, kuidas teksti struktuuri märgistada. Saab kasutada andmete esitamiseks tekstina JSON - Javascript Object Notation Andmete esitamise formaat tekstina Javascripti programmeerimiskeele ,,native" andmestruktuur Väga lihtne ja mugav kasutada Kaasajal brauserirakendustes eelistatum kui XML XHTML: Praktiliselt seesama, mis HTML (samad tagid jne) Tagid peavad olema väikeste tähtedega Peab olema korrektses XML süntaksis (tagi suletud jne) Paar XML-i lisaknihvi ka (namespaced jne) Recursion A subroutine is said to be recursive if it calls itself, either directly or indirectly. That is, the subroutine is used in its own definition. Important to check that recursion terminates
Andmed saab salvestada Vali üks: a. olemisse b. andmebaasi c. faili ja andmebaasi d. olemisse ja faili e. faili Küsimus 13 Füüsiline andmemudel tuletatakse peamiselt (ja ainult) loogilisest andmemudelist Vali üks: Tõene Väär Küsimus 14 Atribuut, mille väärtus on unikaalne ja mis üheselt eristab antud kirje teiste samasuguste kirjete hulgas saab nimetada Vali üks: a. Primary key b. Join attribute c. Secondary key d. Recursive key e. Data Marker Küsimus 15 Andmestruktuur, milles on korduvaid andmeelementide arv on viidud miinimumine nimetakse Vali üks: a. järjestikult struktureerituks (sequentially organized) b. hästi struktureerituks (well-struktured) c. füüsiliseks failiks d. mittenormaliseerituks (denormalized) Küsimus 16 Kui tabelis iga mitte-peavõti sõltub alati kogu peavõtmest (kui peavõti koosneb mitmest väljast), siis tegemist on Vali üks: a. mitte-normaalkujuga b. teise normaalkujuga c. esimese normaalkujuga d. kolmanda normaalkujuga
avada serveri urli 18 XML eXtensible Markup Language Struktureeritud teksti esitamise formaat XML standard ütleb, kuidas teksti struktuuri märgistada. Saab kasutada andmete esitamiseks tekstina Lihtne, aga veidi kohmakas kasutada EI OLE PROGRAMMEERIMISKEEL JSON Javascript Object Notation Andmete esitamise formaat tekstina Javascripti programmeerimiskeele ,,native" andmestruktuur Väga lihtne ja mugav kasutada Kaasajal brauserirakendustes eelistatum kui XML EI OLE PROGRAMMEERIMISKEEL 11. LAMBDA ARVUTUS Lambda-arvutuse keel on Alonzo Churchi poolt 1930. aastatel leiutatud lihtne ja universaalne meetod funktsioonide kirjapanekuks. Lambda-arvutuse keel on Alonzo Churchi poolt 1930. aastatel leiutatud lihtne ja universaalne meetod funktsioonide kirjapanekuks. Churchi tees väidab, et iga algoritmi saab lambda-arvutuse keeles kirja panna. On võimalik
failisüsteemid, kus transaktsioonid (mingi hulga andmete muutmised) logitakse ehk siis märgitakse üles, mida ja kus muudeti või millega asendati ning alles seejärel tehakse see transaktsioon failisüsteemis reaalselt. Kui nüüd transaktsiooni teostamise ajal tekib süsteemi töös tõrge, siis süsteemialglaadimisel on võimalik poolikud transaktsioonid tagasi võtta ning teostamata muudatused teostada. Päevik on faili, andmebaasi vms muudatuste kohta teavet sisaldav andmestruktuur. Päevik paikneb harilikult spetsiaalselt selleks reserveeritud piirkonnas. Failisüsteemid on enamasti väga suured andmestruktuurid ja nende värskendamine võtab palju aega. Kui keset värskendamist toimub süsteemi kokkujooksmine, siis tuleb failisüsteemi taastamiseks läbi käia kogu failisüsteem. Päeviku kasutamise mõte on selles, et muudatusi sisaldav fail salvestatakse kõigepealt päevikusse ja alles hiljem failisüsteemi
.............................................................. 28 Ülesandeid.........................................................................................................................28 Juhuarv..................................................................................................................................28 Ülesandeid.........................................................................................................................29 Omaloodud andmestruktuur..................................................................................................29 Punktimassiiv....................................................................................................................31 Ülesandeid.........................................................................................................................32 Objektorienteeritud programmeerimine...................................................................................
Näiteks ruutvõrrandi lahendamise programmis leidsime kaks lahendit ja võisime neid nimetada x1 ja x2. Kui peaksime aga arvutama 1000 väärtust mingi rutiinse reegli järgi, siis oleks väga ebamugav kirjeldada 1000 eraldi muutujat. Ka tavaelus oleks raske linnas orienteeruda, kui majad poleks tänavate kaupa nummerdatud, vaid igal neist oleks oma nimi (isegi Inglismaal hakatakse sellest aru saama). Seda nummerdamise ideed kannab programmeerimises massiivi mõiste. Massiiv on andmestruktuur, mis lubab samatüübilisi andmeid koondada ühise nime alla ning teha andmeelementidel vahet järjekorranumbri (indeksi) järgi. Üldisemal juhul võib indekseid olla rohkem kui üks - nii saadakse mitmemõõtmelised massiivid. Mitmemõõtmelist massiivi saab käsitleda kui massiivi, mille elementideks on omakorda massiivid (Javas ka nii tehakse). Ühemõõtmelist (ühe indeksiga) massiivi nim. ka järjendiks, kahemõõtmelist massiivi maatriksiks või tabeliks.
3. Piiramatu maht saatja ei blokeeru kunagi 25. Mis on ringpuhvrid, kuidas neid kasutatakse? · Analoogne topelt puhverdamisega, lihtsam kontrollida, n-lugeja, mkirjutaja probleem lihtsam. · Hoitakse päise/alguse (head) - lugemine ja jaluse/lõpu (tail) - kirjutamine aadresse [Ringpuhver on massiiv, mille esimest elementi loetakse viimasele järgnevaks. Ringpuhver (Circular Buffer), mis on oma olemuselt fikseeritud suurusega tsükliliselt läbitav andmestruktuur. Puhvri täitumisel alustatakse uut ringi ning kirjutatakse kõik eelnevalt vastu võetud sõnumid üle. Ringpuhvrit kasutatakse reaalajasüsteemide puhul, kus on tähtis andmeedastuskiirus, kuid vanemate andmete ülekirjutamine ei ole aja progresseerudes enam kriitiline. Taoline lähenemine on otstarbekas näiteks multimeedias, kus reaalajas esitatud pilt ei sõltu sellest, kas mõni pakett minevikus läks kaduma või mitte
Javascript – Brauseri programmeerimiskeel: javascripti programmid töötavad otse brauseris: muudavad htmli, css-i, võtavad ühendust serveriga jne Ajax – kogum omavahel seotud veebiarenduse tehnikaid, mida kasutatakse rakenduse kliendi poolel interaktiivsete veebirakenduste loomisel (ing. k. Asynchronous JavaScript And XML) Json – Andmete esitamise formaat tekstina (Javascripti programmeerimiskeele „native“ andmestruktuur, väga lihtne ja mugav kasutada, kaasajal brauserirakendustes eelistatum kui XML.) (ei ole programmeerimiskeel) Xml – Struktureeritud teksti esitamise formaat, XML standard ütleb, kuidas teksti struktuuri märgistada; Saab kasutada andmete esitamiseks tekstina; Lihtne, aga veidi kohmakas kasutada (ei ole programmeerimiskeel) Klassikaline veebirakendus - server ehitab html teksti (server saadab brauserile html teksti,
. . . . . . . . . . . . . . . 107 14.4 Osasünonüümid . . . . . . . . . . . . . . . . . . . . . 108 15 Ühtluse parandamise meetodeid 111 15.1 Hoolikusel põhinevad meetodid . . . . . . . . . . . . 111 15.2 Lähenemissuunal põhinevad meetodid . . . . . . . . . 112 16 Tehniline mõistelisus 121 16.1 Andmestruktuur . . . . . . . . . . . . . . . . . . . . . 122 16.2 Terminibaasi esitus sõnastikuna . . . . . . . . . . . . 127 16.3 Olemasolevaid terminibaasisüsteeme . . . . . . . . . . 130 16.4 Vastuväiteid . . . . . . . . . . . . . . . . . . . . . . . 133
WriteLine(arv); } } } /* C:Projectsomanaited>Massiiv7 40 48 33 */ Mitmemõõtmeline massiiv Massiivis võib mõõtmeid olla märgatavalt rohkem kui üks. Kahemõõtmelist massiivi saab ette kujutada tabelina, milles on read ja veerud. Kolmemõõtmelise massiivi elemendid oleksid nagu tükid kuubis, mille asukoha saab määrata pikkuse, laiuse ja kõrguse kaudu. Harva läheb vaja enam kui kolme mõõdet - siis on sageli juba otstarbekam ja arusaadavam oma andmestruktuur ehitada. Kasutamine toimub aga nii, nagu allpool näites näha. Massiivi elementidega saab ümber käia nagu tavaliste muutujatega. foreach-tsükliga saab soovi korral läbi käia ka mitmemõõtmelise massiivi kõik elemendid. using System; class Massiiv8{ public static void Main(string[] arg){ int[,] m=new int[2,3]{ {40, 48, 33}, {17, 23, 36} }; Console.WriteLine(m[0, 1]); //48 Console.WriteLine("M66dete arv: "+m.Rank);
Saab kasutada andmete esitamiseks tekstina
Lihtne, aga veidi kohmakas kasutada
XML ei ole:
Programmeerimiskeel.
JSON tähendab
Javascript Object Notation
[1,2,“siin on tekst“, [“sisemine“,5], 10]
{“nimi“:“Peeter“, “pikkus“: 180, “hinded“: [5,3,2] }
JSON on:
Andmete esitamise formaat tekstina
Javascripti programmeerimiskeele „native“ andmestruktuur
Väga lihtne ja mugav kasutada
Kaasajal brauserirakendustes eelistatum kui XML.
JSON ei ole:
Programmeerimiskeel.
XML-s “pakitakse” infoväljad kirjeldavate nn tag-de vahele:
// it's "PHP" $y = "it's "$php""; ?> Kui ei soovi, et pärast muutuja väärtust tuleks tühik või muu sümbol, mille järgi intepretaator saab otsustada, kus lõpeb muutuja nimi ning kust läheb edasi tavaline tekst, sellisel juhul tuleb muutuja nimi panna loogeliste sulgude sisse. Näide Komplekstüübid Massiiv - array Massiiv on andmestruktuur, mis kujutavad ennast elementide hulga. Teisi sõnu, massiivid on omapärased konteinerid, mis võivad hoida samaaegselt mitu väärtust. Vaatleme neid eraldi peatükis 4. Näide '; // väljund: text echo $arr[2]; ?> Objekt - object
See tuleneb
sarnasusest automaadi magasiniga. Kes pole magasini näinud, siis selgituseks kõlbab ka selline
mündihoidja, millel on vedru all ja kuhu saab münte pealtpoolt sisse panna ja samuti välja võtta.
Sellisel "mündimagasinil" ja automaadimagasinil on üks ühine omadus - selle mündi või
padruni, mis sinna esimesena sisse pandi, saadakse kätte kõige viimasena ja vastupidi. Viimane
ese jääb kõige peale ja saadakse esimesena kätte. See on magasini põhimõte.
Pinumälu kui andmestruktuur on kasutusel väga mitmete ülesannete lahendamisel. Lihtsaimaks
ülesandeks, mille jaoks võib kirjutada programmi, on andmejada ümberpööramise ülesanne.
Oletame, et sisestatakse järjest uusi andmeid ning arv 0 tähistab andmejada lõppu. Seejärel on
vaja väljastada kõik sisestatu vastupidises järjekorras. Jada liikmete arv ei ole ette teada.
/* N8_4_C */
#include
See
tuleneb sarnasusest automaadi magasiniga. Kes pole magasini näinud, siis
selgituseks kõlbab ka selline mündihoidja, millel on vedru all ja kuhu saab
münte pealtpoolt sisse panna ja samuti välja võtta. Sellisel "mündimagasinil" ja
automaadimagasinil on üks ühine omadus - selle mündi või padruni, mis sinna
esimesena sisse pandi, saadakse kätte kõige viimasena ja vastupidi. Viimane
ese jääb kõige peale ja saadakse esimesena kätte. See on magasini põhimõte.
Pinumälu kui andmestruktuur on kasutusel väga mitmete ülesannete
lahendamisel. Lihtsaimaks ülesandeks, mille jaoks võib kirjutada programmi, on
andmejada ümberpööramise ülesanne.
Oletame, et sisestatakse järjest uusi andmeid ning arv 0 tähistab andmejada
lõppu. Seejärel on vaja väljastada kõik sisestatu vastupidises järjekorras. Jada
liikmete arv ei ole ette teada.
/* N8_4_C */
#include
WriteLine(arv); } } } /* C:Projectsomanaited>Massiiv7 40 48 33 */ Mitmemõõtmeline massiiv Massiivis võib mõõtmeid olla märgatavalt rohkem kui üks. Kahemõõtmelist massiivi saab ette kujutada tabelina, milles on read ja veerud. Kolmemõõtmelise massiivi elemendid oleksid nagu tükid kuubis, mille asukoha saab määrata pikkuse, laiuse ja kõrguse kaudu. Harva läheb vaja enam kui kolme mõõdet - siis on sageli juba otstarbekam ja arusaadavam oma andmestruktuur ehitada. Kasutamine toimub aga nii, nagu allpool näites näha. Massiivi elementidega saab ümber käia nagu tavaliste muutujatega. foreach-tsükliga saab soovi korral läbi käia ka mitmemõõtmelise massiivi kõik elemendid. using System; class Massiiv8{ public static void Main(string[] arg){ int[,] m=new int[2,3]{ {40, 48, 33}, {17, 23, 36} }; Console.WriteLine(m[0, 1]); //48 Console
annaabi.ee 
