Tematy projektów 2018
- 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. Nie przyjmuję projektów oddawanych później, niż po 15 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.
Tematy projektów
- Safari w trójkącie menela
- Gildia złodziei
- Otaku
- Bezrobotni debile
- Ruch oporu
- Konkurs piękności
- Zawody w piciu na umór
- Uczciwi politycy
- Tunele podprzestrzenne
- Stetryczali amatorzy klubów go-go
Powrót to opisu zasad ogólnych
Safari w trójkącie menela
Poszukujący mocnych wrażeń turyści pokochali nowy sposób spędzania wolnego czasu: safari w Poznaniu, nocą na Dębcu. Po założeniu koszulek "kochamy Legia Warszawa" turyści, pod opieką przewodnika, ruszają na Dębiec.
- Turyści najpierw rezerwują przewodnika. Jest P przewodników, każdy opiekuje się grupą turystów o rozmiarze G.
- Wycieczka rusza, gdy grupa osiąga rozmiar G.
- W czasie wycieczki turysta może zostać pobity. W takim wypadku trafia do szpitala i przez pewien czas nie bierze udziału w wycieczce.
- Przewodnik również może zostać pobity. Na pewien czas przestaje wtedy organizować wycieczki.
Zaimplementować procesy T turystów. T >> P, T*G > P
Wersja uproszczona: : brak punktu 4, można zaimplementować proces przewodnika
Powrót to opisu zasad ogólnych
Gildia złodziei
Po przybyciu do Ankh-Morpork mistrza Wu-Li, sławnego nauczyciela sztuk walki, większość mieszkańców opanowała sztukę samoobrony do tego stopnia, że złodzieje stracili szansę na godziwe zarobki. W celu zapobieżenia rozruchom oraz w ramach społecznego solidaryzmu, Patrycjusz zadecydował, że przyzna złodziejom prawo do obrabowywania domów arystokracji.
Ustalono następujące reguły:
- Złodzieje przed obrabowaniem muszą połączyć się w pary - nie mogą rabować na własną rękę
- Jednocześnie tylko jedna para złodziei może rabować jeden dom
- Przed rabunkiem, złodzieje muszą to zgłosić się w straży dziennej i tam wypełnić stosy papierkowej roboty. Trwa to dość długo, ponieważ złodzieje są nie do końca piśmienni. Równocześnie nie więcej niż P złodziei może wypełniać papierki
- Po obrabowaniu domu, dom musi być przez pewien czas omijany przez złodziei
- Jest N psychotechników, każdy z nich losowo otrzymuje zgłoszenia pojawienia się losowej liczby pasażerów (max. M), albo kuriera, albo obcego.
- Podprzestrzeń naraz może pomieścić P osób, P >N, P < M*N
- Kurier i obcy zajmują tyle miejsca, co jedna osoba
- Kurier zanim wyruszy, nie może przed nim być w podprzestrzeni ani jednego pasażera, ani obcego, chociaż mogą być przed nim inni kurierzy. Transport kuriera trwa szybciej niż pasażera. Pasażerowie mogą się pojawić w podprzestrzeni, jeżeli już są tam kurierzy.
- W chwili wyruszenia obcego w podprzestrzeni mogą znajdować się dowolni inni pasażerowie lub kurierzy, ale gdy już w podprzestrzeni znajdzie się obcy, nie może się w podprzestrzeni pojawić żaden inny pasażer lub kurier, chociaż mogą pojawić się obcy. Transport obcego trwa wolniej niż pasażera.
- Nowe zgłoszenie pojawia się u psychotechnika dopiero po obsłużeniu poprzedniego
- Jest N emerytów, K klubów, N >> K
- Koszt wstępu do każdego klubu wynosi M złotych
- Każdy emeryt dostaje od 1 do M-1 złotych
- Każdy klub jest unikalnym, niezastępowalnym przez inne zasobem
Domów jest D, złodziei jest Z, Z nie musi być parzysta. Z > D, Z > P. Relacje między D i P nie są znane z góry.
Zaimplementuj procesy złodziei
Wersja uproszczona: : brak punktów 3 oraz 4
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
Bezrobotni debile
W odległej przyszłości procesy dysgeniczne oraz postępująca automatyzacja doprowadziła do powstania klasy ludzi niezatrudnialnych w normalnych przedsiębiorstwach. Ludzie ci posiadają tak niski iloraz inteligencji, że brak im kompetencji wymaganych do normalnej pracy. Niemniej jednak obowiązujące teorie społeczne wymagają, by ludzie pracowali, ponieważ wpływa to na ich dobre samopoczucie oraz jest zgodne z wymogiem, by ludzie nie dostawali pieniędzy za nic. Rząd wymaga więc, by każda kompania musiała zatrudniać pewną liczbę debili.
Danych jest Nagentów mających po swoją opieką D niezrozróżnialnych, skończonych debili. Agenci ubiegają się o miejsca pracy w K rozróżnialnych kompaniach, każda mogącą przyjąć pewną liczbę debili (w szczególności większą od D). Po rozdysponowaniu wszystkich debili, agencja odczekuje chwilę przed przyjęciem pod opiekę kolejnej ich partii. Dana kompania posiada związaną zmienną T określającą dany poziom zniszczeń wyrządzonych przez zatrudnionych idiotów. Jeżeli wartość tej zmiennej przekroczy pewien poziom, kompania jest na pewien czas zwolniona z zatrudniania kretynów. Określeniem tego również powinni zajmować się agenci.
Wersja uproszczona: : Brak poziomu zniszczeń, liczba debili w kompaniach jest stała i wynosi zawsze D, kompanie są nierozróżnialne.
Powrót to opisu zasad ogólnych
Ruch oporu
W odległej przyszłości w pewnym totalitarnym kraju panuje totalny zamordyzm i kult "Moich małych kucyków". Narasta ruch oporu, sprzeciwiający się różowym kucykom, potajemnie oglądający anime "Berserk" oraz kolportujący książki Marii Konopnickiej.
Procesy reprezentują konspiratorów. Co pewien czas konspiratorzy postanawiają spotkać się z kolegami. Konspiratorzy powinni być ułożeni w pseudo-drzewiastą strukturę, w której każdy posiada kontakty bezpośrednie (sąsiadów), podwładnych (liście) oraz przełożonego. Komunikacja jest tylko w ramach drzewiastej struktury! Niektóre procesy wyżej w hierarchii posiadają funkcję "akceptora". Proces pragnący spotkania najpierw potrzebuje akceptacji "akceptora" - akceptor równocześnie może wyrazić zgodę na równoczesne spotkanie nie więcej niż P procesów (nie P, spotkań, ale procesów!). Funkcja "akceptora" co pewien czas przekazywana jest innemu procesowi: 10% szansy na przekazanie w dół, 10% w górę, 80% komuś na tym samym poziomie drzewa - ale nigdy nikomu z sąsiadów. Do organizacji spotkania wymagane jest następnie zgromadzenie kilku sąsiadów i podwładnych. Dodatkowo, konieczne jest zdobycie jednego z niewielu egzemplarzy albo DVD z "Berserkiem", albo dzieł wybranych Marii Konopnickiej.
Po ustaleniu, kto bierze udział w spotkaniu i zdobycia zgody akceptora, konspiratorzy spotykają się, rytualnie palą małe różowe kucyki, oraz albo oglądają anime, albo czytają na głos "Naszą Szkapę". Następnie rozchodzą się i przez pewien czas nie biorą udziału w zebraniach.
Wersja uproszczona: Akceptorzy zawsze się zgadzają, jest tylko jeden zasób (DVD Berserk), funkcja akceptora jest stała.
Powrót to opisu zasad ogólnych
Konkurs piękności
Pasztetowo zdecydowało się raz na zawsze skończyć z krzywdzącymi stereotypami na temat wyglądu swoich mieszkańców i mieszkanek. W związku z tym sołtys postanowił urządzić konkurs piękności, w którym mogą z mieszkańcami i mieszkankami konkurować także przybysze z zewnątrz.
N menadżerów spontanicznie decyduje, że będzie w tym roku obsługiwać pewną liczbę modelek. Następnie menadżerowie ubiegają się o dostęp do jednego z lekarzy wyznaczonych przez gminę (lekarzy jest L i są rozróżnialni). Badania lekarskie są konieczne od czasu, gdy jacyś dowcipnisie wystawili w konkursie upudrowaną świnię w bikini, która zdobyła tytuł wicemiss Pasztetowa. Po zdobyciu opinii lekarza, menadżerowie rezerwują odpowiednią liczbę miejsc w salonie kosmetycznym (salon ma pojemność S). Następnie zgłaszają gotowość. Gdy wszyscy menadżerowie są gotowi, rozpoczyna się konkurs (poza kontrolą programu).
Wersja uproszczona: : Brak lekarzy, tzn. świnie są dopuszczane do udziału w konkursie.
Powrót to opisu zasad ogólnych
Zawody w piciu na umór
W pewnym akademiku studenci postanowili urządzić zawody w celu pielęgnowania szlachetnego ducha sportu. Po próbach z podnoszeniem ciężarów oraz biegach na 200 metrów, ostatecznie zadecydowano, że najlepiej do wizerunku studentów Politechniki Poznańskiej będą pasować zawody w chlaniu na umór. Pomysł ten tak się spodobał, że zawody zaczęto urządzać codziennie, a wreszcie ustalono, że dowolna grupa studentów może równocześnie z innymi przystąpić do chlania na umór. Samorząd studencki wyznaczył grupę arbitrów o liczności A (parametr). Arbitrzy są nierozróżnialni i należy ich traktować jako jeden zasób o liczności A.
W celu odbycia zawodów studenci (dowolna podgrupa o liczności większej niż 1) najpierw zgłaszają chęć uczestnictwa (brak punktu centralnego). Następnie studenci ubiegają się o dostęp do któregoś z arbitrów. Następnie odbywają się zawody w chlaniu.
Wersja uproszczona: : Procesy symbolizują grupę studentów - w związku z tym pozostaje tylko problem ubiegania się o arbitrów.
Powrót to opisu zasad ogólnych
Uczciwi politycy
W pewnym europejskim kraju średniej wielkości nieoczekiwanie odkryto kilku uczciwych polityków. Zdarzenie to okazało się szokiem dla opinii publicznej i po długiej debacie postanowiono, że tak rzadkimi okazami należy się jakoś podzielić.
Od tej pory politycy są przekazywani od miasta do miasta, od partii do partii. Niestety, powoduje to duże obciążenie dla polityków, którzy często przeżywają załamanie nerwowe w wyniku obcowania z rzeczywistością. Dlatego też co pewien czas muszą być kierowani do sanatorium, gdzie dzięki śpiewaniu piosenek Majki Jeżowskiej i obcowania z filozofią Kubusia Puchatka z wolna przywracana jest im wiara w ludzkość.
Miasta (reprezentowane przez procesy) mają określone, zmienne zapotrzebowanie na uczciwych polityków (zależnie od wielkości miasta i stopnia skorumpowania miejscowych elit). Co pewien czas próbują zgromadzić odpowiednią liczbę polityków. Każdy polityk otrzymuje następnie legitymację jednej z partii politycznych (obojętnie jakich), przy czym wymagane jest, by jedna partia miała nie więcej niż P uczciwych polityków i by partie były w miarę równie obłożone. Po zdobyciu polityków i przypisaniu im przynależności partyjnej, politycy zaczynają kadencję w mieście. W trakcie kadencji politycy wykruszają się (pojedynczo) udając się na urlop do sanatorium. W sanatorium maksymalnie może być S polityków. Miasto nie może zacząć ubiegania się o nowych polityków, dopóki nie wyśle starych do sanatorium
Wersja uproszczona: : Nie ma partii politycznych, politycy wykruszają się wszyscy naraz
Powrót to opisu zasad ogólnych
Tunele podprzestrzenne
W innej galaktyce podróże międzyplanetarne odbywają się poprzez skorzystanie z usług psychokinetyków. Psychokinetyk może przenieść dowolną liczbę osób otwierając tunel w podprzestrzeni. Podprzestrzeń niestety może naraz pomieścić tylko ograniczoną liczbę P osób. Do psychokinetyka zgłaszają się wycieczki, każda o innej liczbie osób, od 0 do M. Dodatkowo, czasami zgłaszają się specjalni kurierzy, oraz obcy. Występują następujące ograniczenia:
Należy zapewnić, by żaden rodzaj (np. kurierów albo obcych) nie zmonopolizował podprzestrzeni, a więc by każde zgłoszenie do psychotechnika zostało ostatecznie obsłużone. Kurierzy zjawiają się rzadziej niż pasażerowie, obcy zjawiają się rzadziej niż kurierzy.
Wersja uproszczona: : Brak obcych i kurierów
Powrót to opisu zasad ogólnych
Stetryczali amatorzy klubów go-go
Pewna organizacja emerytów co pewien czas losuje niewielką kwotę dla swoich członków (zarówno czas jak i kwota są różne dla różnych emerytów). Emeryci za ta kwotę wybierają się do klubów go-go. Istnieje K klubów, wstęp do każdego z nich kosztuje tyle samo, oferują one jednak różne atrakcje. Niestety koszt wstępu jest płatny zawsze od grup, niezależnie od ich wielkości, w klubie równocześnie może być tylko jedna grupa. Koszt jest ten jest większy od największej kwoty dawanej jednemu emerytowi, więc emeryci muszą dobrać się w grupy (jak najmniejsze), by uzbierać sumę potrzebną do zapłacanie za wstęp. Emeryci muszą także zgodzić się, do którego konkretnie klubu go-go się udadzą. Procesy to emeryci. Jeżeli suma uzbierana przez emerytów jest większa od M, emeryci przepijają w kubie nadwyżkę.
Ograniczenia:
Wersja uproszczona: : Brak