Tematy projektów 2017
- 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
- Portal randkowy
- Egzorcyści
- Akcja afirmatywna
- Płatny mordercy
- Bezrobotni debile
- Bokserzy emeryci
- Modele XXL
- Ruch oporu
Powrót to opisu zasad ogólnych
Portal randkowy
W pewnym mieście akademickim młodzi absolwenci politechniki postanowili stworzyć portal randkowy. Program składa się z brokerów - osobnych procesów, do których zgłaszają się co pewien losowy czas kandydaci na randkę - mężczyźni lub kobiety (w zależności od funkcji rand) o określonej atrakcyjności. Zawsze zgłasza się identyczna liczba K kandydatów, większa od 1. Do czasu zorganizowania wszystkich randek broker nie przyjmuje kolejnych kandydatów.
Organizacja randki: aby doszło do randki, kandydat musi zgodzić się na randkę z pewnym innym kandydatem innego brokera przeciwnej płci. Zgoda zależy od atrakcyjności kandydata: w przypadku atrakcyjności większej równej, zgoda jest zawsze. W przypadku takiej samej, jest 50% szans na zgodę. Kandydat może jednocześnie negocjować warunki randki z kilkoma innym kandydatami, zawsze wybiera najbardziej atrakcyjnego/atrakcyjną.
Wersja uproszczona: : Zawsze jest jeden kandydat, brak atrakcyjności.
Powrót to opisu zasad ogólnych
Egzorcysci
Grupka egzorcystów, sfrustrowana brakiem duchów, postanawia nieco sobie dopomóc w interesie i przy pomocy urządzeń z magazynu (do wytwarzania sztucznej mgły, magnetofonów marki Kasprzak oraz zużytych prześcieradeł z domu opieki społecznej) pokryjomu urządza "nawiedzenia" wybranych domów. Z uwagi na ograniczoną liczbę rekwizytów oraz z uwagi na fakt, że równocześnie nie powinni egzorcyści nawiedzać tych samych domów, konieczne okazało się zaimplementowanie mobilnej aplikacji szeregującej nawiedzanie duchów.
Dane jest K magnetofonów Kasprzak, M urządzeń do wytwarzania sztucznej mgły oraz Pzużytych prześcieradeł. Wreszcie, istnieje D domów, przy czym zachodzi M < K < P < D. Aby nawiedzić dom, egzorcysta musi najpierw zorganizować wszystkie rekwizyty, a dopiero następnie może zarezerwować dom. Dom raz nawiedzony musi chwilę odczekać, zanim będzie go można nawiedzać ponownie.
Wersja uproszczona: : Tylko jeden typ rekwizytów, domy można nawiedzać natychmiastowo, można równocześnie rezerwować domy i rekwizyty
Powrót to opisu zasad ogólnych
Akcja afirmatywna
W pewnym kraju, z uwagi na zaszłości historyczne osoby pewnej grupy rasowej od wielu lat osiągają gorsze wyniki w edukacji. W związku z tym wprowadzono akcję afirmatywną: rząd karze uniwersytety, które mają niewystarczająco wielu studentów należącej do tej grupy rasowej. Powoduje to ciągłą walkę o takich studentów między uniwersytetami, by uzyskać co najmniej A studentów.
Dane są trzy typy procesów: audytor, agenci oraz uniwersytety. Agenci reprezentują grupę studentów (losowo co pewien czas zgłasza się do nich od 1 do S studentów. Uniwerystety ubiegają się o studentów, jednakże nie negocjują z agentami, tylko ustalają między sobą, który uniwersytet weźmie ilu studentów, w ten sposób, by uniwersytety ostatnio karane otrzymywały priorytet. Nowi studenci zgłaszają się do agentów co pewien czas; dopiero, kiedy wszyscy agenci otrzymają zgłoszenia, dopiero wtedy uniwersytety mogą zacząć się ubiegać. Dopiero, kiedy uniwersytety skończą się ubiegać i rozdzielą między siebie studentów, mogą pojawiać się nowi studenci u agentów. Łączna liczba studentów nigdy nie wystarcza dla wszystkich uniwersytetów.
Kiedy uniwersytety skończą się ubiegać, audytor wybiera kilka uniwersytetów i sprawdza, czy mają wystarczająco wielu studentów (>A). Jeżeli uniwersytet nie ma wystarczająco wielu studentów poszkodowanej grupy rasowej, otrzymuje karę finansową. Dopiero po zakończeniu audytu uniwersytety mogą zacząć się ubiegać o nowych studentów.
.Wersja uproszczona: : Istnieje jeden agent, który rozgłasza co pewien czas ilu jest studentów, nie ma audytora, brak priorytetów.
Powrót to opisu zasad ogólnych
Płatni zabójcy
W pewnym dużym mieście w odległej przyszłości istnieje N firm oferujących usługi upraszczające relacje w pracy i rodzinie. Każda firma ma osobną reputację. Procesy reprezentują stałych klientów tych firm, którzy co pewien czas ubiegają się o dostęp do jednej z nich. Każda firma ma od 1 do Z zabójców na stanie. Procesy ubiegają się zawsze o jednego zabójcę, usiłując zawsze wybrać najlepszą firmę, a jeżeli ta ma akurat wszystkich zabójców zajętych, wybrać kolejną z nich - uwaga, procesy nie odpytują firm, raczej cały czas próbują się skolejkować u jednej z nich, a wybierają po prostu najlepszą aktualnie dostępną ofertę. Jeżeli proces widzi, że w jakiejś kolejce o wyższej reputacji jest już blisko, powinien zrezygnować z dostępnego miejsca w kolejce o niższej reputacji.
Po skorzystaniu z usług firmy procesy (losowo) wyrażają opinię o firmie. Wpływa to na zmianę jej reputacji.
Wersja uproszczona: : Brak reputacji, każda firma ma jednego zabójcę.
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
Bokserzy emeryci
W pewnym środkowoeuropejskim kraju, urzędnicy ZUSu wpadli na pomysł, jak umilić czas staruszkom na emeryturze. Otóż emeryci zwykle nie mają nic do roboty, więc zamiast tego mogą wkraczać na ring i stawać tam do walki. Dochody z transmisji telewizyjnych walk dodatkowo zasilą fundusz emerytalny, pozwalając zasypać dziurę budżetową. Wbrew insynuacjom, pomysł urzędników nie ma na celu ograniczenia czasu wypłacania emerytur, wprost przeciwnie, dzięki zaangażowaniu emerytów w aktywność sportową urzędnicy liczą na przedłużanie życia staruszkom.
Procesy reprezentują urzędników mających pod pieczą grupę rozróżnialnych staruszków, początkowo o liczności S. Każdy staruszek ma zmienną Z reprezentującą jego zdrowie. Urzędnik organizuje mecz z innym urzędnikiem, starając się równocześnie zaangażować jak najwięcej swoich staruszków. Mecz wymaga zajęcia zasobów nierozróżnialnych sędziów, których jest N oraz jednego z rózróżnialnych R ringów. Zakończenie meczu wymaga zajęcia jednego z nierozróżnialnych L lekarzy. Po zakończeniu meczu każdemu staruszkowi spada poziom zdrowia (przegranym więcej). Staruszek, którego poziom zdrowia spadnie do zera, wypada z rejestrów ZUSu. Co pewien losowy czas do urzędnika zgłaszają się nowi staruszkowie - tak więc urzędnik może mieć zarówno zero, jak i więcej niż S staruszków.
Wersja uproszczona: : Każdy urzędnik reprezentuje jednego staruszka, staruszkowie nie umierają i nie przychodzą nowi, brak lekarzy
Powrót to opisu zasad ogólnych
Modele XXL
Czas skończyć ze stereotypem, że mężczyzna, by był piękny, musiał być wysportowany, wysoki i szczupły. Mężczyźni nie są obiektami seksualnymi! Ruch feministyczny postanowił więc urządzić konkursy rozlazłych, tłustych, niskich kurdupli, by w ten sposób promować postawę, że o wartości mężczyzny decyduje jego wnętrze, a nie sześciopak na brzuchu.
Proces-agent reprezentuje jednego modela. Co pewien czas procesy chcą zorganizować konkurs. Nie wszystkie procesy mogą chcieć uczestniczyć, niektóre mogą właśnie uczestniczyć w innym konkursie. Do zorganizowania konkursu wymagane jest zarezerwowanie jednej z sal w mieście; istnieje niewiele M miast, w każdym z nich jest kilka S sal. W każdym mieście jest też jeden hotel o X miejscach. Każdy proces uczestniczący w konkursie w danym mieście musi następnie samodzielnie zarezerwować miejsce w odpowiednim hotelu. Po zakończeniu konkursu, sala zwalniana jest natychmiast, a hotel dopiero po pewnym czasie.
Wersja uproszczona: :brak hoteli, istnieją tylko sale.
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.