navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m36tpj:zapisky [2012/01/12 16: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. | * 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) | * u PostFixu je to (CommandSeq, Stack) | ||
| + | * DEF EN: Each state of the abstract machine is called a configuration. | ||
| ==== Přepisovací funkce ==== | ==== Přepisovací funkce ==== | ||
| Řádek 28: | Řádek 29: | ||
| ==== Finální konfigurace ==== | ==== Finální konfigurace ==== | ||
| * u PostFixu je to ([], S) -> již není s čím pracovat, množina příkazů je prázdná | * 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 | + | * Pro finální konfiguraci existuje výstup z výstupní funkce OF |
| ==== Stuck state ==== | ==== Stuck state ==== | ||
| * Je stav, který nelze dále přepsat, ale zároveň pro něj výstupní funkce OF nemá žádný výstup | * 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 | * Dá se odstranit tím, že výstupní funkci předefinujeme přidáním stavu error | ||
| - | * Př: [pop, ε] | + | * 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 | + | * 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 ==== | ==== Operační sémantika ==== | ||
| Řádek 173: | Řádek 174: | ||
| ===== Quicksort ===== | ===== 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í ==== | ==== Zápis relací ==== | ||
| Řádek 182: | Řádek 183: | ||
| ==== Velký krok ==== | ==== 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({}) = ε | QSORT({}) = ε | ||
| Řádek 189: | Řádek 190: | ||
| QSORT(A) -> B | 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 ==== | ==== Malý krok ==== | ||
| Řádek 219: | Řádek 223: | ||
| MSORT(A) -> A if len(A) = 1 | 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 | MSORT(A) -> D | ||
