Projekt z przedmiotu Teoria Obliczeń i Złożoności Obliczeniowej
Sprawy organizacyjne
Prowadzący przedmiot:
- dr Piotr Faliszewski
- dr Marcin Kurdziel
- dr Marek Gajecki
Terminy oddania projektu:
- Pierwszy termin: 7 lipca 2013
14 czerwca
2013, godz
23.59.
- Drugi termin: 15 wrzesnia 2013, godz 23.58.
Zaliczenie projektu w terminie późniejszym niż pierwszy
skutkuje ocena końcową z przedmiotu nie wyższą niż 3.0.
Do wykonania w ramach projektu:
- Należy napisać program, który rozwiązuje zadanie opisane
poniżej oraz wysłać go do systemu arbitrażowego dla zadania.
- Należy także dostarczyć dokumentacje programu. Dokumentacja
nie może przekraczać 8 stron tekstu czcionką 11pt, przy
rozsądnych marginesach. Dokumentacja powinna zawierać wyłącznie
informacje na temat użytych algorytmów i pomysłów rozwiązania
zadania, a nie szczegółów technicznych implementacji.
Dokumentacja istotnie krótsza wcale nie musi być wadą projektu.
Języki programowania: Jedyne dwa dopuszczalne języki programowania
to C oraz C++.
Współbieżność: Programy nie mogą być wielowątkowe, wieloprocesorowe,
itp.
Oceny:
- Na Państwa ocenę największy wpływ ma jakość działania
zgłoszonego programu, a w drugim rzędzie jakość dokumentacji.
- Aby uzyskać zaliczenie, Państwa program musi być w stanie
rozwiązywać zestaw podstawowych testów, który udostępnimy
Państwu przez system arbitrażowy.
- Aby uzyskać wyższą ocenę, program musi być w stanie rozwiązywać
odpowiednio trudniejsze testy. Oceny powstaną na podstawie
porównania jakości programów.
- Bardzo dobra dokumentacja może podnieść ocenę projektu (o pół
stopnia), a bardzo słaba (w tym jej brak) może ocenę obniżyć
(także o pół stopnia).
- Kod źródłowy państwa programów nie jest oceniany, ale
może być przeglądany, więc proszę stosować komentarze i wcięcia.
- W przypadku wykrycia plagiatu, obie zaangażowane osoby otrzymują
ocenę 2.0 z wszystkich trzech terminów.
- Państwa programy powinny się skupić na rozwiązywaniu zadania w
pamięci, bez odwoływania się do dodatkowych zasobów. W szczególności
niedopuszczalne są odwołania do systemu plików oraz do sieci. Złamanie
tych zasad, w szczególności odwołania do sieci oraz próby hackowania
systemu arbitrażowego, mogą być traktowane jako równoważne plagiatowi.
Wymagania na ocenę 3.5
Plansze na oceny 3.5 będą ograniczone do rozmiarów 5x5 (tj.,
dopuszczalne są, na przykład, plansze o rozmiarach 3x5, 5x5,
5x1, ale---na 3.5---nie będzie plansz o rozmiarach 6x6,
2x6 itp.).
Poniżej znajduje się plik z kilkoma przykładowymi planszami podobnymi
do tych, które będą wymagane na ocenę 3.5 oraz z programem sedziego
(wersja alfa! na razie do uzytku na wlasne ryzyko!).
System arbitrażowy
System arbitrażowy dostępny jest pod następującymi adresami:
Treść zadania
W pewniej bardzo skomplikowanej i niewiarygodnie wręcz tajnej operacji
szpiegowskiej bierze udział k agentów. Operacja odbywa się w
pewnym mieście X, które zostało przedstawione jako prostokąt zbudowany
z x na y kwadratów (y wierszy po
x kwadratów) gdzie w środku każdego kwadratu znajduje się
skrzyżowanie ulic biegnących w kierunkach północ-południe i
wschód-zachód. Naszych k agentów znajduje się na k
różnych skrzyżowaniach i ma k różnych skrzyżowań, do których
chce się dostać. Aby jednak zminimalizować ryzyko wpadki, każdy agent
powinien przejść do swojego docelowego skrzyżowania tak, by na pewno
nie spotkać żadnego innego agenta (oczywiście agenc mogą się jedynie
poruszać ulicami). Ponieważ nie wiadomo z jakimi prędkościami agenci
będą się przemieszczać, ich trasy nie mogą się przecinać w żadnym
punkcie.
Zadanie polega na napisaniu programu rozwiązującego problem
wyznaczania tras. Program powinien wczytać ze standardowego wejścia
opis zadania (rozmiar planszy, ilość agentów oraz pozycje ich obecnych
i docelowych skrzyżowań), znaleźć dopuszczalne rozwiązanie i wypisać
je na standardowe wyjście.
Opis wejścia i wyjścia
Dane zawsze są w poprawnym formacie i zawsze istnieje przynajmniej
jedno poprawne rozwiązanie.
Wejście ma następujący format. W pierwszym wierszu znajdują się dwie
liczby, x oraz y, oznaczające rozmiar miasta. Miasto
podzielone jest na xy kwadratów (y wierszy po
x kwadratów każdy). Można założyć, że:
W drugim wierszu znajduje się pojedyncza liczba k zawierająca
ilość agentów w mieście. Mamy:
Następne k wierszy zawiera pozycje agentów i ich docelowych
skrzyżowań w następującym formacie:
gdzie (xi,yi) to współrzędne skrzyżowania
startowego i'go agenta,
a (x'i,y'i) to współrzędne jego
skrzyżowania docelowego. (Skrzyżowanie w północnozachodnim rogu miasta
ma współrzędne (1,1) a to w południowowschodnim (x,y)).
Opis rozwiązania (wyjście) ma następujący format. Pierwszy wiersz
zawiera pojedynczą liczbę, s. Kolejne s wierszy jest
postaci:
gdzie (xj,yj) oznacza współrzędne skrzyżowania
w mieście, a (dxj,dyj) oznacza kierunek, w którym
powinien pójść agent, który znajdzie się na tym skrzyżowaniu. Dopuszczalne
kierunki to północ, południe, wschód i zachód, opisane jako, odpowiednio,
(0,-1), (0,1), (1,0), (-1,0).
Przykładowe wejście i wyjścia
Poniżej znajduje się przykładowe wejście i przykładowe wyjścia.
Wejście:
5 4
2
3 1 5 2
4 1 2 3
Planszę te można graficznie przedstawić jako:
Przykładowe poprawne rozwiązanie:
15
3 1 -1 0
2 1 -1 0
1 1 0 1
1 2 0 1
1 3 0 1
1 4 1 0
2 4 1 0
3 4 1 0
4 4 1 0
5 4 0 -1
5 3 0 -1
4 1 0 1
4 2 0 1
4 3 -1 0
3 3 -1 0
Rozwiązanie można przedstawić graficznie jako:
Przykładowe błędne rozwiązanie (nie wszyscy
agenci mają trasę):
11
3 1 -1 0
2 1 -1 0
1 1 0 1
1 2 0 1
1 3 0 1
1 4 1 0
2 4 1 0
3 4 1 0
4 4 1 0
5 4 0 -1
5 3 0 -1
Rozwiązanie można przedstawić graficznie jako:
Przykładowe błędne rozwiązanie (trasy się przecinają):
7
3 1 0 1
3 2 1 0
4 2 1 0
4 1 0 1
4 2 0 1
4 3 -1 0
3 3 -1 0
Rozwiązanie można przedstawić graficznie jako:
Przykładowe błędne rozwiązanie (zmiana pozycji agenta):
4
3 1 0 1
3 2 1 0
4 2 1 0
4 1 1 0
Rozwiązanie można przedstawić graficznie jako:
Kraków, Marzec 2013