T.P.D.K. - Tanuljunk Progmodra De Kurvagyorsan

[HÓNAPZÉHÁ] Edition

Eloszo

Az Edition cim itt eleg sokat mondo. Kurvagyorsban megerteni sok mindent Nekem is, es ha megkedveltetek ezeket a leirasokat TDDK-tol mondjuk (dimat ehhez a targyhoz ugyis kell), akkor Nektek is. Ajanlom Fóthi Ákos honlapjat, es kifejezetten a konyvet a relacioktol kezdve. Picit amugy lesz neha betekinto programozas fele is, holott szerintem ez egy matematikai targy, de maradjunk csak szemleletesek (a jo ertelemben). Amugy azt is ajanlom, hogy amikor sok kep-oskep innen-oda ez-erre kepez cuccos van, rajzolgassunk. Nagyon sokat segit.

/!\ Disclaimer /!\

Nagyon fontos, hogy az itt leirtak CSAK a megertest segitik. Sok helyen csak elmagyarazok dolgokat, es nem irom le formalisan, meg csak ugy megjegyzem, hogy "ja ennek ez a jele". Erosen ajanlom, hogy ha valaki nem tud formalizalni dolgokat, nem tudja a jeloleseket, akkor miutan megert itt egy temat, azonnal nezze meg hozza a formalizalast.

Tartalomjegyzek

Ha valami [WiP], akkor eppen dolgozok rajta.
Ha valami [SOONish], akkor meg el sem kedztem.
Ha valami [nFIX], akkor reszemrol kesz, de nem erzem teljesnek.
Az ilyen fejezetekben a linkek nem mindig mukodnek.
  1. Alapfogalmak
  2. Specifikacio
  3. Specifikacio irasa
  4. Levezetesi szabalyok
  5. Tipus es tipusspecifikacio
  6. Gyakorlat

Alapfogalmak

Kezdjuk pici dimat visszatekintovel. Nevezetesen relaciokkal (aka halmazok waah). Egyszeruen megfogalmazva, egy (biner) realcio rendezett parok halmaza. Specko esetben muvelet, megjobban specko esetben fuggveny. Alapjaraton egy relacio barhogy lehet definialva, nincs megkotes mint fuggvenyeknel mondjuk az egy-egyertelmuseg. Altalaban igy van irva: R:AxB, vagyis R relacio A es B kozt van ertelmezve, A halmazrol B-re kepez le, AxB direkt szorzat elemeit (rendezett parok) tartalmazza. Ezeket illettuk dimaton mindenfele nevekkel, mint pl tranzitiv, dichotom, satobbi. Volt ket igen nevezetes eset, az ekvivalencia es rendezes. Ide annyira nem fontosak, de szerintem igen latvanyosak, es ezeken keresztul marha konnyu megerteni relaciok adott halmazra kifejtett hatasait. Ami viszont mar fontosabb lesz.
Relaciokhoz kapcsolodo fogalmak roviden. R:AxB eseten A a lekepezendo ertekek halmaza, B a kephalmaz. RGO, ha egy A beli elem R szerinti kepet nezzuk, az az lesz amit R relacioval csinalunk belole. Lehet egy, lehet tobb. Ha minden elemnek legfeljebb egy kepe van, akkor a relacio determinisztikus. Ha csak egy, akkor fuggveny. Visszafele ugyanez, ha B-bol elindulok, es visszafele nezem a relaciot, vagyis, hogy mibol kaptam az adott B beli elemet, az a (kep)elem oskepe (vagy inverze). Leszukites holt ugyanaz mint siman halmazoknal dimatra. Megjegyzem egy elem kepe, oskepe es hasonlok, MINDIG halmazok. Meg ha nem kepez sehova, vagy csak egy elemre (ures halmaz, egy elemu halmaz) akkor is.
Johet az uj anyag, de meg abbol is az alapfogalmak, amik nelkul elhasalsz. Eloszor is, allapotter. Valojaban barmilyen halmaz, csak igy nevezzuk el. Lehetnek az elemei rendezett parok is, amitol gyakorlatilag ez egy relacio, de tekintsunk ra halmazkent. Ez jobban fogja segiteni a gondolkodasmodot (ugyanakkor a masik iranyba eleg durva dolgok lesznek mindjart). Ebben a halmazban vannak az elemek, amikkel a programunk dolgozhat. Errol majd mindjart. Annyit kell meg tudni, hogy ide van ket nagy altalanossagban halmazos fogalom. Az egyik, ha az allapotterunk jele A, akkor A* (A lezartja) az A elemeibol kepezheto barmilyen hosszu sorozatok halmaza. Mint fonyanal. A** ugyanez, de akar vegtelen hosszu sorozatok. (Szoval belegondolva, ha A relacio, akkor minden letezo lepessorozat (pl egy graf gecire sok bejarasa, ha a rendezett parok egy graf csucsai). Programozasnal a specifikaciokban lathatunk ilyent, es tenylegesen ugyanarrol a fogalomrol beszelunk. Kesobb majd parameterezzuk is (valtozok).
Ha egy relaciot igy irok fel: F⊆AxA, ahol A az allapotter, akkor F egy feladat. Vagyis A elemeibol kepzett rendezett parosok halmaza. Ennek kb az a lenyege, hogy ha van csomo (a1,a2) parosom, akkor a "feladat", hogy minden a1-bol eljussak egy hozza tartozo a2-be. Vagyis ha tudunk csinalni egy relaciot, ami pont ezt csinalja, akkor megoldhatjuk a feladatot. Egy program pont ezt tudja. Ez is egy relacio, nevezetesen P:AxA**. Ezt a jelolest mindig mocskosul osszekeverem, de most gondoljuk at egyutt F feladat elemei (a1,a2) parok. Ha adott a1 tobb parban is szerepel, akkor tobb dologba is eljuthat. Ha a2 van tobb parban, az csak annyit jelent, hogy tobbfelekeppen is elerjuk. Vagyis azt csinalom, hogy vegigmegyek az elemeken egyesevel, es megnezem hova lehet beloluk eljutni. Egyesevel az elemeket. Egyszerre egy darabot. Vagyis nem egy sorozatot beloluk, csak egyet. Igy a program lekepezendo elemeinek halmaza is egy darab elemeket tartalmazhat P:AxA**. Egy elem tobb, akar vegtelen sok elembe kepez le, rgo P:AxA**.
Egy program definicioja kicsit bovebb azert. Nevezetesen harom feltetel van, es mindnek az allapotterhez van koze. Eloszor is, es mar igy is jeloltem (rohadtul lehetne tartalmzas is, es szoktak is ugy irni), P:AxA**. Nem ⊆, hanem :. Vagyis P ertelmezesi tartomanya (lekepezendo elemek halmaza), az muszaj, hogy megegyezzen az allapotterrel. Minden elemmel tudjon csinalni valamit (es ne szalljon el tole). Masodszor, ugye minden elem kepe sorozat. Az a fontos, hogy ezek a sorozatok ne legyenek vegtelen hosszuak, illetve harmadszor, hogy mindig ugyanaz legyen az elso elemuk, mint amibol lepekezem oket (vagyis uresek sem lehetnek).
A kovetkezo fogalom kezd mar bonyolultabb lenni, de meg mindig kovetheto. Programfuggveny. A jele p(x), ahol x a vizsgalt program. A betuzesemnel maradva ez p(P). Egy pillanatra kanyarodjunk vissza, hogy mire is kell ez? Ugye egy feladatot akartunk megoldani. Kell az, hogy minden elembol "el tudjunk indulni" ami a feladat rendezett parainak elso elemei kozt van, illetve tudnunk kell, hogy mindbol el jutunk-e oda, ahova kell. Persze az allapotter is legyen ugyanaz. Vagyis a programrol tudni kell, hogy a megfelelo pontokbol elindul-e, es oda er-e ahova a feladat is. Erre van a programfuggveny. Persze ez is egy relacio. p(P)⊆AxA. Az elso A, hogy HONNAN, a masik, hogy HOVA jutunk. Vagyis az ertelmezesi tartomany az olyan P beli elemek, amikbol el tudunk indulni, es nem szallunk el (nincs vegtelen sorozat). A kephalmaz pedig a programbeli sorozatok utolso elemei. Vagyis ha volt egy P beli s elemem, es s P szerinti kepe s,c,s,s,k, akkor p(P) eleme (s,k) lesz, vagyis p(P)(s) = {k} (s p(P) szerinti kepe a k-t tartalmazo egy elemu halmaz). Ha ket kulonbozo program programfuggvenye ugyanaz, akkor ugyanazt csinaljak. Vagyis ugyanazt a feladatot oldjak meg.
Na fogalmazzuk meg vegre a megoldast. Ennek ket feltetele van, amiket igazabol mar atgondoltunk. Ugye az kellett, hogy P program minden elembol el tudjon indulni elszallas nelkul, amibol F feladat is. Az nem baj, ha tobbol, de annyibol muszaj. Vagyis F ertelmezesi tartomanya legyen p(P) ertelmezesi tartomanyanak reszhalmaza. Masodszor pedig az kellett, hogy (mivel egy elembol tobbfele is eljuthatunk), minden olyan elem, ahova P eljut, oda F is jusson el. Az nem baj, ha nem erjuk el az osszes F kepe beli elemet igy, de nem fogunk "kilepni" az elvart ertekek halmazarol. Azaz barmely f F ertelemesi tartomanyabeli elemre p(P)(f) legyen F(f) reszhalmaza (ne jussak el tobb helyre, mint a feladat).
A vegere nehany nevezetes program. SKIP: barmely elemhez az egy hosszu csak azt az elemet tartalmazo sorozatot rendeli, azaz helybenhagyja az elemet. ABORT: barmely elemre hamisat ad vissza (ha jol emlekszem).

Specifikacio

Jobb esetben eddig minden, meg ha picit nyakatekerten is van megfogalmazva, de kovetheto volt jozan paraszti esszel is. Most elkezdunk majd belevetodni a tetelek vilagaba, es az abszraktabb gondolatok koze. Az a jo hir ugyanakkor, hogy ezek Nekunk fognak segiteni. Ha egy nagyobbacska feladatot vizsgaltunk, marha sokaig tarthat megnezni, hogy egy program megoldja-e. Ezt leroviditendo lesz ket modszerunk is. Felig-meddig. Illetve parameterezni is fogunk vegre. Megjegyzem minden konnyebb gyakorlatban, de ha erted is mit csinalsz, az dupla olyan jo.
A programfuggveny utani legbonyolultabban atlathato fogalom szerintem a leggyengebb elofeltetel, szoval kezdjuk ezzel. Amugy is ez a fogalom majdhogynem a programfuggvenyt helyettesiti. Ha van egy A allapotterem es azon P⊆AxA** programom, valamint egy R:AxL logikai relacio (L a logikai ertekek (ketelemu) halmaza). A leggyengebb elofeltetel szinten egy relacio, most kifejezetten fuggveny (vagyis egy-egyertelmu): lf(P,R):AxL. Altalaban az igazsaghalmazaval jellemezzuk. Az igazsaghalmaz az olyan ertekek halmaza, amik csak es kizarolag az IGAZ logikai ertekbe kepeznek le. A jelolese felso egesz resz, de en most ceil() jelet fogom hasznalni. Szoval ceil(lf(P,R)) az olyan elemek halmaza lesz, ahonnan a program nem szall el, es ha fogom a pontokat ahova eljutnak, akkor ezekre R csak es kizarolag IGAZ-at ad. Kicsit formalisabban az olyan A beli k elemek, hogy k p(P) ertelmezesi tartomanyaban van, es p(P)(k) ceil(R) reszhalmaza. Ez teljesen ugyanaz, mintha fognam p(P) inverzet, es meghivnam ceil(R) elemeire. Gondoljuk at. ceil(R) elemei azok az A beli elemek, amikre R csak es kizarolag IGAZ ertekre kepez. p(P) az volt, hogy az olyan elemekbol, ahonnan nem szallunk el, vegul hova jutunk. Azaz az inverze minden olyan elemet megad, ahonnan nem szalltunk el. Szoval minden olyan elem, ahonnan nem szalltunk el, de csak ugy, hogy R egyebkent is igazat adott. Igy talan kicsit erthetobb. Megparasztiasabban: R jo es P el tudott indulni. Szoval itt ceil(R) helyettesiti p(P) kephalmazat, kb.
A masik megkozelites arra van, hogy ha F egy ponthoz rendel sok mindent, akkor ezeket megint fajdalmasan sokaig tart megnezegetni. Ezert megprobaljuk oket osszesuriteni picit. Ez lesz a parameterezes. Illetve kicsit megint ki tudunk tekinteni programozas fele, es szerintem kozelitsuk is meg igy. Az allapotteren kivul van ugye elofeltetel, es utofeltetel. Az elobbi azt mondja meg, hogy mikor hasznalhatod megfeleloen az adott programot, utobbi pedig azt, hogy mikor futott is le jol. Ez nalunk kb ugy fordul le, hogy a feladatban megfelelo rendezett parok vannak, ket szempontbol. De eloszor egy uj fogalom, a parameterter. Egyelore maradjunk annyiban, hogy van egy F⊆AxA feladatunk. Ha tudok csinalni egy koztes B halmazt, hogy egy F1 o F2 kompozicio pont ugyanazt csinalja mint F, de F1⊆AxB es F2⊆BxA, akkor B parameterhalmaz, az elemei parameterek. Visszatekintve, ha mukodik a kompozicio, vagyis egy a1 elembol kiindulva eljutok egy b elembe, ez az elofeltetel. Illeszkedek a parameterhalmazhoz, azaz jol probalom egyaltalan elkezdeni a dolgot (meghivni az eljarast). Ha utana b-bol egy a2 elembe jutok, ahonnan F szerint a1 is eljutna, az az utofeltetel. Hogy nem csak el tudtam indulni, de megfeleloen is erkeztem. Azaz jol futott le az eljaras.
Most jon egy nagyon fontos es hasznos dolog, plusz a parameterezes alkalmazasa. A specifikacio tetele. Ez elegseges feltetelt ad arra, hogy egy program megold egy feladatot. Na nezzuk. A az allapotter, P a programunk, F = F1 o F2 a feladat, B a parameterter, Q es R pedig logikai fuggvenyek (A-rol kepeznek persze). Q azt mondja meg, hogy egy A beli elembol F1 lekepez-e B beli elemre, R pedig azt, hogy mely A beli elemek erhetoek el F2-n keresztul. Ekkor megnezzuk az osszes parametert, es ha Q(parameter) igaz, akkor lf(P,R(parameter)) is igaz (persze az osszesre), es ekkor P megoldja F-et. Magyaran szolva: fogok egy parametert. Legyen b. Ha b-re Q igazat ad (benne van ceil(Q)-ban), azaz van olyan A beli elem, amit F1 erre a b parameterre kepezunk le, akkor megnezem, hogy ceil(lf(P,R(b)) is igaz-e. Ez ugye az volt, hogy R(b) igazat ad, szoval van A beli ertek, amire F2 ezt a b elemet kepezi le, es P nem szall el ugyanebbol az A beli elembol. Gyakorlatilag felirjuk az osszes parameter Q es R szerinti igazsaghalmazat, illetve az olyan P beli elemeket, ahol nem szallunk el, es R is igaz (ezt irtuk fel pont az elobb), aztan megnezzuk, hogy ez tenyleg kovetkezik-e a felirt Q-bol. A kovetkezes azt jelenti, hogy ha G es H logikai fuggvenyek, es ceil(G)⊆ceil(H), akkor G kovetkezik H-bol (G mindenhol igaz, ahol H is).

Specifikacio irasa

Korabban lattuk a specifikacio tetelet. Egy specifikacio reszei ugye az allapotter (A), a parameterter (B) ami gyakorlatilag a feladat (F), valamint egy elofeltetel (Q) es egy utofeltetel (R). Specifikacio irasakor ezt a negy dolgot kell megirni. Az allapotter tobbnyire adja magat. Minden bemeneti es kimeneti adat. A parameterter kb ugyanaz, mint a bemeneti adatok. Az elofeltetel altalaban csak a progrol ismert x = x' meg ilyesmi dolgok, de az invarians felteteleket is ide irhatjuk. Az utofeltetel egy logikai allitas, ami azt irja le, mit varnank el egy programtol, ami ez a speci alapjan mukodik. Ha a bemeneti adatokon nem valtoztatunk, akkor mindig Q ^ (valami) kinezetu, ha a bemeneti adat is valtozik, pl egy szekvencialis input file, amibol megesszuk a sorokat beolvasas kozben, vagy csak egy szimple logikai ertek negacioja, ekkor Q R-be valo beagyazasa nagy hiba, es ekkor az invarianst, ha meg utana is relevans, kulon oda kell tenni. Gyakorlatban erdemes abrat is rajzolni A -F1-> B -F2-> A modon, egy vagy ket peldat bele is irva. Ugyanis az egyetlen trukkos resze az egesznek, hogy mivel a parameterternek altalaban mas elemei vannak, amint az allapotternek, igy nem mindegy, hogyan kepezel ra. Peldaul volt ket bemeneti adat, es egy kimeneti, mondjuk ket szam, es az osszeguk. Ekkor A = N x N x N, ahol az N-ek sorra a, b, es sum. De B ugye csak N x N, amik a' es b'. Mikor meg F1-en keresztul kepezel le, mindegy, hogy sum erteke micsoda. De mikor mar F2-vel ismet A-ba kepezel, csak ugy mehet, hogy sum az a+b legyen.

Levezetesi szabalyok

Ezek lesznek a szekvenciara, ciklusra, es elagazsra. De elotte egy kitekinto: Feltetelek. A ciklus felepitese ugye egy feltetel, valamint egy cilusmag. Egy elagazasban annyi feltetel, ahany fele agazik szet, es mindre egy-egy kulon program, ami adott feltetel teljesulesekor lefut. Egy feltetel egy logikai fuggveny, ami az allapotterrol kepez le. Jellemzoen az igazsaghalmazukkal adjuk meg, es PI-vel jeloljuk. Fontos, hogy ha mondjuk van egy ciklusom, DO = (PI,S), ahol PI a feltetel, S pedig a ciklusmagban lefuto program, lehet, hogy DO es S programfuggvenye rohadtul kulonbozo. Mondjuk a program barmely ket termeszetes szamot ossze tudna adni, de a ciklus csak akkor fut le, ha a valtozoja < 10.
A levezetesi szabalyok arra valok, hogy ha van egy programom, altalaban strukival megadva, es elkezdened az eddig ismert modszerekkel megvizsgalni - feladat megoldasanak definicioa, specifikacio tetele -, kiderulne, hogy sehova sem lehet jutni. DE! Ekkor fogod a relevans levezetesi szabalyt, es mindjart megoldhato lesz. Azert jo, hogy strukival van megadva a program, mert azon ertelemszeruen latszik, hogy milyen levezetesi szabaly kell. Megjegyzem a leveztesi szabaly onmagaban nem azt mondja, hogy megodja a program a feladatot, hanem hogy Q => lf(S,R), ez pedig a specifikacio tetele miatt mondja ki, hogy megoldja. Ha nem jonne ki semmi, ugyan ugy nem tudnank azt mondani, hogy nem oldja meg, mert errol nem mond semmit a tetel.
A legegyszerubb az a szekvencia levezetesi szabalya. A strukin ez ugy latszik meg, hogy meg tudod fogni, es ket (vagy tobb) reszre bontani a program menetet. Pl egy ertekadas utan egy ciklus. Itt ugy kepzeled akkor el, mintha ket kulon program lenne, es a "toresponthoz" elkepzelsz egy uj elofeltetelt, ami ~az elotte levo reszek utofeltetele. Ha az eredeti elofeltetel Q volt, ez pedig Q', akkor a levezetesi szabalynak ket resze van: Q => lf(S1,Q') es Q' => lf(S2,R). Ezekbol egyutt: Q => lf(S,R). S1 es S2 itt a "torespont" elotti es utani programreszek. Ha mondjuk ertekadas volt az elso parancs, akkor ugy lesz belole Q', hogy "elvegezzuk" az ertekadast. Ez nagy altalanossagban annyit tesz, hogy Q' = Q. DE! Lehet, hogy kell tipusellenorzesi felteteleket irni, pl ha van x, y egesz szamunk, es y := x/2 az ertekadas. Ekkor ki KELL kotni, hogy y egesz szam marad. Vagyis Q' = Q ^ "y egesz szam", avagy, hogy x/2 az. Ez igaz minden egyes levezetesi szabalyra, nem csak szekvencaira.
Ciklus levezetese. Ez egyszerre a legnehezebb es legkonnyebb is. Ennek van a leghosszabb definicioja, de a legkonnyebb belatasa. Ot resze van, amibol kettot a gyakorlatban ossze szoktunk vonni (4 es 5).
  1. Q => P
  2. P ^ ¬PI => R
  3. P ^ PI => t > 0
  4. P ^ PI => lf(S0,P)
  5. P ^ PI ^ t = t' => lf(S0,t < t')
Ha ezek mind teljesulnek, akkor Q => lf(S0,R). Itt ugye Q es R az elo- es utofeltetel, PI a ciklus feltetele, S0 a ciklusmag, P egy lgokai fuggveny, ami a strukival egyutt meg van adva, t pedig a ciklusvaltozo (egy sima szamlalo). Igy a 3. feltetelben t > 0 annyit tesz, hogy meg nem ertuk el a ciklus veget, az 5. feltetel pedig onmagaban annyit tesz, a ciklus le tudott futni legalabb egyszer az adott t' erteku ciklusvaltozoval, de az utana csokkent. A levezetes belatasa rohadtul egyszeru. Egy az egybe behelyettesitjuk a betuk es jelek helyett a logikai allitasokat, mint Q, R, P es PI. FIGYELJUNK RA ODA, HOGY HA EZ EGY SZEKVENCIA KOZEPEN VAN PL, AKKOR Q AZ OTTANI Q'!. Hasonloan, ha utana megint lenne egy szekvencia miatti elagazas, akkor R az a Q'' lenne. Naszoval behyelttesitunk, es lesz sok "ebbol kvoetkezik ez" formulank. Belatjuk, hogy tenyleg kijon, a kovetkezo modon: Ha egy dolog a nyil mindket oldalan szerepel, az trivialisan teljesul. Ha mondjuk az egyik oldalon az van, hogy x > 0, es ebbol az kovetkezne, hogy x pozitiv, akkor ezt leirjuk, es ez is megvan. Ha mindenre talaltunk ilyent, ami a JOBB oldalon van, akkor keszen is vagyunk, es johet a kovetkezo sor. Egyedul az olyan sorok okozhatnak fejfajast, amiben t megjelenik, de ahogy P, ugy t is meg kellett adva legyen valami olyan modon, amit itt kezelni lehet.
Az elagazas levezetesi szabalya konnyu, de maceras. Van csomo PI, amik az egyes agak feltetelei, es sok S amik az egyes agak programjai. Errol erdemes emgnezni egy abrat, es rogton ertheto. Aztan persze van Q es R. Ket dolgot kell belatni. Eloszor is, hogy Q => "legalabb egy feltetel teljesul". Ez nagy UNIO PIi jeloles szokott lenni, ahol i az osszes feltetelen vegigmegy. A masik, hogy minden feltetlre: Q ^ PIi => lf(Si). Ha ez mind teljesul, akkor Q => lf(IF,R). Erdemes itt megfigyelni, hogy mig a ciklusnal vegul lf(S0,R) volt, azaz a ciklusmagra lattuk be, itt az egesz elagazasra. Itt is figyeljunk ra, hogy barmelyik S tartalmazhat ertekadast, es ilyenkor tipusellenorzest is kell csinalni.

Tipus es tipusspecifikacio

Egy tipus egy rendezett harmas. (rho,I,$). $ itt vastag vonalas S lenne, mint a valos szamok halmazat jelolo R. rho egy E* x T relacio. E egy adott vagy valaszthato halmaz, ezek az elemi tipusertekek. T szinten egy adott halmaz. I egy E*-rol kepezo logikai fuggveny. $ az pedig programok egy halmaza. A feladat olyan rho es I irasa, hogy a tipus reprezentacio helyes legyen. Akkor helyes, ha I igazsaghalmazanak rho szerinti kepe pontosan T. Legalabbis ez az egyik fele a dolognak. A masik, hogy a tipussepcifikacionak is feleljen meg. Egy tipusspecifikacio is egy harmas. (H, Is,F), ahol F vastag szaru lenne. H egy halmaz (ez altalaban a tipus T-je), ennek az elemeit akarjuk reprezentalni majd valami tipussal. Is egy errol kepezo logikai fuggveny. F pedig feladatok egy halmaza. Ha minden feladatra letezik egy $ beli program, ami "rho-n keresztul megoldja", es persze a reprezentacio helyes, akkor a tipus megfelel a tipusspecifikacionak.
rho es I megalkotasa olyasmi szokott lenni, hogy eloszor I-vel valahogy leszukitjuk az E* beli sorozatokat nekunk tetszoen. Mondjuk ha a tipus az lenne, hogy az egesz egesz szamok halmazat alkossuk meg, es H (ami valszeg T) az a pozitiv egesz szamok halmaza, akkor I lehetne az, hogy csak a ketto hosszu sorozatokat nezzuk. Ekkor rho olyasmi, hogy ha az elso elem 2, akkor a masodik elem ertekere kepez le, ha 1, akkor a masodik elem ellentettjere. Igy minden egyes eleme megvan, ami nem 0. De az is kell, mert az is az egesz szamok eleme. Igy mondjuk I-t egeszitsuk ki a 0 hosszu sorozattal, ami reprezentalja a 0 erteket rhoban. Egy gyakorlati feladatban altalaban F elemei adottak, es nekunk programokat is kell megirni. Ezt erdemes rendezett parokkal megtenni, de figyeljunk ra, hogy itt az elemek maguk sorozatok, szoval egy rendezett par elso eleme egy reprezentacionktol fuggo hosszu sorozat, a masodik eleme pedig egy oylan sorozat, aminek elso eleme ez a sorozat, a masodik eleme az a sorozat, aminek erteke az az ertek, amivel rho-n keresztul kepeztunk le. Ezert "rho-n keresztul" oldja meg.

Gyakorlat

Altalaban nem szoktam gyakorlati anyagot feltenni, de most egy picit elterunk a szokasostol. Eloszor is, hogy mindenki megnyugodjon, nem konkret feladatokat akarok itt megoldani. Helyette, mivel itt szinte minden tipusfeladat, csak mas halmazokkal, vegig akarok menni rajta, hogy melyik feladatban mit kell tenni, mire kell odafigyelni, ilyesmiket. Eloreszolva minden feladatnal altalanos menet, hogy leirjuk amit tudunk, rahuzzuk a megfelelo definiciot, megnezzuk a definiciohoz szolo teteleket es felteteleket, aztan leszurjuk a tanulsagot. Pici alakitgatas es okossag nehol.
Megallapitani egy relaciorol, hogy program-e? Van egy A allapotter, illetve egy S⊆AxA** relacio. Ha nem A-rol A**-ra kepez le, mar most vege a feladatnak, nem az. Ha igen, akkor megnezzuk, hogy milyen elemei vannak (rendezett parok, esetleg felsorolva nyilacskasan). Rogton elokapjuk a definiciot, es sorra nezzuk. Minden A beli elemmel csinal valamit? Ha nem, nem program. Ha igen, nezzuk tovabb. Minden adott s elem kepe s-el kezdodik? Pl 1 -> 1,2,4, vagy 4 -> 4,4,4,4,..? Ha nem, nem program. Ha igen, nezzuk tovabb. Van nem veges ismetlodes a sorozatban? Pl 1-> 1,2,2,4 (3 -> 3,3,3,3,.. lehet)? Ha igen, nem program. Ha nem, akkor vegig ertunk mindenen, azaz program. Ez ilyen egyszeru. Azzal lehet jol megneheziteni, ha S elemei nincsenek szepen felsorolva, hanem halmazkifejezesse, netan struktogrammal vannak abrazolva. Erre nincs kifejezetten jo megoldas. Csak nagyon alaposan gondoljuk at, hogy mi van.
Ez utan lehet programfuggvenyrol beszelni. Szoval ha a feladat nem specifikalja, hogy a relacio program, de a programfuggvenyrol igen, eloszor muszaj ellenorizni, hogy tenyleg programrol van szo. Max fel perc. Na akkor ilyen kerdsek johetnek, hogy mi a programfuggveny ertelmezesi tartomanya (jelolve altalaban Dp(S))? Ez az osszes olyan A beli elem, aminem nem szall el a program. Ha van olyan elem, ami kepez nem veges sorozatba, de kepez vegtelenesbe is, akkor az nem szamit. Csak az olyanok vannak itt, amibol BIZTOS, hogy nem szall el. Ezekre az elemekre ertelmezheto a programfuggveny szerinti kep. Ha en k elemre akarom nezni, akkor p(S)(k) az olyan sorozatok utolso eleme, amikre k-rol kepeztunk le. Pl ha van k -> k,a,b,c es van k -> k,l,k akkor {c,k}. Magyaran szolva nem a sorozatokra kepez a programfuggveny, csak a vegeikre. Ja amugy ne zavarjon meg, hogy a neveben van, hogy fuggveny, mert nem az. A peldamban is k ket elemre is lekepezett (c es k).
Feladat, es annak megoldasa. Egy feladatrol marhara egyszeru megallapitani, hogy az-e. Elokapjuk a definiciot. Igy van felirva: F⊆AxA? Ha nem, akkor nem feladat. Ennyi. Ha megis, akkor megnezzuk, hogy a relacio amit adtak az program-e (hacsak nincs specifikalva a feladatban (marmint a tenylegesben a papiron)). Ha minden franko, akkor nezzuk a definiciot. DF⊆Dp(S)? Ha nem, akkor nem oldja meg. Ha igen, akkor nezzuk tovabb. Nevezetesen megnezzuk az osszes DF osszes elemere megnezzuk, hogy a programfuggveny szerinti kepe (a sorozatok utolso elemei, amikre kepez) reszhalmaza-e az F szerinti kepenek. Egyszerubben, van-e elem, amire p(S) lekepez, de F nem, barmely elemre? Ha van, akkor nem oldja meg. Egyebkent igen. Ez sem tul nehez. Azzal lehet bonyolitani, mint a "program-e ez?" feladatnal, ha F elemei nem felsorolva vannak, hanem valami mas modon definialva. Csak ne szurjuk el.
A fennmarado reszekben, ha logikai fuggveny van benne, vagy kovetkezes, akkor az valszeg leggyengebb elofelteteles. Nezzuk eloszor ezt. Valszeg meg van adva ket logikai fuggveny (az igazsaghalmazukkal), es meg kell nezni, hogy egyik kvetkezik-e a masikbol, vagy reszhalmazai-e egymasnak valahogy? Legyenek P es Q. Amelyik igazsaghalmazanak elemszama nagyobb, azt veszem eloszor. Most ez legyen nekunk Q. Megnezem ceil(lf(S,Q)) halmazt. Ezek ugye azok a ceil(Q) beli ertekek, ahol S nem szall el. Ha ceil(P) minden eleme benne van, akkor okes. Ha nem, akkor bukta. Ha okes volt, es meg kerdes mondjuk, hogy egy adott elem benne lenne-e ceil(lf(S,P))-ben, akkor eloszor megnezzuk, hogy ceil(lf(S,Q)) eleme-e? Ha nem, akkor tovabb nem is kell kutatni. Ha igen, akkor meg lehet nezni rendesen kiszamolva.
Meg egy tipusfeladat, mashogy a "megoldja a program a feladatot?" kerdes. Ha van parameterter, akkor biztos ez. Ugy is meg lehet adva, hogy a feladat kompozicioi, es csak ossze kell belole kaparni az parameterteret. Ha minde infonk megvan, minden relacio az, amire szukseg van (pl a program tenyleg program), akkor elokapjuk a specifikacio tetelet. Picit mechanikusan: felirjuk az osszes parameter ceil(Q) es ceil(R)-jet. Ezek azok, hogy mibol kepez ebbe a parameterbe F1, es mire kepez ebbol a parameterbol F2. Ezutan mindhez a ceil(lf(S,R))-t is, es megnezzuk, hogy az adott elem ceil(Q)-ja reszhalmaza-e. Ha van legalabb egy, aminel nem, akkor bukta, es nem jottunk ra, hogy a feladat megoldja-e. Ez fontos, mert nem mindenkepp akkor van kesz a feladat, ha hurra rajottunk, hanem az is lehet a vegeredmeny, hogy mivel ez egy elegseges feltetel, igy nem allit semmit. Ha megis minden rendben volt, akkor persze megoldja.
Egy halmaz lezartja ertelemszeru. Egy relacio lezartja kicsit mas. Ha a relaciom R, akkor a lezartja R felulvonas. Tegyul fel, hogy mindketto HxH. R felulvonas ertelmezesi tartomanya az olyan H beli a elemek, hogy ha NINCS olyan tetszoleges vegtelen hosszu sorozatot H elemeibol, aminek az elso eleme a, es minden tovabbi eleme benne van az ot megelozo elem R szerinti kepenek. Vagyis ha en most e elemere vizsgalom, es a sorozat kovetkezo eleme f. Ha R(e) eleme f, akkor e nem R felulvonas ertelmezesi tartomanyanak resze. Egy adott a elem kepe R felulvonas szerint az az egy olyan H beli b elem, hogy b Rk(a) eleme, de R ertelmezesi tartomanyanak nem. k 0 is lehet.