Tematy projektów 2015
- Zasady ogólne
- Zasady dotyczące kodu
- Zasady dotyczące sprawozdania
- 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 z opóźnieniem większym niż tydzien, o jeden stopien dla projektów z opóźnieniem większym niż trzy tygodnie, o półtorej stopnia dla projektów opóźnionych więcej niż pięć tygodni. Projekty oddawane w drugiej połowie września będą mogły być zaliczone tylko na trzy.
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.
Tematy projektów
- Szaleni bibliotekarze
- Cyloni
- Otaku
- Straszni Sadyści
- Menelatorium
- Podejście Abelarda Gizy
- Zajączki
- Orgie w domu starców
Powrót to opisu zasad ogólnych
Szaleni bibliotekarze
Bibliotekarze mają dosyć czytelników oddających książki z opóźnieniem. Postanowili więc zakupić Mechanicznych Ponaglaczy Czytelników (MPC), wyposażonych w perswazatory i naganatacze. Niestety, bibliotekarzy jest wielu (B - parametr), MPC są bardzo drogie, więc można było ich kupić tylko M (parametr - B > M ).
Co pewien czas bibliotekarz autonomicznie decydują, że pewna liczba czytelników wymaga przypomnienia o terminie oddania książki. W tym celu bibliotekarz ubiega się o dostęp do MPC, przy czym pierwszeństwo mają zgłoszenia wypożyczenia MPC do przynaglenia mniejszej liczby czytelników.
MPC co pewien czas wymagają serwisu. Kiedy MPC obsłuży K czytelników, powinien zostać oddany do serwisu. Serwisanci, o liczbie S (parametr, S << M ), podejmują się naprawy MPC, po czym MPC wraca do służby. Serwisanci są zasobem, nie aktywnymi procesami, bibliotekarze muszą więc konkurować o dostęp do serwisantów.
Wersja uproszczona: : MPC się nie psują (brak serwisantów).
Powrót to opisu zasad ogólnych
Cyloni
Środowisko naukowe stworzyło cylonów, by ci wyręczali naukowców w prostych czynnościach, takich jak uczęszczanie w naradach produkcyjnych. Istnieje M modeli cylonów (parametr). Istnieje I instytutów, które urządzają narady (parametr, I < M ). Równocześnie w jednej naradzie nie może uczestniczyć dwóch cylonów tego samego modelu (bo wówczas kierownicy by się zorientowali, że coś jest nie tak). Jednakże w tym samym czasie cyloni mogą uczestniczyć w wielu różnych naradach.
Należy napisać kod naukowca. Naukowiec spontanicznie dowiaduje się o uczestnictwie w naradzie o numerze X w jakimś instytucie; natychmiast porozumiewa się z innymi naukowcami, by dowiedzieć się, kto będzie uczestniczył w tej naradzie, i ustala, jaki model cylona jest mu potrzebny. Narada rozpoczyna się, gdy wszyscy naukowcy mający w niej uczestniczyć, deklarują gotowość uczestniczenia w naradzie. Po zakończeniu narady, naukowcy zwalniają cylonów do domu.
Należy zwrócić uwagę, że numery narad X mogą tylko rosnąć, ale należy jakoś zaimplementować w jaki sposób rosną tak, by mniej więcej wszyscy naukowcy wiedzieli, jaki jest aktualnie numer narady i do jakiego numeru mogą zostać obecnie wezwani; a także, by wiedzieli, że jakiś naukowiec na pewno już nie weźmie udziału w naradzie z numerem X.
Uproszczenie: Narady nie mają numerów, można założyć, że trwają bezustannie.
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
Straszni Sadyści
Grupa sadystycznych wielbicieli Disco Polo regularnie organizuje flash moby. Aby uniknąć wykrycia przez policję, czołowi sadyści - "liderzy" - komunikują się przez komórki. Liderzy deklarują, ile w tej chwili mogą zwołać sadystów szeregowych. Następnie umawiają się o organizacji zebrania. Zebranie sadystów musi liczyć co najmniej Z członków.
Każdy z N liderów może skupić od 1 do L sadystów (L jest stałe dla danego lidera, a nie takie samo dla wszystkich). Zebranie sadystów wymaga jeszcze dostępu do sprzętu nagłaśniającego. Istnieje M jednostek sprzętu nagłaśniającego i D dysków CD z muzyką disco polo, którą sadyści będą katować przechodniów w miejscu zebrania. Jednostki te i dyski znajdują się w prywatnych domach liderów.
Zebranie odbywa się w jednym z K miejsc. Liderzy spontanicznie decydują się na udział w zebraniu w jednym z miejsc, następnie decydują o dostępie do dysków CD oraz sprzętu nagłaśniającego. Następnie katują przechodniów, rozbiegają się zanim przybędzie policja i odnoszą sprzęt nagłaśniający oraz dyski CD do domu.
K < D < M, N > K, N > M, N > D.
Uproszczenie: Liczebność grupy danego lidera jest stała. Nie ma sprzętu nagłaśniającego i dysków CD.
Powrót to opisu zasad ogólnych
Menelatorium
W wyniku przemian społecznych zanikają stare zwyczaje, a nawet całe subkultury. Władze Poznania, w trosce o zachowanie zagrożonych kultur, zdecydowały się urządzić muzeum menela. W muzeum, w specjalnej sali o pojemności S, w charakterze eksponatów zjawiają się menele. Aby ekspozycja mogła się rozpocząć i by można było wpuszczać turystów, w sali musi być jednocześnie S meneli.
Podczas ekspozycji turyści mogą podziwiać tradycyjne sposoby spędzania czasu przez meneli: grzebanie w śmietniku, obalanie flaszek, znaczenie terytorium i lektura dzieł wszystkich Tołstoja. Po ekspozycji obsługa musi wyciągnąć z sali zaprawionych meneli, umyć podłogi oraz ściany, oraz uzupełnić zawartość śmietnika.
Nie każdy menel ulegnie zaprawieniu podczas ekspozycji - jest to losowe. Obsługa medyczna, P pielęgniarzy, po zakończeniu ekspozycji wynosi meneli. Potrzeba K (1 do 4) pielęgniarzy do każdego menela, w zależności od jego wagi. Waga meneli jest stała. Dopóki pielęgniarze nie wyniosą meneli, nie można rozpocząć sprzątania sali.
Menele ustalają samodzielnie we własnym gronie, kto z nich ma się zjawić w sali i sami zawiadamiają obsługę muzeum, że ekspozycja może się rozpocząć. Obsługa muzeum może być osobnym procesem, ale jego rola może się sprowadzać tylko do zatwierdzania decyzji (zacznij ekspozycję, zacznij sprzątanie) podjętych przez pielęgniarzy lub meneli - to znaczy, obsługa nie może, na przykład, powiadamiać pielęgniarzy, że należy wynosic meneli.
Parametry: M - liczba meneli (każdy o stałej wadze 1 do 4), P - liczba pielęgniarzy, S - liczba stanowisk dla meneli. 4*P < S. M > S.
Uproszczenie: Menele nie ulegają zaprawieniu (brak pielęgniarzy).
Powrót to opisu zasad ogólnych
Podejście Abelarda Gizy
Zainspirowani sławetnym skeczem Abelarda Gizy, społeczeństwo Bździszewa zadecydowało, że sołtys powinien być dostępny dla swoich wyborców. Każdy wyborca ma prawo przyjść do sołtysa i wyrazić mu uznanie za pomocą dowolnego przedmiotu. Niestety, okazało się, że zbytnia dowolność w doborze przedmiotów skutkuje zbyt szybkim zużyciem sołtysa. Ponieważ zbyt częsta organizacja wyborów zbytnio obciąża budżet gminy, przyjęto ostatecznie, że wyborcy mogą wyrażać wdzięczność sołtysowi tylko przy pomocy jednego z B gumowych bejzbolów.
Każdy z W wyborców musi ubiegać się o dostęp do jednego z bejzbolów, a następnie umówić się na wizytę do sołtysa. Sołtys ma wyznaczone godziny dyżurów - każdy wyborca musi otrzymać wizytę o konkretnej godzinie, następnie wyraża wdzięczność przy pomocy bejzbola. Po zakończeniu wizyty, bejzbol może ulec zniszczeniu; tak czy inaczej, wyborca nie oddaje bejzbola natychmiast po wizycie, ale dopiero, gdy się pochwali nim całej rodzinie (losowy czas, znany jednakże już podczas ubiegania się o bejzbola).
Po zniszczeniu wszystkich bejzboli powiadamiany jest technik gminny, który zamawia ich nową partię. Uwaga: godziny dyżurów są uszeregowane! Sołtys nie może być osobnym procesem! Nie ma procesu technika! Istnieje możliwość, że w jakiejś godzinie dyżurów nikogo nie będzie. Zakładamy, że ubieganie trwa bardzo krótko przed rozpoczęciem dnia roboczego. Ubieganie o wizyty na nowy dzień może się rozpocząć dopiero po zakończeniu wszystkich wizyt poprzedniego dnia - trzeba to rozstrzygnąć w sposób rozproszony, bez centralnego serwera.
Parametry: W (liczba wyborców), B (liczba bejzboli).
Uproszczenie: sołtys może być osobnym procesem, bejzbole nie ulegają zniszczeniu.
Powrót to opisu zasad ogólnych
Zajączki
W pewnym lesie żyje sobie spokojnie Z zajączków i N niedźwiedzi. Co pewien czas zajączki urządzają imprezy. W tym celu uzgadniają między sobą, na której z P polan odbędzie się impreza. Na polanie zmieści się S zajączków, przy czym jednego niedźwiedzia można traktować jako zajmującego tyle miejsca, co 4 zajączki.
Każdy zajączek przynosi na imprezę alkohol. Jeżeli na imprezie pojawi się niedźwiedź, zajączki muszą zezwolić mu na picie na sępa, co oznacza, że muszą przynieść dodatkowy alkohol także dla misiów. Ponadto, zbyt naprany niedźwiedź ma skłonność do pożerania zajączków. W związku z tym, jeżeli na imprezie pojawia się niedźwiedź, zajączki muszą przed rozpoczęciem imprezy ustalić, że tylko część z nich przyniesie alkohol; można przyjąć, że jeden niedźwiedź obali 4 flaszki zanim zacznie pożerać zajączki. Impreza z samymi niedźwiedziami nie może się odbyć, bo nie ma kto przynieść alkoholu.
Uproszczenie: Niedźwiedzie nie piją na sępa, same przynoszą alkohol, nie pożerają zajączków.
Powrót to opisu zasad ogólnych
Orgie w domu starców
W Danii naukowcy przekonali rząd, że kondycję pensjonariuszy w domach starców mogą poprawić orgie. Zdecydowano się na przeprowadzenie eksperymentu w jednym z domów starców. Animatorzy orgii konkurują w dostępie do jednej z S sal, M staruszków i K staruszek. Sale są unikalne, staruszcy i staruszki nie. Każda sala ma różną pojemność, i animator orgii powinien się starać zapełnić całą salę przed rozpoczęciem sali. Konieczne przy tym jest, by orgie nie były jednopłciowe.
Po zakończeniu orgii animator konkuruje o dostęp do sali medycznej, gdzie doktor i lekarz badają, czy kondycja staruszków i staruszek poprawiła się po odbyciu orgii. Staruszkowie i staruszki nie wracają natychmiast do puli dostępnych zasobów, ale dopiero po pewnym czasie, określonym przez doktorów (w implementacji: określane po prostu losowo przez animatora).
Uproszczenie: Sale mają identyczną pojemność i nie są unikalne. Staruszkowie nie wymagają opieki medycznej.