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
1
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. Sprawdz
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
2