JFiZO Lista na piewszy tydzień Epidemii

Przedmioty Zdalne zajęcia z JFIZO
#1

ZADANIE 81. Moje komentarze:

Maciej Korpalski

– Nie. To NIE JEST funkcja z A w B !!
– Dowód drugiej implikacji jest zbyt lakoniczny i czytelnik go nie rozumie. PROSZĘ UZUPEŁNIĆ.

Poza tym dość przyjemnie się to czyta. A jeszcze przyjemniej by się czytało gdyby zecer zechciał odróżnić między
nawiasami z języka w którym mówi a nawiasami będącymi przedmiotem obrad (tymi z \Sigma).

Barbara Zięba

Wszystkie te same uwagi co w przypadku pracy p. Macieja Korpalskiego. Oprócz pierwszej.

Jacek Leja

W tym rozwiązaniu porządnie się definiuje co to znaczy że nawiasowanie jest poprawne. Co mogłoby ułatwić pokazanie, o danym nawiasowaniu, że jest poprawne (tu szydzimy z pozostałej dwójki autorów rozwiązań zadania 81 ). Ale nie ułatwia, bo nigzdie się z tej definicji nie korzysta. Dowody implikacji w obie strony odbywają się głównie przez machanie rękami (choć mają poprawną, indukcyjną strukturę).

Z mniejszych rzeczy: razi pewien brak ekonomii języka: jest “wtedy istnieje jeden lub więcej kontrprzykładów w”, powinno być “istnieje kontrprzykład w”. Ponadto, jak gdzieś już dziś pisałem, za wszelką cenę należy unikać dwóch
formuł nieoddzielonych tekstem. Oddzielenie kropką nie ratuje, a nawet pogarsza. Definicja \sigmy w sekcji 1.1 bardzo by zyskała gdyby po kropce a przed symbolem \sigma było słowo “Funkcja”. Konkluzja: Akceptuję, ale ledwo ledwo.

Zadanie_81.pdf (61,6 KB) Zadanie_81 (1).pdf (86,6 KB) 81.pdf (120,4 KB)

#2

ZADANIE 80. Moje komentarze:

Michał Górniak

Rozwiązanie wydaje mi się poprawne, choć niekoniecznie najprostsze.
W najprostszym nie ma potrzeby używania w argumentacji słów dłuższych niż 2.
To może się nie wydawać kluczowe, ale stałoby się istotne gdyby autor miał rozwinąć
treść słowa “oczywiście” w ostatniej linijce.
Akceptuję to rozwiązanie, ale gdyby to było trudniejsze zadanie to tak znacząca nieoptymalność rozumowania
byłaby problemem.

Michał Kucharczyk

Definicje są poprawne. Pierwsza z formuł z ogólnymi kwantyfikatorami jest trudna do przeczytania, ale od biedy się da przez nią przegryźć. Bardzo by ułatwiało gdyby było napisane, że to jest po prostu przepisana definicja, wtedy czytelnik nie musiałby sam do tego dochodzić.

Natomiast paragraf zaczynający się od słowa “Biorąc” jest nieczytelny. Nie wiem co to znaczy
Biorąc … przyjmuje wszystkie wartości (“przechodząc pod balkonem spadła mu na głowę doniczka”?).
Nie wiem co to znaczy w=a_i,a . Wskazówka: dwie formuły ZAWSZE muszą być od siebie oddzielone tekstem.
DO POPRAWKI! Aaaa – i podpis powinien być na górze, wycentrowany, pod wycentrowanym tytułem. To nie jest list. To jest nanoartykuł.

J23

Do słów “co powoduje że f_T zachowuje długość słowa” tekst jest optymalny: przyjemna definicja,
dokładnie oddająca istotę rzeczy, plus jasne wyjaśnienie w języku naturalnym. Ale potem jest dowód indukcyjny
i czytelnik nie ma pojęcia jakiego lematu to jest dowód, to znaczy jaka jest hipoteza indukcyjna. W dodatku jest
w tym dowodzie jakieś n, które przecież jest mocą alfabetu. W tym miejscu przestaję czytać. DO POPRAWKI!

Szymon Mikler

Czytelnik jeży się gdy widzi napis: “Istnieje T. Mealy’ego nie mający równoważnych T. Moore’a”
Czemu niby ma służyć takie głupie oszczędzanie na znakach? [ całe szczęście że obaj patroni transducerów są na “M”, inaczej nazwiska by im autor też skrócił ].
Ale gorzej, że rozwiązanie nie wydaje mi się być poprawne. Ostatni paragraf chyba nie ma sensu. Cu jest u nas szufladką a co kamykiem? DO POPRAWKI! ZDECYDOWANIE!

JFiZO zad 80.pdf (270,3 KB) J-23 - JFiZo 80.pdf (142,0 KB) jfizo__zad80.pdf (39,9 KB) zadanie80.pdf (100,1 KB)

#3

ZADANIE 43. Moje komentarze:

Krzysztof Guzik

Nic z tego nie rozumiem (a Nieistniejący P.B. mi świadkiem że próbowałem).
Gdyby to był artykuł to wymagałby “Major revision”. W piekle jest
osobne miejsce dla ludzi którzy w ciągłym tekście mają definicję zbioru P_i na 3 linijki.
DO POPRAWKI. GRUNTOWNEJ. Być może warto żeby autor przeczytał mój komentarz do pracy p. Agnieszki Pawickiej.

Jfizo_43 (4).pdf (129,2 KB)

#4

ZADANIE 42. Moje komentarze:

Marcin Rogala

Jest w porządku. Decyzje o tym jak prezentować słowa złożone z krotek, żeby to było z miarę czytelne
podjęte lepiej niż u Beatu. Natomiast w wierszy zaczynającym się od “Weźmy krotkę M” , po tej krotce,
a przed napisem “2l+1>2n” KONIECZNIE powinno być słowo “gdzie”. Za wszelką cenę należy unikać dwóch
formuł nieoddzielonych tekstem.

Beata Janiak

Jest z grubsza OK.

Adrianna Struzik

“Niech n będzie stałą z lematu o pompowaniu.” Jak to? Przecież ten lemat zachodzi tylko dla języków regularnych?
I co znaczy ta piękna błyskawica na końcu ? [ I JAK SIĘ JĄ ROBI w LaTeXu ? ]

zad42.pdf (89,9 KB)
Marcin_Rogala_300084_zadanie42.pdf (60,2 KB) zadanie42.pdf (99,9 KB)

#5

ZADANIE 79. Moje komentarze:

Agnieszka Pawicka

Niestety nie potrafię tego zrozumieć. Choć nie wykluczam że to wszystko jest prawda co jest napisane.
W Pani tekście zabrakło miłości do czytelnika. A – jak pisał psalmista (poprawka: jak p. Agnieszka słusznie mailowo zwraca mi uwagę to jest cytat ze Św. Pawła a nie z psalmu)-- “Gdybym mówił językami ludzi i aniołów
a miłości bym nie miał, stałbym się jak miedź brzęcząca albo cymbał brzmiący.”

Prawdopodobnie zupełnie inaczej by się to czytało, gdyby po napisaniu każdej z tych kolczastych formuł
wyobraziła sobie Pani tego człowieka który siedzi z otwartą paszczą i próbuje to zrozumieć i napisała Pani do niego,
jak człowiek do człowieka, o co właściwie chodzi. Porządny tekst matematyczny powinien mieć dwie warstwy: tę formalną
(która być może tu jest, nie umiem tego zweryfikować) i nieformalną, która prowadzi czytelnika przez warstwę formalną.
I w dodatku dodaje ta warstwa nieformalna tekstowi redundancji: jeśli się Pani gdzieś w jakimś indeksie pomyli,
to czytelnik któremu się opowie o intuicjach będzie w stanie sobie poprawić w głowie ten indeks (albo w ogóle nie
zauważy błędu).

Z drobnych rzeczy – warto się nauczyć używać, w trybie matematycznym, symbolu ; . Spacje są bardzo ważne. Bardzo.
(mam tu Q_A głównie na myśli). Konkluzja: DO POPRAWKI.

Jakub Mendyk

Podobało mi się. O jakości tego tekstu świadczy, że nie musiałem go całego czytać. Przez dowód Lematu 1 przemknąłem
tylko oczami, a wyobraźnia podążyła mi w stronę w którą każdemu podąża ( nie, nie jedzenie, nie jakieś inne przyjemne myśli,
podążyła ku Francy). W każdym razie, nie musiałem czytać tego dowodu, bo jak się doczyta do sformułowania Lematu 1 to
już się wie co będzie dalej. Dlaczego ? Bo to rozwiązanie nie jest jak cymbał brzmiący. I nawet jeśli jest jakiś drobny błąd
w tym dowodzie Lematu 1 to on nie ma znaczenia. ( Co nie znaczy że tego dowodu mogłoby tam równie dobrze nie być – bardzo dobrze że jest).

Wojciech Pawlik

Jest OK. Czysto napisana definicja automatu dla języka A. Omija się (jako oczywisty) lemat który jest u p. Jakuba Mendyka,
więc niestety odpada ta część gdzie jest potrzbna indukcja. No ale rzeczywiście ten lemat jest oczywisty, można go uczciwie pominąć.

zadanie_79_jakub_mendyk.pdf (209,8 KB) jfizo2-79.pdf (108,8 KB) 79_Wojciech_Pawlik.pdf (104,1 KB)

1 polubienie
#6

chyba już jest dobrze jfizo__zad80_popr.pdf (53,2 KB)

#7

Sprawdziłem do tej pory zadania 21, 22, 23. Załączam swoje uwagi jako adnotację w pliku PDF. Chętnie usłyszę co o tym sądzicie (tu na forum albo emailem).

Rozwiązania zaakceptowane:
21ŁuKl.pdf (350,3 KB)
22DoWo2.pdf (178,7 KB) (poprzednia wersja: 22DoWo.pdf (276,5 KB))
22GdzieJestNemo2.pdf (356,9 KB) poprzednia wersja 22GdzieJestNemo.pdf (233,1 KB)

22Kwiatek2.pdf (210,8 KB) poprzednia wersja 22Kwiatek.pdf (232,1 KB)
22PiGd.pdf (192,6 KB)
23KaMi.pdf (173,5 KB)
23OsWi.pdf (108,0 KB)
23WoJa.pdf (215,6 KB)

Proszę mi przysłać poprawione rozwiązania do poniedziałku 23.03 do 11:30.

W razie pytań/skarg/wniosków proszę pisać tu na forum (albo do mniej mailem jeśli ktoś woli).

#8

Sprawdziłem pozostałe zadania 25,41 oraz 43. Załączam swoje uwagi jako adnotację w pliku PDF.

Rozwiązania zaakceptowane:
25MiGrz2.pdf (58,8 KB) poprzednia wersja 25MiGrz.pdf (56,0 KB)
25ŁuWr2.pdf (110,2 KB) poprzednia wersja25ŁuWr.pdf (126,2 KB)
25MaWi.pdf (197,4 KB)
41AlCS.pdf (157,0 KB)
41GrKl2.pdf (204,0 KB) poprzednia wersja 41GrKl.pdf (147,3 KB)
43MiKo3.pdf (149,6 KB) poprzednia wersja 43MiKo.pdf (244,4 KB)
43MaWa.pdf (126,9 KB)

Rozwiązania do drobnej poprawki:

43MiMa.pdf (121,9 KB)

Proszę mi przysłać poprawione rozwiązania do poniedziałku 23.03 do 11:30.

#9

Jak każdy widzi, zadanie 78 nie jest jeszcze sprawdzone. Nie zdążyłem dziś tego zrobić.

#10

Aby poprawić moje rozwiązanie, chciałam pomóc sobie tą “porządną definicją”. Niestety dla nawiasowania: ([)] mówi ona, że jest poprawne, z czym ja się jednak nie zgadzam.

Czy to implikuje, że szydzenie z naszych rozwiązań jest bezpodstawne? Czy rzeczywiście istnieje istotnie mniej lakoniczny dowód drugiej implikacji?

8 polubień
#11

ZADANIE 78. Moje komentarze poniżej. [ I przepraszam za opóźnienie; strasznie dużo czasu niestety tracę na klikanie żeby zobaczyć jak szybko rośnie i potem na denerwowanie się że szybko ]

Michał Wierzbicki

Wszystko niby jest (chyba) dobrze (oprócz drobnych szczegółów, na przykład gdzieś się dodaje q_s jako zbiór, tam gdzie powinno być
{q_s}). Ale czyta się to strasznie. Jak miedź brzęczącą. (patrz moje uwagi do pracy p. Agnieszki Pawickiej). Ciekawe (taki eksperyment jakby zrobić?) czy
umiałby Pan wyobrazić sobie napisanie tego rozwiązania nie używające żadnych formuł? (To by TEŻ nie miało sensu,
mówienie niektórych rzeczy słowami byłoby nieekonomiczne. Tekst zrobiłby się tak długi że byłby niezrozumiały. Ale niektóre
fragmenty dałyby się ładnie opowiedzieć. )

Sławomir Górawski

Cóż za miła odmiana po czytaniu pracy p. Wierzbickiego!

Wiktor Garbarek

O jakie skomplikowane! Naprawdę trzeba mieć |Q|x|Q|x|\Sigma| stanów ?!!?

Mateusz Basiak

Dość porządnie jest to napisane, nie ma za dużo rzeczy do których możnaby się przyczepić. Choć czemu na przykład implikacja w 4 linijce drugiej strony
nie jest równoważnością ? (jak czytelnik chwilę pomyśli to widzi że ona jest równoważnością, tylko autor to przed nami ukrywa). A definicję w drugiej czarnej kropce
na pierwszej stronie o wiele lepiej by się czytało gdyby miała taki format jaki zwykle mają definicje funkcji: F(X)= TERM. A nie (tak jak jest w tekście):
F(X)=A <=> Formuła(X,A). [ Proszę sobie zajrzeć do pracy p. Wierzbickiego żeby zobaczyć jak to bardziej elegancko zrobić)].

zad78.pdf (164,7 KB) 78.pdf (109,7 KB) wg78.pdf (104,4 KB) slawomir_gorawski_78.pdf (61,0 KB)

#12

Jeśli takie nawiasowanie jest zgodne z definicją to rzeczywiście ona nie jest porządna. Na szczęście, jak zdaje się wspomniałem, autor rozwiązania z niej potem nie korzystał :slight_smile: .

Co nie czyni rozwiązań p. Basi Zięby ani p. Maćka Korpalskiego ani trochę bardziej kompletnymi.

#13

Czy znane jest jakieś inne rozwiązanie zadania 22?
Jest ono umieszczone w dziale “Niedeterministyczne automaty skończone”, a wszystkie rozwiązania budują DFA. Zastanawiałam się, czy da się skonstruować jakiś prostszy NFA.

2 polubienia
#14

Ja nie znam takiej łatwiejszej konstrukcji. W zależności od tego co oznacza “prostszy” można dyskutować. Jeśli “prostszy” to “mający istotnie mniej stanów”, to nie wydaje mi się, żeby taka konstrukcja była możliwa.

Odpowiem pytaniem na pytanie zadając zadanie bonusowe (aż żal je marnować, byłoby dobre na egzamin):

Pokaż, że dla każdego n istnieje język L_n rozpoznawany przez NFA (a nawet DFA) o n stanach taki, że każdy NFA rozpoznający L^{iter}_n = \{w \mid \exists_{n \in \mathbb{N}} w^n \in L_n \} ma \Omega(n) stanów.

Hint: Rozważ alfabet \Sigma = \{ 0,\#\}.