JFiZO Lista trzecia wirtualna

ZADANIE 35

Michał Wierzbicki

Gruby błąd w treści zadania! Ale bez konsekwencji, bo autor rozwiązuje zadanie ze Zbioru
a nie ze swojego dokumentu. Co do samego rozwiązania, prosty argument w części c. nie jest
ładnie opisany. Napisane jest “Zauważmy że jeśli P to Q”, po czym idzie (chyba)
argument za tym
że P jest prawdziwe, korzystający z własności zbioru sync. Tymczasem, do tego żeby
P implikowało Q żadne sync nie jest potrzebne. Do małej poprawki!

35MicWie.pdf (90,3 KB)

ZADANIE 37

Michał Maksim

Nie było tak że czytając przymknąłem na chwilę oczy i zdawało mi się że słyszę jak Aniołowie śpiewają.
Ale OK, nie ma się do czego przyczepić.

37MicMaks.pdf (75,4 KB)

Zadanie 36

Agnieszka Pawicka

Rozwiązanie jest poprawne i dość jasne jak na taki stopień formalizmu.

Drobne uwagi: aby utworzyć krotkę, warto zdefiniować makro:
\newcommand{\tuple}[1]{\langle #1 \rangle}
gdzie \tuple{A,B,C} wygląda następująco: \newcommand{\tuple}[1]{\langle #1 \rangle} \tuple{A,B,C}.
36AgnPaw.pdf (119,8 KB)

Oskar Wieczorek

Podoba mi się to rozwiązanie, ale można by lepiej napisać lemat 3. Można napisać, że \delta_w[Q] = Q' to niezmiennik pętli.
36OskWiec.pdf (80,9 KB)

Zadanie 38

Jacek Leja, Szymon Mikler, Adrianna Struzik

Wszystkie rozwiązania są podobne. Są zwięzłe jasne (a Adrianny Struzik najjaśniejsze). Bardzo dobrze.
38AdrStr.pdf (50,9 KB) 38JacLej.pdf (50,2 KB) 38SzyMik.pdf (514,3 KB)

Zadanie 39

Wszystkie rozwiązania są podobne. Są jasne i poprawne. Warto się zastanowić, czy nie można było rozwiązać podpunktów (a) i (b) jedną ogólniejszą konstrukcją.

Beata Janiak

Dobrze by było, jakby tekst był podzielony na akapity.
Zamiast krotek 0-1 w (b) można było rozważać zbiory stanów, dzięki czemu definicja byłaby bardziej intuicyjna.
39BeaJani.pdf (81,1 KB)

Mikołaj Kowalik

Najbardziej mi się podoba to rozwiązanie, bo zdefiniowanie PDFA (co nie jest wprost powiedziane) nasuwa pewne intuicje.

“pewną ilość takich samych stanów” -> "… liczbę … " lub lepiej “powtórzenie takich samych stanów”
39MikKowa.pdf (111,1 KB)

Wojciech Pawlik

Literówka w “Dowód części 1.:”"
|w| > 2|Q| -> w > 2|Q|^3.
39WojPaw.pdf (91,4 KB)

ZADANIE 75

Coś mi się zdaje że musi gdzieś w Internecie krążyć jakiś plik ze zbyt skomplikowanym rozwiązaniem tego zadania. Czy to raczej ja jestem w błędzie i to co mi się wydaje prostszym rozwiązaniem jest jedynie fatamorganą?

GdzieJestNemo

Nic z tego nie rozumiem. Nic! ( Mówię o części B., część A. rozumiem, i jest OK). Co to jest
i, na Miłość Nieistniejącego ? Jaki zbiór ono przebiega ? Czy konstruujemy nieskończenie wiele automatów ?
( A tak ładnie się to da napisać!) aaaaaaH!

Marcin Witkowski

Do połowy drugiej strony czyta się bez żadnego bólu. Potem podstępnie m jest funkcją. Nie powinno tak być,
m to nie jest chrześcijańskie imię dla funkcji. Natomiast oznaczenie P\strzałka P jest na granicy poprawności.
Wołabym id_{P(Q)}. Ostatnia linijka przed słowem “Intuicja”. Mnie zabiła. Rozwiązanie jest za skomplikowane.
Proszę je uprościć, te funkcje nie są potrzebne.

Wiktor Garbarek

Do kropek na str. 2 jest OK. Kropki natomiast są super jak kefir z rana! O, teraz czytam dalej i widzę że jest “id”
tam gdzie u p. Witkowskiego nie było. Potem są TE SAME NIEPOTRZEBNE funkcje co u p. Witkowskiego tylko jaśniej opisane
(i funkcja się nazywa g, tak jak powinna). Za skomplikowane! Proszę je uprościć, te funkcje nie są potrzebne.

Wojciech Jarząbek

Punkt a) chyba nie został napisany całkiem na trzeźwo (albo przeczytany, ale nie, przeczytany został na trzeźwo). Czemu
“słowo w nie może być rozpoznane przez DFA” ? To by było wielkie odkrycie, gdyby znaleziono słowo którego nie zaakceptuje żaden
DFA. Wszystkie gazety by o tym napisały. Punkt b) jest podobnie jak u pp. Witkowskiego i Grabarka. Napisany podobnie jak u
p. Grabarka, ale odrobinę inaczej, nawet lambda się pojawiła. W każdym razie też za skomplikowane i domaga się uproszczenia.

75GdzieJestNemo.pdf (98,3 KB) 75MarWit.pdf (207,5 KB) 75WikGar.pdf (125,4 KB) 75WojJar.pdf (72,2 KB)

ZADANIE 76

Barbara Zięba

Sekcja “Rozwiązanie” bardzo mi się podoba. Bardzo! Prowadzi się gdzieś czytelnika Antycypuje się jego błędne rozumowanie.
I wyprowadza się go z błędu. Widać ze autorka kocha swoich czytelników, nie tak jak Niektórzy. No nic, czytajmy dalej …
… dalej nie widzę po co pokazywać minimalność automatu dla L;
… a dalej, na początku strony 2 (wciąż w tej kropne ze strony 1) wydaje mi się że coś się niestety kupy nie trzyma.
Język L wydaje mi się, że się myli autorce z językiem L_{1/2}. Czy to ze mną jest coś nie tak?

Katarzyna Miernikiewicz

Nieźle się to czyta, miłość do czytelnika w tym jest. Formalne z nieformalnym zmieszane w należytych proporcjach.
Sól i pieprz do smaku. Tylko czy to musi być takie okropnie zawiłe? Nie dałoby się pokazać tych n^2/4 parami nierównoważnych słów?
( dałoby się, Basia dała radę, poległa dopiero potem, moment nieuwagi przy uzasadnieniu). (Aaa-- i pokazuje się tu, tak samo jak u Basi
niepotrzebnie, że L się nie da rozstrzygać mniejszym automatem)

Michał Kucharczyk

Lemat 1 niepotrzebny (podobnie jak u Basi i u Kasi).

Moje wątpliwości budzi notacja z dużym omega. Przecież n jest w tym momencie (gdy formułowany jest Lemat 2) ustalone. Więc nie może być mowy
o żadnej asymptotyce. Nie ma przecież czegoś takiego jak Omega(107).
(Dalej trochę słabo się czyta bo nie widać gdzie się kończy lemat a gdzie zaczyna się dowód; czy autora to nie razi?)
No więc, jak już ustaliłem gdzie jest dowód lematu, to ta omega mnie w dowodzie dalej uwiera. Chociaż w sumie skoro była w sformułowaniu lematu,
to trudno żeby jej nie bylo w dowodzie. Ona nie ma sensu, ale i tak próbowałem to czytać. Wymiękłem na wzorcu 2*#1(w). Do poprawki!

Maciej Walkowiak

Nie ma w tym rozwiązaniu nic niepotrzebnego. Ani grama tłuszczu. Dzięki czemu tekst jest krótki i oszczędza czytelnikowi frustracji jaka się pojawia jak otwiera kolejne rozwiązanie tego zadania i ono ma 3 strony. Krótkie, ale caly komentarz jaki jest potrzebny jest, porządnie prowadzi się
czytelnika przez rachunki, jest jasne o czym one są. No i nie ma niepotrzebnego lematu z dowodem .

Maciej Korpalski

Niby wszystko jest dobrze (tak mi się zdaje) ale nie czułem się tak poprowadzony jak w pracy p. Walkowiaka.

76KaMi.pdf (186,5 KB)

76BarZie.pdf (126,6 KB)

76MacKorp.pdf (67,6 KB)

76MacWal.pdf (119,8 KB)

76MiKuch.pdf (65,5 KB)

W drugiej kropce nie pomyliłam języków, ale widocznie zabrakło trochę wyjaśnienia.

Jeśli słowo w ma dokładnie k jedynek to należy oczywiście do języka L, ale też do języka L_{1/2} – dlatego że słowo w0^{|w|}, dwa razy dłuższe, należy do L.
Natomiast jeśli w ma więcej niż k jedynek, to dla każdego v \in \Sigma^* słowo wv ma więcej niż k jedynek, czyli nie należy do L. Zatem w nie należy do L_{1/2}.

Zadanie 40M

Artur Błaszkiewicz

Podoba mi się Pana rozwiązanie. Wydaje mi się, że dowód by się przyjemniej czytało, jakby listę “Dowód będzie mniał następującą formę” napisał Pan jako listę (\begin{itemize} \end{itemize} lub enumerate), gdzie spostrzeżenia są poprzeplatane dowodami. Lematy są na tyle krótkie, że formułowanie ich zabiera miejsce. Dobrze by było, jakby taki dowód znalazł się na tej samej stronie co rysunek. Zaznaczyłem literówki do poprawienia. (Do drobnej poprawki.)
40MArtBla.pdf (178,4 KB)

Łukasz Klasiński

Ładne i jasne rozwiązanie z dziwną końcówką (od NWW(c_1, c_2,c_3) pod koniec pierwszej strony). Można łatwo pokazać, że dla każdej liczby naturalnej m>0 mamy NWW(m,m+1,m+2) \in \{m \cdot (m+1) \cdot m+2, \frac{m \cdot (m+1) \cdot m+2}{2}\} (w zależności od tego czy m jest parzysta czy nie). (Sugeruję drobną poprawkę, żeby umieścić czyste rozwiązanie na forum).
40MŁukKlas.pdf (159,8 KB)

Zadanie 40L

Mateusz Basiak

Ładne i jasne rozwiązanie. Moja jedyna uwaga to rachunki pod koniec rozwiązania. Wydaje mi się, że można je nieco
uprościć, jeśli chcemy pokazać że wielomian jest ostatecznie majoryzowany przez funkcję wykładniczą.
40LMatBasi.pdf (221,2 KB)

Piotr Gdowski

Bardzo ładne rozwiązanie. Nie mam uwag.
40LPioGdo.pdf (169,3 KB)

Michał Górniak

Rozwiązanie jest jasne i ciekawe. Autor nie korzysta ze wskazówek dla L, więc warto je przeglądnąć. Bardzo ładny rysunek.

Wydaje mi się, że akapit “Pokażmy zatem (2).” jest zbyt długi i powinien być podzielony na więcej akapitów.
Np. akapit 2 od “Najpierw przeanalizujmy literę 2.”, akapit 3 od " Rozpatrzmy teraz literę 0."
akapit 3 od “Ta liczba musi mieć taką własność”
40LMicGor.pdf (216,4 KB)

Grzegorz Klocek

Rozwiązanie jest ładnie i jasno pisane. Udało się autorowi uniknąć niepotrzebnych rachunków. Wydaje mi się, że końcówka
dowodu (też jasna) zyskałaby na wyodrębnieniu dwóch kluczowych kroków:

  1. Pokażemy, że najkrótsze słowo w \in csync(S) jest postaci 2 0^k 1, oraz
  2. k musi mieć odpowiednią wartość.
    40LGrzKloc.pdf (104,6 KB)

Zadanie 40XL

Jakub Mendyk

Bardzo ładne i jasne rozwiązanie.
Znalazłem drobne literówki (zaznaczone w PDFie) i jedno przejście, które można lepiej wyjaśnić.

40XLJakMend2.pdf (2,8 MB)

J-23

Bardzo ładne i jasne rozwiązanie. Nie mam uwag. (Rachunki można było uprościć, przyjmując np. k = n^{1/3}).
40XLJ-23.pdf (170,2 KB)

Poprawione 40M
40MŁukKlas.pdf (169,1 KB)

Poprawione 40M
40MArtBla.pdf (101,0 KB)

ZADANIE 77

Aleksander Czeszejko-Sochacki

Sformułowanie Twierdzenia 2 pozostawia pole do interpretacji (jest w nim coś z precyzji Konstytucji RP). Ponieważ nie wiem jak je czytać powstrzymam się od stwierdzenia że jest fałszywe, ale swoje podejrzenia mam. W konsekwencji nie wiadomo jak się ma Twierdzenie 3 do Twierdzenia 2. Nie wiadmo też
czy poprawne jest użycie Twierdzenia 2 (nie “twierdzenia 2”) w dowodzie Tw. 4. Do poprawki!

Sławomir Górawski

Dwukrotnie wypowiada się zaklęcie “co daje sprzeczność”. A ja nie widzę żadnej sprzeczności. Patrzę i nie widzę. Do poprawki!

77AleCze.pdf (117,8 KB)

77SlaGor.pdf (53,6 KB)

OK. To pierwszą kropkę rozumiem. Z drugą mam dalej kłopot. “To oznacza że automat” – który automat? I dalej też nie jest lekko.

Poprawiłam nieco, ze szczególnym uwzględnieniem drugiej kropki.

76BarZie2.pdf (125,1 KB)

1lajk

Poprawione 77
77SlaGor.pdf (57,7 KB)

Zaznaczyłem to już w poprawce; L, L_{1/2} oraz B są jawnymi funkcjami zmiennej n, więc nie widzę problemu w używniu notacji \Omega. Mógłbym zdefiniować te 3 obiekty przed ustaleniem n, ale nie wiem czy by to pozytywnie wpłynęło na rozwiązanie.
jfizo__zad76 (2).pdf (65,0 KB)