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