JFiZO II lista z II części kursu i kolejne listy

Na drugie ćwiczenia z drugiej części kursu proponuję zadania:

94 i 97 – 106.

Ćwiczenia odbędą się w kolejną środę, która prawdopodobnie wypadnie 22 kwietnia.

I odbędą się z grubsza takim sposobem jak wczorajsze. ( Bo to chyba było OK, prawda?)

Na trzecie ćwiczenia z II części kursu czekają zadania:

112 (bardzo ważne, z niego się korzysta w niektórych innych, np. 119 albo 130 i w tysiącu innych miejsc)

oraz: 110, 111, 117–119, 128-- 130.

Przy okazji zadania 119 wspominamy jego autora:

Zapomniałem ogłosić kolejną CZWARTĄ listę z drugiej części kursu.

I NIKT SIĘ NIE UPOMNIAŁ. Co mnie nieco martwi.

No więc w każdym razie. Na najbliższą środę mamy zadania: 114–116; 120 (Bardzo Ważne), 121, 131 (Nawiązujące do jutrzejszego wykładu), 136-- 138.

Jak słusznie zauważa p. Oskar w Zadaniu 121 jest błąd.

Można go poprawić na 2 sposoby. Albo zamiast program w MUJP mieć maszynę Turinga. Albo mieć MUJP, ale jako miarę długości programu mieć nie liczbę instrukcji tylko całkowitą liczbę znaków. (Bo przecież n można wypisać jedną instrukcją, tylko że ona będzie musiała być długa).

Zastanawiałem się nad formatem dzisiejszych ćwiczeń (nawiązuję tu do dyskusji po ostatnim wykładzie). I postanowiłem że nie powiem Wam wcześniej kto robi które zadanie na ćwiczeniach. Bardzo Was przepraszam, ale to by było niezgodne z moim sumieniem.

Głównym problemem zajęć (ćwiczeń) on-line naprawdę nie jest to, że prezentacje zadań są technicznie kostropate. Z tym się da żyć. Może się z tego powodu opowiada 20% wolniej, ale co z tego?

Problemem jest to, że ludzie są nieobecni, nie są skupieni na słuchaniu. I obawiam się że gdybym Wam wcześniej powiedział kto ma zrobić które zadanie to problem by się tylko pogłębił, bo każdy by się zajął szykowaniem swojej prezentacji.

Problemem jest to, że ludzie są nieobecni, nie są skupieni na słuchaniu. I obawiam się że gdybym Wam wcześniej powiedział kto ma zrobić które zadanie to problem by się tylko pogłębił, bo każdy by się zajął szykowaniem swojej prezentacji.

Nie rozumiem, według mnie jest odwrotnie.

Jeśli nie powie mi się, które zadanie będę robił, to podczas czyjejś prezentacji zadania n, zamiast słuchać, będę przygotowywał się do swojej prezentacji zadania n+1, jeśli takowe zadeklarowałem – na wypadek gdybym został wybrany. Taki system uniemożliwia mi naukę na ćwiczeniach.

Jeśli natomiast powie mi się, które zadanie będę prezentował to – po upewnieniu się, że pamiętam, jak chcę je rozwiązać – zacznę słuchać rozwiązań innych zadań. Bez większych obaw i stresu o grzyba.

4lajki

Jakiego grzyba na miłość Boską. Kiedy ktoś dostał grzyba ostatnio ?

Nie wiem. Nie zmienia faktu, że taka możliwość istnieje. Nawet nie ma to znaczenia, bo bez grzybów też nie chcę publicznie rozwiązywać zadania które robiłem dwa dni wcześniej. Więc, jak wcześniej napisałem, przygotowuję się do każdego zadania do którego potencjalnie mogę zostać wybrany.

2lajki

@jma @jotop Czy jeśli na liście są zadania A i B i moje rozwiązanie zadania B korzysta z tezy zadania A, ale nie umiem zrobić zadania A, to czy takie rozwiązanie zadania B będzie zaakceptowane?

2lajki

W mojej grupie można zadeklarować samo zadanie B.

4lajki

I NIKT SIĘ NIE UPOMNIAŁ

tym razem się upominamy. Przy okazji: jak będą wyglądały zajęcia w środę? Od czego zaczniemy? Ile (mniej więcej) czasu zostanie przeznaczone na wykład, a ile na ćwiczenia?

Bardzo dziękuję! Jakoś inaczej czas teraz płynie.

Na najbliższą środę proponuję zadania:

122–124, 127, 134

Proponuję, żeby ćwiczenia trwały od 4:15 pm do 5:30 pm. A od 5:45 pm zaczniemy trzecią część kursu, i zaczniemy ją wykładem. Który potrwa do 7:00 pm

W zadaniu 124 jest błąd:


W H10 chcemy wiedzieć czy układ ma rozwiązanie w liczbach naturalnych.

O rozwiązaniach w jakich liczbach mamy zatem myśleć w 124 – naturalnych nieparzystych czy całkowitych nieparzystych?

Myślę że można moje niejasne (bo niestaranne) sformułowanie uczynić jasnym na dowolnie przez siebie wybrany z dwóch oczywistych sposobów.

Na pierwszą listę z III części kursu
czyli na ćwiczenia 20 maja
trafiają
zadania
139 – 147 i 153.

Mam dwa pytania do listy zadań

  • Nie udało mi się dotrzeć do polskiej wersji podręcznika Ullmana i Hopcrofta. Czy problem z zadania 146 różni się od problemu 2SAT?
  • W zadaniu 153 jest pytanie o złożoność problemu. Czy wystarczy rozstrzygnąć czy jest to złożoność wielomianowa, czy należy udowodnić dokładną złożoność?
  1. To jest 2SAT, tak. Muszę zmienić treść tego zadania, studenci na szczęście nie uczą się z tej strasznej książki już.

  2. Dla nas złożoność to odpowiedź na pytanie do jakiej klasy złożoności problem należy: PTIME, NP, PSPACE itd. “Dokładna złożoność” to jest subtelna sprawa: od razu zaczynają się pytania o model obliczeń. Których my sobie nie musimy zadawać, bo wszystkie sensowne modele są wielomianowo równoważne.

Kolejne listy idą tak:

Na 27 maja będą zadania 148-- 152, 154, 155, 158, 159 i 179

a na 3 czerwca najprawdopodobniej:

173, 180 --184, 192 oraz, wymagające materiału z wykładu 1 czerwca:

193, 202, 203.

To by znaczyło, że ćwiczenia 27 maja odbędą się w normalnym wymiarze. A 25 maja, przypominam, wykładu nie będzie, z powodu wyborów rektora,

Mam pytanie do zadania 179:
Czy Melmażelon pożre każdą daną przez nas formułę boolowską – niekoniecznie w 3-CNF?

Tak. Zeżre co mu dadzą. Ale to nie ma znaczenia.