Tematy projektów 2021
- Zasady ogólne
- Zasady dotyczące kodu
- Zasady dotyczące sprawozdania
- Terminy oddawania projektów
- Lista tematów
Zasady ogólne
Zaliczenie projektu jest indywidualne; to znaczy, grupa może zdawać w tym samym czasie, ale ocena końcowa w ogólności może się różnić (chociaż zazwyczaj jest taka sama). Zaliczenie odbywa się osobiście (nie można przesłać kodu i sprawozdania pocztą elektroniczną). Sprawdzony jest kod źródłowy oraz sprawozdanie.
Zaliczenie odbywa się w laboratorium, przy czym program odpalony musi zostać na conajmniej trzech różnych maszynach. Program powinien umożliwić modyfikację parametrów projektów. Mogą to być stałe zapisane na sztywno w kodzie, lub (lepiej widziane) argumenty dla programu.
Uruchomiony program powinien wyświetlać informację o aktywności każdego procesu. Każdą wypisaną informację należy poprzedzić wartością zegara logicznego Lamporta - konieczna jest więc implementacja zegara Lamporta w kodzie każdego projektu. Minimalne informacje to ID procesu i aktualny stan (np. ubiegam się o sekcję krytyczną, otrzymałem miejsce w sekcji krytycznej), plus ewentualnie lokalna wiedza procesu o innych procesach.
Rozwiązania powinny być maksymalnie równoległe. Rozwiązanie, w którym wszystkie procesy mają zmienne globalne chronione przez sekcje krytyczne (i tylko jeden proces naraz może je wtedy modyfikować), jest niedopuszczalne.
Każdy projekt posiada wersję uproszczoną. Można oddać wersję uproszczoną (otrzymuje się wtedy ocenę 3.0) pod warunkiem, że odda się ją na ostatnich zajęciach oraz jeżeli się zadeklaruje implementację wersji uproszczonej najpóźniej na przedostatnich zajęciach.
Projekty oddane na czas otrzymują "bonus" w postaci łagodniejszego oceniania. Im później projekt będzie oddany, tym surowiej będzie oceniany. W przypadkach skrajnego opóźnienia będę na siłę wyszukiwał rzeczy, do których się można doczepić, i będę kazał jej poprawić. Celem jest maksymalne zniechęcenie do oddawania projektów nie na czas. Dodatkowo, ocena będzie zmniejszona o pół stopnia dla projektów oddanych z opóźnieniem (patrz "terminy" poniżej). Nie przyjmuję projektów oddawanych później, niż po 9 października (wymagany wtedy jest nowy temat i powtarzanie przedmiotu).
Powrót to opisu zasad ogólnych
Zasady dotyczące kodu
Nie może istnieć jeden element centralny; wszystkie algorytmy powinny być w pełni rozproszone, bez liderów, wyróżnionych procesów pełniących specjalne funkcje i tak dalej. Nie wolno niczego zakładać o czasie działania lub przesyłania komunikatów. Przyjmujemy, że środowisko jest w pełni asynchroniczne. Należy przyjąć, że kanały między procesami są FIFO i niezawodne, a procesy nie ulegają awarii.
Kod powinien być podzielony na krótkie funkcje o nazwach jasno określających ich rolę. Czytelność i elegancja kodu nie wpływają na decyzję o odrzuceniu lub nie projektu, ale mogą wpływać na ocenę końcową (wyjątek: kiedy ktoś oddaje na czas).
Należy unikać aktywnego czekania i nieblokujących funkcji. W przypadku ich użycia, należy umieć uzasadnić konieczność ich użycia.
Można użyć dowolnego języka programowania, ale tylko C oraz C++ mają 100% wsparcie. W przypadku użycia innego języka (Pythona, Javy itp) należy samodzielnie sprawdzić, czy program się uruchomi w laboratorium i samodzielnie zabiegać u administratora o doinstalowanie odpowiednich bibliotek (jeżeli będzie to wymagane).
Powrót to opisu zasad ogólnych
Zasady dotyczące sprawozdania
Sprawozdanie nie powinno zawierać kodu. Powinno natomiast zawierać opis problemu podany słownie lub w postaci pseudokodu (zawierającego tylko faktycznie potrzebne do zrozumienia algorytmu informację), założenia przyjęte na temat środowiska komunikacyjnego w tym pojemność kanałów (ile wiadomości maksymalnie naraz może być w kanale), oraz złożoność komunikacyjną i czasową
Sprawozdanie musi być tak napisane, by na jego podstawie inna osoba by była w stanie napisać implementację wymyślonego algorytmu.
Terminy dotyczące projektów
- Termin oddania algorytmu: dwa tygodnie od otrzymania tematu, tj. tydzień 13-18.04.2021
- Termin "bonusowy": do ostatnich zajęć (de facto tydzień 8-12.06.2021)
- Termin bez obniżania oceny: do 19.06.2021
- Najwyższa ocena 4.5: do 30.06.2021
- Najwyższa ocena 4.0: do 3.09.2021
- Najwyższa ocena 3.5: do 17.09.2021
- Najwyższa ocena 3.0: do 9.10.2021 (termin ostateczny!)
UWAGA! Po 9.10.2021 trzeba zdobyć nowy temat, co jest równoznacze z oceną 2.0 z pierwszego terminu. Następnie należy zdobyć akceptacje algorytmu i zaimplementować. W tym roku będę bezlitosny i nie będę przyjmował projektów łamiących te wymogi.
Tematy projektów 2021
- Łowcy nagród
- Kosmiczne fajerwerki
- Conan bibliotekarz
- Cywilizowane debaty
- Space above and beyond
- Mistrzowie Yoda
- Obrażalscy kosmici
- Bramy międzywymiarowe
Powrót to opisu zasad ogólnych
Łowcy nagród
Ludzkość opanowała układ słoneczny, ale nie własne, kryminalne popędy. Liczni przestępcy napadają na spokojnych górników i handlarzy. Ich łapaniem zajmują się zespoły łowców nagród, tradycyjnie złożone z ex-policjanta lubiącego drzewka bonsai, przystojnego żigolaka o sztucznym oku, pięknej ex-przestępczyni, dziecka-komputerowego geniusza o nieokreślonej płci oraz psa Eina. Przed wyruszeniem w podróż muszą się więc dyskretnie zaopatrzyć w odpowiedni sprzęt: psie żarcie, komputery, nawóz dla drzewek bonsai itd - oraz, oczywiście, najtańsze samonaprowadzające rakiety i amunicję. W tym celu zaopatrują się w sklepie, w którym naraz może przebywać nie więcej, niż S łowców.
Dane są N procesów reprezentujące łowców nagród oraz Z procesów-zleceniodawców, co pewien czas rozgłaszających zlecenia do procesów-łowców. Łowcy zdobywają zlecenie, następnie ubiegają się o dostęp do sklepu o pojemności S. W sklepie przebywają jakiś czas (dość długo, ale nie wiadomo jak długo), następnie wyruszają na wyprawę. Procesy-zleceniodawcy mają ograniczenie od góry HM na liczbę niewykonanych zleceń; jeżeli nagromadzi się zbyt dużo niewykonanych zleceń, przestają generować nowe zlecenia, póki ich liczba nie spadnie poniżej LM.
Wersja uproszczona:: Tylko jeden proces-zleceniodawca, brak HM oraz LM, S=1
Powrót to opisu zasad ogólnych
Kosmiczne fajerwerki
Pewien milioner przypadkowo zamiast zwykłych inżynierów zatrudnił tabuny inżynierów i inżynierek-piromanów, uwielbiających wielkie BUM, zwłaszcza transmitowane na żywo w telewizji. Od tego czasu milioner naiwnie finansuje zespoły inżynierów i inżynierek, którzy konstruują gigantyczne rakiety pod pozorem podróży w kosmos. Rakiety te widowiskowo ulegają destrukcji podczas startu, ku nieopisanej radości inżynierów (i inżynierek) piromanów.
Danych jest N procesów, zespołów-inżynierów piromanów, każdy o liczebności In (In inne dla każdego zespołu). Ubiegają się oni o nierozróżnialne zasoby: najpierw determinują, co tym razem wysadzą. W tym celu zajmują In z B nierozróżnialnych biurek. Następnie zajmują jedną z K salek konferencyjnych, gdzie z poważnymi minami obwieszczają, że tym razem start rakiety zakończy się sukcesem. Później zajmują jedno pole startowe, odpalają rakietę, cieszą się jak dzieci z BUM i zajmują tym razem jedno z B biurek (tych samych co poprzednio), gdzie wysmarowują wiarygodnie brzmiące wyjaśnienie, dlaczego rakieta znowu wybuchła.
Wersja uproszczona: : Zespoły mają liczebność 1, nie trzeba zajmować biurek.
Powrót to opisu zasad ogólnych
Conan Bibliotekarz
Bibliotekarki i bibliotekarze mają dosyć czytelników spóźniających się z oddaniem książek, plamiących kartki albo wręcz przywłaszczających sobie biblioteczne egzemplarze. Dlatego też zaczęli współpracować z OTA (organizacją twórczego anachronizmu), zajmującego się do tej pory głównie prężeniem mieśni i lataniem w samych slipkach i mieczami po ulicach polskich miast. Bibliotekarze wysyłają prośby o pomoc do kilku wybranych barbarzyńców. Barbarzyńcy podejmują zlecenie. Najpierw udają się do magazynu OTA, gdzie pobierają jedno z S strojów służbowych (slipki i gumowy miecz). Następnie wyruszają na miasto, dopadają czytelnika/czytelniczkę, tłumaczą łagodnie z użyciem gumowego miecza, że książki należy oddawać na czas. Idą następnie do punktu kontaktowego, porozumiewywają się z bibliotekarzem, przekazują mu książkę i czekają na kolejne zlecenie. Bibliotekarz nie wysyła więcej zleceń niż jedno naraz, ale zawsze może wysłać do więcej niż jednego barbarzyńcy - tylko jeden z nich może podjąć zlecenie. Po zlecenie barbarzyńcy oddają slipki do pralni miejskiej (o pojemności P) i dopiero potem zwracają je do magazynu.
Dane jest B bibliotekarzy oraz C conanów barbarzyńców. Zasoby są niezrozróżnialne: S strojów służbowych. Należy zapewnić, by zlecenia bibliotekarzy były wypełniane, oraz by barbarzyńcy dzielili się równo pracą.
Wersja uproszczona: : Jeden bibliotekarz, wysyła zlecenie do jednego barbarzyńcy, slipki można oddać bez wyprania.
Powrót to opisu zasad ogólnych
Cywilizowane debaty
W pewnym mieście powstały kluby dyskusyjne, których członkowie, wyznający różne poglądy na różne tematy, co jakiś czas spotykają się na cywilizowane debaty. Z biegiem lat w użycie weszło coraz więcej chwytów retorycznych, ułatwiających wygranie dyskusji. Dlatego też przed rozpoczęciem debaty członkowie muszą się odpowiednio zaopatrzyć.
Dane są N procesów. Dobierają się w pary do debaty, wynajmują jedną z S nierozróżnialnych salek konferencyjnych. Każdy proces osobno zaopatruje się w losowo wybrane zasoby: jeden z M misek do rzucania, jedno z P pudełek pinezek, jedno z G pancernych slipek. W debacie slipki pokonują pinezki, pinezki pokonują miski, miski pokonują slipki. Po zakończeniu debaty procesy jakiś czas odpoczywają, pokonany krócej.
Wersja uproszczona: : Procesy są schizofreniczne i debatują same z sobą (nie ma dobierania w pary)
Powrót to opisu zasad ogólnych
Space Above and Beyond
Ludzkość toczy wojnę z kosmicznym wrogiem. Do walki stają marines, których najpierw z wielkim nakładem środków szkoli się na pilotów, a potem często wysyła na misje typowe dla zwykłych piechociarzy. Zespoły okresowo ruszają na misje różnego typu: (a) obejmujące loty myśliwcami (b) obejmujące bieganie po błocie na obcych planetach. Po misjach typu (a) należy naprawić myśliwce, po (b) zająć szpitalne łóżka. Po każdej misji zespoły świętują zwycięstwa w jednej z dwóch rozróżnialnych knajp.
Danych jest N zespołów, każdy o innej pojemności Mn. Zespół spontatnicznie decyduje, że wyrusza na misję określonego typu. Po każdej misji określone jest, ile myśliwców wymaga naprawy lub ilu marines musi trafić do szpitala. Zajmuje się wtedy odpowiednią liczbę miejsc w warsztacie (pojemność W) albo szpitalu (pojemność SZ). Trwa to pewien czas; zwalnianie miejsc trwa pojedynczo (ludzie zdrowieją w różnym tempie). Po wysłaniu myśliwców/rannych, marines rezerwują miejsce w knajpie (jednej z dwóch; pojemność K). Mogą przystąpić do kolejnej misji, o ile mają jeszcze sprawne myśliwce ORAZ zdrowych marines.
Wersja uproszczona: : Jest tylko jeden typ misji, z myśliwcami. Myśliwce naprawiane są od razu. Jest tylko jedna knajpa.
Powrót to opisu zasad ogólnych
Mistrzowie Yoda
W odległej galaktyce działa zakon mistrzów utrzymujących kosmiczną równowagę. W zakonie są trzy rodzaje mistrzów: dwa z nich współpracują, czerpiąc energię z nadhiperprzestrzeni, by przywracać równowagę. Trzeci rodzaju spędza czas głównie wpatrując się we własne pępki, od czasu do czasu tylko jest przyzywany, by uzupełnić energię w nadhiperprzestrzeni.
Dane są procesy reprezentujące X mistrzów siły Iks, Y mistrzów siły Yoda oraz Z mistrzów siły Zet. Dana jest nadhiperprzestrzeń, w której jest makysmalnie Z energii. Mistrzowie Iks oraz Yoda dobierają się w pary, po czym czerpią jednostkę energi z nadhiperprzestrzeni. Gdy energia się skończy (spadnie do zera), ktoś musi powiadomić mistrzów Zet. Mistrzowie Zet wspólnie, każdy osobno, w dogodnym dla siebie czasie uzupełnia energię nadhiperprzestrzeni, po czym powracają do wpatrywania w pępek. Nie można uzupełniać energii, gdy ktokolwiek z niej czerpie (i vice versa). Seanse czerpania oraz energii trwają długo, losowo długo.
Wersja uproszczona: : Nie ma mistrzów Iks, więc tylko mistrzowie Yoda czerpią energię, a Zet uzupełniają. Można uzupełniać energię, gdy ktoś czerpie z nadhiperprzestrzeni.
Powrót to opisu zasad ogólnych
Obrażalscy kosmici
Ziemię odwiedzają kosmici, zachwyceni uroczą zaściankowością naszej planety. Po przybyciu zajmują jedno z miejsc w jednym z H hoteli, następnie wynajmują jednego z przewodników, ruszają na wyprawę, po powrocie zwalniają miejsce z hotelu. Problem jest tylko w tym, że są to okropnie drażliwi kosmici, należący do jednej z dwóch fakcji: Fioletowych oraz Błękitnych. Błękitni i Fioletowi nienawidzą się wzajemnie i dlatego nie może dojść do sytuacji, w której w hotelu równocześnie przebywaliby Błękitni i Fioletowi - należy zapewnić, że w danym hotelu zawsze jest tylko jedna fakcja - ale nie wolno przypisać hotelu na sztywno do jednej z fakcji. Co jakiś czas hotele muszą być sprzątane przez ludzkie ekipy sprzątające.
Modelujemy procesy Fiolotewe, Błękitne, oraz Sprzątaczy.
Wersja uproszczona: : Brak przewodników, brak sprzątaczy
Powrót to opisu zasad ogólnych
Bramy międzywymiarowe
Pewien naukowiec odkrył w czasie badania pseudonakowych bredni pewnego medium, że jeżeli wspomoże się medium odpowiednią ilością środków wspomagających (denaturat, klej butapren), medium jest w stanie rzeczywiście otworzyć przejścia do innych wymiarów. Od tej pory organizuje wycieczki (za odpowiednią opłatą). Turyści wynajmują jedno z M medium, w sklepie firmowym o pojemności F zakupują denaturat i klej, następnie czekają, aż medium otworzy tunel. Wkraczają do tunelu i docierają do innego wymiaru - po pewnym czasie, nie wiadomo jak długim, automatycznie wracają z powrotem. Tunel musi być FIFO, chociaż turyści mogą iść nim różną ilosć czasu. Medium po otwarciu T tuneli musi odpocząć, zanim będzie w stanie wrócić do pracy
Modelujemy turystów.
Wersja uproszczona: : Nie trzeba kupować denaturatu i kleju, Medium nie musi odpoczywać.