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/05 22:20] rychtluk |
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 127: | Řádek 128: | ||
| ==== DS ==== | ==== 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 144: | Řádek 145: | ||
| Máme výraz: (3 + (6 * (4 + 8)) + (4 * 8)) | 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 : prvni: (char)4 ->(int) 4 a druha: (char)8 ->(int) 8 | + | |
| 4 8 | 4 8 | ||
| Řádek 174: | Řá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 183: | Řá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 190: | Řá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 220: | Řá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 | ||
