Tematy projektów 2019
- 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 8 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ń 8-12.04.2019
- Termin "bonusowy": do ostatnich zajęć (de facto tydzień 10-15.06.2019)
- Termin bez obniżania oceny: do 21.06.2019
- Najwyższa ocena 4.5: do 31.06.2019
- Najwyższa ocena 4.0: do 6.09.2019
- Najwyższa ocena 3.5: do 20.09.2019
- Najwyższa ocena 3.0: do 8.10.2019 (termin ostateczny!)
UWAGA! Po 8.10.2019 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 2019
- RPG
- Przyjazny Spisek Telepatów Z Maszyną Czasu
- Polowania na robozające
- Bandersnatche
- Wycieczki po morzu nieprawdopodobieństwa
- Obsługa Pyrkonu
- Wskrzeszanie smoków, Inc.
- Nanozombie
Powrót to opisu zasad ogólnych
RPG
W pewnym dużym mieście grupa N graczy RPG założyła ligę graczy. Gracze co pewien czas spontanicznie odczuwają chęć gry. Niektórzy z nich chcieliby być w danej rozgrywce Mistrzami Gry, inni graczami. Gracze najpierw decydują spontanicznie, kim tym razem woleliby być. Następnie, Mistrzowie Gry dobierają się w grupy z graczami. Gra rusza, gdy w grupie jest Mistrz Gry i dwóch Graczy. W każdej chwili nie może być mniej niż M mistrzów gry. Dodatkowo, zachowane jest N= 3M. Jeżeli w danej chwili jest już M mistrzów, gracz może zrezygnować z bycia mistrzem gry. Gracz nie może zmienić zdania i zostać mistrzem. Należy zapewnić, by gry zawsze się odbywały.
Wersja uproszczona: : Procesy na sztywno są podzielone na mistrzów i graczy, pozostaje problem dobierania ich w grupy.
Powrót to opisu zasad ogólnych
Przyjazny Spisek Telepatów z Maszyną Czasu
Od dawien dawna światem kieruje pradawny spisek telepatów, którzy kradną ludziom pomysły, a potem wykorzystują maszyny czasu, aby cofać się w czasie i pomysły implementować, czasami nawet przed narodzinamy oryginalnych odkrywców. Każdy telepata, aby działać, potrzebuje do działania jednej z m maszyn czasu oraz, do wyboru: jednej z c czapek niewidek lub jednej z x kompletów oszałamiaczy+maszyna do wymazywania pamięci. Telepata spontanicznie decyduje, czy tym razem chce skorzystać z czapki niewidki, czy też woli bardziej siłową wersję z młotkiem i wymazywaniem pamięci. Maszyn czasu jest znacznie mniej, a sama operacja cofnięcia się w czasie jest bardzo szybka, po czym telepata spędza długi czas w przeszłości, i ponownie potrzebuje maszyny czasu, by powrócić (przy czym maszyna automatycznie jest przyzywana z przyszłości, by umożliwić mu powrót). Tak więc całość operacji to: telepata zdobywa pomysł, cofa się w przeszłość, długo implementuje pomysł, telepata powraca do teraźniejszości.
Wszystkie zasoby są nierozróżnialne
Wersja uproszczona: : Tylko czapki niewidki, operacja cofnięcia się w czasie i powrót jest krótka i może być realizowana przy użyciu tej samej maszyny.
Powrót to opisu zasad ogólnych
Polowania na robozające
W odległej przyszłości ludzie nie muszą pracować, zabijają więc czas urządzając polowania na robozające. Są dwa typy procesów: myśliwi oraz proces reprezentujący techników, projektów robozajęcy. Każdy myśliwy zdobywa jedną z L nierozróżnialnych licencji na wejście do parku. Tam jakiś czas poluje, aż ubija jednego z R nierozróżnialnych robozajęcy. Każdy myśliwy spontanicznie decyduje, ile chce zdobyć trofeów. Gdy zdobędzie trofeum, wzywa jeden z T transportów. Gdy liczba robozajęcy spadnie do zera, do parku wchodzą technicy, produkując nowe robozające. Technicy mogą wejść do parku tylko wtedy, gdy nie ma tam myśliwych, i wpuszczają myśliwych dopiero, gdy stworzą nowe robozające. Gdy liczba robozajęcy spadnie do zera, wszyscy myśliwi obecnie przebywający w parku powinni go opuścić. Powinni mieć oni priorytet przy kolejnym dostępie do parku.
Wersja uproszczona: : Robozające się nie kończą, w związku z tym nie ma techników
Powrót to opisu zasad ogólnych
Bandersnatche
Myśliwi, którzy w odległej przyszłości mają dość robozajęcy, mogą wybrać się na obcą planetę, gdzie mieszkają bandersnatche. Te łagodne zwierzątka znane są z wielkich oczu rodem z anime oraz upodobania do przerabiania myśliwych na kotlety mielone, więc polowania na nie dostarczają myśliwym wrażeń zarówno czysto estetycznych, jak i odpowiedniego zastrzyku adrenaliny. Każdy myśliwy zdobywa jedną z broni: K karabinów lub M mieczy (to drugie dla twardzieli). Następnie długo polują. Polowanie kończy się: (a) bardzo rzadko, śmiercią myśliwego (b) okaleczeniem myśliwego (wówczas musi wezwać jednego z s sanitariuszy) lub, najczęściej (c) upolowaniem bandersnatcha. Po upolowaniu myśliwi rezerwują miejsce w centrum wypychania bandersnatchy. Bandersnatche ważą od 1 do W jednostek wagi, centrum może maksymalnie pomieścić T jednostek wagi. Program trwa do czasu, aż wyginą wszyscy myśliwi.
Wersja uproszczona: : Nie ma śmierci i okaleczenia myśliwego, każdy bandersnatch waży tyle samo
Powrót to opisu zasad ogólnych
Wycieczki po morzu nieprawdopodobieństwa
Nieoczekiwanie koło jeziora maltańskiego odkryto przejście do innego wymiaru, gdzie wśród wijących się całek i numerycznych sztormów można ujrzeć obrazy żywcem wyjęte z surrealistycznych majaków. Przewodnicy organizują grupy wycieczkowe pragnące pożeglować w niemożliwe. Spontanicznie zgłasza się do każdego przewodnika x osób, po czym przewodnik zdobywa dostęp do morza nieprawdopodobieństwa (równocześnie może żeglować nie więcej niż M osób, ale może mniej). Następnie muszą zdobyć jeden z P rozróżnialnych pojazdów. Każdy pojazd zużywa się podczas podróży, jego stan techniczny, początkowo równy s, powoli spada do zera (po każdej wycieczce). Gdy przewodnik zauważy, że pojazd się zepsuł, zdobywa dostęp do jednego z tnierozróżnialnych techników; dopóki pojazd się nie naprawi, nie bierze udziału w wycieczkach, tak samo jak przewodnik.
Wersja uproszczona: : Pojazdy się nie psują.
Powrót to opisu zasad ogólnych
Obsługa Pyrkonu
Uczestnicy Pyrkonu najpierw zdobywają jeden z b biletów na tegoroczny Pyrkon. Następnie wybierają pojedynczo kilka (ale nie wszystkie) z rozróżnialnych warsztatów, do każdego z nich zdobywając osobny bilet (na warsztacie może być maksymalnie w uczestników. Po przejściu kilku warsztatów uczestnik zwalnia bilet i przestaje się ubiegać, dopóki nie zacznie się kolejny Pyrkon. Gdy wszyscy uczestnicy zwiedzą Pyrkon, konwent się kończy i po jakimś czasie zaczyna kolejny.
Wersja uproszczona: : Pyrkon nigdy się nie kończy
Powrót to opisu zasad ogólnych
Wskrzeszanie smoków, Inc.
Ubić smoka może byle idiota. Za to wskrzesić... do tego potrzeba profesjonalisty. Są dwa rodzaje procesów: jeden generuje co pewien czas zlecenie. O zlecenie ubiegają się profesjonaliści o jednej z trzech możliwych specjalizacji (głowa, ogon, tułów). Do realizacji zlecenia potrzeba trzech profesjonalistów o różnych specjalizacjach - należy zapewnić, by nie doszło do zakleszczeń! Dodatkowo, profesjonaliści muszą wypełnić robotę papierkową (robi to jeden z nich) przy jednym z b biurek w gildii Wskrzeszania Smoków. Następnie profesjonaliści zdobywają dostęp do jednego z s szkieletów smoków i rozpoczynają wskrzeszanie. Należy zapewnić, by profesjonaliści dzielili się w miarę równo pracą.
Wersja uproszczona: : Brak specjalizacji.
Powrót to opisu zasad ogólnych
Nanozombie
Archeolodzy odkryli starożytne, podwodne miasto, opanowane całkowicie przez chmury nanitów, które po wykryciu obecności ludzi przybierają kształt zombie. Ponieważ miasto położone jest na międzynarodowych wodach, każdy może zostać turystą i zwiedzić miasteczko. Potrzebne jest do tego: strój kucyka (bo zombie, zmylone strojem, głupieją i zaczynają tańczyc i palić zioło), transport oraz osobisty sprzęt eksploracyjny. Transport to jedna z rozróżnialnych łodzi podwodnych, każda o innej pojemności. Każdy turysta musi zdobyć strój kucyka (nierozróżnialne) oraz dostęp do jednej z łodzi podwodnych. Każdy turysta zajmuje od 1 do n pojemności łodzi. Gdy łódź zostanie zajęta tak, że żaden inny turysta się nie zmieści (niekoniecznie optymalnie, rozważane jest wg kolejności zgłoszeń) wyrusza na wyprawę.
Wersja uproszczona: : Jedna łódź - jeden turysta.