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)
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)
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)
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)
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)
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ą.
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)
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)
Literówka w “Dowód części 1.:”"
|w| > 2|Q| -> w > 2|Q|^3.
39WojPaw.pdf (91,4 KB)
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ą?
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!
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.
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.
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)
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?
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)
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!
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 .
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}.
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)
Ł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)
Ł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)
Bardzo ładne rozwiązanie. Nie mam uwag.
40LPioGdo.pdf (169,3 KB)
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)
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:
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)
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)
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!
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)
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)