Tematy projektów 2022
- 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ń 11-15.04.2022
- Termin "bonusowy": do ostatnich zajęć (de facto tydzień 13-16.06.2022)
- Termin bez obniżania oceny: do 19.06.2022
- Najwyższa ocena 4.5: do 30.06.2022
- Najwyższa ocena 4.0: do 2.09.2022
- Najwyższa ocena 3.5: do 16.09.2022
- Najwyższa ocena 3.0: do 7.10.2022 (termin ostateczny!)
UWAGA! Po 7.10.2022 (czyli od 8.10 włącznie) 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 2022
- Stowarzyszenie umarłych poetów
- Skrzatowisko
- Pojedynki
- Badacze nawiedzonych domów
- Winiarze
- Ogrodnicy
- Otaku
- Wojna
- Obrażalscy kosmici
Powrót to opisu zasad ogólnych
Stowarzyszenie umarłych poetów
W pewnym mieście uniwersyteckim grupa młodych ludzi wpadła na pomysł, by zwiększyć swoje zdolności twórcze konsumpcją dużej ilości alkoholu. W tym celu tworzą kółka poetyckie, po czym każdy przynosi alkohol lub zagrychę, przeprowadzają libację, przy okazji usiłując spłodzić dzieła mające przebić Przybyszewskiego. Po libacji poeta jakiś czas odpoczywa. Poeci działają pod natchnieniem chwili, więc mogą zdecydować w sposób losowy, że do jakiegoś kółka nie chcą przynależeć.
Danych jest P poetów. Poeci dobierają się w kółka o dowolnej wielkości. Przy dobieraniu się w kółka poeta może zdecydować, że do danego kółka nie chce należeć. Po zebraniu w kółko poeci decydują, kto przyniesie alkohol, a kto zagrychę, a kto może pić na sępa. Poeci nie lubią być frajerami, więc nie mogą non stop przynosić jednego rodzaju towaru lub sępić. Następnie wynajmują jeden z pokojów pracy twórczej, przeprowadzają libację, rozwiązują kółko. Po libacji powiadamiani są wolontariusze, która doprowadza pokój do porządku. Wolontariuszy jest W, decydują między sobą, kto posprząta pokój. Pokoje wynajmowane są na mieście, można więc przyjąć, że jest ich nieskończenie wiele - poeci z kółka nie mogą jednak przystąpić do kolejnej libacji, dopóki nie mają pewności, że jakiś wolontariusz zajął się pokojem.
Wersja uproszczona:: Kółka są wielkości X, wszyscy przynoszą alkohol (nie trzeba decydować), poeci nie odmawiają (gdy chcą przeprowadzać libację, zawsze się zgadzają na udział), pokoi nie trzeba ich doprowadzać do porządku (nie ma wolontariuszy).
Powrót to opisu zasad ogólnych
Skrzatowisko
W Bździszewie urządzono skansen skrzatów. Skrzaty żyły tam przez jakiś czas spokojnie, zaplatając koniom warkoczyki, ale po jakimś czasie znerwicowane konie miały dosyć - ostatecznie więc przyjęto system, w którym skrzaty muszą konkurować o konie i warkoczyki, a po każdej sesji konia ze skrzatem, koń musi odbyć sesję z psycholożkami.
Danych jest S skrzatów i P psycholożek. Skrzaty konkurują o losową liczbę w < W wstążeczek (wstążeczek jest maksymalnie W) oraz o K koni. Po zakończeniu sesji skrzata, koń trafia na kozetkę do psycholożki, która rozplata mu warkoczyki, puszcza muzykę relaksacyjną oraz pyta o relacje z matką. Dopiero po sesji wstążeczki trafiają z powrotem do puli do wykorzystania. Psycholożki konkurują o konie oraz o S salek terapeutycznych. Wstążeczki i sale są nierozróżnialne.
Wersja uproszczona:: Konie są nie do zdarcia, nie potrzeba psycholożek.
Powrót to opisu zasad ogólnych
Pojedynki
W alternatywnej rzeczywistości o technologii zbliżonej do wojen napoleońskich, weterani wojen znudzeni pokojem postanowili urządzić sobie pojedynki. W tym celu najpierw zgłaszają swój udział, dobierają się w pary, następnie dobierają sekundantów, przeprowadzają pojedynek, po którym przegrany trafia pod opiekę szpitalną i na jakiś czas nie może brać udziału w dalszych pojedynkach.
Danych jest W weteranów. Sekundantów jest S i jest im wszystko jedno, komu sekundują. Sal szpitalnych jest SZ i są nierozróżnialne.
Wersja uproszczona:: Pojedynki przeprowadza się z dostarczanym przez państwo przeciwnikiem, których jest P. Nie trzeba sekundantów. Po pojedynku zawsze trzeba trafić do jednej ze szpitalnych sal.
Powrót to opisu zasad ogólnych
Badacze nawiedzonych domów
Członkowie TBZNiP (towarzystwa badania zjawisk nadprzyrodzonych i porąbanych) mają dostęp do kilku nawiedzonych domów. Jako profesjonaliści, nie potrzebują jechać na miejsce bezpośrednio, by przeprowadzać badania. Wystarczy, że popadną w trans i dołączą do mentalnej grupy badającej dany dom. Po dołączeniu przesyłają innym członkom grupy mentalne wiadomości przy pomocy tzw. udowymewii (l. poj. udowymewia: urządzenia do wysyłania mentalnych wiadomości). Po pewnym czasie odłączają od grupy. Mentalne wiadomości nie mogą dotrzeć do kogoś, kto nie jest członkiem grupy. Wyjście z grupy może trwać i podczas procesu wychodzenia, badacz może otrzymać jeszcze wiadomość. Wiadomości można wysyłać tylko wtedy, gdy dana grupa ma co najmniej dwóch członków. Nie można wyjść z grupy, jeżeli nie wyśle się co najmniej jednej wiadomości. Grupa ma maksymalną wielkość M. Udowymewii jest U, przy ich pomocy można wysłać dowolną liczbę wiadomości (a więc badacz nie zwalnia ich natychmiast po wysłaniu wiadomości).
Wersja uproszczona: : Grupy nie mają maksymalnej wielkości, można wysyłać wiadomość do grupy tylko z jednym członkiem. Udowymewie służą do wysłania jednej wiadomości, potem trzeba się o nie ubiegać od nowa.
Powrót to opisu zasad ogólnych
Pomocni ogrodnicy
W pewnej betonowej dżungli istnieje kilku nieogarniętych właścicieli działek, którzy co jakiś czas mogą potrzebować pomocy ogrodników. Ogrodnicy są zrzeszeni w organizacji pomocowej i starają się dzielić pracą sprawiedliwie. Osobny instytut (jeden proces) powiadamia ogrodników o nowym zleceniu na pomoc. Ogrodnicy wtedy ustalają międy sobą, kto weźmie zlecenie, po czym losowy czas konsultują się z literaturą przedmiotu i przystępują do gromadzenia sprzętu ogrodniczego potrzebnego do zlecenia: jednego z trzech rodzajów (do obsługi trawnika, przycinania żywopłotów lub wyganiania szkodników).
Jest O ogrodników oraz T, P i W sprzętu ogrodniczego.
Wersja uproszczona: : Jest tylko jeden rodzaj sprzętu, instytut może ustalać, komu przydzielić zlecenie.
Powrót to opisu zasad ogólnych
Winiarze
W małym francuskim miasteczku grupa winiarzy uwielbia produkować wino. Niestety, kiepskiej jakości. W efekcie nikt nie chciał go kupować. Problem rozwiązali altruistycznie nastawieni studenci politechniki, którzy zjawiają się, by nieodpłatnie odebrać niechciany trunek, a następnie go w bezpieczny sposóby zutylizować.
Mamy W winiarzy i S studentów. Winiarze co pewien czas produkują beczkę wina o pojemności iluś tam (X, za każdym razem inne) litrów.
Każdy student co pewien czas spontanicznie decyduje, że potrzebuje ileś tam (Y, różne od X) litrów wina na imprezę w akadamiku
do utylizacji. Studenci konkurują o wino, po utylizacji przez jakiś czas mogą być niezdolni do dalszej pracy. Aby winiarz mógł przekazać wino
studentowi, potrzebne jest wynajęcie przez winiarza jednego z B bezpiecznych miejsc. Winiarz nie przystępuje do produkcji nowej partii
wina, dopóki nie pozbędzie się poprzedniej. Studenci decydują między sobą, bez udziału winiarzy, kto i w jakiej kolejności pobierze wino (winiarze
tylko produkują, wynajmują miejsca, oddają wino).
Wersja uproszczona: : Studenci zawsze biorą całe wino, winiarze więc produkują po prostu "jedną jednostkę" wina. Winiarz może zdecydować, komu dać wino.
Powrót to opisu zasad ogólnych
Otaku
Z uwagi na liczne skargi zwykłych uczestników, organizatorzy konwentu Pyrcon w Poznaniu przygotowali specjalne, wydzielone pomieszczenie dla Otaku ze stanowiskami dostępu do internetu (zwykli fani nie są w stanie przebywać w tych samych pomieszczeniach co otaku, z uwagi na niekonwencjonalne podejście do higieny osobistej prezentowane przez tych ostatnich).
W pomieszczeniu znajduje się S stanowisk. W pomieszczeniu, z uwagi na przepisy porządkowe, musi znajdować się co najmniej jeden przedstawiciel organizatorów. Pojedyńczy otaku wydziela pewną ilość specyficznego zapachu, mierzoną w cuchach. Liczba cuchów rośnie w czasie (można przyjąć, że po każdym odwiedzeniu pomieszczenia, a przed kolejną próbą dostania się do niego, liczba cuchów wydzielonych przez otaku wzrasta o losową ilość). Przedstawiciel organizatorów jest w stanie znieść równocześnie M cuchów, a po przekroczeniu dawki X cuchów mdleje; powoduje to konieczność zawiadomienia straży konwentu, która organizuje pierwszą pomoc oraz sprowadza nowego przedstawiciela.
Należy przyjąć, że początkowo sumaryczna liczba cuchów dowolnych S otaku jest mniejsza od M (tzn. początkowo musi się udać wejście do stali dowolnej kombinacji otaku). Można zauważyć, że ewentualnie jeden otaku samodzielnie zasmradza całą salę. Uwaga: algorytm symuluje tylko zachowania otaku, którzy przez komórki ustalają, kto obecnie ma wejść do sali i czy należy zawiadomić straż konwentu o konieczności wymiany przedstawiciela. Otaku mają oczywiście dostęp do cuchomierzy.
Parametry: S, N (liczba otaku), M, X.
Uproszczenie: Przedstawiciele organizatorów nie mdleją, liczba cuchów wydzielanych przez otaku jest stała.
Powrót to opisu zasad ogólnych
Wojna
W odległej przyszłości wybucha wojna federacji terrańskiej z puchatymi misiami, których słitaśny wygląd kompletnie nie pasuje do ich mrocznej i sadystycznej natury. Wojna ma charakter podjazdowy, federacja wysyła pojedyncze okręty do walki, po których wracają zniszczone w różnym stopniu.
N okrętów co pewien czas kończy walkę i wraca do bazy, gdzie ubiega się o jeden z K doków. Dodatkowo, dowództwo okrętów ubiega się o mechaników. Liczba mechaników wymaganych do naprawy jest zależna od zniszczeń. Łącznie jest M mechaników, i są oni nierozróżnialni.
Wersja uproszczona: : Brak mechaników.
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