Prawda jest, że
- NPC zawiera się w co-NPTIME
- PTIME zawiera się w LOGSPACE (czy coś w tym stylu w każdym razie niepoprawne)
- EXPTIME zawiera się w EXPSPACE
- (algorytm) szachów uogólnionych należy do klasy PTIME
Funkcja przejścia (w innej grupie wyjścia) zmienia się przy przejściu z
- NAD -> DAS
- DAS -> NAS
- Moore -> Mealy
- NAS z E -> NAS
Wyjasnij dlaczego możliwe jest, że ograniczona ilośc punktów funkcji f(n) jest poniżej wykresu funkcji g(n)
jeśli
ograniczenie f(n)=OMEGA(g(n)).
Opisac ograniczenia O OMEGA TETA dla problemów NP.
Opisac problem k-klika
Rozpisac instrukcję if deklarowaną w dowolnym języku programowania za pomocą diagramu syntaktycznego
(podpowiadam
że to to samo co Wykres składniowy)...
(innych nie jestem pewien)
Z testowych było jeszcze pamiętam mniej więcej pytanie o prawidłowość złożoności/ograniczoności m.in.
n=O(log n)
...
n^k=OMEGA(2^n)
n!=O(n^k)
Czy gramatyka: A-> Aa, B-> Ba, A->a, B->b (lub coś wtym stylu) jest
~ lewostronnie liniowa
- gramatyką regularną
- gramatyką bezkontekstową
- ...
1.Lemat o pompowaniu opisac
2. Wieloznaczność gramatyki regularnej (albo bezkontekstowej cos takiego )
3.Zapisac if za pomoca wykresu skaładniowego (diagram syntaktyczny)
4.Po co i do czego jest n0 i c w obliczaniu wielomianow
1. Prawda jest ze:
n=O(logn) (chyba zle)
n^k = O(2^n) (k stala) - czyli ograniczeniem wielomianu jest f. wykladnicza - wydaje sie ze jest ok
k^n = OMEGA(n^k) (k stala) - czyli wykladnicza ma ograniczenie z dolu f. wielomianowa - tez chyba ok
zadne z powyzszych (falsz)
2. Prawda jest ze:
np-zupelne to podklasa jezykow np (chyba rawda choc ja tego nie zaznaczylem)
problemem np-zupelnym jest rpoblem komiwojarzera (prawda)
kazdy problem np-zupelny mozna zredukowac do stopu (falsz)
zadne z powyzszych (falsz)
3. Tutaj co sie w czym zawiera:
PTIME w co-NPTIME (chyba nie)
dalej nie pamietam...
4. W jakim przypadku mowimy ze zmienia sie funkcja przejscia:
DAS -> NAS
NAS -> DAS
Moore'a -> Meally (zaznaczylem tylko tu)
NAS-e -> NAS
5. Dana jest gramatyka
B->aBb A->aC ..... (dokaldnie nie pamietam jaka ale napewno to nie byl chomsky i nie byl to greibach)
pytanie jaka to jest gramatyka:
kontekstowa (falsz)
Bezkontekstowa (prawda bo nieterminale po lewej a ciagi terminali i nieterminali po prawej)
regularna (chyba nie bo gramatyki regularne moga ale nie musza byc bezkontekstowe)
(cos tam) liniowo prawostronnie - nie wiem (nie zaznaczalem)
wiecej testowyxch nie pamietam
OPISOWKA
---------------
1. Wyjasnij znaczenie swiadkow n0 i c w ograniczeniu gornym
2. Lemat o pompowaniu wyrazen regularnych
3. Niejednoznacznosc w gramatyce bezkontekstowej
4. Diagram syntaktyczny polecenia if
================================================================================
==========================================
jak cos nie bedziesz wiedzial to pytaj...
ja z opisowek mialam jeszcze
- zastosowanie chomskiego (odp. algorytm CYK)
- k-kliki (w wykladach jest ale rysunek jest błędny!!!)
- Problem SAT (czyli ze jest to pewne logiczne rownanie boolowskie ktore zawsze jest rowne jeden - czyli
zawsze jest
prawdziwe)
- wykazac ze jakies tam rownanie jest O(n.^5)
czyli np.masz równanie z wykładu (wykład "Elementy teorii złozoności i obliczeń" slajd 5)
f(n)=5n.^3+2n.^2+22n+6 jest O(n.^3)
robimy: rozbijamy kazda zmienna
5n.^3<= 5n.^3
2n.^2 <=2n.^3
22n<=22n^3
6<=6n.^3
prawa strona wszystko do n.^3 bo masz to udowodnic.. a wartosci z rownania przepisuje sie tak jak sa.. potem
sumujemy prawa
strone czyli bedzie 35n.^3 zamieniamy wartosc 35 jako symbol O i tym samym uzyskalismy => O(n.^3)