omavahel? 3 Kas RSA algoritm on DES algoritmi analoog? Ei Kelle poolt loodi esimene kalkulaator, mis suutis jagada? (arvestada neid, mille kohta on ka teada, et need valmis tehti) Blaise Pascal Milline allolevatest on kõige väiksema keerukusega keerukusklass? O(1), O(log n), O(sqrt(n)), O(n), O(nLog n), O(n2), O(n2Log n), O(n3), O(nk), O(2n), O(n!), O(nn), O( 2^(2^(2^(...))) n) Sellega kas ülesandele on võimalik leida lahendusalgoritmi tegeleb: lahenduvus Kas keerukusteoorias kasutatakse keerukuse hindamisel ühe parameetrina programmi ridade arvu? Mitte alati Mille järgi on nimetatud Apple viimased operatsioonisüsteemid? Kasslased Mitu arvutuskeskust ühendati esialgselt Arpaneti? 4 Millise ettevõtte poolt tehti esimene transistoritel põhinev arvuti? AT&T Bell Kes esitas esimesena süllogismid? Aristoteles Mis materjali järgi on saanud ,,Abacus" endale nime? Liiv
11. Nädal Eksamiks: rekursiooni äratundmine, baasjuht ja rekursiivne juht, rekursiooni ekvivalentsus tsükliga, arusaamine funktsionaalse keele näitejuppidest loengus: mida mingi näitekood teeb / mis on rehkendamise tulemus. Mis on lambda-arvutus. Proloogi näide tuleb ära tunda (et on Prolog). 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
Alumine kiht pakub ülemisele teenuseid. Andmeühik PDU(Protocol Data Unit) • Kanalikihi kaader • Võrgukihi pakett (datagramm) • Transpordikihi segment (või datagramm) Teenuse juurdepääsupunkt SAP (Service Access Point). • Kanalikihi LSAP • Transpordikihi port (Päiste detailide kohta ei küsita.) 10 Eksamiks: lahenduvus Eksamteoreetilises Eksamja Eksamtavamõttes, mis on lahenduvad Eksamülesanded. 1. Lahenduvus Eksam- Eksamehk kas üldse ülesannet saab lahendada 2. Lahendubus Eksamtavamõttes - Tüüpilised põhjused, miks me ei saa tavaprobleeme lahendada: näiteks, kuidas saada kiiresti väga palju raha (pole piisavalt infot ja juhuslikkus segab) 3. Lahendubus Eksammatemaatilises Eksammõttes Eksam- EksamInfot on piisavalt: meil on olemas kõik vajalikud aksioomid /
kui ka akende valmistamisega. Organisatsioon on tänaseks päevaks saavutanud kindla koha Eesti turul. Toodete valik on laienenud klientide soovidest lähtuvalt ning uueneb pidevalt. Organisatsioonil on 2 müügiosakonda üle Eesti, kus töötab hea väljaõppe saanud personal. Tehas pakkub tööd käesoleval ajal rohkem kui 130-le inimesele. Ettevõte on väga avatud uuendustele ja tulevikus plaanib laieneda veelgi. Organisatsiooni esmaseks eesmärgiks on pakkuda kliendile parim lahenduvus vastava tellimuse puhul ning seda parima hinna- ja kvaliteeditaseme juures. Organisatsiooni missiooniks on pidev tehnoloogia uuendamine, mis aitaks tagada toodetele kõrge kvaliteedi ja töökindluse, mis omakorda tagab klientide rahulolu. Samuti on ettevõte huvitatud kasumi teenimisest ja vähem tähtis pole ka kindlustada töötajatele konkurentsivõimeline palk. Antud organisatsiooni üheks visiooniks võib kindlasti pidada ka toodangu valmistamist välisturule. 1
Prolog on esimene loogilise programmeerimise keel. Põhiidee on nõuda otsitava lahenduse kirjeldamist esimest järku predikaatarvutuse keeles, kusjuures Prolog-i süsteem sisaldab teatud tüüpi automaatset teoreemitõestajat, mis on võimeline lahendust automaatselt otsima ja tuletama. Siiski pole Prolog automaatse teoreemitõestamise süsteem. __________________________________________________________________ 11. 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. Lahenduvus tavamõttes:
Python (time): kui kiiresti algoritm peatub, kui kiireid algoritme on mingite ülesannete jaoks olemas? Mälukasutus ehk ruum def sumto(n): (space): kui palju mälu algoritm kasutab, kui väikese mälukasutusega algoritme on mingite ülesannete jaoks olemas? sum=0 LAHENDUVUS. kas üldse ülesannet lahendada saab? Selgub, et iga täpselt formuleeritud probleemi jaoks ei leidugi for i in range(n+1): lahendavat algoritmi! Saab näidata, et erinevaid probleeme on lõpmatult rohkem, kui erinevaid algoritme sum=sum+i return sum
Malukasutus hk ruum l9(r.l - Mrxxc'i scadrrs. BASIC (5pace): kui palju malu algoritm kasutab, kui v:iikese mAluka*tusega algorilrne on mingite Ulesannete jaoks olemas? 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
funktsioon" ülesande jaoks suurusega n. Easy to verify answers. Difficult to find answers. Easy ---> polynomial time Difficult --> not polynomial time. NP: Class of problems for which it is easy to verify the answers but exponential or factorial number of combinations to check. Travelling salesman problem is in NP. Nobody has managed to prove (yet) that there are no polynomial algorithms for P. Open question: does NP = P ? Lahenduvus: Selgub, et iga täpselt formuleeritud probleemi jaoks ei leidugi lahendavat algoritmi! Uuritakse, millistele ülesannetele on algoritme, millistele ei Uuritakse, mis ülesande lahendamine taandub teisele ülesandele Uuritakse lahendumist, poollahendumist, kreatiivseid hulki jne jne Uuritakse lõpmatuse struktuuri, mis on kirjeldamatult keeruline Uuritakse lahendumise struktuuri, mis on kirjeldamatult keeruline Uuritakse loogikaklasside lahendumise taandumist muudele ülesannetele
Prolog-i põhi-idee on nõuda otsitava lahenduse kirjeldamist esimest järku predikaatarvutuse keeles, kusjuures Prolog-i süsteem sisaldab teatud tüüpi automaatset teoreemitõetajat, mis on võimeline lahendust automaatselt otsima ja tuletama. Sellegipoolest ei ole Prolog siiski automaatse teoreemitõestamise süsteem: viimast realiseeriv mehhanism on Prolog-is väga piiratud, spetsiifline ja loogiliselt mittetäielik. 12. GÖDEL lahenduvus: ei saa olla lõplikku aksioomide ja reeglite kogu, millest saab järeldada kõiki tegelikult õigeid matemaatikaväiteid. Gödeli mittetäielikkuse teoreemid (inglise Gödel's incompleteness theorems) ehk Gödeli teoreemid on Kurt Gödeli (19061978) kaks teoreemi matemaatilises loogikas, mis demonstreerivad iga loogilise süsteemi, mis sisaldab formaalse aritmeetika, piiratust või mittetäielikkust[1]. Gödel väitis, et igas formaalses aritmeetikas leidub tõene lause, mis ei ole
..♯qa♯♯ C0…Cm on konfiguratsioonide jada x aktsepteerimisel. Cm’ jne on saadud Cm-i algusest 1, 2 jne sümboli kustutamisel. Konfiguratsioonide jada, mille puhul TM aktsepteerib ja peatub, ei saa ette teada. Turingi masina määramispiirkond on sisendite hulk, mille puhul see TM peatub. See hulk ei ole määratud. 27 Ülesannete redutseeritavus. KV keelte ühesuse mittelahenduvus. Ülesannete lahenduvuse üle otsustamiseks kasutasime nende taandamist ülesannetele, mille lahenduvus on teada. Olgu A ja B ülesanded. Öeldakse, et ülesanne A on reduseeritav ülesandele B, kui B iga lahendus annab lahenduse ka A-le. DEF: Keel A on m-redutseeritav keelele B, mida tähistatakse A <=m B, kui leidub selline arvutatav funktsioon f : Σ* → Σ*, nii et iga w ∈ Σ* korral w ∈ A f (w) ∈ B. Teoreem: Kui A on redutseeritav B-le ja hulk B on lahenduv, siis hulk A on lahenduv.
Paljusid selliseid ülesandeid saab kavalate algoritmidega praktikas päris hästi lahendada ka üpris suure ülesannete (suure N) jaoks: lihtsalt sellised algoritmid ei tööta alati efektiivselt, vaid vahete-vahel. ka sellest on palju kasu, kui neid ülesandeid vahete-vahel õnnestub mõistliku ajaga lahendada Vahete-vahel kiirelt lahenduvate juhtude protsent võib praktikas osutuda üpris kõrgeks Lahenduvus Teame, et iga probleemi jaoks ei leidu kiiret algoritmi. Kas aga iga probleemi jaoks on üldse olemas algoritmi, mis seda lahendab? Eeldame, et vaatame ainult probleeme, mis on täpselt ja üheselt kirjeldatud ja kus on lahendamiseks olemas piisavalt infot (a la travelling salesman, malemäng jne) Selgub, et iga täpselt formuleeritud probleemi jaoks ei leidugi lahendavat algoritmi!
aksiomatiseerida ja tõestada suudame. Predikaatarvutuse täielikkus ja aritmeetika ning keerulisemate sßuteemide mittetäielikkus on küll kõige kuulsamad, kuid kaugeltki mitte ainsad 20. sajandi loogika fundamentaalsetest teoreemidest, mille autoriks on Gödel. Oma elu jooksul jõudis Gödel publitseerida aukartustäratava hulga artikleid ning käsitleda pea kõiki loogikavaldkondi. 2.5.6 Automaadid, programmeerimine ning lahenduvus Tuhandeid aastaid on lisaks sõrmedele kasutatud arvutamise juures abiks arvutuspulki, arvelaudu jm. Selliseid abivahendeid ei saa nimetada arvutusmasinateks, sest arvutamise meetodid pidid olema ikkagi kasutaja peas. Esimesed mehaanilised arvutusmasinad leiutati Euroopas 17. sajandil, tuntumad neist on Prantsuse filosoofi Blaise Pascali liitmise-lahutamise masin ning Leibnizi masin, mis suutis lisaks korrutada, jagada ja ruutjuuri arvutada. 1822. ehitas
Pihl Sissejuhatus informaatikasse 20 Loe juurde! •http://www.itil.org/en/ •www.isaca.org/cobit/ •http://builder.com.com/5100-6315-1046507.html •http://agilemanifesto.org/ •http://www.agilealliance.org/home •http://www.paulgraham.com/bronze.html •http://www.paulgraham.com/start.html •http://www.joelonsoftware.com/articles/fog0000000245.html •http://www.joelonsoftware.com/articles/fog0000000074.html ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 21 Keerukusteooria ja lahenduvus Millest räägime •Keerukusteooria mõiste •Kasutusvaldkonnad •Lahenduvusest ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 2 Matemaatikast –Vanad “vist ekslikud” oletused: 1.Mathematics isconsistent. Roughly this means that we cannot prove a statement and its opposite; we cannot prove something horrible like 1=2. 2.Mathematics is complete. Roughly this means that every true mathematical assertion can be proven i.e. every mathematical
annaabi.ee 
