Stosy - struktura algebraiczna: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
 
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, e, =\rangle </math></center>
+
<center><math>A = \langle E \cup S; w, u, p, n, =\rangle </math></center>
<br /> której uniwersum jest sumą dwu rozłącznych zbiorów <math>E</math> i <math>S</math>, z działaniami<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>n\colon S \rightarrow E </math><br />
+
<math>p\colon S \rightarrow E </math><br />
<math>e\colon S \rightarrow \{true, false\}</math><br />
+
<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>=_S \colon S \times S \rightarrow \{true, false\} </math><br />
Linia 15: Linia 15:
 
<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}\  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_{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>
+
<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

[math]A = \langle E \cup S; w, u, p, n, =\rangle [/math]


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.