Ülessanne Kas antud hulkade omadused on rekursiivselt invariantsed: 1. Sisaldab vähemalt 3 elementi 2. On tühi 3. On lõputu 4. On rekursiivselt loenduv (RL) Millised neljast omadusest: on rekursiivne on rekursiivselt loenduv omab rekursiivst täiendit omab rekursiivselt loenduvat täiendit on antud hulkade põhjal 1. A = {x | x on paarisarv} 2. B = {x | x on väiksem kui 100} 3. C = {x | x on algarv} 4. D = {x | Wx on tühi} 5. E = {x | Wx sisaldab vähemalt 3 elementi} Lahendus Alusteooria Hulk on rekursiivselt invariantne, kui iga bijektiivse ja rekursiivse junktsiooni f korral, kui hulgal A on omadus P, siis ka hulgal f (a) on omadus P.
map-4.4.0-104-generic Ülesanne 2 Kopeeri kataloog /etc koos alamkataloogidega kataloogiks /var/backups/etc-copy , nii et säiliksid kataloogi ja failide omanikud ja ajatemplid. Kontrolli korraldusega diff , kas kataloogid /etc ja /var/backups/etc-copy on identse sisuga. Käsk cp (copy) kopeerib faile ja katalooge. Lipuga -d ei järgita sümboolseid viitasid kopeeritavas kataloogis. Lipuga -R (recursive) kopeeritakse kataloogi sisu rekursiivselt ehk kopeeritakse kõik kataloogis olevad alamkataloogid koos nendes sisalduvate failidega. Lipuga -v (verbose) näeme detailset informatsiooni käsu täitmise kohta. Lipuga --preserve=all säilivad kõik kataloogide ja failidega seotud atribuudid, sealjuures omanikud ja ajatemplid. Käsk cp nõuab, et kopeeritava faili või kataloogi aadress kirjutatakse enne koopia aadressi. Kasutame korraldust sudo (super-user do), et anda käsu täitmise ajal lisanduvaid
keelt aktsepteerivaks deterministlikuks lõplikuks automaadiks M = (Q’, Σ, δ′, Q0′, F′). Kui mittedeterministlikul on k olekut, siis talle vastaval deterministlikul võib olla kuni 2k olekut. T: eeldame, et N-is pole ε-üleminekuid. 4 Regulaarsete avaldiste ja lõplike automaatide samaväärsus. Teoreem: Regulaarse avaldisega defineeritud keel on aktsepteeritav (mittedeterministliku) lõpliku automaadiga. T: vastavalt avadlise struktuurile saame rekursiivselt teha automaadi: Teoreem: Lõpliku automaadi poolt aktsepteeritav keel on defineeritav regulaarse avaldisega. T: Olgu M = (Q,Σ,δ,Q1,F) lõplik automaat olekute hulgaga Q = {q0,q1,…,qn}. Defineerime Rk ij kui sõnede hulga, mis viivad automaadi olekust qi olekusse qj vahepeal olekuid qk,...,qn läbimata. Hulk R0 ij = {a∈Σ | qj ∈ δ(qi ,a)} on lõplik ja seega esitatav regulaarse avaldisega.
3) Sümmeetriliselt vasak-juur-parem. Nii saab kronoloogilise tulemuse. Nt nimekirja tähestiku järjekorras. 4) Laiuti - juur-vasak-parem 2,3,4 kõik rekursiivsed. Külastuse eesmärgiks külastatav tipp hävitada ja et üldse puu mälust likvideerida, kõik tipud vabaks lasta sellisel juhul tuleb külastada süviti strateegia järgi. Proge antakse sisse viit puu juurele. Sorditud loendi moodustamine puu põhjal. Puu läbikäik sümmeetriliselt, aga mitte rekursiivselt. Kasutatud on stacki. Puu läbikäik(3). - läbi vaadata see näide. Kaval progeja kasutab rekursiooni ikka siis, kui ta leiab, et see talle midagi annab. Mida teha siis, kui ei ole tegemist kahendpuuga, vaid tütarde arv ei ole piiratud. Viit vektorile ning see viitab omakorda tütardele. Viidad tütardele on ühes vektoris, kui üks tütar tuleb juurde, siis tuleb seda vektorit pikendada. Ei ole kõige parem lahendus. Parem lahendus. Teha tipp selliselt, et seal on viit kirjele
filesystem). Lipuga -t saame argumendiks anda failisüsteemi tüübi. student@server:~$ sudo mkfs -t ext4 /dev/sda3 Monteeri see ajutisse asukohta ja kopeeri kogu /var/www . Kontrolli, et sisud on identsed. Monteerime sda3 ajutisse monteerimispunkti /mnt ja määrame lipuga -t failisüsteemi tüübiks ext4 . student@server:~$ sudo mount -t ext4 /dev/sda3 /mnt Kopeerime /var/www sisu /mnt sisuks lipuga -a : rekursiivselt ja jättes muutmata kõik atribuudid. student@server:~$ sudo cp -a /var/www/* /mnt Kontrollime sisu erinevusi käsklusega diff . Erinevusi ei ole. student@server:~$ sudo diff -rq /var/www /mnt/www Kustuta /var/www sisu ja monteeri uus failisüsteem /var/www alla. Kustutame /var/www sisu, jättes kataloogi alles. student@server:~$ sudo rm -r /var/www/* Monteerime uue failisüsteemi /var/www alla.
möödapääsmatu probleem; sellest tulebki rakendada efektiivsemad meetodeid nagu nt. Miller-Rabini test. *Miller-Rabini test: *Miller-Rabini test on sisuliselt Fermat' teoreemi karastatud versioon, mis peaks olema immuunne ka Carmichaeli arvude vastu: a). Vaatleme avaldist an a = a(an 1) , kus n on testitav naturaalarv ning a suvaline n'ist väiksem naturaalarv. b). Eelnevalt esitatud avaldise parem pool lahutatakse rekursiivselt lahti teguriteks vastavalt seosele x2 - 1 = (x 1)(x + 1). (nii pikalt kui võimalik). c). Kui avaldis an a ei jagu n'iga, siis ei jagu selle arvuga ükski tegur. Sellest tulenevalt ei tohi üksi parema poole teguritest jaguda arvuga n. Kui aga vähemalt üks neist teguritest n'iga jagub, on tõenäoliselt tegu algarvuga. Tõenäosuse suurendamiseks tuleks katset korrata mingi teise juhusliku alusega. [31]. Graafid ja graafide omadused. Ahelad ja tsüklid graafis.
fakt(x) = x*fakt(x-1) (ehk: fakt(x) = if x=0 then 1 else x*fakt(x-1)) map(f,[]) = [] map(f,[h|t]) = [f(h) | map(f,t)] Avaldise map(fakt,[3,5,0]) väärtuseks on [6,120,1] kui fakt = 3, siis 3*fakt(3-1) = 3*fakt(2) = 3*(2*1) = 6 3*FAKT(2) = 3 * 2*FAKT(1) = 3*2*1*FAKT(0) = 3*2*1*1 = 6 kui fakt = 5, siis 5*fakt(5-1) = 5*fakt(4) = 5*(4*3*2*1) = 120 5*FAKT(4) = 5*4*FAKT(3) = 5*4*3*FAKT(2)=60*2*FAKT(1)=120*1*FAKT(0) = 120 kui fakt(0), siis = 1 Kirjutatud funktsionaalses programmeerimiskeeles, rekursiivselt. Millist tarkvaraüsteemi soovitab Joel Spolsky projektiplaani koostamiseks kasutada? - Evidence Based Scheduling FUNKTSIONAALSED KEELED: Funktsionaalseid keeli saab jämedalt jagada kahte liiki: puhtad ja kombineeritud. Puhtas funktsionaalses keeles -- Haskell, Hope, Miranda, FP -- ei ole programmeerijal peale funktsioonide defneerimise ja sisseehitatud baasfunktsioonide (aritmeetika, loendid jms) mingeid lisavahendeid -- kõik
terve süsteemi ümber tegema. Tarkvaraarhitektuuri disainimeks ei ole universaalset, aksepteeritud protsessi. Iga juhtum on erinev, iga süsteem ja klient on erinevad. Iga protsess tuleb valida või kohandata vastavalt parasjagu valitsevatele olukordadele. Mõned protsessid: • ADD – Attribute Driven Design - rekursiivne protsess. Töötati välja Carnegie Mellon Ülikooli pool. Koosneb kahest osast. Neid kahte osasid rekursiivselt kogu aeg ketratakse. o 1. osa – taktika. § Kontrolli, et nõuded oleks piisavad. § Vali süsteemi osa, mida komponentideks lahutada. § Identifitseeri arhitektuuri juhtivad nõuded. § Vali kontseptsioon, mis täidab juhtivad nõuded. o 2. osa – dokumenteerimine. § Algväärtusta arhitektuuri elemendid ja jaota vastutused.
massiiv (näiteks a[1]=2; a[2]=20; a[3]=15; y=2; x=a[y]+a[1]+3;) Avaldised: näiteks x = (y*2) – (5+x); Elementaarsed juhtkonstruktsioonid: valik: if ... then ... else tsükkel: while(x<10) x=x+1; Funktsioonid: defineerime: int kuup(int x) { return x * x * x} kasutame: x = kuup(1+kuup(3))+kuup(y); kasutame rekursiivselt: int fact(int x) { if (x<=0) return 1; else return x*(fact(x-1)); } Keeled: näited lisavõimalustest eri keeltes Kiired bitioperatsioonid, otsepöördumine mälu kallale: C Keerulisemad andmetüübid: listid, hash tabelid jne: Lisp, Python, Javascript Erikonstruktsioonid stringitöötluseks: Perl, PHP Objektid: C++, Java, C#, Python, Lisp Moodulid (enamasti ühendatud objektidega): C++, Java, C#
6 5-7 2 MDNK leidmiseks: 3 7 6-7 1 1. Grupeerida 1de piirkonna arvud tabelisektsioonidesse kokku vastavalt 4. Korrata rekursiivselt eelmist sammu seni kuni võimalik — viimasel nende indeksitele: kleepimisel saadud intervallide edasikleepimiseks veelgi suuremateks. index 1de pk (käesolevas näites ei saa enam 4-seid intervalle kokku kleepida 8-steks) 0 0 Kleepimisel moodustunud korduvaid intervalle võib ignoreerida ehk jätta
hostinimi. * MX-kirje – nimeks hostinimi ja väärtuseks sellele hostinimele vastav mailiserver. DNS-i päringu ja vastuse sõnumid on samas formaadis (vt. joonist), neid eristatakse ühebitise flagi abil – päringu puhul 0 ja vastuse puhul 1. Esimesed 12 baiti on mitme väljaga päis, siis 16-bitine päring, mis jäetakse ka päringu vastusesse, vastus, info autoritatiivsete serverite kohta ja lisainfo. Flagidega eristatakse ka soovi teha päring rekursiivselt, rekursiooni võimalikkust ning autoritatiivset päringut. 20. Töökindel andmeedastus Töökindel andmeedastus on oluline transpordi-, rakendus- ja kanalikihi jaoks. On üks olulisemaid probleeme võrgunduses üldse. Töökindel kanal tagab selle, et ükski bitt ei muunduks või ei läheks kaduma ning bittide järjekord jääks samaks. Töökindel andmeedastusprotokoll (reliable data transfer protocol) peab läbi viima andmeedastuse kanalisse ja andmed kanalist vastu võtma
Kui n on naturaalarv, siis S(n) := n ∪ {n} olgu naturaalarvule n järgnev naturaalarv. Me tähistame 2 := S(1) = {∅}, 3 := S(2) = {∅, {∅}}, 4 := S(3) = {∅, {∅}, {∅, {∅}}} jne. Kõigi ülaltoodud konstruktsiooni põhjal saadud hulkade hulka tähistame sümboliga N ning tema elemente nimetame naturaalarvudeks (natural numbers, натуральные числа). Järgnevalt viime naturaalarvude hulka sisse liitmise ja korrutamise. See toimub rekursiivselt: nõuame, et a+1 = S(a) ja a+S(b) = S(a+b), kus a, b ∈ N. Korrutamine: a·1 = a ja a·S(b) = a+(a·b). Kontroll näitab, et liitmine ja korrutamine on assotsiatiivsed, kommutatiivsed ning on seotud distributiivsuse võrdustega. Defineerime veel, et a < b ⇔ ∃c ∈ N : a+c = b. Saadud seos < rahuldab trihhotoomia, transitiivsuse, liitmise ja korrutamise monotoonsuse nõudeid. Märkus. Sageli defineeritakse hoopis 0 = ∅ ning viiakse läbi ülaltoodud konstruktsioon, tulemuseks
pakub •Primitiivsed andmetüübid: .int, char etc (näiteks: 1 ja –3 on int-id, „c. ja „a. on char-id) .string (näiteks “aaa123bb”) .massiiv (näiteks a[1]=2; a[2]=20; a[3]=15; y=2; x=a[y]+a[1]+3;) •Avaldised: .näiteks x = (y*2) –(5+x); •Elementaarsed juhtkonstruktsioonid: .valik: if ... then ... else .tsükkel: while(x<10) x=x+1; •Funktsioonid: .defineerime: int kuup(int x) { return x * x * x} .kasutame: x = kuup(1+kuup(3))+kuup(y); .kasutame rekursiivselt: int fact(int x) { if (x<=0) return 1; else return x*(fact(x-1)); } ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 10 Sumto MIPS-I (SGI spinoff) assembleris •Argumendid registritesse $4 •Resultaat registrisse $2 sumto: ; Register $4 on n li $3, 0 ; Register $3 on summa li $2, 0 ; Register $2 on i blt $4, $0, L3 ; Kui n<0 mine L3 L5: addu $3, $3, $2 ; sum = sum + i addu $2, $2, 1 ; i = i + 1 ble $2, $4, L5 ; Kui i<=n mine L5 L3: move $2, $3 ; Sum sisaldab resultaati.
Kordjajate cj leidmiseks tuleb uldjuhul ¨ lahendada vastav ~ lintmaatriksiga lineaarvorrandis usteem. ¨ ¨ G. Tamberg (TTU) YMM3731 Matemaatilne analu¨ us ¨ I 11 / 17 Splainid B-splainid B-splainid defineeritakse traditsiooniliselt rekursiivselt, kasutades konvolutsiooni B := B -1 B 0 ( 1), st kujul -1 -1 B (t) := (B B 0 )(t) = B (t - u)B 0 (u)du. R Siin B 0 defineeritakse traditsiooniliselt loigu ~ [-1/2, 1/2] karakteristliku funktsioonina [-1/2,1/2] kujul 1
annaabi.ee 
