Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m36tpj:zapisky [2012/01/05 08:43]
woxie2
+++ courses:a4m36tpj:zapisky [2025/01/03 18:29] (aktuální)
@@ Řádek 21: / Řádek 21: @@
   * Stav, ve kterém se může program nacházet (čili v případě aritmetických výrazů všechny možné kombinace jako (1+2), (2+1), (2+(5*6)+3), ...). Konfigurací tedy může být (a většinou i je) nekonečně mnoho.
   * u PostFixu je to (CommandSeq, Stack)
+  * DEF EN: Each state of the abstract machine is called a configuration.
 ==== Přepisovací funkce ====
@@ Řádek 28: / Řádek 29: @@
 ==== Finální konfigurace ====
   * u PostFixu je to ([], S) -> již není s čím pracovat, množina příkazů je prázdná
-  * Finální konfigurace je konfigurace, která se již nemůže přepsat pomocí přepisovacího pravidlo (neexistuje na ní přepisovací pravidlo)
+  * Finální konfigurace je konfigurace, která se již nemůže přepsat pomocí přepisovacího pravidla (neexistuje pro ni přepisovací pravidlo)
+  * Pro finální konfiguraci existuje výstup z výstupní funkce OF
+==== Stuck state ====
+  * Je stav, který nelze dále přepsat, ale zároveň pro něj výstupní funkce OF nemá žádný výstup
+  * Dá se odstranit tím, že výstupní funkci předefinujeme přidáním stavu error
+  * Př: [pop, ε] //příkaz pop na prázdném zásobníku//
+  * Př odstranění: Postfixový stav se přepíše na chybový výstup, [pop, ε] -> error, po této úpravě se stav [pop, ε] změní ze  stuck state na finální konfiguraci
 ==== Operační sémantika ====
@@ Řádek 34: / Řádek 42: @@
   * DEF(Turband): Operační sémantika vysvětluje význam jednotlivých konstruktů programovacího jazyka pomocí "navazujících" kroků abstract machine.
   * EN DEF: An operational semantics explains the meaning of programming language constructs in terms of the step-by-step process of an abstract machine.
 ==== Operační sémantika malého kroku (SOS - Small Step Operational Semantics) ====
-  * Definujeme přepisovací pravidla, které vždycky v jednom kroku přepíšou konfiguraci na jinou - nelze použít rekurzivní pravidlo.
+  * Definujeme přepisovací pravidla, která mají v předpokladech jiné JEDNOKROKOVÉ relace
 ==== Operační sémantika velkého kroku (BOS - Big Step Operational Semantics) ====
-  * Přepisovací pravidla mohou být zadány rekurzivně (ale těch jednoduchých elementárních pravidel se stejně nezbavíme)
+  * Přepisovací pravidla, která mohou mít v předpokladech
 ==== Denotační sémantika ====
@@ Řádek 57: / Řádek 66: @@
 ==== Množina ====
   * Klasická množina jak jí známe, nemá žádné uspořádání a každý prvek se zde vyskytuje jen jednou - př. {0, 1, 2} == {2, 0, 1}
-  * Pozor, když máme množinu A = {0, 1, 2}, tak A* = (0, 1, 2, 1, 2, 0, 1, ...) čili sekvence
+  * Pozor, když máme množinu A = {0, 1, 2}, tak A* = (0, 1, 2, 1, 2, 0, 1, ...) je sekvence
 ==== Sekvence ====
@@ Řádek 75: / Řádek 84: @@
 E = E | (E+E) | (E*E) | N
- * Pozn.: Uvědomme si, že znaménko + u výrazů(je za nimi znak přepisovací relace - šipka) vyjadřuje něco jiného než u N, u E znamená opravdu jen character, zatímco u N znamená klasické sčítání. Stejně tak pro * (násobení). Pokud jej píšeme na papír, měli bychom tato znaménka u E psát v kolečku (tady v dokuwiki je to aspoň tučným písmem). V denotační sémantice už je jejich rozdílný význam díky hranatým závorkám vidět lépe.
+  * Pozn.: Uvědomme si, že znaménko + u výrazů(je za nimi znak přepisovací relace - šipka) vyjadřuje něco jiného než u N, u E znamená opravdu jen character, zatímco u N znamená klasické sčítání. Stejně tak pro * (násobení). Pokud jej píšeme na papír, měli bychom tato znaménka u E psát v kolečku (tady v dokuwiki je to aspoň tučným písmem). V denotační sémantice už je jejich rozdílný význam díky hranatým závorkám vidět lépe.
- * Pozn.2: Opravujte nám to, pokud si myslíte, že máme něco špatně (v ničem si nejsme 100% jistí).
 ==== SOS ====
  E -> N
- (N<sub>1</sub>**+**N<sub>2</sub>) -> N<sub>3</sub> kde N<sub>3</sub>=N<sub>1</sub>+N<sub>2</sub>
+ (N<sub>1</sub> **+** N<sub>2</sub>) -> N<sub>3</sub> kde N<sub>3</sub> = N<sub>1</sub>+N<sub>2</sub>
- (N<sub>1</sub> * N<sub>2</sub>) -> N<sub>3</sub> kde N<sub>3</sub>=N<sub>1</sub>*N<sub>2</sub>
+ (N<sub>1</sub> * N<sub>2</sub>) -> N<sub>3</sub> kde N<sub>3</sub> = N<sub>1</sub> * N<sub>2</sub>
  E<sub>1</sub> -> E<sub>2</sub>
  --------------------------------------------------------------
- (E<sub>3</sub>** + ** E<sub>1</sub>) -> (E<sub>3</sub>** + **E<sub>2</sub>)
+ (E<sub>3</sub> ** + ** E<sub>1</sub>) -> (E<sub>3</sub> ** + ** E<sub>2</sub>)
  E<sub>1</sub> -> E<sub>2</sub>
  --------------------------------------------------------------
- (E<sub>3</sub>*E<sub>1</sub>) -> (E<sub>3</sub>*E<sub>2</sub>)
+ (E<sub>3</sub> * E<sub>1</sub>) -> (E<sub>3</sub> * E<sub>2</sub>)
  E<sub>1</sub> -> E<sub>2</sub>
  --------------------------------------------------------------
- (E<sub>1</sub>** + ** E<sub>3</sub>) -> (E<sub>2</sub>** + ** E<sub>3</sub>)
+ (E<sub>1</sub> ** + ** E<sub>3</sub>) -> (E<sub>2</sub> ** + ** E<sub>3</sub>)
  E<sub>1</sub> -> E<sub>2</sub>
  --------------------------------------------------------------
- (E<sub>1</sub>*E<sub>3</sub>) -> (E<sub>2</sub>*E<sub>3</sub>)
+ (E<sub>1</sub> * E<sub>3</sub>) -> (E<sub>2</sub>*E<sub>3</sub>)
@@ Řádek 120: / Řádek 128: @@
 ==== DS ====
- *  [ [E]] = [ [N]]
+  *  [ [E]] = [ [N]]
- *  [ [N]] = N
+  *  [ [N]] = N
- * [ [** + **]] = +
+  * [ [** + **]] = +
- * [ [*]] = *
+  * [ [*]] = *
- * [ [E<sub>1</sub>** + ** E<sub>2</sub>]] = [ [E<sub>1</sub>]] [ [** + **]] [ [E<sub>2</sub>]]
+  * [ [E<sub>1</sub>** + ** E<sub>2</sub>]] = [ [E<sub>1</sub>]] [ [** + **]] [ [E<sub>2</sub>]]
- * [ [E<sub>1</sub>*E<sub>2</sub>]] = [ [E<sub>1</sub>]]  [ [*]] [ [E<sub>2</sub>]]
+  * [ [E<sub>1</sub>*E<sub>2</sub>]] = [ [E<sub>1</sub>]]  [ [*]] [ [E<sub>2</sub>]]
@@ Řádek 137: / Řádek 145: @@
 Máme výraz: (3 + (6 * (4 + 8)) + (4 * 8))
-  * Při vyhodnocování postupujeme odspodu, bacha, mezi cisly s mezery neni znamenko, ta jsou rovnou vyhodnocena
+Při vyhodnocování postupujeme odspodu, bacha, mezi cisly s mezery neni znamenko, ta jsou rovnou vyhodnocena napr radek 4   8   jsou dve vetve : prvni: (char)4 ->(int) 4    a druha: (char)8 ->(int) 8
-  *  napr radek 4   8   jsou dve vetve : (char)4 ->(int) 4     (char)8 ->(int) 8
    8
             -------
@@ Řádek 166: / Řádek 174: @@
 ===== Quicksort =====
- Dokuwiki neumí matematickou syntaxi, takže ε je epsilon a · je symbol zřetězení.
+ malé epsilon - ε je prázdná množina a · je symbol zřetězení.
 ==== Zápis relací ====
@@ Řádek 175: / Řádek 183: @@
 ==== Velký krok ====
-  * A = {A<sub>1</sub>, A<sub>2</sub>, ..., A<sub>n</sub>} - vstupní neseřazená množina
+   * A = {A<sub>1</sub>, A<sub>2</sub>, ..., A<sub>n</sub>} - vstupní neseřazená množina
-  * B - výstupní seřazená množina
+   * B - výstupní seřazená množina
  QSORT({}) = ε
@@ Řádek 182: / Řádek 190: @@
  QSORT(A) -> B
- B = QSORT(A)·A<sub>1</sub>·QSORT(A)
+ // znak ā neznamena nic podstatneho, jde jen o to, aby se rozlisily podmnoziny//
-  * x ∈ A: x > A<sub>1</sub>
-  * x ∈ A: x ≤ A<sub>1</sub> AND x != A<sub>1</sub>
+ B = QSORT(ā)·A<sub>1</sub>·QSORT(a)
+   * ā ⊂ A, a ⊂ A
+   * x ∈ ā: x > A<sub>1</sub>
+   * x ∈ a: x ≤ A<sub>1</sub> AND x != A<sub>1</sub>
 ==== Malý krok ====
@@ Řádek 212: / Řádek 223: @@
    MSORT(A) -> A  if len(A) = 1
-   D-> MSORT(B)·MSORT(C) pro všechny x ∈ B: pro všechny y ∈ C: x < y
+   MSORT(B)·MSORT(C) -> D pro všechny x ∈ B: pro všechny y ∈ C: x < y
    -----------------------------------------------------------
                       MSORT(A) -> D
@@ Řádek 256: / Řádek 267: @@
 ==== 3.3 ====
-  * a - je to rotace, vezmu prvek z vrcholu zásobníku a dám ho na konec
+  * a - <del>je to rotace, vezmu prvek z vrcholu zásobníku a dám ho na konec</del>
-  * b - 432432
+      - je to rotace, vyjmu prvek (pop()) z vrcholu zásobníku a pokud je to cislo > 1 posunu prvek na vrcholu zasobniku (prvek hned za cislem, ktere jsem vyjmul) o N - 1 pozic dolu v zasobniku
+  * b - <del>432432</del>
+      - **IF**(postfix 0 2 3 4 2 3 4 rot rot rot, [])
+      - = (2 3 4 2 3 4 rot rot rot, [])
+      - =><sup>6</sup> (rot rot rot, [4 3 2 4 3 2]) **[num]**
+      - => (rot rot, [2 4 3 3 2]) **[rot]** //(4 > 1, posunu 3 o 3 dolu)//
+      - => (rot, [3 3 4 2]) **[rot]** //(2 > 1, posunu 4 o 1 dolu)// nemělo by to tedy být [3 4 3 2] ?
+      - => (, [4 2 3]) **[rot]** //(3 > 1, posunu 3 o 2 dolu)//
+      - Odpoved je **[4 2 3]** pokud bychom pokracovali dal
+      - (, [4 2 3]) nalezi do FC a tedy muzeme **OF**(, [4 2 3]) = 4
   * d - program by se zasekl na prázném zásobníku, např. (postfix 0 rot)
+      - (rot . Q, N . S) kde N neni cislo nebo N < 2 nebo |S| < N
 ==== 3.4 ====
@@ Řádek 307: / Řádek 328: @@
   * (Q_1.V_1.V_2.swap.Q_2) -> (Q_1.V_2.V_1.Q_2)
-  * (Q_1.N_1.N_2.add.Q_2) -> (Q_1.N_ans.Q_2)  //stejně tak i pro mul, sub, ..
+  * (Q_1.N_1.N_2.add.Q_2) -> (Q_1.N_ans.Q_2)  //stejně tak i pro mul, sub, ..//
   * (Q_1.(Q_exec).exec.Q_2) -> (Q_1.Q_exec.Q_2)
   * (Q_1.V_1.V_2.N.sel.Q_2) -> (Q_1.V_1.Q_2) if N = 0
@@ Řádek 317: / Řádek 338: @@
 ===== BOS =====
 ==== 3.16 ====
-  //doplňujeme ELM o if a operace s booleanem
+  doplňujeme ELM o if a operace s booleanem
   E = NE
   NE = (NE_1 op NE_2) | (if BE NE_1 NE_2) | N
@@ Řádek 351: / Řádek 372: @@
 ===== Denotační sémantika =====

courses/a4m36tpj/zapisky.1325749424.txt.gz · Poslední úprava: 2025/01/03 18:25 (upraveno mimo DokuWiki)

Nahoru