|
|
Wprowadzenie do informatyki
Informatyka, I rok, egzamin zerowy
Egzamin pisemny, 15.12.97, czas: 75 min
|
- Dana jest następująca maszyna Turinga:
Niech x oznacza wartość liczby zapisanej w systemie binarnym
i będącej daną wejściową. Korzystając z wyrażeń języka Pascal
określ wartość y liczby binarnej, jaka pozostanie na taśmie po
zakończeniu pracy maszyny (np. y=2*x + 5).
- Dany jest następujący schemat translacji:
E: E '+' E {write('a');}
| E '*' E {write('b');}
| '1' {write('c');}
| '2' {write('d');}
;
W schemacie tym wyrażenia arytmetyczne są przedstawione
za pomocą gramatyki niejednoznacznej, czyli takiej,
dla której istnieje więcej niż 1 wywód prawostronny
(a także lewostronny). W przedstawionym schemacie translacji
objawia się to tym, że dla ciągu wejściowego "1+2*2" istnieją
2 translacje tego ciągu. Jedna z nich ma postać "cdadb".
Znajdź drugą możliwą translację ciągu "1+2*2".
- Niech D(*X, *Y, *Z) oznacza predykat opisujący dodawanie
(x + y = z), który był omawiany na wykładzie. Dane są następujące klauzule prologowe:
+G(Z,Z).
+G(S(Z),S(Z)).
+G(S(S(*X)),*Y)-D(*A,*B,*Y)
-G(S(*X),*A)-G(*X,*B).
Opisują one relację G(x,y) ş g(x)=y. Uzupełnij definicję
rekurencyjną funkcji g odpowiadającej tym klauzulom:
g(0)= 0, g(1)=1,
- Uzupełnij podany schemat blokowy tak, aby przedstawiał
algorytm obliczania największego wspólnego dzielnika dwóch
liczb. Np. największy wspólny dzielnik liczb 10 i 6 jest równy
2. Przyjąć, że a,b są zawsze liczbami całkowitymi i a,b > 0.
- W celi jest 5 więźniów. Ich życie można w dużym uproszczeniu
przedstawić następująco:
procedure ŻycieWięźnia;
begin
while true do
begin
DoczekajDoPosiłku;
Posiłek
end
end;
Posiłek polega na wzięciu wolnej łyżki, umyciu jej, zjedzeniu
posiłku i odłożeniu łyżki, która w tym momencie staje się wolna.
Problem w tym, że liczba łyżek jest mniejsza niż liczba więźniów i
czasami więzień musi poczekać, aż jakaś łyżka się zwolni.
Załóżmy, że mamy semafor uogólniony Lyzki,
którego początkowa wartość odpowiada liczbie łyżek w celi.
Uzupełnij poniższą procedurę Posilek tak, aby rozwiązanie było poprawne.
procedure Posilek;
|