Diskrečioji matematika

1. Rekursyviosios funkcijos. Mūsų funkcijų apibrėžimų srities ir reikšmių aibė bus IN+ = {0,1,2,3,…}. Jei moku apskaičiuoti f-ją f-ja rekursyvioji. Apibrėžimas: Rekusyvioji f-ja – bazinės f-jos ir gautos naudojant 3 operatorius. Bazinės f-jos = 0, suc(x) (s(x); x+1), prip (prip(x1, ..., xp)). Operatoriai: 1. kompozicijos operatorius. f(x1, .., xn); q1, ... ,qn } f (q1, ..,qn)  naujoji f-ja. Pvz.: s(x) -> s(s(x)) => x+2 ir taip galima gauti x+n. 2. Primityviosios rekursijos operatorius. F-ja f(x1, .. xn) gauta primityvios rekursijos operatoriumi iš 2-jų, žinomų, apskaičiuojamų f-jų, taip pat apskaičiuojama; Duota: q (x1, .. xn-1); h (x1, ... xn, xn+1); tai f (x1, .. xn-1,0) = q (x1, .. xn-1) ir f (x1, .. xn-1, y+1) = h (x1, ... xn-1, y , f (x1, .. xn-1, y); => f-jos f reikšmė apibrėžta perjos pačios reikšmę, grįžus 1 žingniu atgal. Apibrėžimas: Pati mažiausia aibė, kuriai priklauso bazinės funkcijos ir kuri uždara kompozicijos bei primityvios rekursijos atžvilgiu, vadinama primityvios rekursijos f-jų aibė. Žymėsime PR. Šiai aibei priklausančios f- jos yra apibrėžtos; Pvz.: 1. x+y  PR – įrodyti; f(x,y) , q(x); h(x,y,z); f (x,0) = q(x); f(x,y+1) = h(x,y,f (x,y)); q(x) = ? ; h (x,y,z) = ? } -> pr11(x) ; ir x + (y+1) = (x+y) +1 => pr33(x, y, s(z)) = h(x,y,z).; t.y. x+ (y+1) = pr33(x, y, s(x+y)) = s (x+y) = x+y+1./\ (f- ja + (x,y) = x+y); +(x,y) = R (pr11(x), pr33(x, y, s(z)); PR schema f-jai: f(x) -> h(x,y) => f(0) = c, f(y+1) = h (y, f(y)). 2. x*y PR – įrodyti; f(x,y); g(x); h(x,y,z); f(x,s(0))=g(x); f(x,y+1)= h(x,y,f(x,y)); f(x,0)=0  g(x)=0  pr 22 (x,0); x(y+1)= x*y+x; h(x,y,z {vietoj z yrasom apacioj xy})= pr 22 (y,z+x); ir (x,y+1)= pr 22 (y,xy+x)=xy+x ; 3. xy ; x0 =1 pr 22 (x,s(0))  g(x,0); xy+1 =x y xy *x pr 22 (y,z*x)  h(x,y,z); Charakteringoji aibės f-ja N+ ; A  N+ XA (x)= {1, x A ; 0, x ne  A}; Aibė vadinama primityviai rekursiška jei jos XA yra primityviai rekursiškas; 1. sgx  PR sgx= {1, jei x>0 ; 0, jei x=0}; f(0)=0; f(y+1)=h(y,f(y)); h(x,y)= pr33 (x,y, s(0)) ; 2. sg x = { 1, jei x=0 ; 0, jei x>0; c=s(0); h(x,y) = pr33(x, y, 0); 3. xּ- y = { x-y, jei x>y; 0, jei x ≤ y; a) x ּ- 1 PR; c=0; h(x,y) = pr12(x, y); b) xּ- y; g(x)=?; f(x,y); h(x,y,z)=?; f(x ,y+1)= h(x,y ,f(x,y)); g(x)= pr11 (x); h(x,y,z) = pr33 (x,y,x ּ-1); 4. | x-y|  PR; |x-y|= (xּ- y)+( yּ- x) 2. Minimizacijos operatorius. g(x1, .. ,xn-1 ,y)= xn ; f(x1, ... xn)= My (tipo miu raide)(g(x1, .. ,xn-1 ,y)= xn); mažiausio radimo paieškos algoritmas; g(x1, .. ,xn-1 ,0)= xn ? ; g(x1, .. ,xn-1 ,1)= xn ? ; g(x1, .. ,xn-1 ,2)= xn ? ; ............... ; rekursyviųjų = DR (dalinai rekursinių) f-jų klasė: klasė f-jų, gaunamų iš bazinių f-jų 3 operatoriais.; dalinė f-ja : y= f(x) : neapibrėžta su kai kuriomis argumento reikšmėmis (jei y neegzistuoja arba iki jo neprieisim pagal paieškos algoritmą) ; Pvz.: 1. x-y= Mz (tipo miu raide) (y+z=z) 2. f(x)=My (miu) (y- (x+1)=0); neapibrėžta!!! Imam x=4 ir y-5=0 nerasim y! BR- bendrarekursinės f-jos PRBRDR 3. Baigtinumo problema. Nagrinejame vienajuostes determinuotas standartines. Tiuring masinas. A = {0,1,b,*,2,….,9,δ,=,(,),k,d,n, ,}; δ (q0,1) = (q2 ,0,D) (……..) δ (qi ,0) = (qj,1,K).;Tokia masina galime užrašyti kaip žodį abėcėlėje A.; Σ= {a1……am} Σ*- visų galimų žodžių abc. Σ aibė; Taigi A* - skaičioji. Visų Turing mašinų aibė yra  A*, ji yra skaičioji. Išrašome jas visas : T1 , T2 , ... , Tn , ... šių mašinų apsk. Funkcijos: 1 , 2 , .... , n , ...kiekviena funfcija turi be galo daug n y = x + 1;y = x + 3 – 2; baigtinumo problema : ( m, n ) – skaciu pora; m (n) A Pažymim L=t, B=k Aksm 2.2 (A&B)->B Aksm 2.3 (A&B)->((A->C)->(A->(B&C))) p ┐p p, q pVq p, q p&q                      p&q≡q A&B≡B 2.1 B->A nėra t.t 2.2 B->B t.t 2.3 (A->B)-> ((A->C)-> (A->C)) t.t I uždav. p&q≡p A&B≡A 2.1A->A 2.3(A->B)-> ((A->C)-> (A->A)) II uždav 2.1 ->teisinga 2.2->teisinga Įrodyti 4.1 (A&B)->( ┐B->┐A) 4.2 A->┐┐A 4.3┐┐A->A 4.1 4.2 4.3 p ┐p p ┐p p ┐p             Bendrarekursinės funkcijos Gautos iš bazinių (0,S(x), perii ir operatorių – kompozicijos, prim. Rekursijos, minimizacijos. BR f-jos visur apibrėžtos funkcijos. B(x,y) sąrašys(predikatas) Turim aibę A; B(x,y) x,y A Šis sąryšis: 1 refleksyvus su visais x  A, B(x,x)=t 2 tranzityvus su visais x, y, z (B(x,y)&B(y,z))->B(x,z) 3 antisimetrinis x, yA (B(x,y)&B(y,x))->x=y B(x,y) Šis sąryšis vadinamas tvarkos sąryšiu. Jei x,y

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!