|
|
Wprowadzenie do informatyki
Informatyka, I rok, egzamin pisemny
5.02.97, czas: 90 min
|
- Należy skonstruować maszynę Turinga, która mając ciąg wejściowy zaczynający się symbolem L, po którym występuje ciąg symboli x a po nim zera i jedynki, usuwa z niego symbole x i ustawia głowicę na końcu, za ostatnim znakiem ciągu wynikowego. Na przykład, jeżeli na początku mamy ciąg postaci
L x x 0 1 0 B B ...
(głowica znajduje się nad symbolem L), to po wykonaniu obliczeń otrzymamy ciąg
L 0 1 0 B B ....
i głowica będzie znajdować się nad lewym symbolem B.
Oto proponowane rozwiązanie:
Co należy wpisać w miejsca oznaczone literami a i b,
aby to rozwiązanie było kompletne i poprawne ?
- Należy napisać schemat translacji, który czyta ciąg zawierający
najpierw n zer, a po nim dwukropek i ciąg n jedynek (n>=0) i przepisuje
na wyjście tylko zera. Na przykład, jeśli na wejściu pojawi się ciąg 000:111,
to na wyjściu powinniśmy otrzymać 000. Ciąg 00:111 jest niepoprawny
(jedynek jest więcej niż zer). Również niepoprawny jest ciąg 0101:0101
(najpierw mają być same zera a potem dwukropek i same jedynki). Oto rozwiązanie:
%%
S: *** {writeln('0');}
| ':'
;
Co należy wpisać w miejsce trzech gwiazdek, aby to rozwiązanie było poprawne ?
- Niech x będzie niepustą listą, np. (A B C D). Wówczas wartością
car[x] jest pierwszy symbol listy x, czyli w naszym przypadku będzie to symbol A.
Należy napisać funkcję last[x], której wartością jest ostatni symbol niepustej
listy x (w naszym przy- kładzie powinien to być symbol D).
Przypomnijmy, ze lista (A B C D) zapisana w notacji kropkowej będzie miała postać
(A.(B.(C.(D.NIL)))).
Oto definicja funkcji last[x]:
label[last; lambda[[x]; [atom[cdr[x]] -> car[x];
T -> ***
] ] ]
Co należy wpisać w miejsce trzech gwiazdek, aby to rozwiązanie było poprawne ?
- Dany jest następujący program w Prologu:
+D(Z,*X,*X).
+D(S(*X),*Y,S(*Z)) -D(*X,*Y,*Z).
-D(S(Z),*Y,S(S(S(Z)))) - SORT(*Y) !
Jaki będzie wynik działania tego programu ?
- Funkcja F(x) jest zdefiniowana następująco:
F(x)= (m a) [x < 2a+1 ]
Poniższy schemat ma opisywać czytanie nieujemnej liczby x
i drukowanie wartości F(x):
Co należy wpisać w miejsce trzech gwiazdek, aby ten schemat był poprawny ?
|