http://ii.drx.pl/ 2026-05-23T20:27:16+02:00 http://ii.drx.pl/ http://ii.drx.pl/lib/images/favicon.ico text/html 2011-09-05T19:01:38+02:00 http://ii.drx.pl/jfizo:egzaminy?rev=1315242098&do=diff stareegzaminy text/html 2010-03-06T20:38:43+02:00 http://ii.drx.pl/jfizo:lista2?rev=1267904323&do=diff for $i in {{topic>jfizolista2&list&nodate&nouser}} do {{page>$i&fullpage}} text/html 2011-05-03T13:16:20+02:00 http://ii.drx.pl/jfizo:stareegzaminy?rev=1304421380&do=diff text/html 2010-03-04T14:40:28+02:00 http://ii.drx.pl/jfizo:zadanie09.001?rev=1267710028&do=diff Z dedykacją dla driksa, chociaż jest pałkossaczem. Załóżmy sobie nie wprost, że istnieje automat , o , rozpoznający . Weźmy ,, takie, że . (Jak się robi deltę z daszkiem? Na bazy się spieszę, nie mam czasu googlać.) Takie i istnieją, bo każde słowo zwraca jakiś stan, a stanów jest mniej niż słów -znakowych. text/html 2010-03-07T18:11:56+02:00 http://ii.drx.pl/jfizo:zadanie09.002?rev=1267981916&do=diff Niech będzie stałą z lematu o pompowaniu dla języka . Wtedy słowo możemy podzielić na , jedynie tak, że będzie ciągiem liter . Czyli również będzie ciągiem (niepustym, z założenia w lemacie) liter (niechaj ), więc powinno należeć do L, a nie należy, gdyż dla żadnego naturalnego dodatniego nie jest . Sprzeczność. text/html 2010-03-07T23:22:18+02:00 http://ii.drx.pl/jfizo:zadanie09.003?rev=1268000538&do=diff * Rozwiązanie w Hopcroft, Przykład 3.2, strony 72-73 Treść Zbiór tych słów nad , które są liczbą pierwszą w zapisie binarnym nie jest regularny. Lemat 1 FIXME Ten lemat nie dowodzi równoważności regularności tych języków. Bez tego lematu dowód na dole nic nie daje. --- Alistra 2010/03/07 21:55 text/html 2010-03-06T20:37:55+02:00 http://ii.drx.pl/jfizo:zadanie09.004?rev=1267904275&do=diff Niech będzie dowolnym podzbiorem . Udowodnij, że jest językiem regularnym. Rozwiązanie. Rozpatrzmy dowolny język . Rozważmy trzy przypadki: * jest pusty. Wtedy jest regularny. * jest niepusty i zawiera wyłącznie słowo puste. Wtedy również składa się wyłącznie ze słowa pustego – jest więc regularny. * jest niepusty i istnieje najkrótsze niepuste słowo . Niech i niech oraz . Pokażemy, że dla każdego język jest regularny, co znaczy, że jest regularny (jako suma skończenie wiel… text/html 2011-03-07T21:31:51+02:00 http://ii.drx.pl/jfizo:zadanie09.007?rev=1299529911&do=diff 13 stanów. Konstrukcja trywialna. Szkic dowodu: rozważmy język sufiksów najwyżej 4-znakowych wyrazów naszego języka (czyli ). Podobnie jak w zadaniu 001, pokażmy że automat nie może mieć mniej niż 13 stanów. [listy zadan] text/html 2011-02-27T00:46:17+02:00 http://ii.drx.pl/jfizo:zadanie09.009?rev=1298763977&do=diff Hopcroft strona 81-82 text/html 2010-03-12T18:46:22+02:00 http://ii.drx.pl/jfizo:zadanie09.010?rev=1268415982&do=diff [Automat do zadania] Sprawdzając wszystkie możliwe przejścia ze stanu początkowego na akceptujący mamy: * , * , * , * , * Jednak i analogicznie . Zatem całe wyrażenie to . [listy zadan] text/html 2010-03-14T13:30:09+02:00 http://ii.drx.pl/jfizo:zadanie09.011?rev=1268569809&do=diff [Automat do zadania] * Regexp1 (błędny): * Regexp2: Duży nawias to wszystkie możliwe przejścia ze stanu początkowego ponownie na stan początkowy. Następnie są wszystkie możliwe zakończenia na stanach akceptujących. [listy zadan] text/html 2010-03-14T22:23:24+02:00 http://ii.drx.pl/jfizo:zadanie09.012?rev=1268601804&do=diff . Niech - zbiór wszystkich słów nad alfabetem nie zawierającym słowa : Nasze słowo to . [listy zadan] text/html 2010-03-15T04:29:14+02:00 http://ii.drx.pl/jfizo:zadanie09.013?rev=1268623754&do=diff Rozwiązanie drxa Automat: Automat można „zwinąć” w ten sposób: Na pierwszym grafie usunąłem ścieżki prowadzące do „martwych” stanów. Na drugim „zwinąłem” rogi -- usunąłem je (te wierzchołki) jednocześnie wstawiając do grafu krawędzie, które zachowują równoważność z grafem z rogami. Na trzecim grafie zrobiłem osobny stan początkowy i osobny stan końcowy. Na czwartym usunąłem kolejny wierzchołek. Po czym stwierdziłem, że tyle kroków wystarczy by zobaczyć sens algorytmu, a efekt końco… text/html 2011-03-13T20:55:54+02:00 http://ii.drx.pl/jfizo:zadanie09.014?rev=1300046154&do=diff 1. Czy istnieje takie wyrażenie regularne , że ? Nie. Załóżmy nie wprost, że istnieje. Rozważmy . Wtedy niewątpliwie . A więc zaczyna się od i kończy na . Mamy: dla pewnego i dodatkowo (usuwamy końcowe z wyrazu będącego w ) oraz (usuwamy początkowe z wyrazu w ). text/html 2010-03-13T21:27:26+02:00 http://ii.drx.pl/jfizo:zadanie09.015?rev=1268512046&do=diff a): * - deterministyczny i niedeterministyczny on-line (np. napisy i ) * - deterministyczny, ale nie deterministyczny on-line (np. napisy i ) * - ani nie deterministyczny (np. napis ), ani nie deterministyczny on-line (np. napisy i ) b): text/html 2010-03-16T13:34:48+02:00 http://ii.drx.pl/jfizo:zadanie09.016?rev=1268742888&do=diff Język generowany przez nie posiada deterministycznego on-line wyrażenia regularnego go opisującego. Pozostaje to udowodnić. TODO text/html 2010-03-13T20:06:32+02:00 http://ii.drx.pl/jfizo:zadanie09.017?rev=1268507192&do=diff * [listy zadan] text/html 2010-03-07T22:00:27+02:00 http://ii.drx.pl/jfizo:zadanie09.018?rev=1267995627&do=diff Począwszy od najbardziej znaczącego bitu Stany 0...4 odpowiadają wartości wczytanej liczby modulo 5, a e oznacza ciąg pusty. [Automat do zadania 18a] Począwszy od najmniej znaczącego bitu * * * Funkcja przejścia opisana poniżej * * Stan początkowy: text/html 2010-03-07T22:07:52+02:00 http://ii.drx.pl/jfizo:zadanie09.019?rev=1267996072&do=diff Twierdzenie 4.11 z Hopcrofta Jeśli jest regularny, to też jest regularny. (indukcja względem struktury wyrażenia regularnego) Skoro jest regularny, to istnieje wyrażenie regularne takie, że . Pokażemy, że istnieje wyrażenie regularne takie, że . text/html 2010-03-07T13:15:59+02:00 http://ii.drx.pl/jfizo:zadanie09.020?rev=1267964159&do=diff Niech będzie językiem regularnym, a automatem, który go rozpoznaje. . Pokażemy, że jest językiem regularnym. Niech . Zdefiniujmy automat : * , * , * , więc , * , gdzie . Przykład stanu akceptującego. Załóżmy, że i . Po wczytaniu pewnego słowa, ze stanu początkowego znaleźliśmy się w przykładowym stanie . Sprawdźmy teraz ciąg . Z definicji wiemy, że . Patrzymy na pozycję 1 i tam jest 0, więc . Teraz patrzymy na pozycję 0 i tam jest , które jest stanem akceptującym. Czyli dla , c… text/html 2010-03-13T10:45:50+02:00 http://ii.drx.pl/jfizo:zadanie09.021?rev=1268473550&do=diff * * niech * niech * więc * * niech * niech * niech * niech * niech * niech * niech * niech , * niech * * Automaty to DFA * niech * niech * wtedy [listy zadan] text/html 2010-03-13T20:36:52+02:00 http://ii.drx.pl/jfizo:zadanie09.022?rev=1268509012&do=diff Mamy automat rozpoznający słowa z L, nazwijmy go . Idea jest taka, że budujemy nowy automat, którego zbiorem stanów, jest krotka stanów starego automatu (przedstawiona jako funkcja ) - symbolizuje, gdzie doszełby ten nasz automat wczytając k liter, jeśli zaczynałby w każdym ze stanów oraz podzbiór stanów (podsłowo ) - symbolizuje stany osiągalne po k krokach (dowolną literą)(podsłowo ). text/html 2010-03-14T19:25:21+02:00 http://ii.drx.pl/jfizo:zadanie09.023?rev=1268591121&do=diff * REQUIRE: zadanie 21 Lemat 1: jest pusty, wtw , - ilość stanów automatu . Dowód : trivial Dowód : . Jeśli - najkrótsze słowo, to z lematu o pompowaniu - nie jest najkrótszym słowem, sprzeczność * , - NFA z treści zadania. * , * Używając wiedzy z zadania 21 konstruujemy automat rozpoznający - automat ten rozpoznaje słowa które należą do tylko jednego z języków. * Karmimy ten automat wszystkimi słowami długości , - ilość jego stanów. Jeśli któreś słowo zostanie zaakceptowane t… text/html 2010-03-08T02:04:31+02:00 http://ii.drx.pl/jfizo:zadanie09.024?rev=1268010271&do=diff Udowodnij, że istnieje L, który można rozpoznać NDFA o mniej niż 20 stanach, a (dopełnienia) nie da sie rozpoznać NDFA z mniej niż 200 stanami. NDFA rozpoznający L NDFA rozpoznający dopełnienie L Załóżmy, że NDFA rozpoznający ten język ma mniej niż 210 stanów. To znaczy, że podczas czytania słowa jakiś stan wystąpił więcej niż raz. Można usunąć te przejścia wraz z powtórzonym stanem i akceptacja automatu się nie zmieni. To znaczy, że automat zakceptuje też słowo , , co jest sprze… text/html 2010-03-22T02:23:40+02:00 http://ii.drx.pl/jfizo:zadanie09.025?rev=1269221020&do=diff . . Lemma 1: - nie wprost, . - najkrótsze słowo, którego nie akceptujemy. Ale wtedy pewien stan występuje dwukrotnie, więc nie akceptujemy również pewnego słowa , , sprzeczność. Lemma 2: , - prime - Załóżmy, że . Weźmy słowo . Należy ono do języka . To znaczy, że na drodze do stanu akceptującego w automacie powtórzył nam się jakiś stan, czyli droga stanów wygląda tak . Przyjmijmy, że długoś tego cyklu to . Chcemy tyle razy powtórzyć ten cykl, aby uzyskać false positive. - liczba powt… text/html 2011-03-15T22:36:51+02:00 http://ii.drx.pl/jfizo:zadanie09.027?rev=1300225011&do=diff dwa razy więcej zer niż jedynek, i parzysta ilość jedynek * * * wszystkie permutacje z poprzeplatanymi * - trivial * - * W każdym istnieje podciąg, który jest permutacją . * Dowód: niech , , . Wiemy, że . Wykazać, że dla każdego istnieje t. że . TODO text/html 2010-03-21T15:39:05+02:00 http://ii.drx.pl/jfizo:zadanie09.028?rev=1269182345&do=diff * * * S S0S1S | S1S0S | S0S1S1S | S1S0S1S | S1S1S0S | * TODO Tutaj chyba można olać leading --- Alistra 2010/03/21 15:37 : Zawsze dokładamy nic, zero i jeden, dwa zera i jeden. Co zapewnia nam warunek: : listy zadan text/html 2011-03-27T21:05:17+02:00 http://ii.drx.pl/jfizo:zadanie09.029?rev=1301252717&do=diff Zgadliście! Nie jest bezkontekstowy! Dowód. Najpierw przekrawamy ten język z regularnym , innymi słowy rozpatrujemy takie słowa, które nie mają nietrywialnych bloków zer. Teraz, niech będzie SzLoP (stałą z lematu o pompowaniu) i bierzemy słowo . To oczywiście należy do naszego okrojonego języka. Zgodnie z LoP, możemy sobie pompować. Zauważmy jednak, że jeżeli podzielimy , to , zatem do słowa wpadnie najwyżej jedno zero. Mamy więc dwa przypadki: 1. w nie ma zer, czyli , . Weźmy teraz (… text/html 2011-03-21T20:22:29+02:00 http://ii.drx.pl/jfizo:zadanie09.030?rev=1300735349&do=diff Jakieś pierdolenie, do tego niekompletne Taki pomysł, proszę o weryfikację. Najpierw z produkcji tworzę sobie graf (dwudzielny), w sposób następujący: Niech na początku , czyli wierzchołkami są nieterminale. Niech ->->-> będą wszystkimi produkcjami wychodzącymi z nieterminala N. Wówczas tworzę wierzchołki etykietowane (dokładam k nowych) i rysuję krawędzie ->. Natomiast z rysuję krawędzie prowadzące do wierzchołków etykietowanych nieterminalami występującymi w . Łatwo zauważyć, że j… text/html 2010-03-21T12:33:28+02:00 http://ii.drx.pl/jfizo:zadanie09.031?rev=1269171208&do=diff * * * * * * * * * * * * listy zadan text/html 2011-03-21T21:02:10+02:00 http://ii.drx.pl/jfizo:zadanie09.032?rev=1300737730&do=diff Zadanie 32. Czy język jest bezkontekstowy? Twierdzenie. jest bezkontekstowy. Dowód. Pokażemy gramatykę , a następnie udowodnimy, że . Zbiorem produkcji gramatyki będą następujące relacje: * * -- długość jest nieparzysta, więc nie da się podzielić słów na połowy. * . Niech i . Widac zatem, ze . Jesli podzielimy na polowy o takiej dlugosci, to w kazdej polowie na -tej pozycji znajda sie dwa rozne symbole. text/html 2010-03-21T15:01:50+02:00 http://ii.drx.pl/jfizo:zadanie09.033?rev=1269180110&do=diff Zadanie 33. Czy język jest bezkontekstowy? Twierdzenie. Język nie jest bezkontekstowy. Dowód. Rozpatrzmy język . Przecięcie języka bezkontekstowego z regularnym, daje nam język bezkontekstowy (dowodu jednak nie będzie, a mógłby polegać na łączeniu dwóch automatu w jeden). text/html 2010-03-27T02:44:58+02:00 http://ii.drx.pl/jfizo:zadanie09.036?rev=1269654298&do=diff Zadanie. Czy jest bezkontekstowy? Nie jest. Dowód. Załóżmy nie wprost, że jest bezkontekstowy. Niech będzie stałą z lematu o pompowaniu. Rozpatrzmy słowo . Musielibyśmy móc pompować wszystkie trzy części tego słowa, a te części są odległe o więcej niż . Zatem język nie jest bezkontekstowy. text/html 2010-03-29T06:26:59+02:00 http://ii.drx.pl/jfizo:zadanie09.038?rev=1269836819&do=diff Zadanie. Czy jest bezkontekstowy? Nie jest. Dowód. Przekroić z i wziąć słowo . BULLSHIT Kontrprzykład: podział na może być taki, że i zawierają tylko z pierwszego . Wtedy pompując dodatkowe zachowujemy warunek wyrażenia regularnego oraz warunek oryginalnego języka (bo dodatkowe możemy wepchnąć do prefiksu ) text/html 2010-03-21T15:28:22+02:00 http://ii.drx.pl/jfizo:zadanie09.040?rev=1269181702&do=diff Załóżmy, że L - język tych palindromów nad alfabetem {0,1}*, które mają taką samą ilość zer i jedynek jest bezkontekstowy. Rozważmy słowo w = , gdzie N jest stałą z lematu o pompowaniu. Jakikolwiek podział słowa „w” sobie nie wybierzemy to znajdziemy takie k, że nie należy do L, ponieważ albo zaburzy nam się równowaga liczb albo palindromowość. text/html 2011-03-27T21:16:27+02:00 http://ii.drx.pl/jfizo:zadanie09.041?rev=1301253387&do=diff W jedną stronę jest to oczywiste, na mocy wiadomych twierdzeń z wykładu, zatem pozostaje pokazać implikację „bezkontekstowy => regularny”. Niech będzie SzLoP dla języka L. Rozważmy języki: , . Oczywiście, . No i teraz pokazujemy, że każdy z tych języków jest regularny. Dla jest to oczywiste, jako że to język skończony. Natomiast w przypadku zauważamy, że , czyli w są wszystkie słowa przystające do modulo (lub jest on pusty), co pociągałoby oczywiście regularność tego języka. Powyższa … text/html 2010-03-28T11:43:07+02:00 http://ii.drx.pl/jfizo:zadanie09.042?rev=1269769387&do=diff Zadanie. Czy jest bezkontekstowy? Nie jest. Dowód. Załóżmy nie wprost, że jest bezkontekstowy. Niech będzie stałą z lematu o pompowaniu. Rozpatrzmy słowo . Musimy pompować zarówno zera jak i jedynki. Ani ani nie może zawierać zarówno jedynek jak i zer. , . Czy słowo ? Przybyło zer i jedynek. Czy ? . Wiemy, że . Jeśli to , sprzeczność. Jeśli to , sprzeczność. text/html 2010-03-29T05:25:15+02:00 http://ii.drx.pl/jfizo:zadanie09.043?rev=1269833115&do=diff * * * Wniosek 1: * Jeśli , regularne, to czy regularny? * Jeśli , CFL, to czy CFL? Regularny Weźmy DFA i , takie że i . Zbudujmy NDFA, którego . Funkcja przejścia to połączenie obu tych funkcji, tylko przesuwa lewą współrzędną, a prawą. Stan akceptujący to taki, gdy obie współrzędne stanu są akceptujące w oryginalnych automatach. text/html 2010-03-27T18:59:21+02:00 http://ii.drx.pl/jfizo:zadanie09.044?rev=1269712761&do=diff [Mało zadeptany śnieg - drak] (zad 43) text/html 2010-03-27T18:59:39+02:00 http://ii.drx.pl/jfizo:zadanie09.045?rev=1269712779&do=diff [Mało zadeptany śnieg - drak] (zad 44) text/html 2010-03-27T19:00:08+02:00 http://ii.drx.pl/jfizo:zadanie09.046?rev=1269712808&do=diff [Mało zadeptany śnieg - drak] (zad 45) text/html 2010-03-28T16:22:00+02:00 http://ii.drx.pl/jfizo:zadanie09.047?rev=1269786120&do=diff [Mało zadeptany śnieg - drak] (zad 46) int fun(n) { for (i = 0; ; i++) { dom = 0; for (arg = 0; arg < i; arg++) { for (steps = 0; steps < i - arg; steps++) { if (fi_n(arg) == 1 po steps krokach) { dom++; break; } } } if (dom >= 7) … text/html 2010-03-27T19:32:47+02:00 http://ii.drx.pl/jfizo:zadanie09.048?rev=1269714767&do=diff Zbiory rekurencyjnie przeliczalne A, B, C, D. Każda liczba naturalna należy do dokładnie dwóch z nich. Zbiory są rekurencyjnie przeliczalne, więc istnieją , takie, że . Zbudujmy , takie, że : int g_A(n) { int count = 0; for(i = 0; ; i += 100) { if (w i krokach f_A(n) == 1) { return 1; } else { for X (B, C, D) { if (w i krokach f_X(n) == 1) count++; } } if (count == 2) return 0; } } text/html 2010-03-29T08:55:40+02:00 http://ii.drx.pl/jfizo:zadanie09.049?rev=1269845740&do=diff [Mało zadeptany śnieg - drak] (zad 47) func: * niemalejąca: * całkowita: * rekurencyjna: , Przypadek 1: func - od pewnego momentu stała int g(n) { for(i = 0; func(i) <= max; i++) { if (func(i) == n) return 1; if (func(i) == max) return 0; } } text/html 2010-04-07T17:37:58+02:00 http://ii.drx.pl/jfizo:zadanie09.050?rev=1270654678&do=diff Zadanie 48 w [Mało zadeptany śnieg - drak]. text/html 2010-04-07T18:20:35+02:00 http://ii.drx.pl/jfizo:zadanie09.051?rev=1270657235&do=diff Zadanie 49. w [Mało zadeptany śnieg - drak]. text/html 2010-03-27T18:50:28+02:00 http://ii.drx.pl/jfizo:zadanie09.052?rev=1269712228&do=diff Zadanie 50. w [Mało zadeptany śnieg - drak (50)]. text/html 2010-05-24T08:02:10+02:00 http://ii.drx.pl/jfizo:zadanie09.054?rev=1274680930&do=diff [Mało zadeptany śnieg - drak] (zad 53) text/html 2010-05-24T08:02:14+02:00 http://ii.drx.pl/jfizo:zadanie09.055?rev=1274680934&do=diff [Mało zadeptany śnieg - drak] (zad 53) text/html 2010-03-27T18:49:27+02:00 http://ii.drx.pl/jfizo:zadanie09.056?rev=1269712167&do=diff [Mało zadeptany śnieg - drak] (zad 55) text/html 2011-04-03T14:40:35+02:00 http://ii.drx.pl/jfizo:zadanie09.057?rev=1301834435&do=diff Dowód z wykładu: - nietrywialny, ekstensjonalny zbiór Zakładamy, że funkcje puste nie należą do A (wpp. można wszystko pokazać dla ). Dodatkowo jest niepuste więc niech . - funkcja redukcji : " wczytaj n napisz taki kod (i go nie uruchamiaj): " wczytaj t uruchom uruchom i zwróć wynik" text/html 2010-03-27T18:22:59+02:00 http://ii.drx.pl/jfizo:zadanie09.058?rev=1269710579&do=diff [Mało zadeptany śnieg - drak] text/html 2010-03-27T18:23:05+02:00 http://ii.drx.pl/jfizo:zadanie09.059?rev=1269710585&do=diff [Mało zadeptany śnieg - drak] text/html 2011-04-11T19:25:36+02:00 http://ii.drx.pl/jfizo:zadanie09.060?rev=1302542736&do=diff [Mało zadeptany śnieg - drak (59)] text/html 2010-03-27T18:47:48+02:00 http://ii.drx.pl/jfizo:zadanie09.061?rev=1269712068&do=diff [Mało zadeptany śnieg - drak (60)] text/html 2010-05-23T17:55:36+02:00 http://ii.drx.pl/jfizo:zadanie09.063?rev=1274630136&do=diff [Mało zadeptany śnieg - drak (62)] text/html 2011-04-04T02:02:04+02:00 http://ii.drx.pl/jfizo:zadanie09.065?rev=1301875324&do=diff Hopcroft, 7.5, „Wielowymiarowe maszyny Turinga”, strona 190. Żmudne text/html 2010-03-27T18:45:41+02:00 http://ii.drx.pl/jfizo:zadanie09.066?rev=1269711941&do=diff [Mało zadeptany śnieg - drak (64)] text/html 2010-03-27T18:45:01+02:00 http://ii.drx.pl/jfizo:zadanie09.068?rev=1269711901&do=diff [Mało zadeptany śnieg - drak (66)] text/html 2011-04-19T02:50:13+02:00 http://ii.drx.pl/jfizo:zadanie09.069?rev=1303174213&do=diff Nie, nie jest rozstrzygalny. Dowód będzie poprzez pokazanie redukcji tego problemu do znanego nam problemu stopu maszyny Turinga. Innymi słowy, dostając maszynę Turinga T, zbudujemy maszynę skanującą S, która będzie symulować T, czyli wykonywać na taśmie te same operacje, w szczególności będzie zachodzić równoważność: T się zatrzymuje S się zatrzymuje. To będzie bajka o żuczku z Altzheimerem. text/html 2011-04-19T01:49:00+02:00 http://ii.drx.pl/jfizo:zadanie09.070?rev=1303170540&do=diff To zadanie jest prostym wnioskiem z zad 69. Łatwo bowiem zasymulować maszynę skanującą za pomocą maszyny zawracającej, pokrótce opisuję jak to zrobić. Zbiór stanów nowej maszyny będzie zdublowanym zbiorem stanów starej; każdy stan jest w dwóch wersjach „normalnej” i „skampionej”. Wykonujemy dokładnie te same operacje co skanująca i w momencie dojścia do końca, przechodzimy w stan taki, w jaki by przeszła skanująca, tyle że w wersji „skampionej” i wracamy na początek, bez zmieniania niczego po… text/html 2010-03-27T18:44:14+02:00 http://ii.drx.pl/jfizo:zadanie09.071?rev=1269711854&do=diff [Mało zadeptany śnieg - drak (67)] text/html 2010-03-27T18:43:35+02:00 http://ii.drx.pl/jfizo:zadanie09.072?rev=1269711815&do=diff [Mało zadeptany śnieg - drak (68)] text/html 2010-03-27T18:43:01+02:00 http://ii.drx.pl/jfizo:zadanie09.073?rev=1269711781&do=diff [Mało zadeptany śnieg - drak (69)] text/html 2010-03-27T18:39:58+02:00 http://ii.drx.pl/jfizo:zadanie09.076?rev=1269711598&do=diff [Mało zadeptany śnieg - drak] text/html 2010-03-27T18:39:27+02:00 http://ii.drx.pl/jfizo:zadanie09.078?rev=1269711567&do=diff [Mało zadeptany śnieg - drak] text/html 2010-03-27T18:38:55+02:00 http://ii.drx.pl/jfizo:zadanie09.079?rev=1269711535&do=diff [Mało zadeptany śnieg - drak] text/html 2010-03-27T18:38:00+02:00 http://ii.drx.pl/jfizo:zadanie09.081?rev=1269711480&do=diff [Mało zadeptany śnieg - drak] text/html 2010-05-10T10:41:17+02:00 http://ii.drx.pl/jfizo:zadanie09.085?rev=1273480877&do=diff Jeśli , to istnieje NTM . Maszyna niedeterministyczna podczas obliczenia korzysta z niedeterminizmu wtedy, gdy ma więcej niż jedną możliwą akcję, dla jednej konfiguracji. Możemy zmodyfikować maszynę, aby najpierw wyznaczała sobie na taśmie pewien obszar, zapisała na nim tyle liczb, ile ma niedeterministycznych wyborów w obliczeniu. Potem przechodzimy do normalnego obliczenia. W momencie natrafienia na niejednoznaczną konfigurację, czytamy pierwszą z wylosowanych liczb od lewej, niech to będzi… text/html 2010-05-09T17:44:11+02:00 http://ii.drx.pl/jfizo:zadanie09.086?rev=1273419851&do=diff JFiZO - Zadanie 86 Jeśli należy do , to istnieje maszyna Turinga i wielomian takie, że rozpoznaje czy po nie więcej niż krokach. Rozważmy zbiór . Skonstruujmy niedeterministyczną maszynę Turinga , która najpierw wyznacza blok o długości (za obecną zawartością taśmy), niedeterministycznie zapisuje go zerami i jedynkami, a potem zachowuje się jak , gdzie niedeterministycznie zgadnięta liczba to . text/html 2010-05-10T10:19:31+02:00 http://ii.drx.pl/jfizo:zadanie09.087?rev=1273479571&do=diff JFiZO - Zadanie 87 Z tresci zadania: * * - wielomian * , * Miejmy: * - niedeterministyczna machina turinga rozstrzyga przynaleznosc do tego zbioru. determinuje przynaleznosc do zbioru zgadujac ciag stanow przez ktore przechodzi. Stanow w tym ciagu jest conajwyzej (z definicji przynaleznosci do ). Ten ciag stanow mozemy zakodowac jako ciag liczb naturalnych. Ten ciag liczb naturalnych mozemy zakodowac jako liczba naturalna. Niech ta liczba to . Jesli wiec . Znamy wiec sek… text/html 2010-05-09T12:54:45+02:00 http://ii.drx.pl/jfizo:zadanie09.088?rev=1273402485&do=diff Każdą klauzę z zamieniamy osobno. Mamy . Dodajemy dwie nowe zmienne logiczne i . Z tworzymy . Dowód. Załóżmy, że istnieje wartościowanie, które spełnia tę formułę . Każda klauzula musi zostać spełniona, zatem w każdej klauzuli istnieje co najmniej jeden literał, który jest spełniony przez to wartościowanie. W takim wypadku ustawiamy odpowienio wartościowania i . text/html 2010-05-10T10:03:42+02:00 http://ii.drx.pl/jfizo:zadanie09.089?rev=1273478622&do=diff Pokażemy, że . Redukcja Liczba w to liczba zmiennych w formule. Tworzymy graf: * dla każdej zmiennej w tworzymy 3 wierzchołki: , * dokładamy krawędzie: , * dla klauzuli o numerze tworzymy wierzchołek z krawędziami do literałów, jakie ma w sobie, np. ma krawędzie: . text/html 2010-05-09T14:11:52+02:00 http://ii.drx.pl/jfizo:zadanie09.090?rev=1273407112&do=diff * . Po prostu dla każdej nieskierowanej krawędzi z grafu , do grafu dodajemy dwie skierowane krawędzie i . * . Dla każdego wierzchołka z , do dodajemy wierzchołki i . Dla każdej skierowanej krawędzi z dodajemy do nieskierowane krawędzie . * Oprócz tego dla każdego wierzchołka z dodajemy do krawędzie oraz . text/html 2011-05-08T13:17:12+02:00 http://ii.drx.pl/jfizo:zadanie09.091?rev=1304853432&do=diff wazniak text/html 2011-05-08T13:50:29+02:00 http://ii.drx.pl/jfizo:zadanie09.092?rev=1304855429&do=diff wazniak text/html 2010-05-17T09:55:37+02:00 http://ii.drx.pl/jfizo:zadanie09.093?rev=1274082937&do=diff Weźmy . Dla każdej zmiennej w formule , która wystepuje więcej niż 3 razy, zamień jej wystąpienia na dodatkowe zmienne: gdzie k to liczba wystąpień tej zmiennej. Zapewnij, że wszystkie nowe zmienne są tak samo wartościowane: =>=>...=>=> (dodajemy te implikacje parami do naszej formuly). Dla każdego zanegowanego wystąpienia zmiennej, w formule zawierajacej implikacje przed nową zmienną obrazującą to wystąpienie zmiennej , dodajemy negację. text/html 2011-05-23T20:54:14+02:00 http://ii.drx.pl/jfizo:zadanie09.094?rev=1306176854&do=diff <http://cs482.elliottback.com/lecture-25-hamiltonian-cycle-problem/> W pierwszej edycji Cormena była redukcja z 3SAT. W drugiej zmienili na redukcję z VERTEX-COVER, bo łatwiej:/ W trzeciej dowód jest pewnie zupełnie pominięty. text/html 2010-05-16T18:57:08+02:00 http://ii.drx.pl/jfizo:zadanie09.095?rev=1274029028&do=diff gdzie Problem komiwojażera, to pytanie, czy istnieje cykl Hamiltona o wadze mniejszej niż . Potrafimy tym rozwiązać pytanie o jakikolwiek cykl Hamiltona, jeżeli damy dobre ograniczenie górne. Tutaj tym ograniczeniem jest suma wag krawędzi (każdy cykl Hamiltona nigdy nie będzie miał w sumie większej wagi). text/html 2010-05-23T19:13:12+02:00 http://ii.drx.pl/jfizo:zadanie09.096?rev=1274634792&do=diff Pokażemy, że problem znalezienia ścieżki dwa razy gorszej od optymalnej dla problemu komiwojażera jest nie łatwiejszy od problemu cyklu Hamiltona, czyli potrafiąc go rozwiązać, potrafimy rozwiązać problem Hamiltona. Skonstruujemy redukcję wielomianową przekształcającą instancję problemu cyklu Hamiltona (dowolny graf nieskierowany) w instancję problemu komiwojażera. text/html 2010-05-20T16:46:41+02:00 http://ii.drx.pl/jfizo:zadanie09.097?rev=1274366801&do=diff <http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/AproxAlgor/TSP/tsp.htm> <http://wazniak.mimuw.edu.pl/index.php?title=Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa/Wyk%C5%82ad_7:_Algorytmy_aproksymacyjne#Wersja_metryczna> text/html 2010-03-20T17:51:54+02:00 http://ii.drx.pl/jfizo:zadanie09.100?rev=1269103914&do=diff * [Rozwiązania niektórych zadań Arkadiusza Janickiego] listy zadan text/html 2010-03-20T17:52:02+02:00 http://ii.drx.pl/jfizo:zadanie09.102?rev=1269103922&do=diff * [Rozwiązania niektórych zadań Arkadiusza Janickiego] listy zadan text/html 2010-05-23T20:45:23+02:00 http://ii.drx.pl/jfizo:zadanie09.104?rev=1274640323&do=diff <- Bierzemy instancję i konstruujemy instancję Jeśli x = y -> trywialne Jeśli x < y -> w tym drugim potrzebujemy większej procentowo kliki dokładamy w nim wierzchołków połączonych ze wszystkim uzasadnienie: czyli jeśli w nowym znajdziemy klikę rozmiaru to automatycznie mamy klikę w pierwotnym grafie. text/html 2010-03-20T17:52:11+02:00 http://ii.drx.pl/jfizo:zadanie09.105?rev=1269103931&do=diff * [Rozwiązania niektórych zadań Arkadiusza Janickiego] listy zadan text/html 2010-06-05T09:49:38+02:00 http://ii.drx.pl/jfizo:zadanie09.109?rev=1275724178&do=diff Graf ma mieć taką własność, że dla każdego wierzchołka może on sąsiadować z conajwyzej jednym wierzchołkiem o takim samym kolorze. Wówczas można pokazać redukcję do naszego zmodyfikowanego problemu. Wygląda ona następująco: do każdego wierzchołka w grafie oryginalnym dodajemy klikę pięcioelementową, łącząc każdy wierzchołek kliki z (Czyli de facto zastępując pojedyncze wierzchołki sześcioelementowymi klikami). text/html 2010-05-30T14:08:19+02:00 http://ii.drx.pl/jfizo:zadanie09.110?rev=1275221299&do=diff * a) gdzies kiedys juz bylo. zamieniamy na . text/html 2010-05-31T20:54:21+02:00 http://ii.drx.pl/jfizo:zadanie09.113?rev=1275332061&do=diff Dobre rozwiązanie jest obliczalna w wielomianowym czasie, natomiast nie jest. Złe rozwiązanie - obliczalna w wielomianowym czasie. Czy obliczalna w wielomianowym czasie. Ponumerujmy ciagi zerojedynkowe. Niech . Wtedy obliczymy w nastepujacy sposob: text/html 2010-05-23T20:53:56+02:00 http://ii.drx.pl/jfizo:zadanie09.114?rev=1274640836&do=diff Redukcja z do (komiwojażer -> komiwojażer spełniający silny warunek trójkąta) - instancja - suma wag wszystkich krawędzi Każdej krawędzi z zwiększ wagę o text/html 2010-03-20T17:52:23+02:00 http://ii.drx.pl/jfizo:zadanie09.117?rev=1269103943&do=diff * [Rozwiązania niektórych zadań Arkadiusza Janickiego] listy zadan text/html 2010-06-05T10:19:30+02:00 http://ii.drx.pl/jfizo:zadanie09.121?rev=1275725970&do=diff Musimy udowodnic, ze . Regexp mozemy reprezentowac w postaci NFA w liniowej pamieci (Lemma 1.29, example 1.30, example 1.31, Sipser). TODO text/html 2010-06-07T16:44:34+02:00 http://ii.drx.pl/jfizo:zadanie09.123?rev=1275921874&do=diff Zdefiniujmy sobie 3-arnego XOR'a tak: Teraz używamy po prostu algorytmu z zadania 126, z tym, że XOR'a 2-arnego zastępujemy 3-arnym. text/html 2010-06-11T23:07:03+02:00 http://ii.drx.pl/jfizo:zadanie09.125?rev=1276290423&do=diff Definiujemy sobie język L, budując algorytm A, który go rozstrzyga wczytaj x; wczytaj maszynę $M_x$ odpowiadającą x //umawiamy się, że każda maszyna ma nieskończenie wiele poprawnych reprezentacji utwórz wielomian $p(y)=y^{log(x)} + log(x)$ Zapuść maszynę $M_x(x)$. Jeśli maszyna się zatrzyma, zużywając co najwyżej $p(|x|)$ pamięci i zaakceptuje, to słowo $x \not \in L$. W przeciwnym wypadku $x \in L$ text/html 2010-06-04T18:45:57+02:00 http://ii.drx.pl/jfizo:zadanie09.126?rev=1275669957&do=diff O tym, że problem TExtendedQBF jest PSPACE trudny, łatwo się przekonać - każda formuła w QBF jest przecież także formułą ExtendedQBF. Pozostaje jedynie dowieść, że TExtendedQBF jest w PSPACE. Zwykłego QBF rozwiązywało się tak: (wiki) text/html 2010-06-05T11:27:55+02:00 http://ii.drx.pl/jfizo:zadanie09.133?rev=1275730075&do=diff - analogicznie 3 * 3 kwantyfikatory na R16,R8 i R4 oraz 1 na R2 dają w sumie równe 10 kwantyfikatorów text/html 2010-06-05T11:27:47+02:00 http://ii.drx.pl/jfizo:zadanie09.135?rev=1275730067&do=diff Problem opisany w zadaniu jest NP trudny. Dlaczego? Otóż pytanie, czy formuła , w której występują tylko kwantyfikatory , jest prawdziwa, to właściwie pytanie, czy formuła pozbawiona kwantyfikatorów jest spełnialna. Gdy dokładamy kwantyfikatory , sytuacja zmienia się. Jednak, ponieważ mamy tylko dwa takie kwantyfikatory , to możemy rozpatrzyć 4 przypadki - za każdym razem podstawiając pod p i q różne wartości sprawdzić, czy wtedy formuła jest spełnialna. A to możemy, gdy dysponujemy niedetermi… text/html 2011-04-19T21:00:32+02:00 http://ii.drx.pl/jfizo:zadanie11.001?rev=1303239632&do=diff Łatwo zauważyć, że możemy bez problemu rozpoznać język , który działa dokładnie tak samo, z taką różnicą, że wczytujemy słowa od lewej (od najbardziej znaczącego bitu). Widzimy, że i skorzystamy z tego, że NDFA się łatwo odwracają. Pokażę teraz krótko konstrukcję automatu rozpoznającego odwrócony język. Niech , to . Idea konstrukcji jest taka: text/html 2011-03-29T03:13:59+02:00 http://ii.drx.pl/jfizo:zadanie11.006?rev=1301361239&do=diff Pokazać, że jeśli jest regularny, to też jest. Niech będzie DFA takim, że, . Skonstruujemy sobie NFA B rozpoznający . - oznacza to trójki złożone ze stanu A, ze stanu odwróconego A (podzbioru ) i jednej flagi. Odwrócony A to NFA powstały przez odwrócenie strzałek (funkcja przejścia staje się relacją). Flagę będziemy czytać jako „czy przekroczyłeś już granicę ”. text/html 2011-03-29T15:37:52+02:00 http://ii.drx.pl/jfizo:zadanie11.007?rev=1301405872&do=diff FIXME Źle odczytałem definicję, więc to rozwiązanie prawdopodobnie nie działa. Pokazać, że DFA rozpoznający może potrzebować wykładniczo więcej stanów niż DFA rozpoznający . Niech = będzie językiem słów nad mających 0 na dziesiątej pozycji. text/html 2011-03-29T15:40:19+02:00 http://ii.drx.pl/jfizo:zadanie11.008?rev=1301406019&do=diff Czy jeśli jest regularny, to również jest regularny? FIXME Źle odczytałem definicję, więc to rozwiązanie prawdopodobnie nie działa. No nie bardzo. Weźmy sobie . Wtedy . Niech będzie stałą z lematu o pompowaniu. Rozważmy słowo zad. 40 text/html 2011-06-29T04:36:09+02:00 http://ii.drx.pl/jfizo:zadanie11.042?rev=1309314969&do=diff Na razie nie wiemy, czy to zadanie znajdzie się w zbiorze i pod jakim numerem, ale jest szansa, że jako siódme zadanie z egzaminu w tym roku, pojawi się pod numerem 35+7, więc niech sobie tu na razie będzie. To rozwiązanie bardzo mi się podoba, chociaż nie mam pewności, czy jest poprawne, bo jeszcze nie zostały sprawdzone nasze prace. Niemniej jest ciekawe i pokazuje pewien smaczek złożoności obliczeniowej, więc napiszę je dla potomnych. text/html 2010-03-27T18:57:08+02:00 http://ii.drx.pl/jfizo:zbior_zadan?rev=1269712628&do=diff Listy zadań * [Zbiór zadań] (2009) * [Zbiór zadań] (2008) * [Zbiór zadań] (2007) Rozwiązania 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 08…