Zajęcia 9 marca

Zadanie domowe na 16.03

Kartkówka (konkurs wirtualny) z programowania dynamicznego

https://themis.lo14.wroc.pl/IIAB1718KAR2, hasło: dynamiczki.

Dwa zadania na programowanie dynamiczne, krótko omówienie na zajęciach.

• Zadanie na optymalną kolejność mnożenia macierzy. Omówienie problemu i pseudokod algorytmu można znaleźć tutaj: http://ii.drx.pl/_media/aisd:notatki_full.pdf, strony 35-37.
• Zadanie, w którym mamy tablicę o wymiarach 4xN i pytamy się na ile sposobów można w tej tablicy ułożyć kamyki tak, aby żadne dwa nie sąsiadowały ze sobą w pionie lub w poziomie. W rozwiązaniu rozważamy stany postaci dp[i][ułożenie kamyków w kolumnie i] = liczba możliwych ustawień w tablicy obciętej do kolumn 1,..., i. W celu zgrabnego zapisania możliwych ustawień kamyków w kolumnach można użyć masek bitowych. Można również zauważyć, że tak naprawdę potrzebujemy w tym zadaniu tylko stałej ilości pamięci (ale nie jest to wymagane, aby program został zaakceptowany).

Po uruchomieniu konkursu wirtualnego macie 2h na wysyłanie rozwiązań. Kartkówka ma na celu przećwiczenie przez was umiejętności implementowania i debugowania programów. Należy rozpocząć konkurs wirtualny przed godziną 20.00 w niedzielę 12.03 (o godzinie 22.00 wystawię oceny). Skala ocen: 2 zadania - 5, 1 zadanie - 3, 0 zadań - 1.

Zadania na Themisie z listy "Programowanie dynamiczne znów"

Wskazówki do zadań:

• Zadadnie Mapa Gęstości jest proste, a poza tym pojawiło się na I etapie VIII Olimpiady Informatycznej, więc zawsze można sobie przeczytać jego omówienie w niebieskiej książeczce. To zadanie pojawiło się kiedyś na egzaminie końcowym na ITN i osoba, która ten egzamin zdawała zaimplementowała poprawne rozwiązanie "w ciemno" tzn. bez możliwości wysłania kodu na sprawdzaczkę. Oczekuję więc, że nie sprawi ono wiele kłopotu.
• W zadaniu Wybieranka oczekiwana złożoność to O(n^3).

Termin zgłaszania rozwiązań jest ustawiony na godzinę 9.10 w czwartek 16.03. Skala ocen: 3 zadania - 6, 2 zadania - 5, 1 zadanie - 3, 0 zadań - 1.

Teoria gier

Planowałem w czwartek przepytać kogoś z dowodu tw. Sprague-Grundy'ego, ale zaniechałem tego pomysłu, macie wystarczająco dużo zadane ode mnie i od Karola.

Na najbliższych zajęciach opowiem coś z teorii gier. Jeśli ktoś się niecierpliwi, to może przygotować się dodatkowo, oglądając wykład Jakuba Radoszewskiego, który jest dostępny tutaj: http://was.zaa.mimuw.edu.pl/?q=node/18.