Test GR2: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 1: Linia 1:
<quiz type="exclusive">
 
Jeśli <math>\displaystyle M</math> jest termem rachunku lambda, zaś <math>\displaystyle x</math> jest zmienną, to <math>\displaystyle \lambda M.x</math> nazywamy:
 
<rightoption reply="Dobrze">abstrakcją</rightoption>
 
<wrongoption reply="Źle">aplikacją</wrongoption>
 
<wrongoption reply="Źle">termem wolnym</wrongoption>
 
<wrongoption reply="Źle">to w ogóle nie jest term rachunku lambda</wrongoption>
 
</quiz>
 
 
<quiz type="exclusive">
 
W termie <math>\displaystyle \lambda xy.yz</math> wolna jest zmienna:
 
<wrongoption reply="Źle"><math>\displaystyle x</math></wrongoption>
 
<wrongoption reply="Źle"><math>\displaystyle y</math></wrongoption>
 
<rightoption reply="Dobrze"><math>\displaystyle z</math></rightoption>
 
<wrongoption reply="Źle">żadna</wrongoption>
 
</quiz>
 
 
<quiz type="exclusive">
 
Który term jest wynikiem <math>\displaystyle \alpha</math>-konwersji termu <math>\displaystyle \lambda x.xy</math>?
 
<wrongoption reply="Źle"><math>\displaystyle \lambda x.xz</math></wrongoption>
 
<wrongoption reply="Źle"><math>\displaystyle \lambda y.yy</math></wrongoption>
 
<rightoption reply="Dobrze"><math>\displaystyle \lambda z.zy</math></rightoption>
 
<wrongoption reply="Źle">żaden z wymienionych</wrongoption>
 
</quiz>
 
 
<quiz type="exclusive">
 
Wynikiem <math>\displaystyle \beta</math>-redukcji termu <math>\displaystyle (\lambda xy.xy)z</math> jest term:
 
<wrongoption reply="Źle"><math>\displaystyle \lambda x.xz</math></wrongoption>
 
<rightoption reply="Dobrze"><math>\displaystyle \lambda y.zy</math></rightoption>
 
<wrongoption reply="Źle"><math>\displaystyle \lambda zy.zy</math></wrongoption>
 
<wrongoption reply="Źle">żaden z wymienionych</wrongoption>
 
</quiz>
 
 
<quiz type="exclusive">
 
Aplikacja <math>\displaystyle PQ</math> zwana jest redeksem, jeśli:
 
<rightoption reply="Dobrze"><math>\displaystyle P</math> jest w postaci abstrakcji</rightoption>
 
<wrongoption reply="Źle"><math>\displaystyle Q</math> jest w postaci bstrakcji</wrongoption>
 
<wrongoption reply="Źle"><math>\displaystyle P</math> nie zawiera zmiennych wolnych</wrongoption>
 
<wrongoption reply="Źle"><math>\displaystyle Q</math> nie zawiera zmiennych wolnych</wrongoption>
 
</quiz>
 
 
<quiz type="exclusive">
 
Mówimy, że term jest w postaci normalnej, jeśli:
 
<rightoption reply="Dobrze">żaden jego podterm nie jest redeksem</rightoption>
 
<wrongoption reply="Źle">zawiera dokładnie jeden redeks</wrongoption>
 
<wrongoption reply="Źle">zawiera co najmniej jeden redeks</wrongoption>
 
<wrongoption reply="Źle">nie zawiera zmiennych wolnych</wrongoption>
 
</quiz>
 
 
<quiz type="exclusive">
 
Postać normalna (o ile istnieje) jest unikalna z dokładnością do:
 
<rightoption reply="Dobrze"><math>\displaystyle \alpha</math>-konwersji</rightoption>
 
<wrongoption reply="Źle"><math>\displaystyle \beta</math>-redukcji</wrongoption>
 
<wrongoption reply="Źle">i <math>\displaystyle \alpha</math>-konwersji, i <math>\displaystyle \beta</math>-redukcji</wrongoption>
 
<wrongoption reply="Źle">jest bezwzględnie unikalna</wrongoption>
 
</quiz>
 
 
<quiz type="exclusive">
 
Przymując standardową reprezentację liczb naturalnych w rachunku lambda,
 
term <math>\displaystyle \lambda mnsx.(ms)(nsx)</math> reprezentuje:
 
<rightoption reply="Dobrze">dodawanie</rightoption>
 
<wrongoption reply="Źle">mnożenie</wrongoption>
 
<wrongoption reply="Źle">potęgowanie</wrongoption>
 
<wrongoption reply="Źle">żadne z wymienionych tu działań</wrongoption>
 
</quiz>
 
 
<quiz type="exclusive">
 
Funkcje reprezentowalne w rachunku lambda (klasycznym, beztypowym)
 
odpowiadają dokładnie modelowi:
 
<rightoption reply="Dobrze">funkcji obliczalnych totalnych (nieczęściowych)</rightoption>
 
<wrongoption reply="Źle">funkcji obliczalnych częściowych</wrongoption>
 
<wrongoption reply="Źle">funkcji dających się obliczyć w stałej pamięci</wrongoption>
 
<wrongoption reply="Źle">żadnemu z wymienionych</wrongoption>
 
</quiz>
 
 
<quiz type="exclusive">
 
Operator punktu stałego to term <math>\displaystyle Y</math> taki, że dla dowolnego termu <math>\displaystyle M</math> aplikacja <math>\displaystyle YM</math> jest równa, modulo <math>\displaystyle \beta</math>-redukcja:
 
<wrongoption reply="Źle"><math>\displaystyle M</math></wrongoption>
 
<rightoption reply="Dobrze"><math>\displaystyle M(YM)</math></rightoption>
 
<wrongoption reply="Źle"><math>\displaystyle Y</math></wrongoption>
 
<wrongoption reply="Źle"><math>\displaystyle YM</math></wrongoption>
 
</quiz>
 
 
 
 
 
 
 
 
 
 
  
  

Wersja z 10:05, 29 wrz 2006


 0   0       1                  1            
 0   1       0                  1            
 1   0       1                  1            
 1   1       1                  1            


Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left| x \right|\ = \left\{ \begin{array}{rll} x & \text{ gdy }, x\geq 0 \\ -x & \text{ w przeciwnym przypadku}. \end{array} }


Parser nie mógł rozpoznać (nieznana funkcja „\nonumber”): {\displaystyle \displaystyle \nonumber w_3 &\rightarrow bv_3v_2w_3v_1v_3v_3v_2\ |\ aw_3v_1v_3v_3v_2\ |\ bv_3v_2v_1v_3v_3v_2 \\ \begin{array}{lll}\nonumber & & |\ av_1v_3v_3v_2\ |\ bv_3v_3v_2 \end{array}}

oraz

Parser nie mógł rozpoznać (nieznana funkcja „\nonumber”): {\displaystyle \displaystyle \nonumber w_3 &\rightarrow bv_3v_2w_3v_1v_3v_3v_2w_3\ |\ aw_3v_1v_3v_3v_2w_3\ |\ bv_3v_2v_1v_3v_3v_2w_3 \\ \begin{array}{lll}\nonumber & & |\ av_1v_3v_3v_2w_3\ |\ bv_3v_3v_2w_3 \end{array}}

Ostatecznie, gramatyka w postaci Greibach ma postać:

Parser nie mógł rozpoznać (nieznana funkcja „\nonumber”): {\displaystyle \displaystyle \nonumber v_1 &\rightarrow bv_3v_2w_3v_1v_3\ |\ aw_3v_1v_3\ |\ bv_3v_2v_1v_3\ |\ av_1v_3\ |\ bv_3 \\ \nonumber v_2 &\rightarrow bv_3v_2w_3v_1\ |\ aw_3v_1\ |\ bv_3v_2v_1\ |\ av_1\ |\ b \\ \nonumber v_3 &\rightarrow bv_3v_2w_3\ |\ aw_3\ |\ bv_3v_2\ |\ a \\ \nonumber w_3 &\rightarrow bv_3v_2w_3v_1v_3v_3v_2\ |\ aw_3v_1v_3v_3v_2\ |\ bv_3v_2v_1v_3v_3v_2 \\ \begin{array}{lll}\nonumber & & |\ av_1v_3v_3v_2\ |\ bv_3v_3v_2 bv_3v_2w_3v_1v_3v_3v_2w_3 \\ \nonumber & & |\ aw_3v_1v_3v_3v_2w_3\ |\ bv_3v_2v_1v_3v_3v_2w_3\ \\ \nonumber & & |\ av_1v_3v_3v_2w_3\ |\ bv_3v_3v_2w_3 \end{array}}














Algorytm Minimalizuj2 - algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji



  1  Wejście:  - automat taki, że .
  2  Wyjście: automat minimalny  dla .
  3  ;
  4  ;
  5  repeat
  6    Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle \slash \slash}
 oblicz : ;
  7    ;
  8    empty 
  9    for each  do
 10      flagtrue;
 11      for each  
 12        if not  then
 13          flagfalse;
 14        end if
 15      end for
 16      if flag=true and  then
 17        ;
 18      end if
 19    end for
 20  until 
 21  Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle S' \leftarrow S \slash \overline{\rho}_i}
;
 22  for each Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle [s]_{\overline{\rho}_i} \in S \slash \overline{\rho}_i}
 do
 23    for each  do
 24      ;
 25    end for
 26  end for
 27  ;
 28  ;
 29  return ;



Uzupelnij tytul

|| ||

|| || ||

|| || ||

|| || ||

|| || ||

|| || ||

|| || ||

|| || ||

|| || ||

... || ... || ... || ...




 alalalalaa
alala
Złożoność czasowa Złożoność pamięciowa
Maszyna dodająca



Maszyna rozpoznająca


0 1 ... ...
Cell1 Cell2


0 1
 0   1   1 
 1   0   1 


 0   1 
 1   0 


0 1
 0   0   0 
 1   0   1 
0 1
 0   0   1 
 1   1   1 
Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{q}} Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p} \wedge \textnormal{q}}
 0   0  0 1 1 1 1
 0   1  0 1 1 0 1
 1   0  0 1 0 1 1
 1   1  1 0 0 0 0


Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{q}} Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{r}} Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle (\textnormal{p} \wedge \textnormal{q})}
0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 1
0 1 0 0 0 1 1 1
0 1 1 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 1 0 1 0 1 1
1 1 0 1 0 1 1 1
1 1 1 1 1 0 1 1


Numer
funkcji




   
0 0 0 0 0  
1 0 0 0 1  
2 0 0 1 0  
3 0 0 1 1   Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}}
4 0 1 0 0  
5 0 1 0 1   Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{q}}
6 0 1 1 0  
7 0 1 1 1  
8 1 0 0 0  
9 1 0 0 1  
10 1 0 1 0  
11 1 0 1 1  
12 1 1 0 0  
13 1 1 0 1  
14 1 1 1 0  
15 1 1 1 1  


Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{q}} Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{r}}
0 0 0 1 0 1 0
0 0 1 1 1 0 1
0 1 0 0 1 0 1
0 1 1 0 0 1 0
1 0 0 0 1 1 1
1 0 1 0 0 0 0
1 1 0 1 0 0 0
1 1 1 1 1 1 1


Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{q}} Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{r}}
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1


Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{q}} Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{r}}
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1


0 1 2
 0   2   2   2 
 1   0   2   2 
 2   0   1   2 







Nagroda Goedla
Zobacz Nagroda Goedla]]

Nagroda Turinga
Zobacz Nagroda Turinga

Nagroda Knutha
Zobacz Nagroda Knutha


Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle g(C)=\begincases C\cup \{f(C')\} C \endcases }


Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle g(C)=\left\{\aligned C\cup \{f(C')\}\\C\endaligned \right}

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle c\forall d\; c\in C \land d\in C \land c\sqsubseteq d\implies c\sqsubseteq' d, (C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq') \iff C\subset C' \land \left\{\aligned \forall c \forall d\; &(c\in C\land d\in C) \implies (c\sqsubseteq d \iff c\sqsubseteq' d) \textrm{ oraz }\\ \forall c \forall d\; &(c\in C\land d\in C'\setminus C) \implies c\sqsubseteq' d \endaligned \right}


dla każdego Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \in A \\h(n', a) = g(h(n, a), n, a)} dla każdego i


dla każdego Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \in A \\ e(g(n, a), n, a)} dla każdego i