FEI archív 2010/2011 > 4. ročník
SPJ - Sémantika programovacích jazykov
jan:
Zhrnutie príspevkov z minulého roka
meno/heslo na hornad spj/Semantika
----------------------------------------------------------------------------------------------------
04.05.2010, 23:13:49 neviem ci viete ale prednasky boli dost inspirovane touto knizkou http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html, (si pamatam ze som bol dost debil z denotacnej semantiky a tam je to pekne vysvetlene)
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------
09.04.2010, 12:28:05 NEJDE naskenovany priklad zo 7.tyzdna : http://stargate.cnl.tuke.sk/~tanka/SPJ/
11.04.2010, 14:09:11 ako tak pozeram otazky z minulych rokov, pisomka bude pomerne jednoducha
11.04.2010, 15:28:09 na poslednej prednaske to bolo niekolko krat zopakovane ze ani staticka ani dynamicka semantika nebude (cize ziadne bloky, lokalne a globalne premenne...)
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------
co bude na zapocovke
----------------------------------------------------------------------------------------------------
13.04.2010, 09:29:35
slodicak vravel ze bude presne toto:
1.rosirenie semantiky algebraickych vyrazov
2.rozsirenie semantiky boolovskych vyrazov
3.semantika cisel
4.vyhodnotit nejaky vyraz (algebraicky, bolovsky) ("aj" vyhodnotenie vyrazu, aj nejake volne premenne, aj neviem co este)
5.program - naturalna semantika
6.program - operacna semantika
7.program - abstraktny strom
nic viac, nic menej
13.04.2010, 13:44:26 pod algrbraickym/boolovskym vyrazom sa mysli napr: B[[ (x<x+1) /\ (x=x) ]] , my sme to mali na 3. cviku.
13.04.2010, 10:57:26
nam diktoval mihalyi toto:
1 rozsirenie syntaxe aritmetickych vyrazov
2 rozsirenie syntaxe boolovskych vyrazov
3 semantika binarneho cisla
4 semantika vyrazov
5 naturalna semantika
6 strukturalna operacna semantika
7 derivacne stromy abstraktnej syntaxe
vraj to bude tak na 30-45 minut
na A4 bude nejaky ten oficialny tahak pre kazdeho..
13.04.2010, 13:44:26 bodove ohodnotenie: 3, 3, 2, 2, 4, 4, 2
----------------------------------------------------------------------------------------------------
13.04.2010, 13:37:59 pytal som sa ci bude ten strom z prveho cvicenia a ze nebude
13.04.2010, 14:31:01
1.rosirenie semantiky algebraickych vyrazov
Rozsirte jednoduchy programovaci jazyk o exponent e1e2 (riesenie bolo na prednaske)
2.rozsirenie semantiky boolovskych vyrazov
Rozsirte jednoduchy programovaci jazyk o operator implikácie (e1->e2) (taktiez bolo na prednaske)
13.04.2010, 15:53:30
dalsie rozsirenia syntaxe
minuleho roku bola napriklad absolutna hodnota, dalej pri boolovskych vyrazoch mozu byt lubovolne operacie(or,xor,nand,ekvivalencia atd...)
z boolovskych... pre jednu premennu su styri funkcie, pre dve je ich dokopy 16, vsetky sa robia prakticky rovnako
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------
Tu som teraz vypocital tych 7 typov prikladov
----------------------------------------------------------------------------------------------------
15.04.2010, 10:52:13 Tu som teraz vypocital tych 7 typov prikladov , sa moze niekto inspirovat alebo ma zjebat ze co mam zle . http://denature.netkosice.sk/sk/spj.jpg
15.04.2010, 11:32:57 tam v druhom priklade by asi mal byt vsade znak B(bool) namiesto E(epsilonu) a zvysok by som rovnako riesil...
15.04.2010, 12:14:08 pri SOS ti chyba na zaciatku este sekvencia 3os1 pravidlo lebo nemas nikde napisane podla coho si dostal <x:=x+2;y:=y+1,s0>
15.04.2010, 12:35:41
tt
---------------------------------(4ostt)
<S,s0> => <x:=x+2,s0>
---------------------------------(3os1)
ALFA1 => <x:=x+2;y:=y+1,s0>
S je celz prikay if
este doplnene uplne
15.04.2010, 13:28:54 no este ako tak pozeram blizsie tak tie stavy v NS su kus zle ..s2 tam nema byt vobec
15.04.2010, 13:48:27 takto by to malo byt:
<x:= x+2,s0> -> s1
______________________________________
<if(x<=5) then x:=x+2 else x:=x+y, s0> -> s1 , <y:=x+1, s1> -> s
________________________________________________________
<if(x<=5) then x:=x+2 else x:=x+y; y=x+1, s0> -> s
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------
zapocovka
----------------------------------------------------------------------------------------------------
14.04.2010, 07:47:48
Takze zapoctovka uspesne za mnou, bolo na to 45 minut, oficialny tahak dostal kazdy (obsahuje ns a os pravidla)
priklady v skutku jednoduche.
Skupina A:
1. abs(e)
2. e1 nand e2
3. 11100
4. FV(e1*e2)
5., 6. 7. if (x<=5) then x:=x+2 else x:=x+y;y=x+1
Skupina F:
1. -e
2. implikacia
3. 10011
4. FV (e1*e2+e3)
5. 6. 7. x:=2; if(y<=5) then x:=x+y else x:=x-y
GL (thx to kakan7)
----------------------------------------------------------------------------------------------------
14.04.2010, 08:19:40 7. uloha bola nakoniec derivacny strom(to co sa robilo na 1.cviku) a davajte si pozor kde je bodkociarka a kde zatvorka, pretoze sa mozte pomylit a tym padom mate 5.,6.,7. ulohu zle, konkretne v skupine A.
14.04.2010, 12:43:16 k tym FV, ja som napisal len FV(e1*e2) = FV(e1) U FV(e2)
14.04.2010, 13:23:27 som sa pytal ci to tak staci, a povedala ze ano
14.04.2010, 15:23:27 -e = e - (2 x e)? E[|-e|] = 0 - E[|e|] toto staci..lebo aj ked e bude nula tak to bude fungovat
14.04.2010, 16:46:00 abs(e) musis to riesit cez podmienky, ak je vyraz mensi alebo rovny nule tak je to 0-E[[e]]s inak E[[e]]s
14.04.2010, 17:23:20 moje vydenie prikladu z if v naturalnej semantike na http://www.megaupload.com/?d=L87QLICM Prezentácia1.jpg
14.04.2010, 17:42:22 oficialny tahak - pravidla naturalnej a štrukturalnej operacnej semantiky, prakticky vsetky pravidla ktore trebalo (sekvencia, skip, while, if..)
----------------------------------------------------------------------------------------------------
test K
1 max (e1,e2)
2 bsucc (b)
3 11011 = 27
4 FV (true V b1)
5, 6 a 7 if neg(x<=3) then y := y - 1 else y:= y + 1;
okrem toho, ze nam povedal cely druhy a stvrty priklad a v miestnosti bol hluk, tak to bolo v pohode
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------
otazky z archivu minuleho roku
----------------------------------------------------------------------------------------------------
24.05.2010, 14:57:11
ja som z archivu minuleho roku take nico vytiahol:
1) Denotacia cyklu a definicie: monotonej a spojitej f-cie, funkcionalu, fixny bod
2) Definicia formalneho jazyka (abstraktna syntax a semantika jazyka)
3) Akcna semantika
4) Semantika aritmetickych vyrazov a booolovskych vyrazov
5) Denotacna semantika pre blok prikazov (medzi begin a end)
6) nejaka otazka z poslednej prednasky - take bludy
----------------------------------------------------------------------------------------------------
24.05.2010, 15:08:46
ja som z archivu minuleho roku take nico vytiahol:
tak tahala som tri veci, jeden dokaz (NS - OS, while + postupnost prikazov), co som rozpisala na dve strany, dalej priklad (definovat semantiku + syntax osmickovych cisel) a jednu teoreticku (posledna prednaska nejake bludy)
----------
Ale nie všetky otázky sú také v pohode. Aspoň pre mne sa to zdalo dosť hard. Moja písomka:
1)Príklad: Naturálna, operačná a denotačná sémantika pre rozšírenie S:=...l for c1 to c2 do S;
naturalna:
pre B[[b(nezvyraznuj :))]] = tt
<S;s>->s` <c1:=c1+1, s`> -> s`` <for c1 to c2 do S, s``> -> s```
______________________
<for c1 to c2 do S,s> -> s```
b:= c1<=c2
pre B[[b :)]] = ff pises ze sa nevykona nic z cyklu
pre strutruralnu pises:
<for c1 to c2 do S, s> => <if B[[b :)]] then S;c1:=c1+1;for... else skip, s>
pre denotacnu pises:
<for c1 to C2 do S> = fix F
F g = cond(B[[b :)]], S ° c1:=c1+1 ° g, id)
2)Teória: Denotačná sémantika pre blok prikazov(to je toto medzi begin a end,neviem ci sa to vola blok prikazov).
3)Dôkaz: Dokáž že jednoduchý programovací jazyk je deterministický.
strukturalnou indukciou na pravidla NS
----------
Priklad: Cyklus s 3 iteraciami a z toho konstruovat odvodzovaci strom.
Dokaz: Dokazat semanticku ekvivalentnost S1 a S2.
S1 = while b do S
S2 = if b then (S; while b do S) else skip
Teoria: Semantika aritmetickych vyrazov a boolovskych vyrazov.
----------
Ako je vyjadrena denotacia cyklu? Co je to monotonna fcia? Spojita fcia? Funkcional? A co je to fixny bod?
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------
predtermin
----------------------------------------------------------------------------------------------------
12.05.2010, 17:58:55 predtermin
Tahali sa tri otazky - priklad, teoreticka a jeden dokaz, vymenit sa neda. Ku kazdemu je potrebne mat aspon nieco.
Ja som mal
priklad odvodzovaci strom pre naturanulnu semantiku.
Dokaz bol preukazat korektnost implementacia suctu a premennej pre aritmet.vyrazy a logickeho suctu a negacie.
Teoria Denotacia cyklu a defincie monotonnej f-cie, spojitej, funkcional, fixny bod ...
12.05.2010, 20:39:49 ja som bol pri novitzkej a ja som si vytiahol otazku na
Teoria definiciu formalneho jazky(def. abstraktnej syntaxe a semantiky jazyka),
dokaz pre podmienku v abstraktrom stroji a dokazat jej korektnost a
priklad som mal odvodzovaci strom pre NS
prof.novitzka bola super, pytala sa normalne otazky ani nie na presne definicie, ci je dokaz dobry ale ci tomu chapem a ci to viem vysvetlit...
priklad ani nepozrela, len videla ze tam mam strom, tak sa pytala ako funguje vlastne NS pre prikaz a som jej to mal vysvetlit...
13.05.2010, 17:01:04 nic viac ako prednasky ti netreba...plus cvika priklady pre lepsie pochopenie a vyskusanie si prikladov
13.05.2010, 17:22:42
ja som mal
dokazat korektnost implementacie pre konjukciu boolovskych vyrazov, vztah mensi a rovny pre aritmeticke vyrazy a pre konstantu true...a boolovske vyrazy v prednaske nie su dokazane len je tam spomenute ze sa dokaz vykonava podobne jak pre artimeticke
22.05.2010, 17:24:02 ja som mal akcnu semantiku
22.05.2010, 19:22:25 co vseko je obsahom toho povoleneho tahaka - su tam aj instrukcie abstraktneho stroja a aj prekladove instrukcie AM
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------
skuska
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------
09.06.2010, 12:56:06 a ucit sa staci cisto z prednasok? - jj + nejake priklady z cvik tiez neuskodia
----------------------------------------------------------------------------------------------------
24.05.2010, 15:19:40 Priklad na akcnu urcite nebude - to povedal aj na prednaske ...
----------------------------------------------------------------------------------------------------
08.06.2010, 18:14:10 prekladove funkcie pre AM boli na tahaku
----------------------------------------------------------------------------------------------------
09.06.2010, 13:49:40 dokaz ekvivalencie SOS a DS..(strany 27-41 v 8 prednaske) - ja mam v zosite napisane, ze tento dokaz nebude, takze to asi hovoril na cviku...
----------------------------------------------------------------------------------------------------
15.06.2010, 16:23:57
ako sa riesi rozsirenie pre Fib(n)...nty clen fibonaciho postupnosti
e := ... | fib(n)
E[fib(0)]s=0 (s je index)
E[fib(1)]s=1
E[fib(n)]s= E[fib(n-2)]s + E[fib(n-1)]s
----------------------------------------------------------------------------------------------------
euklidov algoritmus v operacnej semantike
s0[x->96, y->24]
P=
z:=0;
while(neg(x=y)) do
if (x =< y) then y:=y-x else x:=x-y;
z:=x;
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------
26.05.2010, 11:58:42
----------------------------------------------------------------------------------------------------
skuska bola spolu s dalsim predmetom novitzkej.
rozsadzali podla abecedy do radov. Kazdy dostal papier aj zadania do ruky.
ustna cast bola najma u soldicaka, ktory chcel, aby bola kazda uloha spravena aspon na polovicu.
Siel som ako prvy, bez pripravy, k prof. Novitzkej. K teorii som jej povedal svoje. Nepytala sa ma nic extra. P a D - chcela vediet akym postupom by som ich riesil. Z toho ako som reagoval videla, ci rozumiem tematike alebo nie. Na papieri som mozno mal 3 - 4 vztahy.
----------------------------------------------------------------------------------------------------
26.05.2010, 12:32:12
Co sa tika otazok mal som:
T: Druhy entit v akcnej semantike, definovat akcie, ake vysledky akcie pozname, a ake druhy
informacii akcie mozu spracovat a popisat jednotlive druhy informacii
D: Dokazat korektnost implementacie pre prikaz while (v oboch smeroch)
P: Vytvorit syntax a semantiku jazika Hexadecimalnych cisel
Ja som mal :
Priklad: zaviest pravidla pre prikaz"for x:=e1 to e2 do S" pre NS,OS a DS
otazka: Denotacna semantika prikazu cyklu a vsetky pojmy s tym suvisiace
dokaz: ekvivalencia sekvencie a if v NS a OS
01.06.2010, 12:28:35
pr1 prepises na x:=e1;while(x<=e2)do(S;x:=x+1)
pr2 prepises na S;while(neg b) do S
v tomto tvare to uz snad vies prepisat do ns os a ds
1. teoria: Denotacna semantika - definovat prikazy JPJ (okrem prikazu while) plus popisat pojmy.
2. dokaz: ekvivalencia medzi NS a OS pre prikazy postupnosti a cyklu.
3. priklad: Odvodzovaci strom pre dynamicku NS (taky priklad medzi begin end s deklaraciou var)
26.05.2010, 14:34:56
ja som mal
priklad: repeat S until b -urobte ns os ds
teoria: v skratke ... vysvetlite os
dokaz: dokazte ekvivalenciu ns os (priradenie, podmienka)
Ja som nastastie vystihol Novitzku
1. elementarna fazeta
2. euklidovym algoritmom vypocitat najvacsi spolocny delitel cisel 96 a 24 v operacnej semantike
3. dokazat korektnost implementacie v abstraktnom stroji z oper. sémantiky pre priradovaci prikaz a príkaz vetvenia Sos[]=Sam[]
T: denotacna semantika vyrazov, zakl. pojmy: semanticka funckia, sem. rovnice, pomocna fcia, sem. oblast
P: program prepisat do AM a vykonat : while neg(y=1) do (x:=y; y:=z; z:=x) ///alebo tak nejak, nevim presne
D: ci je naturalna semantika JPJ deterministicka
26.05.2010, 22:10:06
Ja som mal priklad a dokaz taky isty ako zuzanka, len teoriu som mal definovat štrukturalnu operačnu semantiku + zakladne pojmy abo daco take.
----------------------------------------------------------------------------------------------------
02.06.2010, 10:12:56
----------------------------------------------------------------------------------------------------
Dnesna skuska (2.6):
- hned na zaciatku Slodicak povedal, ze budu skusat inym systemom -> naraz iba 5 boli v miestnosti na spj a 5 na log.inf, ostatni cakali vonku
- nemuseli sme mat pripravu
- Slodicak za radom vytahoval otazky
T - syntax a sem. abstr. stroja
D - korrektonost impl. cyklu v abs. stroji
P - Denotacia prikazu if (?dajaka podmienka?) then (x:=?,y:=?,z:=?) else skip pre s0= [x=?,y=?,z=?]
- samozrejme namiesto ? boli nejake premenne
02.06.2010, 11:07:04
P: Definovat syntax a semantiku desiatkovej sustavy, kladne a zaporne cisla
D: Dokazat korektnost implementacie na AM - priradenie a skip (operacna semantika)
Teoria: Bloky, procedury, volania, deklaracia, (staticka, dynamicka...)
P: Vypocitaj denotaciu pre x:=z;z:=y;y:=x; s0=[z->1;y->6] (nepamatam presne cisla) a vysledok overit na abstraktnom stroji.
D: Dokazat korektnost pre b1^b1, e1<=e2 a pre true
T: Nepriama denotacna semantika - popisat princip
T:Zakladne pojmy strukturalnej operacnej semantiky
D:Dokazte ze naturalna semantika JPJ je deterministicka
P:Jednoduchy while prepisat do instrukcii abstraktneho stroja a urcit vysledny stav vykonavania
P: urcite volne viazane FV premenne
T: jazyk definicia + vysvetlit pojmy
D: ekvivalencia cyklu v OS a na AM
P: Euklidov algoritmus pre vypocet najvacsieho spolocneho delitela cisel x a y.
T: Semantika aritmetickych a boolovskych vyrazov v JPJ.
D: Dokazte korektnost implementacie aritmetickych vyrazov na abstraktnom stroji.
----------------------------------------------------------------------------------------------------
09.06.2010, 11:09:16
----------------------------------------------------------------------------------------------------
T: Definovat semantiku bool a exp vyrazov JPJ
P: Napisat dynamicku naturalnu semantiku pre program (boli tam dva bloky vnorene s deklaraciami premennych)
D: Dokazat korektnost implementacie na abstraktnom stroji pre priradovaci prikaz a skip
T: Definovat NS prikazov JPJ a vysvetlit
D: Dokazat pre postupnost a priradenie, ci ekvivalentne NS OS
P: case x of e1:S1;e2:S2 else S3 NS OS DS
T: Nepriama denotacna semantika + zakl. pojmy.
P: Rozsirenie JPJ (Syntax aj semantika) o nasledovnika prirodzeneho cisla, Fib(n) - nty clen Fibbonachiho postupnosti a o nonekvivalenciu bool. vyrazov.
D: Korektnost implementacie komutativnosti a asociativnosti nasobenia vyrazov pomocou AM.
T: Akcna semantika, fazety, atd...
D: Ekvivalencia prikazov priradenia a podmienky pre NS a SOS
P: Odvodzovaci strom v SOS pre taky priklad ze boli v podstate sekvencia S1(priradovaci prikaz), S2(cyklus while), S3(priradovaci prikaz)
P: rozsirit syntax o b1=b2, b1=>b2, e1>e2
T: typy vykonavania akcii, definovat zberace, typy udajov v akcnej semantike = proste dajake haluze z akcnej
D: korektnost podm. prikazu, cize Sos[|if b then S1 else S2|] pomocou AM
----------------------------------------------------------------------------------------------------
16.06.2010, 11:24:32
----------------------------------------------------------------------------------------------------
T: akcna semantika a veci okolo toho
D: Dokázať korektnosť implementácie komutatívnosti a asociatívnosti násobenia výrazov pomocou AM.
P: repeat S until b - urobte NS OS DS
T ŠOS //pohoda, jahoda
D komutativnost scitania a nasobenia na abstraktnom stroji //easy
P NS, OS a DS pre for //staci previest na while a po pomoci od Ľaľovej som o uz vedel vyriesit
T: Definovat semantiku aritmetickych vyrazov JPJ
D: Korektnosť implementácie komutatívnosti a asociatívnosti násobenia výrazov pomocou AM
P: Syntax a semantika kladnych a zapornych desiatkovych cisel
T: Nepriama denotacna semantika
D: Korektnosť implementácie komutatívnosti a asociatívnosti scitania výrazov pomocou AM
P: case x of e1:S1;e2:S2 else S3 - pravidla pre NS, SOS, DS
T: naturalna, setko k nej
D: podmienovaci prikaz v NS a AM
P: AM, cyklus while
domino3d:
ty uz na skusku mozes ist :)
si nas novy hero
jan:
skripta k predmetu
http://rapidshare.com/files/448824373/SEMANTICS_WITH_APPLICATIONS_-_A_Formal_Introduction_-_Hanne_Riis_Nielson_-_Flemming_Nielson.pdf
sandusky:
prip. aj sem:
http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html
radix:
ste mali dat na ftp rovno
Navigácia
[0] Index správ
[#] Ďalšia strana
Go to full version