Stosy - struktura algebraiczna: Różnice pomiędzy wersjami
| (Nie pokazano 3 pośrednich wersji utworzonych przez tego samego użytkownika) | |||
| Linia 1: | Linia 1: | ||
| − | Stosy to struktura algebraiczna znajdująca wiele zastosowań w informatyce.<br /> | + | Stosy to struktura algebraiczna znajdująca wiele zastosowań w informatyce. By wymienić kilka przykładów: automaty ze stosem to ważna część każdego kompilatora, stos rekordów aktywacji to podstawowa struktura maszyny wirtualnej (lub running-systemu), ...<br /> |
'''Definicja'''<br /> | '''Definicja'''<br /> | ||
Struktura algebraiczna<br /> | Struktura algebraiczna<br /> | ||
| − | <center><math>A = \langle E \cup S; w, u, p, | + | <center><math>A = \langle E \cup S; w, u, p, n, =\rangle </math></center> |
| − | <br /> | + | <br /> taka, że jej uniwersum jest sumą dwu rozłącznych zbiorów <math>E</math> i <math>S</math>, <math>E \cap S=\emptyset</math>z działaniami<br /> |
<math>w\colon E \times S \rightarrow S </math><br /> | <math>w\colon E \times S \rightarrow S </math><br /> | ||
<math>u\colon S \rightarrow S </math><br /> | <math>u\colon S \rightarrow S </math><br /> | ||
<math>p\colon S \rightarrow E </math><br /> | <math>p\colon S \rightarrow E </math><br /> | ||
| − | <math> | + | <math>n\colon S \rightarrow \{true, false\}</math><br /> |
<math>=_E \colon E \times E \rightarrow \{true, false\} </math><br /> | <math>=_E \colon E \times E \rightarrow \{true, false\} </math><br /> | ||
| − | + | <math>=_S \colon S \times S \rightarrow \{true, false\} </math><br /> | |
| − | <math>\forall_{e \in E}\,\forall_{s \in S} \lnot e(w(e,s)) </math><br /> | + | które zapewniają prawdziwość następującego zbioru aksjomatów <br /> |
| + | <math>\forall_{e \in E}\,\forall_{s \in S}\ \lnot n(w(e,s)) </math><br /> | ||
| + | <math>\forall_{e \in E}\,\forall_{s \in S}\ p(w(e,s)) =_E e </math><br /> | ||
| + | <math>\forall_{e \in E}\,\forall_{s \in S}\ u(w(e,s)) =_S s </math><br /> | ||
| + | <math>\forall_{e \in E}\,\forall_{s \in S}\ \lnot n(s) \implies w(p(s),u(s)) =_S s </math><br /> | ||
| + | <math>\forall_{s \in S}\ \{\mathbf{while}\ \lnot n(s) \ \mathbf{do} \ s:= u(s) \ \mathbf{od}\}\ n(s)</math><br /> | ||
| + | oraz aksjomaty identyczności dla relacji <math>=_E</math> i <math>=_S</math> <br /> | ||
| + | jest strukturą stosów. '''koniec definicji'''.<br /> | ||
| + | Zbiór <math>E</math> jest nazywany zbiorem elementów. Elementy zbioru <math>S</math> to stosy. Działanie <math>w</math> najczęściej jest nazywane ''push'', działanie <math>u</math> to operacja ''pop'', działanie <math>p</math> to operacja ''top''. Predykat <math>n</math> oznacza relację ''empty''. <br /> | ||
Aktualna wersja na dzień 09:41, 12 mar 2017
Stosy to struktura algebraiczna znajdująca wiele zastosowań w informatyce. By wymienić kilka przykładów: automaty ze stosem to ważna część każdego kompilatora, stos rekordów aktywacji to podstawowa struktura maszyny wirtualnej (lub running-systemu), ...
Definicja
Struktura algebraiczna
taka, że jej uniwersum jest sumą dwu rozłącznych zbiorów [math]E[/math] i [math]S[/math], [math]E \cap S=\emptyset[/math]z działaniami
[math]w\colon E \times S \rightarrow S [/math]
[math]u\colon S \rightarrow S [/math]
[math]p\colon S \rightarrow E [/math]
[math]n\colon S \rightarrow \{true, false\}[/math]
[math]=_E \colon E \times E \rightarrow \{true, false\} [/math]
[math]=_S \colon S \times S \rightarrow \{true, false\} [/math]
które zapewniają prawdziwość następującego zbioru aksjomatów
[math]\forall_{e \in E}\,\forall_{s \in S}\ \lnot n(w(e,s)) [/math]
[math]\forall_{e \in E}\,\forall_{s \in S}\ p(w(e,s)) =_E e [/math]
[math]\forall_{e \in E}\,\forall_{s \in S}\ u(w(e,s)) =_S s [/math]
[math]\forall_{e \in E}\,\forall_{s \in S}\ \lnot n(s) \implies w(p(s),u(s)) =_S s [/math]
[math]\forall_{s \in S}\ \{\mathbf{while}\ \lnot n(s) \ \mathbf{do} \ s:= u(s) \ \mathbf{od}\}\ n(s)[/math]
oraz aksjomaty identyczności dla relacji [math]=_E[/math] i [math]=_S[/math]
jest strukturą stosów. koniec definicji.
Zbiór [math]E[/math] jest nazywany zbiorem elementów. Elementy zbioru [math]S[/math] to stosy. Działanie [math]w[/math] najczęściej jest nazywane push, działanie [math]u[/math] to operacja pop, działanie [math]p[/math] to operacja top. Predykat [math]n[/math] oznacza relację empty.
