Lisaks neile peab olema võimalik odavalt sooritada kirjete lisamist. Sobivad seega eelistusjärjekorra realiseerimiseks. 1 Kahendkuhjad 5 Kahendkuhjad 1 Kahendkuhjad 6 Invariant Kahendkuhja (ingl binary heap) puhul nõutakse kuhjatingimust ja et tegu oleks kompaktse kahendpuuga. 1 Kahendkuhjad 7 Kuhjatingimuse rekurrentne määratlus Kahendpuu rahuldab kuhjatingimust, kui kas ta on tühi või juure kirje võti on maksimaalne üle kogu puu (pöördkuhja puhul minimaalne), ja mõlemad harud rahuldavad kuhjatingimust. 1 Kahendkuhjad 8 Ülekanduvus alampuudele Kahendkuhja iga alampuu on kahendkuhi. 1 Kahendkuhjad 9 Esitus Eeldame, et
Jada ja arvrida nimetatakse lõplikuks kui selles on lõplik arv elemente või liikmeid. Näited: 4. Mis on lõpmatu jada, arvrida? Esitage 2 näidet! Jada ja arvrida nimetatakse lõpmatuks kui selles on lõpmatu palju elemente või liikmeid. Näited: 5. Millised on tuntuimad jadad, arvread? Aritmeetiline jada, geomeetriline jada. 6. Kodanik paneb panka 10000 krooni. Kui palju on temal pangas raha täpselt 10 aasta pärast, kui intress on 10 aasta jooksul stabiilselt 3%. 7. Mis on rekurrentne seos? Esitage 2 näidet! Seos, mis võimaldab jada k-ndat elemnti leida selle jada eelmiste elementide kaudu, nimetatakse rekurentseks seoseks. 8. Milline on esimest järku rekurrentne seos? Esitage näide! Esimest järku rekurentne seos: , kus a ja b on konstandid ja n=1,2,.... 9. Milline on teist järku rekurrentne seos? Esitage näide! Teist järku rekurrentseks seoseks nimetatakse seost , kus a,b,c on konstandid. 10
1) Kui alustan vertikaalse doominonupuga, siis jääb veel katmata 2x(n-1) ruutu ja ülejäänud malelaua katmiseks on mul võimalust. 2) Kui alustan horisontaalse doominonupuga, siis jääb veel katmata 2x(n-2) ruutu ja ülejäänud malelaua katmiseks on mul # võimalust. 3) Kolmandat varianti pole. Seega kokku võimalusi: # = + #, mida tuligi näidata. Saadud rekurrentne seos erineb Fibonacci jadast üksnes algväärtuste poolest(# = 1 ja $ = 2), $ vastab % -le ja # $ -le. Järelikult W = ÜLESANNE 5 Hulgal {1,2, ..., n} on W = W + W + W sellist alamhulka, milles ei leidu kolme järjestikust arvu, kusjuures W = , W = , W = Põhjendus: Katsetan 1 3 J 3 5 korral. Tähistan sobivate alamhulkade arvu -ga. Vaatan ka " -i, sest teda on vaja rekurrentse seose kasutamisel.
töötatud aluseks võttes vähimruutude meetodi põhimõtteid.Lihtsustatud tasandamisel ei järgita neid põhimõtteid täiel määral, vaid tehakse arvutuste käigus mitmesuguseid lihtsustamisi.Üheks põhiliseks võtteks parandite arvutamise lihtsustamisel on matemaatiliste tingimuste jaotamine gruppidesse ja mõõdetud suuruste või nende funktsioonide mitmekordne parandamine tasandamisarvutuste käigus.Mitme sõlmpunktiga käikude tasandamine-Tasandatakse järk järguliste lähenduste ehk rekurrentne viis.Põhimõtteliselt toimub siin sõlmjoonte direktsiooninurkade või sõlmpunktide koordinaatide kaalutud keskmiste väärtuste arvutamine.Olenevalt sellest, kas tasandatakse nurki, koordinaatide juurdekasve või kõrguskasve, arvutatakse esiteks sõlmjoonte direktsiooninurkade või sõlmpunktide koordinaatide või kõrguste esimesed lähendused.Pärast seda teised lähendused ja nii edasi kuni saadakse lähendused mis ühe ja sama sõlmpunkti mingi kahe
meetodi põhimõtteid.Lihtsustatud tasandamisel ei järgita neid põhimõtteid täiel määral, vaid tehakse arvutuste käigus mitmesuguseid lihtsustamisi.Üheks põhiliseks võtteks parandite arvutamise lihtsustamisel on matemaatiliste tingimuste jaotamine gruppidesse ja mõõdetud suuruste või nende funktsioonide mitmekordne parandamine tasandamisarvutuste käigus.Mitme sõlmpunktiga käikude tasandamine-Tasandatakse järk järguliste lähenduste ehk rekurrentne viis.Põhimõtteliselt toimub siin sõlmjoonte direktsiooninurkade või sõlmpunktide koordinaatide kaalutud keskmiste väärtuste arvutamine.Olenevalt sellest, kas tasandatakse nurki, koordinaatide juurdekasve või kõrguskasve, arvutatakse esiteks sõlmjoonte direktsiooninurkade või sõlmpunktide koordinaatide või kõrguste esimesed lähendused.Pärast seda teised lähendused ja nii edasi kuni saadakse lähendused mis ühe ja
NÄIDE: Seost Pn = nPn-1 nimetatakse faktoriaalijada (Pn) rekurrentseks võrrandiks ja avaldis Pn = n! selle võrrandi lahendiks. (e. jada (Pn) üldliikme analüütiliseks esituseks). Rekurrentsi järk k on rekurrentse võrrandi ,,sügavus": see näitab, kui mitmest eelmisest jada liikmest iga järgnev üldliige sõltub. Lahendamismeetodid: a). ad hoc meetod e. ,,for the cause" meetod sellisel juhul on tavaliselt ette antud kas rekurrentne võrrand või mõni muu seos, mille abil on võimalik jada liikmeid leida. Liikmete väärtuste põhjal saab heuristiliselt tuletada algebralise hüpoteesi, mida juba omakorda on võimalik kontrollida induktsiooni abil. (Eeldades et n=k, heaks näiteks on siin noore Gaussi meetod). b). Iteratsioonimeetodi puhul võetakse ette rekurrentne võrrand (näiteks Zn = aZn-1 + b) ning hakatakse seda järjest ,,koorima nagu sibulat" rekurrentset liiget hakatakse
Definitsioon Ortonormaalset süsteemi , mille korral Parsevali võrdus kehtib iga integreeruva ruuduga funktsiooni f(x) korral, nimetatakse täielikuks süsteemiks. 11.Fourier' rida ortogonaalsete polünoomide süsteemi järgi Lehendre'i või Tšebõšovi polünoomide näitel. Definitsioon: (1-liiki) Tšebõšovi polünoomideks nimetatakse funktsioone, mis x ϵ [-1,1] korral on defineeritud kujul (k = 0, 1, 2, …) Tk=(x) := cos(k arccos x). Lause: Kehtib rekurrentne seos T0(x) = 1, T1(x) = x, Tk+2(x) = 2x Tk+1(x) – Tk(x) Tõestus: T0(x) = cos(0) = 1, T1(x) := cos(arccos x) = x Rekurrentse seose jaoks vaatame valemit 2cos t cos ((k+1)t) = cos ((k+1)t+t) + cos ((k+1)t+t) = cos ((k+2)t) + cos kt Võtame t = arccos x ja saame cos ((k+2)arccos x) = 2(cos arccos x) cos ((k+1)arccos x) + cos (k arccos x) = 2x cos ((k+1)arccos x) + cos (k arccos x) k-järku (k € N) Tšebõšovi polünoomid on esitatavad k x k determinandina. Lause:
Definitsioon Ortonormaalset süsteemi , mille korral Parsevali võrdus kehtib iga integreeruva ruuduga funktsiooni f(x) korral, nimetatakse täielikuks süsteemiks. 11.Fourier' rida ortogonaalsete polünoomide süsteemi järgi Lehendre'i või Tsebõsovi polünoomide näitel. Definitsioon: (1-liiki) Tsebõsovi polünoomideks nimetatakse funktsioone, mis x [-1,1] korral on defineeritud kujul (k = 0, 1, 2, ...) Tk=(x) := cos(k arccos x). Lause: Kehtib rekurrentne seos T0(x) = 1, T1(x) = x, Tk+2(x) = 2x Tk+1(x) Tk(x) Tõestus: T0(x) = cos(0) = 1, T1(x) := cos(arccos x) = x Rekurrentse seose jaoks vaatame valemit 2cos t cos ((k+1)t) = cos ((k+1)t+t) + cos ((k+1)t+t) = cos ((k+2)t) + cos kt Võtame t = arccos x ja saame cos ((k+2)arccos x) = 2(cos arccos x) cos ((k+1)arccos x) + cos (k arccos x) = 2x cos ((k+1)arccos x) + cos (k arccos x) k-järku (k N) Tsebõsovi polünoomid on esitatavad k x k determinandina. Lause:
Definitsioon Ortonormaalset süsteemi , mille korral Parsevali võrdus kehtib iga integreeruva ruuduga funktsiooni f(x) korral, nimetatakse täielikuks süsteemiks. 11.Fourier' rida ortogonaalsete polünoomide süsteemi järgi Lehendre'i või Tsebõsovi polünoomide näitel. Definitsioon: (1-liiki) Tsebõsovi polünoomideks nimetatakse funktsioone, mis x [-1,1] korral on defineeritud kujul (k = 0, 1, 2, ...) Tk=(x) := cos(k arccos x). Lause: Kehtib rekurrentne seos T0(x) = 1, T1(x) = x, Tk+2(x) = 2x Tk+1(x) Tk(x) Tõestus: T0(x) = cos(0) = 1, T1(x) := cos(arccos x) = x Rekurrentse seose jaoks vaatame valemit 2cos t cos ((k+1)t) = cos ((k+1)t+t) + cos ((k+1)t+t) = cos ((k+2)t) + cos kt Võtame t = arccos x ja saame cos ((k+2)arccos x) = 2(cos arccos x) cos ((k+1)arccos x) + cos (k arccos x) = 2x cos ((k+1)arccos x) + cos (k arccos x) k-järku (k N) Tsebõsovi polünoomid on esitatavad k x k determinandina. Lause:
2𝑘+1 2 = . Cauchy tunnuse Lause: Kehtib rekurrentne seos T0(x) = 1, T1(x) = x, Tk+2(x) = 2x Tk+1(x) – Tk(x) ∞ 𝑑𝑥 𝐴 𝑑𝑥 𝐴1−α −1
1. Mitmemuutuja funktsiooni lokaalsete ekstreemumite mõisted. Statsionaarne punkt. Kriitiline punkt. piirkonna D rajajoon. Eeldame, et piirkonnas D on täidetud tingimus f(x,y)>=g(x,y). Kahekordse integraali 𝑥 = 𝜌 𝑐𝑜𝑠𝜑 Mitmemuutuja funktsiooni lokaalse ekstreemumi tarvilik tingimus. Definitsioon 1. Öeldakse, et kahe omaduse tõttu ∬𝐷[𝑓(𝑥, 𝑦) − 𝑔(𝑥, 𝑦)]𝑑𝑥𝑑𝑦 = ∬𝐷 𝑓(𝑥, 𝑦)𝑑𝑥𝑑𝑦 − ∬𝐷 𝑔(𝑥, 𝑦)𝑑𝑥𝑑𝑦. Mõlemad kahekordsed 𝑦 = 𝜌 𝑠𝑖𝑛𝜑 muutuja funktsioonil on punktis P1(x1, y1) lokaalne maksimum, kui sellel punktil leidub niisugune ümbrus teisendus on kujul 𝑧=𝑧 .Tavaliselt € [0, +lõpmatus) φ € [0, 2π). ∭Ω 𝑓(𝑥, ...
else return fib(n-1) + fib(n-2) } •Tegemist on rekursiivse algoritmiga –lõpetamistingimuse täitmisel algoritm peatub –muul juhul kutsub funktsioon välja iseenda muudetud argumendiga ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 9 Näide ikka jätkub •Iga fib funktsiooni väljakutse on kas 1 või 2 rida –n <= 2 korral üks rida –n = 3 korral 2 rida + 1 rida kummagi uue väljakutse kohta: 4 –n = 4 korral 2 + 4 + 1 = 7 –n = 5 korral 2 + 7 + 4 = 13 •Keerukuse rekurrentne võrrand time(n) = 2 + time(n-1) + time(n-2) •Read paljunevad nagu jänesed ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 10 Näide jätkub ka siin •Püüame lahendada selle võrrandi F(n) suhtes F(5) / F(4) F(3) / / F(3) F(2) F(2) F(1) / F(2) F(1) Sellises puus on iga n korral –F(n)lehte ( F(1), F(2) ) –F(n) -1 sisemist sõlme( F(k), k > 2 ) ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 11 Näide läheb veel edasi •F(n) lehte
annaabi.ee 
