Test GR: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
W  tym wykładzie podamy  algorytmy konstrukcji  automatu minimalnego
<quiz type="exclusive">
i twierdzenia dowodzące ich poprawności.<br>
Programowanie imperatywne jest ściśle związane z budową sprzętu
komputerowego o architekturze:
<wrongoption reply="Źle">Dijkstry</wrongoption>
<wrongoption reply="Źle">Hoare'a</wrongoption>
<wrongoption reply="Źle">Turinga</wrongoption>
<rightoption reply="Dobrze">von Neumanna</rightoption>


==Algorytmy konstrukcji automatu minimalnego==
</quiz>


Dla języka rozpoznawanego <math>L</math> konstrukcję automatu minimalnego można  rozpocząć, startując z opisu języka danego na przykład przez wyrażenie regularne lub też jakiegoś automatu rozpoznającego ten język. W niniejszym wykładzie przedstawimy  algorytmy konstrukcji automatu minimalnego obejmujące oba wspomniane punkty startu. Jako pierwszy, nawiązując do rezulatów przedstawionych w poprzednim wykładzie, prezentujemy algorytm, dla którego punktem wyjścia jest język <math>L</math>. Prezentację poprzedzimy wprowadzeniem pewnej operacji na słowach zwanej pochodną J.Brzozowskiego.
<quiz type="exclusive">
Abstrakcją komórek pamięci (w paradygmacie imperatywnym) są:
<wrongoption reply="Źle">efekty uboczne podprogramów</wrongoption>
<wrongoption reply="Źle">pętle</wrongoption>
<wrongoption reply="Źle">podstawienia</wrongoption>
<rightoption reply="Dobrze">zmienne</rightoption>
</quiz>


{{definicja|1.1.||
<quiz type="exclusive">
Dziedziczenie jest cechą charakterystyczną dla programowania:
  <wrongoption reply="Źle">funkcyjnego</wrongoption>
  <wrongoption reply="Źle">imperatywnego</wrongoption>
  <rightoption reply="Dobrze">obiektowego</rightoption>
  <wrongoption reply="Źle">w logice</wrongoption>
</quiz>


Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem, a <math>\; u \in A^* \;</math> dowolnym słowem. '''Pochodną Brzozowskiego''' (residuum) z języka <math>L</math> względem słowa <math>u</math> nazywamy język
<quiz type="exclusive">
Obiekt to powiązanie danych z:
  <wrongoption reply="Źle">kontrolą temperatury procesora</wrongoption>
  <wrongoption reply="Źle">mechanizmem obsługi przerwań</wrongoption>
  <rightoption reply="Dobrze">operacjami na tych danych</rightoption>
  <wrongoption reply="Źle">systemową obsługą wejścia-wyjścia</wrongoption>
</quiz>


<center><math> u^{-1}L=\{w \in A^*\;\; :\;\;\; uw \in L \}.</math></center>
<quiz type="exclusive">
}}
W programowaniu funkcyjnym nie występują:
  <rightoption reply="Dobrze">pętle</rightoption>
  <wrongoption reply="Źle">wywołania rekurencyjne</wrongoption>
  <wrongoption reply="Źle">składanie funkcji</wrongoption>
  <wrongoption reply="Źle">tablice</wrongoption>
</quiz>


Podczas obliczeń  pochodnych Brzozowskiego (residuów języka <math>L</math>) można wykorzystać poniższe równości.
<quiz type="exclusive">
Automatyczne dowodzenie twierdzeń (prostych...) jest możliwe w programowaniu:
  <wrongoption reply="Źle">funkcyjnym</wrongoption>
  <wrongoption reply="Źle">imperatywnym</wrongoption>
  <rightoption reply="Dobrze">obiektowym</rightoption>
  <wrongoption reply="Źle">w logice</wrongoption>
</quiz>


Niech <math>L_1, L_2\subset A^* \;</math> będą dowolnymi językami, <math>a \in A</math> dowolną literą, a <math> u,v \in A^*</math> dowolnymi słowami. Prawdziwe są  następujące równości:
<quiz type="exclusive">
Język C++ reprezentuje paradygmat:
  <wrongoption reply="Źle">funkcyjny</wrongoption>
  <rightoption reply="Dobrze">imperatywny i obiektowy</rightoption>
  <wrongoption reply="Źle">logiczny</wrongoption>
  <wrongoption reply="Źle">żaden z wymienionych</wrongoption>
</quiz>


<center><math>\begin{array}{rll}\nonumber u^{-1}(L_1 \cup L_2) & = & u^{-1}L_1 \cup u^{-1}L_2, \\
<quiz type="exclusive">
\nonumber u^{-1}(L_1 \backslash L_2) & = & u^{-1}L_1 \backslash
Pierwszym językiem obiektowym był język:
u^{-1}L_2, \\
  <wrongoption reply="Źle">Ada</wrongoption>
\nonumber u^{-1}(L_1 \cap L_2) & = & u^{-1}L_1 \cap u^{-1}L_2, \\
  <wrongoption reply="Źle">C++</wrongoption>
\nonumber a^{-1}(L_1L_2) & = & (a^{-1}L_1)L_2 \mbox{, jeśli }
  <wrongoption reply="Źle">Pascal</wrongoption>
1 \notin L_1, \\
  <rightoption reply="Dobrze">Simula 67</rightoption>
\nonumber a^{-1}(L_1L_2) & = & (a^{-1}L_1)L_2 \cup a^{-1}L_2 \mbox{,
</quiz>
jeśli } 1 \in L_1, \\
\nonumber a^{-1}L^* & = & (a^{-1}L)L^*, \\
\nonumber v^{-1}(u^{-1}L) & = & (uv)^{-1}L.
\end{array}</math></center>


{{przyklad|1.1.||
<quiz type="exclusive">
Czy optymalizacja kodu wykonywana przez kompilator może poprawić
asymptotyczną złożoność obliczeniową programu?
  <wrongoption reply="Źle">nie, nigdy</wrongoption>
  <rightoption reply="Dobrze">tak, ale rzadko</rightoption>
  <wrongoption reply="Źle">tak, często tak jest</wrongoption>
  <wrongoption reply="Źle">tak, jest tak praktycznie zawsze (po to jest optymalizacja)</wrongoption>
</quiz>


Obliczmy wszystkie pochodne dla języka <math>L=a^+b^+</math>. Okazuje się, że są tylko cztery różne pochodne liczone względem <math>a</math>, <math>b</math>, <math>ab</math> i słowa pustego <math>1</math>. Mianowicie:<br>
<quiz type="exclusive">
<math> a^{-1}L=a^*b^+ </math>,<br>
Składnię języków programowania opisuje się za pomocą gramatyk:
<math> b^{-1}L= \emptyset </math>,<br>
   <wrongoption reply="Źle">regularnych</wrongoption>
<math>ab^{-1} L=b^*</math>,<br>
   <rightoption reply="Dobrze">bezkontekstowych</rightoption>
<math>1^{-1}L=L</math>.<br>
   <wrongoption reply="Źle">kontekstowych</wrongoption>
Dla wszystkich innych słów otrzymujemy uzyskane powyżej języki, co wynika z własności pochodnych (patrz wyżej wypisane równości) i z następujacych obliczeń: <br>
  <wrongoption reply="Źle">typu 0</wrongoption>
<math>\forall n \in \mathbb{N} (a^n)^{-1}L=a^*b^+  </math>,<br>
</quiz>
<math>\forall n \in \mathbb{N} (b^n)^{-1}L= \emptyset </math>,<br>
<math>\forall n \in \mathbb{N}(ab^n)^{-1} L=b^*</math>.
}}
 
Zauważmy również, nawiązując raz jeszcze do rezulatów przedstawionych w poprzednim wykładzie, że prawdziwa jest następująca równoważność wiążąca wprowadzone pojęcie pochodnej Brzozowskiego z prawą kongruencją syntaktyczną:
 
<center><math>u \;P{^r}_L\; v  \Longleftrightarrow u^{-1}L=v^{-1}L.</math></center>
 
Rozpisując z definicji lewą stronę tej równoważności, otrzymujemy, iż dla dowolnego słowa <math>z \in A^*</math> słowo <math>uz \in L</math> wtedy i tylko wtedy, gdy  <math>vz \in L</math>. A to równoważnie oznacza (znów z definicji), że  <math>u^{-1}L=v^{-1}L.</math>
 
Z uzasadnionej równoważności oraz twierdzenia 3.4 o prawej kongruencji syntaktycznej z poprzedniego wykładu wnioskujemy równoważność rozpoznawalności języka <math>L</math> i skończonej ilości różnych pochodnych Brzozowskiego tego języka.
 
Pierwszy z przedstawianych algorytmów będzie konstruował automat minimalny, wyznaczając prawą kongruencję automatową poprzez zastosowanie metody pochodnych Brzozowskiego. Metoda ta umożliwia przeprowadzanie odpowiednich obliczeń bezpośrednio na wyrażeniach regularnych. Ogólny opis algorytmu jest następujący. Stany konstruowanego automatu minimalnego etykietowane są zbiorami odpowiadającymi pewnym językom. Mając dany język <math>L</math>, ustanawiamy stan początkowy automatu jako <math>L</math>, wpisujemy go na listę <math>\mathcal{L}</math> i obliczamy <math>a^{-1}L</math> dla każdej litery <math>a \in A</math>. Jeśli wśród obliczonych wartości znajduje się język niewystępujący na liście, dodajemy go do listy. Obliczenia pochodnych Brzozowskiego wykonujemy, dopóki będziemy uzyskiwać nowe języki (nowe stany). Funkcja przejść konstruowanego automatu minimalnego zdefiniowana
jest następująco:
 
<center><math>f(X, a)=a^{-1}X,</math></center> gdzie <math>X</math> jest pewnym językiem  z listy <math>\mathcal{L}</math>.
 
Obliczone języki określają stany automatu minimalnego.
 
{{uwaga|[Dla zainteresowanych]||
 
Obliczone języki określające stany automatu minimalnego  to
elementy monoidu syntaktycznego języka <math>L</math>.
}}
Automatem minimalnym dla automatu <math>\mathcal{A}=(S, A, f, s_0, T)</math> będzie zatem automat
 
<center><math>\mathcal{A}_L=(S_L, A, f_L, s_0^L, T_L),</math></center>
gdzie:
 
* <math>S_L=\{u^{-1}L:\ u \in A^*\}</math>,
 
* <math>s_0^L = L </math>,
 
* <math>T_L = \{u^{-1}L:\ u \in L\}</math>,
 
* <math>f_L(u^{-1}L,a) = a^{-1}(u^{-1}L)=(ua)^{-1}L</math>.
 
Jeśli zdefiniujmy odwzorowanie <math>\nu: S \rightarrow S_L</math>, kładąc:
<center><math>\nu(s)=u^{-1}L, \mbox{ gdzie } s=f(s_0,u),</math></center>
 
to można dowieść, że <math>\nu</math> jest dobrze określone, jest epimorfizmem oraz <math>\nu(s_0) = s_0^L</math> - porównaj twierdzenie 3.1 z wykładu 4. Prawdą jest też, iż <math>s \in T</math> wtedy i tylko wtedy, gdy <math>\nu(s) \in T_L</math> oraz że następujący diagram komutuje:
 
<center><math>\beginCD
s @>{a}>> s' @. \ \ \ \ \mbox{ w } \mathcal{A} \\
@V{\nu}VV  @V{\nu}VV \\
u^{-1}L @>{a}>> (ua)^{-1}L @. \ \ \ \ \mbox{ w } \mathcal{A}_L.
\endCD  </math></center>
 
Formalny zapis algorytmu przedstawiony jest poniżej.
{{algorytm|Minimalizuj1 - algorytm minimalizacji wykorzystujący pochodne Brzozowskiego|algorytm minimalizacji wykorzystujący pochodne Brzozowskiego|
  1  Wejście: <math>\mathcal{A}=(S, A, f, s_0, T)</math> - automat taki, że <math>L=L(\mathcal{A})</math>
  2  Wyjście: automat minimalny <math>\mathcal{A}'=(S_L, A, f_L, s_L,
T_L)</math> dla <math>\mathcal{A}S_L \leftarrow \{L\}</math>;
  3  <math>S_L \leftarrow \{L\}</math>
  4  '''włóż'''<math>(\mathcal{L},L)</math>;
  5  '''while''' <math>\mathcal {L}\ne \emptyset</math> '''do'''
  6   <math>M \leftarrow</math> '''zdejmij'''(<math>\mathcal {L}</math>); 
  7    '''for''' '''each''' <math>a \in A</math> '''do'''
  8      <math>N \leftarrow a^{-1}M</math>;
  9      '''if''' <math>N \cap S_L = \emptyset</math> '''then'''
  10      <math>S_L \leftarrow S_L \cup \{N\}</math>;
  11      '''włóż'''<math>(\mathcal{L},N)</math>;
  12    '''end''' '''if'''
  13    '''end''' '''for'''
  14  '''end''' ''' while''' 
  15  '''for''' '''each''' <math>M \in S_L</math> '''do'''
  16    '''for''' '''each''' <math>a \in A</math> '''do'''
  17      <math>f_L(M,a) \leftarrow a^{-1}M</math>;
  18   '''end''' '''for'''
  19  '''end''' '''for'''
  20  <math>s_L \leftarrow L</math>;
  21  <math>T_L \leftarrow \{u^{-1}L:\ u \in L\}</math>;
  22  '''return''' <math>\mathcal{A}'</math>;
}}
 
 
Funkcja '''zdejmij'''<math>(\mathcal{L})</math>, występująca w linii 6., zdejmuje z kolejki <math>\mathcal{L}</math> pierwszy element i zwraca go jako swoją wartość. Procedura '''włóż'''<math>(\mathcal{L},L)</math>, występująca w liniach 4. oraz 11., wstawia na koniec kolejki <math>\mathcal{L}</math>  element <math>L</math>.
 
{{przyklad|1.2.||
 
Dla języka <math>L=a^+b^+</math> z przykładu 1.1 w wyniku działania powyższego algorytmu
otrzymamy czterostanowy automat
<math>\mathcal{A}_L=(S_L,A,  f, L, T),</math> gdzie<br>
<math>S_L= \{L, a^*b^+  ,\emptyset, b^*\}</math>,<br>
a funkcja
przejść zadana jest grafem: <br>
 
RYSUNEK ja-lekcja5-w-rys1
 
}}
 
Prezentowane poniżej twierdzenie uzasadnia kolejny algorytm  konstrukcji automatu minimalnego. Tym razem punktem wyjścia jest dowolny automat rozpoznający język <math>L </math>.
 
{{uwaga|[Dla zainteresowanych]||
 
Algorytm oblicza również monoid syntaktyczny języka <math>L </math>.
 
}}
 
Analogicznie do konstrukcji relacji <math>\rho _{i} </math>, przedstawionej w wykładzie 4, możemy określić ciąg odpowiednich relacji na zbiorze stanów dowolnego automatu rozpoznającego język <math>L </math>. Relacje te służą do efektywnego określenia automatu minimalnego, równoważnego zadanemu.
 
{{twierdzenie|1.1.||
 
Niech <math>\mathcal{A}= (S,A,f,s_0,T)</math> będzie dowolnym automatem i niech <math>L = L(\mathcal{A})</math>. Przez <math>\approx _\mathcal{A} \subset S \times S</math> oznaczmy relację równoważności zawierającą dwie klasy równoważności <math>T</math> i <math>S\setminus T</math>. Przez <math>\overline \rho_i</math> dla <math>i\in \Bbb N</math>
oznaczmy zstępujący ciąg relacji określony następująco:
 
<math>\overline \rho _1 = \approx _\mathcal{A} </math>, a dla <math> i = 2,... </math> przyjmijmy
 
<math>\overline \rho _i = \{ (s,t) \in \; S \times S \; : \;\; \forall a \in A \cup \{1\} \; \; f(s,a) \overline{\rho}_{i-1} f(t,a) \;\}. \;</math>.
 
Wtedy <math>\bigcap \overline \rho_i</math> jest największą prawą kongruencją automatową zawartą w relacji <math>\overline \rho_1 = \approx _ \mathcal{A} </math> i automat minimalny ma postać
 
<center><math>\mathcal{A}_{L}=\left( S/ \bigcap \overline \rho _i,A,f^*,[s_{0}],T/ \bigcap \overline \rho _i \right) </math>.</center>
 
}}
 
Dowód tego twierdzenia przebiega analogicznie do dowodu twierdzenia 3.3 z wykładu 4.
 
Algorytm działajacy w oparciu o powyższe twierdzenie na podstawie
zadanego automatu <math>A = (S, A, f, s_0, T)</math>, konstruuje efektywnie automat minimalny dla <math>\mathcal{A}</math>, obliczając ciąg relacji <math>\rho _1</math>. Proces konstrukcji przebiega w sposób iteracyjny. Zaczynamy od zdefiniowania relacji <math>\approx _\mathacal {A}</math>, która posiada tylko dwie klasy abstrakcji: do pierwszej z nich należą wszystkie stany końcowe, a do drugiej - wszystkie pozostałe stany. Tak więc
 
<center><math>\forall s, t \in S\ s \approx_\mathcal{A} t \Leftrightarrow (s \in T \wedge t \in T) \vee (s \in S \backslash T \wedge t \in S \backslash T)</math>.</center>
 
Definiujemy pierwszą z relacji <math>\overline \rho</math>, czyli relację <math>\overline \rho_1</math>  jako równą <math>\approx \mathcal {A}</math>, a następnie, dla każdej obliczonej już relacji
<math>\overline \rho_i-1</math>, obliczamy relację <math>\overline \rho_i</math> w następujący sposób:
 
<center><math>s_1 \overline \rho_i s_2 \Leftrightarrow (s_1 \overline \rho_{i-1} s_2) \wedge (\forall a \in A\ f(s_1, a) \overline \rho_{i-1} f(s_2,a))</math>.</center>
 
Nowo obliczona relacja <math>\overline \rho_i</math> albo podzieli jedną lub kilka klas abstrakcji relacji <math>\overline \rho_{i-1}</math>, albo będzie identyczna z relacją <math>\overline \rho_{i-1}</math>. Jeśli zajdzie ta druga sytuacja, to znaczy, że dla każdego <math>j>i</math> w oczywisty sposób spełniona jest równość <math>\overline \rho_j=\overline \rho_i</math>, czyli ciąg relacji ustabilizuje się. W tym momencie algorytm kończy swoje działanie i klasy abstrakcji relacji <math>\overline \rho_i</math> będą reprezentować stany automatu minimalnego.
 
{{algorytm|Minimalizuj2 - algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji|algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji|
  1  Wejście: <math>\mathcal {A} = (S, A, f, s_0, T)</math> - automat taki, że <math>L = L(\mathcal{A})</math>
  2  Wyjście: automat minimalny <math>\mathcal{A}' = (S',A',f', s_0',
T')</math> dla <math>\mathcal{A}</math>
  3  <math>\overline \rho_1 \leftarrow \approx_ \mathcal{A}</math>;
  4  <math>i \leftarrow 1</math>;
  5  '''repeat'''
  6    // oblicz <math>\overline \rho_i</math>: <math>s_1\overline\rho_{i}s_2 \leftrightarrow (s_1\overline\rho_{i-1}s_2) \wedge (\forall a \in A  f(s_1, a)\overline\rho_{i-1}f(s_2, a))</math>; 
  7   <math>i \leftarrow i+1</math>
  8    '''empty'''(\overline \rho_i)
  9    '''for''' '''each''' <math>(s_1, s_2) \in S \times S</math> '''do'''
  10    flag <math>\leftarrow</math> '''true'''; 
  11  '''end''' '''for'''
  12  '''end''' '''if'''
  13  '''while''' <math>\mathcal{L} \neq \emptyset</math> '''do'''
  14  <math>(Y, a) \leftarrow </math> '''zdejmij''' <math>(\mathcal{L})</math>;
  15  <math>\mathcal{X} \leftarrow \{X \in P:\ |X \slash \rho^a_Y| =
2\}</math>;
  16  '''for''' '''each''' <math>X \in \mathcal{X}</math> '''do'''
  17    '''for''' '''each''' <math> b \in A</math> '''do'''
  18      <math>\{X_1, X_2\} \leftarrow X \slash \rho^a_Y</math>;      <math>\triangleright </math><math>X \slash \rho^a_Y</math> zawiera dwie klasy abstrakcji
  19      <math>P \leftarrow (P \backslash X) \cup X_1 \cup X_2</math>;
  20      '''if''' <math>(X, b) \in \mathcal{L}</math> '''then'''
  21        <math>\mathcal{L} \leftarrow \mathcal{L} \backslash (X, b)</math>;            <math>\triangleright</math> zdejmij z <math>\mathcal{L}</math> dokładnie parę <math>(X, b)</math>
  22        '''włóż'''<math>(\mathcal{L},(X_1,b))</math>;
  23        '''włóż'''<math>(\mathcal{L},(X_2,b))</math>;
  24      '''else''' 
  25        '''if''' <math>|X_1|<|X_2|</math> '''then'''
  26          '''włóż'''<math>(\mathcal{L},(X_1,b))</math>;
  27        '''else'''
  28          '''włóż'''<math>(\mathcal{L},(X_2,b))</math>;
  29  '''return'''
 
}}
 
 
{{cwiczenie|[Uzupelnij]||
 
Zminimalizujemy automat </math>{A}<nowiki>=</nowiki>(S,A,f,s_0,T)<math>, dla którego\\
</math>S<nowiki>=</nowiki> s_{0},s_{1},s_{2},s_{3},s_{4},s_5 , A<nowiki>=</nowiki>a,b,
T<nowiki>=</nowiki>s_1, s_{2},s_{4}  <math>,
a funkcja przejść określona jest przy pomocy grafu.\\
RYSUNEK ja-lekcja5-w-rys2\\
Konstruujemy ciąg
relacji </math>{}_i<math>.
 
Na początku  </math>{}_1<math> dzieli </math>S<math> na dwie klasy
abstrakcji; pierwsza zawiera stany końcowe, a druga -- wszystkie
pozostałe, czyli uzyskujemy dwa zbiory </math>s_1,s_2,s_4<math> oraz
</math>s_0, s_3, s_5<math>.
 
Obliczmy </math>{}_2<math> (pierwszy przebieg pętli w liniach 5.-20. algorytmu). Aby dwa elementy
(stany) </math>s<math> i </math>t<math> były ze sobą w relacji </math>{}_2<math> muszą
być ze sobą w relacji </math>{}_1<math> oraz musi zachodzić
</math></center> a  A  f(s, a) {}_1 f(t,a).<center><math>
Czyli kolejna, nowa relacja może ewentualnie podzielić już
istniejące zbiory zdefiniowane przez poprzednią relację. Nie może
więc zajść taka sytuacja, że w jednej klasie abstrakcji relacji
</math>{}_{i+1}<math> znajdą się elementy z różnych klas
abstrakcji relacji </math>{}_i<math>.
 
Rozważmy najpierw zbiór </math>s_1, s_2, s_4<math>. Oczywiście każde dwa
stany z tego zbioru są ze sobą w relacji </math>{}_1<math>.
Zauważmy, że </math>f(s_2, a)<nowiki>=</nowiki>f(s_4,a)<nowiki>=</nowiki>s_2<math>, </math>f(s_2,b)<nowiki>=</nowiki>f(s_4,b)<nowiki>=</nowiki>s_4<math>, więc
</math>s_2 {}_2 s_4<math> (bo </math>s_2 {}_1 s_2<math> oraz </math>s_4 {}_1 s_4<math>).
Ponieważ </math>f(s_1,b)<nowiki>=</nowiki>s_5<math> i </math>f(s_2,b)<nowiki>=</nowiki>s_4<math>, a wiemy, że </math>s_5<math> nie jest
w relacji </math>{}_1<math> z  </math>s_4<math>, zatem stany </math>s_1<math> i </math>s_2<math>
nie mogą być ze sobą w relacji </math>{}_2<math>, a to oznacza, że
także stany </math>s_1<math> i </math>s_4<math> nie mogą być ze sobą w relacji
</math>{}_2<math>.
 
W analogiczny sposób można sprawdzić, że relacja </math>{}_2<math> nie
podzieli zbioru </math>s_0, s_3, s_5<math>. Ostatecznie, po pierwszym
wykonaniu pętli algorytmu minimalizacji obliczyliśmy relację
</math>{}_2<math>, która dzieli </math>S<math> na następujące podzbiory:
</math></center>s_1, s_2, s_4, s_0, s_3, s_5.<center><math>
 
W kolejnym kroku obliczamy </math>{}_3<math>. Zbiór </math>s_1<math>
oczywiście nie może być już podzielony na mniejsze podzbiory.
Łatwo zauważyć, że </math>{}_3<math> nie podzieli także zbioru </math>s_2,
s_4<math>.
 
Rozważmy teraz zbiór </math>s_0, s_3, s_5<math>. Mamy </math>f(s_3, a)<nowiki>=</nowiki>f(s_5, a)<math> oraz
</math>f(s_3, b)<nowiki>=</nowiki>s_3<math>, </math>f(s_5, b)<nowiki>=</nowiki>s_5<math> i wiadomo, że </math>s_3 {}_2
s_5<math>, zatem </math>s_3<math> i </math>s_5<math> będą ze sobą w relacji
</math>{}_3<math>.
 
Ponieważ </math>f(s_0, a)<nowiki>=</nowiki>s_2<math> i </math>f(s_3, a)<nowiki>=</nowiki>s_1<math>, ale </math>s_2<math> i </math>s_1<math> nie są
ze sobą w relacji </math>{}_2<math>, zatem nie mogą być także ze
sobą w relacji </math>{}_3<math>. Relacja </math>{}_3<math>
dzieli więc zbiór </math>s_0, s_3, s_5<math> na zbiory </math>s_0<math> oraz
</math>s_3, s_5<math>.
 
Podział zbioru </math>S<math> przez relację </math>{}_3<math> wygląda więc
następująco: </math></center>s_0, s_1, s_2, s_4, s_3, s_5.<center><math>
 
Relacja </math>{}_4<math> nie podzieli już ani zbioru </math>s_2,
s_4<math>, ani zbioru </math>s_3, s_5<math>, więc uzyskujemy równość
</math>{_4}<nowiki>=</nowiki>{}_3<math> i ponieważ ciąg relacji się
ustabilizował, algorytm kończy działanie.
 
Podsumowując, mamy:
 
; </math>{} _{1}<math>
:  </math>s_1, s_{2},s_{4}, s_{0},s_{3},s_5,  <math>
 
; </math>{} _{2}<math>
:  </math>s_{1},s_2,s_{4}, s_{0},s_{3},s_5,<math>
 
; </math>{} _{3}<math>
:  </math>s_{1},s_2,s_{4}, s_{0},s_{3},s_5.{} _{3}<nowiki>=</nowiki>{} _{4}<math> i równoważny minimalny automat </math>{A}_L<nowiki>=</nowiki>(S,f^*,s_0,T)<math> ma </math>4<math> stany. \\
</math>q_0<nowiki>=</nowiki>s_{0}, q_1<nowiki>=</nowiki>s_{1}, q_2 <nowiki>=</nowiki> s_2,s_{4}, q_3
<nowiki>=</nowiki>s_{3},s_5<math>, </math>T<nowiki>=</nowiki>q_1 ,q_2<math>.
Jak łatwo zauważyć jest to automat z przykładu 3.1 zamieszczonego w wykładzie 4.
 
RYSUNEK ja-lekcja5-w-rys3
 
}}
 
Jednym z najczęściej stosowanych algorytmów automatu minimalnego jest algorytm, który
buduje "tabelkę" na podstawie której określa się automat minimalny.
Poprawność tego
algorytmu również uzasadnia twierdzenie  [[##twrho|Uzupelnic twrho|]].
 
W algorytmie tym wyznaczać będziemy tzw. stany rozróżnialne.
Algorytm działa w czasie </math>O(|A|n^2)<math>, gdzie </math>|A|<math> jest mocą
alfabetu, a </math>n<math> -- liczbą stanów automatu wejściowego, czyli
podlegajacego  minimalizacji. Złożoność pamięciowa jest również
</math>O(|A|n^2)<math>. Prezentowany algorytm nosi nazwę algorytmu
Hopcrofta-Ullmana. Znana w literaturze jest pewna zmodyfikowana
wersja tego algorytmu. Jest to algorytm Aho-Sethiego-Ullmana, który
ma tę samą złożoność czasową, ale lepszą złożoność pamięciową -
</math>O(|A|n)<math>. Natomiast w ramach ćwiczeń prezentujemy jeszcze jeden
algorytm, znany jako algorytm minimalizacji Hopcrofta. Czas
działania  tego algorytmu wynosi </math>O(n  n)<math>.
 
Niech  będzie relacją zdefiniowaną przez funkcję przejść automatu
w następujący sposób:
</math></center>p  q  w  A^* (f(p,w)  T
f(q,w)  T).<center><math>
 
\begindefin 
Stany </math>p<math> i </math>q<math> są równoważne, jeśli </math>p  q<math>.
\enddefin
 
Jeśli stany nie są równoważne, to będziemy mówić, że są
rozróżnialne.
 
Zadaniem algorytmu jest wyznaczenie stanów równoważnych, celem ich
utożsamienia ze sobą. Algorytm musi zdecydować, dla każdej pary
stanów </math>(p,q)<math>, czy są one rozróżnialne. Jeśli pod koniec działania
algorytmu okaże się, że nie stwierdziliśmy rozróżnialności tych
stanów, to znaczy, że są one równoważne; następuje ich utożsamienie,
czyli "połączenie" ich w jeden stan. Gdy takiego połączenia dokonamy
dla wszystkich par stanów, wobec których nie stwierdziliśmy ich
rozróżnialności, powstanie automat o minimalnej liczbie stanów.
 
W praktyce algorytm nie wyznacza stanów równoważnych, ale stany
rozróżnialne, gdyż jest to po prostu łatwiejsze. Po wyznaczeniu
wszystkich par stanów rozróżnialnych pozostałe pary stanowić będą
stany równoważne.
 
W algorytmie wykorzystywać będziemy tablicę list </math>{L}[p,q]<math>,
po jednej liście dla każdej pary stanów. Funkcja
</math>'''initialize'''({L}[p,q])<math> inicjalizuje listę pustą,
funkcja </math>'''zdejmij'''({L}[p,q])<math> zdejmuje jeden z
elementów, natomiast funkcja
</math>'''włóż'''({L}[p,q],x)<math> wkłada element </math>x<math> na listę
</math>{L}[p,q]<math>. Funkcja </math>'''empty'''({L}[p,q])<math>
zwraca wartość </math>'''true'''<math> gdy lista jest pusta, oraz
</math>'''false'''<math> w przeciwnym wypadku. Zwróćmy uwagę, że elementami
każdej z list </math>{L}[p,q]<math> są pary stanów </math>(s,t) S S<math>.
 
\newpage
 
\beginalgorithm 
\caption{\textsc{Minimalizuj3} -- algorytm minimalizacji
wykorzystujący relację }
\beginalgorithmic [1]
\STATE Wejście: </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math> -- automat
 
\STATE Wyjście: </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math> -- automat
minimalny taki, że </math>L({A}')<nowiki>=</nowiki>L({A})<math>.
 
\FOR{\textbf{each} </math>p  T<math>}
 
\FOR{\textbf{each} </math>q  S  T<math>}
 
\STATE \textbf{zaznaczone}</math>[p,q]  1<math>;
 
\STATE \textbf{initialize}(</math>{L}[p,q]<math>)
 
\ENDFOR
 
\ENDFOR
 
\FOR{</math>'''each'''(p,q)  (T  T)  ((S  T)
(S  T))<math>}
 
\STATE \textbf{zaznaczone}</math>[p,q]  0<math>;
 
\ENDFOR
 
\FOR{</math>'''each ''' (p,q)  (T  T)  ((S  T)
(S  T))<math>}
 
\STATE flag\textbf{false}
 
\FOR{\textbf{each } </math>a  A<math>}
 
\IF{ \textbf{zaznaczone}</math>[f(p,a),f(q,a)]<nowiki>=</nowiki>1<math>}
\STATE flag\textbf{true};
 
\ENDIF
\ENDFOR
 
\IF{flag=\textbf{true}}
 
\STATE \textsc{Oznacz}</math>(p,q)<math>;\hfill  para
</math>(f(p,a),f(q,a))<math> była oznaczona dla pewnego </math>a<math>;
 
\ELSE
 
\FOR{\textbf{each } </math>a  A<math>}
 
\IF{</math>f(p,a) f(q,a)<math>}
 
\STATE \textbf{włóż}</math>({L}[p,q],(f(p,a),f(q,a)))<math>;
 
\ENDIF
 
\ENDFOR
 
\ENDIF
 
\ENDFOR
 
\STATE </math>S'  S _<math>;\hfill
relacja  jest dopełnieniem tabeli </math>'''zaznaczone'''<math>
 
\FOR{\textbf{each} </math>[s]_{ }  S _<math>}
 
\FOR{\textbf{each} </math>a  A<math>}
 
\STATE </math>f'([s]_{},a)  [f(s,a)]_{}<math>;
 
\ENDFOR
 
\ENDFOR
 
\STATE </math>s_0'  [s_0]_{}<math>;
 
\STATE </math>T'  [t]_{}:t  T<math>;
 
\RETURN </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math>;
 
\endalgorithmic
\endalgorithm
 
Występujaca w algorytmie procedura \textsc{Oznacz} opisana jest poniżej.
 
\beginalgorithm
\beginalgorithmic [1]
 
\STATE \textbf{procedure} \textsc{Oznacz}</math>(p,q  S)<math>
 
\IF{\textbf{zaznaczone}</math>[p,q]<nowiki>=</nowiki>1<math>}
\STATE{ \textbf{return}}
\ENDIF
 
\STATE{\textbf{zaznaczone}</math>[p,q] 1<math>}
 
\WHILE{\textbf{not empty}</math>({L}[p,q])<math>}
\STATE{\textsc{Oznacz}(\textbf{zdejmij}</math>({L}[p,q])<math>)}
\ENDWHILE
 
\STATE \textbf{end procedure}
\endalgorithmic
\endalgorithm
 
Działanie algorytmu łatwo przedstawić na tabelce, która
złożona jest z kwadratów -- pól, odpowiadających parom stanów automatu.
Fakt znalezienia przez algorytm pary stanów rozróżnialnych
zaznaczamy symbolem "x" w polu tabelki odpowiadającym tej parze, co
wykorzystamy w przykładzie.
 
{{cwiczenie|[Uzupelnij]||
 
Zminimalizujemy automat przedstawiony na rysunku
[[##ja-lekcja5-w-rys4|Uzupelnic ja-lekcja5-w-rys4|]], używając algorytmu \textsc{Minimalizuj3}.
 
RYSUNEK ja-lekcja5-w-rys4
 
Proces działania algorytmu i konstrukcji tabelki przedstawiony jest
na poniższej animacji
}}
 
TUTAJ ANIMACJA. Opis animacji znajduje się w pliku
ja-lekcja5-w-anim1.pdf. Wygląd ekranu animacji znajduje się w pliku
ja-lekcja5-w-anim1.jpg.\\
 
Wypełniona tabelka po zakończeniu działania algorytmu przedstawiona
jest na rysunku [[##ja-lekcja5-w-rys5|Uzupelnic ja-lekcja5-w-rys5|]].
 
RYSUNEK ja-lekcja5-w-rys5.
 
Z tabelki odczytujemy, że stanami równoważnymi są stany </math>s_1, s_5<math>,
stany </math>s_2, s_8<math> oraz stany </math>s_4, s_6<math>. Automat minimalny
przedstawiony jest na rysunku [[##ja-lekcja5-w-rys6|Uzupelnic ja-lekcja5-w-rys6|]].
 
RYSUNEK ja-lekcja5-w-rys6.</math>

Wersja z 18:50, 12 wrz 2006

Programowanie imperatywne jest ściśle związane z budową sprzętu komputerowego o architekturze:

Dijkstry

Hoare'a

Turinga

von Neumanna

Abstrakcją komórek pamięci (w paradygmacie imperatywnym) są:

efekty uboczne podprogramów

pętle

podstawienia

zmienne

Dziedziczenie jest cechą charakterystyczną dla programowania: 

  

 funkcyjnego 


  

 imperatywnego 


  

 obiektowego 


  

 w logice

Obiekt to powiązanie danych z: 

  

 kontrolą temperatury procesora 


  

 mechanizmem obsługi przerwań 


  

 operacjami na tych danych 


  

 systemową obsługą wejścia-wyjścia

W programowaniu funkcyjnym nie występują: 

  

 pętle 


  

 wywołania rekurencyjne 


  

 składanie funkcji 


  

 tablice

Automatyczne dowodzenie twierdzeń (prostych...) jest możliwe w programowaniu: 

  

 funkcyjnym 


  

 imperatywnym 


  

 obiektowym 


  

 w logice

Język C++ reprezentuje paradygmat: 

  

 funkcyjny 


  

 imperatywny i obiektowy 


  

 logiczny 


  

 żaden z wymienionych

Pierwszym językiem obiektowym był język: 

  

 Ada 


  

 C++ 


  

 Pascal 


  

 Simula 67

Czy optymalizacja kodu wykonywana przez kompilator może poprawić asymptotyczną złożoność obliczeniową programu? 

  

 nie, nigdy 


  

 tak, ale rzadko 


  

 tak, często tak jest 


  

 tak, jest tak praktycznie zawsze (po to jest optymalizacja)

Składnię języków programowania opisuje się za pomocą gramatyk: 

  

 regularnych 


  

 bezkontekstowych 


  

 kontekstowych 


  

 typu 0

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_GR&oldid=49208”