1

Formalizmy definiujące klasę funkcji częściowo rekurencyjnych to:

a) Maszyna Touringa z jedną taśmą
b) Automaty komórkowe
c) Rachunek „Lambda”
d) Maszyna Touringa wielotaśmowa

Prawdą jest że:

a) maszyna RAM zawiera ograniczoną liczbę rejestrów
b) maszyna RAM może zawierać więcej niż dwie taśmy
c) w maszynie RAM występują instrukcje do przesuwania głowicy
d) żadne z powyższych

Koszt logarytmiczny w maszynie RAM

a) można stosować tylko dla złożoności pamięciowej
b) jest bardziej realistyczny od kosztu zunifikowanego
c) jest różny dla różnych trybów adresowania (operandum)
d) żadne z powyższych

Algorytm CYK ( Cocke-Younger-Kasami)

a) służy do sprawdzania, czy dany wyraz został wygenerowany z danej gramatyki kontekstowej
b) ma złożoność wykładniczą
c) ma złożoność wielomianową TSE
d) żadne z powyższych

Zgodnie z definicją dowolny problem NP.:

a) jest rozwiązywany w czasie wielomianowym na maszynie niedeterministycznej (weryfikowalny w

czasie wielomianowym na maszynie deterministycznej) TSE

b) jest rozwiązywany w czasie wykładniczym na maszynie deterministycznej
c) jest weryfikowany w czasie wielomianowym na maszynie niedeterministycznej
d) jest weryfikowany w czasie wykładniczym na maszynie niedeterministycznej

Problem jest rozstrzygalny:

a) jeżeli istnieje algorytm klasy P, który jest w stanie go rozwiązać
b) jeżeli istnieje algorytm, który dla przynajmniej jednych danych udzieli poprawnej odpowiedzi
c) jeżeli istnieje algorytm, który dla dowolnych danych udzieli poprawnej odpowiedzi /TSE
d) żadna z powyższych

Prawdą jest, że:

a) f(n)=O(g(n)), jeżeli istnieją takie liczby naturalne c i n0, że dla każdego n>=n0 zachodzi f(n)<=c.g(n),
b) O() jest asymptotycznym ograniczeniem górnym
c) F(n)=O(g(n)) jeżeli istnieją takie liczby naturalne c i n0, że dla każdego n>=n0 zachodzi coś tam coś tam
d) O() jest asymtotycznym ograniczeniem dolnym

Automaty których wyjścia zależą tylko od stanu aktualnego, to:

a) automaty skończone
b) automat ze stosem
c) automaty Moore’a
d) Automat Meale-go

Prawdą jest, że zbiór :

a) języków rekurencyjnych zawiera się w zbiorze języków regularnych
b) deterministycznych języków bezkontekstowych zwiera się w zbiorze niedeterministycznym (TSE- może to

tez)

c) zbiór gramatyk ogólnego przeznaczenia zawiera się w zbiorze gramatyk kontekstowych
d) języków bezkontekstowych zawiera się w zbiorze języków kontekstowych /TSE

Konwersja, w której zmienia się funkcja wyjścia, to:

a) automat Moore’a -> automat Mealye’go
b) automat Mealy’ego - > automat Moore’a
c) NAS -> DAS
d) DAS -> NAS

Pytania w mniejszym lub większym stopniu zapamiętane: jak maszyna RAM kończy działanie

1. Przy czym się zmienia zbiór akceptujacy:

a) przy przeksztalceniach nas z e-przejsciami na nas
b) przy przeksztalceniach nas - das
c) przy przeksztalceniach moor - mealego

2

d) przy przeksztalceniach das - nas

Ktore poprawne:

- Maszyna turninga mozne byc sumylowana za pomoca maszyny ram
- maszyna ram moze byc symulowana a pomoca maszyny rutninga
- maszyna ram moze byc symulowana a pomoca przejsc z pamięcią
- maszyna Tourninga może być symulowana za pomocą ... nie pamiętam ale chyba była niepoprawna

Pytanie dotyczące stanów akceptujących??? kiedy się zmieniają jak się przechodzi z :
i tu chyba było

DAS - >NAS NAS -> DAS NAS-E -> NAS Moore -> Mealy

Kiedy maszyna RAM akceptuje ciag wejsciowy:

jak przeczyta cala tasme
jak napotka instrukcje HALT
jak akumulator jest pusty i maszyna znajduje sie w stanie akceptujacym
i cos czwartego nie wiem moze nic z powyzszego albo co

Czy prawdą jest że:
f(n)=O(g(n)), jeżeli istnieją takie liczby naturalne c i n0, że dla każdego n>=n0 zachodzi f(n)<=cg(n)
reszta była chyba fałszywa, chyba było coś o O(asymptotyczne ograniczenie górne), Ω(asymptotyczne ograniczenie
dolne), 0(asymptotyczne ograniczenie górne i dolme)

Pyt: Ktore z automatow umozliwiaja istnienie przejscia w rozne miejsca
za pomoca tych samych symboli. (jakos tak to bylo sformulowane lub podobie).

W odpowiedziach bylo: aut. Moore'a, niedetrministyczne (to chyba dobra odp.), niedeterministyczne z E-przejsciami
(to tez chyba dobra) i chyba byla jeszcze jakas odpowiedz z deterministycznymi.

f(n) co to jest O(g(n))
- asymptotyczne ograniczenie gorne
- Ogarniczenie gorne takie ze f(n) < cn cos takiego
- Ograniczneie dolne itp

Obliczyc jakis wielomian przy O(g)n)) = n^5
Symulacja maszyny RAM na Turingu i odwrotnie, itd. (czy mozna)
Rownowaznosc zbioru stanow ( nas->das, das->nas, meally->moor, moor->meally).

1. Problemami NP-zupełnymi są:
a) wszystkie problemy NP,
b) problem kliki,
c) problemy logicznych układów scalonych,
d) arytmetyka Presburgera.

2. Które przejście powoduje zmianę stanu końcowego (tzn. stan końcowy jest inny)
a) DAS->NAS,
b) NAS z e-przejściami ->NAS,
c) NAS->DAS,
d) Moore->Mealy

3. Sprawdź słuszność założenia:
a) f(n)=? (g(n)), gdy g(n)=O(f(n)),
b) f(n)= ?(g(n)), gdy g(n)=O(f(n)),
c) f(n)= O(g(n)), gdy g(n)=?(f(n)),
d) żadna z powyższych

4. Jeżeli mamy automat, w którym możliwe jest nieograniczone przejście tym samym symbolem do
następnego stanu, to mówimy o automacie:
a) deterministycznym,
b) niedeterministycznym,
c) automacie Moore'a i Mealy'ego,
d) niedeterministycznym skończonym

5. Języki bezkontekstowe:
a) są nadzbiorem języków kontekstowych,
b) są podzbiorem języków rekurencyjnie przeliczalnych,
c) są nadzbiorem języków deterministycznych bezkontekstowych
d) są podzbiorem języków regularnych