TARTU ÜLIKOOLI TEADUSKOOL PROGRAMMEERIMISE ALGKURSUS 2005-2006 Sisukord KURSUSE TUTVUSTUS: Programmeerimise algkursus.........................................6 Kellele see algkursus on mõeldud?..................................................................6 Mida sellel kursusel ei õpetata?.......................................................................6 Mida selle kursusel õpetatakse?......................................................................6 Kuidas õppida?.................................................................................................7 Mis on kompilaator?.............................................................................................8 Milliseid kompilaatoreid kasutada ja kust neid saab?......................................8 Millist keelt valida?...........................................................................................8 ESIMENE TEEMA: sissejuhatav sõnavõtt ehk 'milleks on v
Programmeerimise algkursus 1 - 89 Mida selle kursusel õpetatakse?...................................................................................................3 SISSEJUHATAV SÕNAVÕTT EHK 'MILLEKS ON VAJA PROGRAMMEERIMIST?'......3 PROGRAMMEERIMISE KOHT MUUDE MAAILMA ASJADE SEAS.............................3 PROGRAMMEERIMISKEELTE ÜLDINE JAOTUS ..........................................................7 ESIMESE TEEMA KOKKUVÕTE........................................................................................8 ÜLESANDED......................................................................................................................... 8 PÕHIMÕISTED. OMISTAMISLAUSE. ...................................................................................9 ................................................................................................................................................. 9 SISSEJUHATUS.......
tsükkel, siis seda serva ei võeta). Alt-üles (alguses on üksikud tipud, lõpuks peavad kõik tipud esinema omas sidususkomponendis), ahne strateegia (valitakse hetkel parim tee). Primi algoritm: töötatakse antud lähtetipust laiuti sarnaselt Dijkstra algoritmiga (toesesse valitakse hetkejätkudest minimaalse kaaluga serv, meeles peetakse kaalu ja eellast, vajadusel parandatakse eellast teel allikast antud tipuni). 20. Rekursioon, näide: Hanoi tornid. Rekursiooni eemaldamine, "sabarekursioon" (tail recursion). Hanoi tower on 2n käiku. Alusta algseisust, sest mõned lubatud seisud ei ole algseisust saavutatavad. Eksponentsiaalselt keeruline ülesanne. Ümber laduda nii, et suurem ketas ei oleks väiksema peal. Lahenda baasjuht ja liigu sealt sammu kaupa edasi (induktsioon). Rekursiivne algoritm sisaldab sellesama algoritmi poole pöördumist mingi "lihtsama juhu" jaoks.
Iga registermasina programm on realiseeritav Turingi masinal: Esitame registermasina kõigi nullist erinevate registrite sisu Turingi masina lindil Turingi masin ja registermasin on arvutatavuse mõttes ekvivalentsed. Church-Turingi tees: iga efektiivselt arvutatav funktsioon on realiseeritav Turingi masinal 24. Lihtrekursiivsed funktsioonid, nende arvutatavus Turingi mõttes. Arvtatavuseks piisab kolmest operaatorist: · superpositsioon (f.-nide järjest rakendamine) · rekursioon (f.-ni rakendamine iseenda sees omaenese eelmistele väärtustele) · minimeerimine arvutamine teatud tingimuse täitumiseni Superpositsioon: n-kohaline f.-n f on saadud m kohalisest f.-nist g ja n kohalistest f.-nidest hi (i = 1,..,m) superpositsioonioperaatori rakendamisel, kui f = Sm+1(g;h1,..,hm) = g(h1,..,hm) Rekursioon: n+1-kohaline f-n f on saadud n-kohalisest f.-nist g ning n+2-kohalisest f.-nist h
Diskreetne matemaatika II Suulise eksami konspekt IABB 2011 [1]. Hulgad. Alam- ja ülemhulgad. Tehted hulkadega. [2]. Hulga võimsus. Kontiinumhüpotees. [3]. Järjendid. Permutatsioonid. Kombinatsioonid. [4]. Binoomi valem. Pascali kolmnurk. [5]. Liitmis- ja korrutamisreegel kombinatoorikas. [6]. Kordustega permutatsioonid. Multinoomkordajad. [7]. Elimineerimismeetod (juurde- ja mahaarvamise valem). [8]. Korratused ja subfaktoriaalid. [9]. Dirichlet` printsiip. [10]. Arvujadade genereerivad funktsioonid. Jadade ja genereerivate funktsioonide teisendamine. [11]. n objekti jaotamine k gruppi. [12]. Rekurrentsed võrrandid. Rekurrentsi lahendamine ad hoc meetodil ja iteratsioonimeetodil. [13]. Tasandi tükeldamine n sirgega ja n nurgaga. [14]. Lineaarsed rekurrentsed võrrandid. [15]. Rekurrentsete võrrandite lahendamine genereerivate funktsioonide meetodil. [16]. Fibonacci arvud. Üldliikm
1 Lõplikud automaadid ja regulaarsed keeled. DEF: Lõplik automaat on sellise arvuti mudel, millel puudub mälu (või seda on väga vähe). DEF: Automaadi M keeleks nimetatakse sõnede hulka A, mida M aktsepteerib. L(M)=A DEF: Keelt nimetatakse regulaarseks, kui seda aktsepteerib mingi deterministlik lõplik automaat. Reg. keelest saab teha lõpliku arvu sõnesid. Tehted regulaarsete keeltega: A∪B = {x|x ∈ A või x ∈ B} ühend nt good, girl, boy, bad A◦B ={xy|x ∈ A ja y ∈ B} konkatenatsioon nt goodboy, goodgirl, badboy, badgirl A∗ = {x1x2...xk|k>=0 ja iga xi ∈ A} sulund nt ε, good, bad, goodgood, badgood… 2 Regulaarsete keelte omadusi. Regulaarsed avaldised. Teoreem: Regularsete keelte hulk on kinnine ühendi suhtes. T: Aktsepteerigu automaat N1 = (Q1,Σ,δ1,Q10,F1) keelt A1 ja automaat N2 = (Q2,Σ,δ2,Q20,F2) keelt A2. Eeldame, et keeltel pole ühiseid olekuid. Ühendi A1 ∪ A2 aktsepteerib lõplik automaat N=(Q;Σ,δ,Q0,F), kus: • Q = {q0} ∪ Q1 �
Turingi masin 1937 Universaalne masin suudab arvutada/järeldada kõike Turingi tees: kõike mida saab üldse mingi masinaga järeldada/arvutada, saab ka Turingi masinaga arvutada Parmenides (5 saj. e.m.a) kasutas pikki loogilisi põhjendusi. Zenon Elast (5 saj e.ma) paradoksid Sofistid-Sokrates (470-399 e.m.a), Platon (428/427 - 348/347e.m.a) Aristoteles: väidete struktuur kui iseseisev uurimisobjekt Süllogismi näited:1eeldus:iga koer on imetaja, 2eeldus mõned neljajalgsed on koerad, järeldus: mõned neljajalgsed on imetajad. Süllogism on väitlus, kus mingitest etteantud väidetest järeldub paratamatult uus väide. Aristotelese puhul alati kaks kategoorilist eeldust, üks kategooriline järeldus Stoikud uurisid, kuidas saab loogiliste sidesõnade (ja, ei, või, kui ...siis)abil lihtsamatest lausetest keerulisemaid kokku panna ja kuidas näidata selliselt moodustatud lausete õigsust. Ramon Llull 1235- 1315 müstik Peateos Ars magna, generalis et ultima; Leonardo da Vinci ca 15
LTMS.00.022 ÜHE MUUTUJA MATEMAATILINE ANALÜÜS Loengukursus Tartu Ülikooli loodus- ja täppisteaduste valdkonna üliõpilastele 2019./2020. õppeaasta Toivo Leiger Joonised: Ksenia Niglas Pisitäiendused 2016–20: Märt Põldvere, Natalia Saealle, Indrek Zolk, Urve Kangro 2 Sisukord 1 Reaalarvud 6 1.1 Järjestatud korpused . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Korpuse aksioomid . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Järjestatud korpus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 Täielik järjestatud korpus . . . . . . . . . . . . .
Kõik kommentaarid