Andrzej M. BorzyszkowskiAndrzej M. Borzyszkowski
Obliczalność i złożoność, wykład

Ćwiczenia 1 (4.X 2025)

Przykłady automatów skończonych. Niedeterministycznych. Z cichymi przejściami. Automaty dla wyrażeń regularnych:
  1. a*ba*
  2. słowa parzystej długości
  3. kończące się sekwencją aba
  4. słowa z n-tą od końca literą a (niedeterministyczny na ok. n stanów, deterministyczny wymaga 10^n stanów)
  5. automat rozpoznający liczby binarne podzielne przez 6

Ćwiczenia 2 (18.X 2025)

Poniższe języki są nieregularne (lemat o pompowaniu), czy są bezkontekstowe? (jeśli tak to pokaż gramatykę):
  1. {a^k⋅b^l | k>l>0}
  2. {w| |w|_a=|w|_b} liczba wystąpień a i b w słowie
  3. {w| |w|_a=2⋅|w|_b} liczba wystąpień a i b w słowie
  4. {w| w=w^R} (palindromy)
  5. {a^p| p jest liczbą pierwszą} (nie jest bezkontekstowy, pompowanie dla bezkontekstowych tak samo tego dowodzi jak i dla regularnych)
  6. dobrze ustawione nawiasy
Dokonaj determinizacji automatu niedeterministycznego (tzn δ nie jest funkcją i być może ma kilka wartości)
  1. δ(q_0,a)=q_0, δ(q_0,a)=q_1, końcowy q_1
  2. δ(q0,a)=q0, δ(q0,b)=q0, δ(q0,b)=q1, δ(q1,b)=q2, δ(q2,b)=q2, δ(q2,a)=q2, końcowy q_2
  3. δ(p,0)=q, δ(p,0)=s, δ(p,1)=q, δ(q,0)=r, δ(q,1)=q, δ(q,1)=r, δ(r,0)=s, δ(r,1)=p, δ(s,1)=p, końcowe q i s

Ćwiczenia 3 (25.X 2025)

Podaj automat ze stosem akceptujący język
  1. {a^nb^2n| n>=0}
  2. {w| |w|_a=|w|_b} liczba wystąpień a i b w słowie w
  3. {w| w=w^R} (palindromy)
Udowodnij, że następujące języki nie są bezkontekstowe używając lematu o pompowaniu dla tych języków
  1. {a^nb^nc^n| n>0}
  2. {w| |w|_a=|w|_b=|w|_c} liczba wystąpień a,b i c w słowie w
  3. {wcw| w słowo nad {a,b}}

Ćwiczenia 4 (15.XI 2025)

Zaprojektuj deterministyczną maszynę Turinga z jedną taśmą akceptującą język
  1. język nad {a,b,c} taki, że pierwsza litera w słowie dalej nie występuje
  2. język nad {a,b,c} taki, że pierwsza litera i ostatnia litera w słowie są równe
  3. {w| |w|_a=|w|_b} liczba wystąpień a i b w słowie w
  4. {a^nb^nc^n| n>0}
Zaprojektuj deterministyczną Turinga być może z wieloma taśmami akceptującą język
  1. {a^nb^nc^n| n>0}
  2. {w| |w|_a=|w|_b=|w|_c} liczba wystąpień a,b i c w słowie w
  3. {wcw| w słowo nad {a,b}}

Ćwiczenia 5 (22.XI 2025)

Zaprojektuj deterministyczną i niedeterministyczną maszynę Turinga rozpoznająca język
  1. {ucv| u podsłowo v, oba nad {a,b}}
  2. {ucv| u rozproszone podsłowo v, oba nad {a,b}}
  3. {o^n| n jest liczbą złożoną}
Jakie są różnice złożoności czasowej działania tych maszyn?
Maszyna Turinga obliczająca funkcję zatrzymuje się z wypisaną wartością na taśmie wyjściowej. Skonstruuj maszynę Turinga obliczającą następującą funkcję:
  1. na wejściu dwie liczby unarne (tzn ciąg zer) rozdzielone znakiem #, na wyjściu sumę tych liczb, nadal w układzie unarnym
  2. wejście j.w, wyjście większa z tych liczb
  3. wejście j.w, wyjście mniejsza z tych liczb
  4. na wejściu liczba w układzie binarnym, na wyjściu liczba o 1 większa
  5. suma liczb zapisanych binarnie

Ćwiczenia 6 (6.XII 2025)

Udowodnij, że problem jest klasy P, tzn. skonstruuj deterministyczną maszynę Turinga działającą w czasie wielomianowym
  1. 2SAT: wejście: formuła zdaniowa w postaci koniunkcyjnej, klauzule długości 2, problem: spełnialność
  2. osiągalność w grafie: wejście: graf nieskierowany podany poprzez listę sąsiedztw oraz dwa wierzchołki, problem: czy jest ścieżka miedzy nimi
  3. spójność grafu: wejście: graf nieskierowany j.w. problem: czy każde dwa wierzchołki są połączone
  4. dwudzielność grafu: wejście: graf nieskierowany, problem: czy jest dwudzielny, tzn. 2-kolorowalny
  5. cykl Eulera: wejście: graf nieskierowany, problem: czy ma cykl Eulera
Dany język {ucw| u podsłowo w, oba nad {a,b}}. Zbadaj złożoność maszyny niedeterministycznej i deterministycznej akceptującej ten język
  • maszyna niedeterministyczna: przepisuje u i w na dwie taśmy, ustawia się gdzieś w słowie w, porównuje u oraz część słowa w
  • maszyna deterministyczna: przepisuje u i w na dwie taśmy, następnie po kolei próbuje porównać u oraz podsłowo w zaczynając od kolejnej litery

Ćwiczenia 7 (13.XII 2025)

Problem SAT jest NP-zupełny. Pokaż NP-zupełność problemów
  1. 3SAT: wejście: formuła zdaniowa w postaci koniunkcyjnej, klauzule długości 3, problem: spełnialność
  2. pokrycie wierzchołkowe: wejście: graf nieskierowany i liczba k, problem: czy graf posiada pokrycie wierzchołkowe wielkości k (redukcja z 3SAT)
  3. liczba chromatyczna: wejście graf nieskierowany i liczba k, problem: czy graf da się pokolorować k kolorami (redukcja z 3SAT)

Ćwiczenia 8 (10.I 2026)

Podaj maszynę Turinga z pamięcią logarytmiczną lub mniejszą akceptującą język
  1. {a^nb^n| n>0}
  2. {a^nb^nc^n| n>0}
  3. {0^k| k złożone}
  4. {w| |w|_a=|w|_b=|w|_c} liczba wystąpień a,b i c w słowie w
  5. {ucv| u podsłowo v, oba nad {a,b}}
  6. {w| w=w^R} (palindromy)
  7. {wcw| w słowo nad {a,b}}
Do góry