|
|
Wprowadzenie do informatyki
Informatyka, I rok,
Egzamin poprawkowy, czas: 90 min
|
- Wiadomość zapisaną w języku polskim za pomocą alfabetu łacińskiego
(czyli bez ą, ę itd.) zakodowano w stosunkowo prosty sposób. Oto szyfrogram:
OGKYGKP
Spróbuj go odczytać.
- Uzupełnić poniższe klauzule prologowe tak, aby
M (*A, *B, *C) ≡ A· B = C
czyli predykat M ma określać relację dotyczącą mnożenia liczb naturalnych.
D (Z, *X, *X).
D (S (*X),*Y, S (*Z)) - D (*X, *Y, *Z).
M (Z, *X, Z).
- Liczba automorficzna to taka liczba naturalna, która znajduje się na końcu
swojego kwadratu. Np. 5, 6, 25 są liczbami automorficznymi, bowiem
52 = 25, 62 = 36, 252 = 625. Ale 7, 8 czy 11 nie są liczbami automorficznymi.
Należy opracować schemat blokowy sprawdzania, czy liczba
naturalna x > 0 jest automorficzna. Jeśli x jest liczbą automorficzną,
to powinien się pojawić napis 'Tak', a w przeciwnym razie 'Nie'.
Uzupełnić podany schemat blokowy.
- Załóżmy, że na taśmie maszyny Turinga znajduje się symbol A,
a po nim n cyfr 0, 1 reprezentujących liczbę x z przedziału otwartego
(-2n-1 , +2n-1 ). Załóżmy, że n > 1. Należy uzupełnić podaną maszynę
Turinga tak, aby na podstawie reprezentacji liczby x w uzupełnieniu do
2 generowała reprezentację liczby (-1)·x również w uzupełnieniu do 2.
W uzupełnieniu do 2 n-bitowa liczba ujemna -x jest przedstawiana
jako liczba naturalna 2n-x. Oto wszystkie liczby całkowite jakie można
reprezentować w uzupełnieniu do 2 za pomocą trzech bitów i ich reprezentacje:
Po zakończeniu obliczeń głowica ma się znajdować na początku taśmy nad symbolem A.
Oto przykład działania maszyny Turinga, o której mowa:
Uwaga: (-1)·x = 1 + neg(x), gdzie neg(x) oznacza ciąg binarny,
w którym każdy bit reprezentacji liczby x zastąpiono jego negacją.
- Dany jest ciąg wierszy zawierających litery X zakończony wierszem
zawierającym kropkę. Należy uzupełnić podaną specyfikację dla Yacca w taki sposób,
aby wygenerowany program sprawdzał czy figura przedstawiona za pomocą liter X
tworzy prostokąt. Na przykład dla pliku wejściowego postaci:
XXXX
XXXX
XXXX
.
powinniśmy otrzymać komunikat 'ok', natomiast dla danych wejściowych:
XXXX
XXXXX
XXXXX
.
na wyjściu powinien pojawić się komunikat 'wrong'.
%{
var p,sz: integer; (* p=poprzedni wiersz;
sz=szerokość *)
ok: boolean=true;
%}
%%
S: F '.' { if ok then writeln('ok')
else writeln('wrong') }
|