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

[jim-beam33]

aky je login a pass na hornade?

[drtic]

login: spj
password: Semantika

[elvolcanoik]

nema niekto materialy z cvik z minuleho roku

[Matejus]

nema niekto materialy z cvik z minuleho roku

Sú ti zbytočné, ževraj je tam veľa chýb (Slodičák vravel).

[ropman]

lepsie jak dratom do oka

[Havran]

no, tak dneska sme fasli pisomku za tych +-5 bodov

[domino3d]

no, tak dneska sme fasli pisomku za tych +-5 bodov

slodi?

[jardo]

no, tak dneska sme fasli pisomku za tych +-5 bodov

s kym a v ktorom case?

[Havran]

slodicak, 15:55

[markus]

no, tak dneska sme fasli pisomku za tych +-5 bodov

neze by si bol rad vo stvrtom tyzdni tam este nic nieje casom sa to bude len a len nabalovat

[jardo]

co bolo v pondelok na cviku so slodicakom o 14 15

[qwerty]

Nemohol by tu niekto postnut ofotene cviko u slodicka zo stvrtka o 14:15 (resp.15:00 kedze bolo prelozene)? 

[t0Mi]

no, tak dneska sme fasli pisomku za tych +-5 bodov

tazky ste mali priklad ? alebo dva ?

[dodo]

2 skupony jeden priklad

[Havran]

no, tak dneska sme fasli pisomku za tych +-5 bodov

tazky ste mali priklad ? alebo dva ?

presne toto co sme na minulom cviku s nim robili a priklad nebol tazky sak to su zatial suche veci, ale ta ked sa do toho ani nepozres tak syntakticke chyby tam budu minimalne

[Matejus]

Dnes sme aj my mali "prepadovku" (skupina 10:40 - utorok). Príklad: naturálna sémantika 3 príkazy (priradenie, if, priradenie)

[domino3d]

Dnes sme aj my mali "prepadovku" (skupina 10:40 - utorok). Príklad: naturálna sémantika 3 príkazy (priradenie, if, priradenie)

s kym? kto vas uci?

[radix]

[hide]slodicak[/hide]

[scream]

z coho sa da ucit?

[elvolcanoik]

tak dnes bola prepadovka na cviku o 7:30 ...