JFiZO Lista druga wirtualna

ZADANIE 15 moje komentarze

Michał Maksim i Piotr Gdowski

Jeśli czegoś nie przeoczyłem (wiadomo, nie da się skupić jak człowiek ciągle klika żeby zobaczyć jak słupki rosną),
to to oba rozwiązania, choć na pierwszy rzut oka poprawne i porządnie napisane, zawierają istotny błąd logiczny.
Zasadniczo istotny.

Wiktor Garbarek

A tu nie ma tego błędu!

15MiMa.pdf (55,5 KB)
15PioGdo.pdf (128,3 KB) 15WikGar.pdf (102,0 KB)

ZADANIE 50

Marcin Witkowski

Jest OK. Warto może zobaczyć jak można do tego samego celu zaprząc automat ze stosem. Wydaje mi się dość pouczające, że to zadanie ma
dwa równie naturalne rozwiązania.

Michał Kucharczyk

Skład w okolicach napisu: “który rozpoznaje L_3 . Obserwacja:” u ToMasza Wierzbickiego wywołałby Atak Serca.
Obserwacja jest do przeczytania.
Ponadto, “czytelnik” pisałbym w tym kontekście dużą literą, bo to przeciez chodzi o mnie. A “Takowy”
podpowiada niezależnie od swojego istnienia lub nieistnienia. Decyzja, że: “W tym rozwiązaniu, jak ognia, wystrzegałem się
symbolicznego zapisania funkcji przejścia” wydaje mi się poprawna. Ale opisu automatu w języku naturalnym nie dałem rady przeczytać,
(podobnie jak “dowodu” później). Proponuję nad tym popracować.

Autor Nieznany

Piękny rysunek na pierwszej stronie, ale zupełnie niepotrzebny. Naprawdę, Świat może jutro przestać istnieć. Nie warto tracić
czasu na konstrukcję automatu ze stosem akceptującego słowa o nieparzystej długości. W dodatku na początku drugiej strony okazuje się że
właściwie ie wiadomo jak ten automat działa. A już wcześniej nie wiadomo po co mu stos. Nie ma jakichś prostszych automatów
rozstrzygających parzystość długości wejścia ?

Potem przychodzą “obserwacje” (czarne kropki na drugiej stronie) i nie wiadomo czym w nich są x_1, x_2, y_1 i y_2. I pojawia się jakiś
skoplikowany rysunek i ciężko jest coś zrozumieć (ja oczywiście udaję że nie rozumiem, bo akurat wiem jak się robi to zadanie).
W każdym razie słabo to jest napisane. Okazuje się że rysunki i rozwlekłość nie implikują wcale jasności.

50MikKow.pdf (149,9 KB) 50MichKuch.pdf (59,4 KB) 50MarWit.pdf (178,7 KB)

ZADANIE 72

Grzegorz Klocek i Wojciech Jarząbek

Oba rozwiązania są OK. Rozwiązanie p. Jarząbka podoba mi się nawet bardziej, bo ładnie wyjaśnia, w języku naturalnym,
o co chodzi z tymi konfluentnymi językami. Na sukces, jaki odnieśli autorzy rozwiązań, należy w tym przypadku patrzeć
przez pryzmat pewnej łatwości zadania.

72WojJar.pdf (51,9 KB)72GrzKlo.pdf (83,4 KB)

Zadanie 16

Barbara Zięba

Podoba mi się to rozwiązanie. Jest jasne i zwięzłe.
16BarZie.pdf (92,4 KB)

Michał Wierzbicki

*Trudno mi się czyta to rozwiązanie. Myślę, że należałby je poprawić. *
Przykładowy problem “Skutkuje to sprzecznością z naszym założeniem, …”. Którym założeniem? Może warto napisać je wprost.
16MichWierz.pdf (69,7 KB)
Nowa wersja: 16MichWierz2.pdf (77,3 KB)

Sławomir Górawski

Rozwiązanie jest poprawne, ale są w nim niejasności. Do drobnej poprawki.

“W takim razie φ musi zaczynać się od symbolu a (w przeciwnym wypadku równość na pewno nie byłaby prawdziwa).” To nie jest użyte w dowodzie, bo można założyć, że x \geq 0 i niczego w dalszym rozumowaniu to nie zmieni.

"Niech x – najmniejsza możliwa ilość symboli a na początku słowa z L_{\phi}". najmniejsza możliwa???
Proponuję:
“Niech x to największa liczba taka, że każde słowo w z L_{\phi} zaczyna się od a^x.”

Nigdzie w rozwiązaniu nie zostało użyte, że L_{\phi} jest niepusty.
16SlaGor.pdf (43,7 KB)*

Nowa wersja: 16SlaGor2.pdf (44,2 KB)

Zadanie 55

Adrianna Struzik

Zwięzłe i poprawne rozwiązanie.

“Zgodny z lematem o pompowaniu” warto napisać to wprost.
55AdrStr.pdf (81,6 KB)

Beata Janiak

Podobają mi się rysunki. Gdyby były jeszcze narysowane słowa po (od)pompowaniu, rozwiązanie byłoby jeszcze jaśniejsze.
W pierwszym rozważanym przypadku brakuje mi odwołania do nowego słowa, które można było nazwać np. w, tak, żeby
było jasne, do środka którego słowa się odwołujemy.
55BeaJan2.pdf (114,1 KB)

GdzieJestNemo?

Rozwiązanie jest poprawne a rozrysowanie słów ułatwia czytanie. Mimo tego jest rozpatrywanych dość dużo przypadków (przypadek 1 tak naprawdę składa się z 4 podprzypadków). Warto się zastanowić, w jaki sposób można ograniczyć liczbę przypadków. Można to zrobić na wiele sposobów. Przykładowo, jeśli L jest bezkontekstowy, to L przekrojone z językiem regularnym 1^* 0^* 1^* 0^* też. Dla tego drugiego języka, łatwiej jest pompować a przypadki zaznaczone niebieską kropką są niemożliwe. Proszę spróbować to poprawić, jeśli się uda.
55GdzieJestNemo2.pdf (87,0 KB)
Nowa wersja:
55GdzieJestNemo2.pdf (75,4 KB)

Maciej Korpalski

To jest raczej szkic rozwiązania, który nie jest dla mnie przekonujący. W przypadku 2. (oraz 4.) autor argumentuje, że “liczba jedynek w pierwszej połowie słowa się zmniejszyła”. Po takiej operacji podział słowa się zmienił, więc nie jest dla mnie jasne czy się faktycznie zmniejszyła. Rozwiązanie jest do poprawki.
55MacKor2.pdf (71,7 KB)

Poprawiona wersja:
55MacKor3.pdf (53,6 KB)

Oskar Wieczorek

Podoba mi się to rozwiązanie. Jest jasne i wystarczająco ścisłe, żeby być przekonujące. Zaznaczyłem drobne uwagi.

  1. W przypadkach 1,2 “Ponieważ |yz|<n” należy zamienić na “Ponieważ |ytz|<n”.
  2. Warto napisać, że pozostały przypadek “zy jest postaci 0^* i zawiera zera z obu połówek” jest niemożliwe.

55OskWie2.pdf (87,1 KB)

ZADANIE 73

Łukasz Wróblewski

Myślę, że to chyba jest dobrze. Ale przeczytać nie dałem rady. Te formuły pod koniec z dwiema deltami po kolei to nie są na moje
zmęczone facebookiem oczy. Jest jasne że autor rozumie co pisze. Ale jeszcze jaśniejsze jest, że jego rozwiązanie jest spektakularnym przykładem na to
jak niedobrą decyzją potrafi być redagowanie rozwiązania jako rozumowania nie wprost.

Maciej Walkowiak

Nie podjął w/w niedobrej decyzji.

Jacek Leja

Też nie podjął niedobrej decyzji. Ale lekko nie jest. Sekcję 2.2. jakoś rozumiem. Ale 2.3 już nie rozumiem, z tym powtarzaniem się czegoś, o co tu chodzi?
Więcej miłości do czytelnika proszę. Aaa – “O liczbie stanów równej ilości klas abstrakcji relacji ~_L^inf” – to akurat nieprawda.

Marcin Rogala

Autor również nie podjął niedobrej decyzji. Najprzyjemniej mi się to rozwiązanie czytało.

73ŁuWr.pdf (64,6 KB) 73MarRog.pdf (54,9 KB) 73MacWal.pdf (111,0 KB) 73JacLej.pdf (73,0 KB)

1 polubienie

ZADANIE 74

Agnieszka Pawicka

Fajna, elegancka struktura rozumowania. Być może nawet za dużo szczegółów (co może wynikać z moich narzekań przy poprzedniej liście).
Naprawdę byłoby super, gdyby cały ten tekst nie wyglądał jak wyjęty psu z gardła. Przecież musi Pani chyba mieć świadomość że
książki tak nie wyglądają, prawda ? (poprzednio też tak było). Na początej proponuję spellcheckera. A potem ogarnąć tych 100 różnych paskudnie wyglądających drobiazgów.

Ale, przy całym tym moim narzekaniu, muszę przyznać że jest kolosalny postęp w porównaniu z tym co przeżywałem przy poprzedniej liście.

Aleksander Czeszejko-Sochacki

O rany jakie tam głupstwo jest napisane! Nie będę dalej czytał póki autor sobie nie przemyśli.

Jakub Mendyk

Podoba mi się zabieg że “Dowód dla wnikliwych czytelników znajduje się na końcu dokumentu”. Chociaż mógłby być w jednej linijce ten dowód, gdyby
pamiętać że CFL mają nie tylko charakteryzację przez gramatyki ale również automatową. Poza tym rozwiązanie bardzo mi się podoba. Tylko strasznie jest podobne do
rozwiązania pani Agnieszki. W związku z tym przypominam że spory o to czy św. Mateusz przepisywał od św. Łukasza, czy na odwrót, czy też może obaj korzystali
z tego samego, zaginionego, Dokumentu Q, trwają szczęśliwie od stuleci.

Szymon Mikler

Fajnie, przyjemnie się czytało. O co nie jest łatwo, kiedy się czyta siedemnastą pracę.
Prosty argument, prosto opowiedziany.

Wojciech Pawlik

Jest OK. Jeszcze lepiej by było gdyby było o jedną trzecią krótsze.

UFFFFFFFFFFFF!

74SzyMik.pdf (105,1 KB) 74JakMen.pdf (198,6 KB) 74AleCze.pdf (114,7 KB)
74WojPaw.pdf (135,8 KB)
74AgnPaw.pdf (131,9 KB)

Zadanie 29

Michał Górniak

Świetnie! Bardzo przyjemnie czyta się to rozwiązanie. Wiadomo skąd i dokąd idziemy i jest dobrze dobrany poziom abstrakcji.
29MicGor.pdf (117,3 KB)

Katarzyna Miernikiewicz

Bardzo mi się podobało to rozwiązanie. Wszystkie kroki są jasno wytłumaczone.
29KaMi.pdf (190,8 KB)

Kwiatek

Autor skoncentrował się na łatwych przekształceniach, a zaniedbał trudniejszą i najważniejszą część rozwiązania.
Tak nie można; to co jest trudne trzeba tłumaczyć a w przypadku jaśniejszych części można napisać “to widać”. Nigdy na odwrót. Rozwiązanie wymaga poprawy.

29Kwiatek2.pdf (199,8 KB)

Poprawiona wersja:
29Kwiatek3.pdf (137,7 KB)

Artur Błaszkiewicz

Rozwiązanie do przepisania od ZERA. Nie jestem w stanie niczego zrozumieć.

  1. Intuicyjne wyjaśnienie niewiele wnosi.
  2. Stan q_{i,a,b} nie jest zdefiniowany i nie wiem co miałby oznaczać.
  3. Definicja X_{i,j} jest niejasna. (Można zgadnąć o co autorowi chodzi, w przypadku q_{i,a,b} nie za bardzo.)

29ArtBla2.pdf (168,3 KB)

1 polubienie

Zadanie 56

Mateusz Basiak

Rozwiązanie jest poprawne i jasne. Dobrze się czyta i podoba mi się pomysł z separatorami aa (mogły to być np. ##, żeby było lepiej widać). Myślę, że pokazywanie, że ta gramatyka generuje język \{a^n b^m c^m aa d^3n \mid n,m >0\} nie było konieczne.

Dlaczego nie ma wcięć na początkach akapitów? Latexa trzeba zmusić do tego a wygląda to gorzej.
56MatBas.pdf (149,9 KB)

J-23

Rozwiązanie jest poprawne i tłumaczenie jest jasne. Zastanawiam się, czy jest to najbardziej efektywny sposób rozwiązania tego zadania. Być może, można ograniczyć liczbę rozpatrywanych przypadków.
56J-23.pdf (111,3 KB)

Łukasz Klasiński

Rozwiązanie nie jest całkowicie złe, ale ma luki i wymaga poprawek.

  1. Warto pokazać jakieś ogólne własności, tak aby rozpatrywanie każdego z przypadków było łatwiejsze. Przy pięciu przypadkach można zaoszczędzić sobie trochę pracy.
    2.Brakuje mi argumentu, że to są wszystkie przypadki (oraz epilogu “a zatem język L/2 nie jest bezkontekstowy.”)
  2. Są błędy w rozpatrywanych przypadkach. Np. w przypadku 2, wbrew temu co jest napisane, słowo a^n b^{n+k} c^n należy do L/2, bo słowo a^n b^{n+k} c^n \; c^k d^{3n} należy do L.
    56ŁukKla.pdf (172,0 KB)

Mea maxima culpa, przesyłam poprawione.Jfizo74.pdf (120,5 KB)

Przesyłam poprawkę do rozwiązania: uszczegółowiłem sekcję 2.3 oraz usunąłem jedno niepotrzebne zdanie z sekcji 2.1.
73JacLej.pdf (72,1 KB)

Przesyłam poprawkę zadania 56
56ŁukKla.pdf (180,8 KB)

Ufff, mam nadzieję, że w końcu się udało jakoś sensownie zapisać rozwiązanie29ArtBla.pdf (132,7 KB)