Punktacja zadań domowych

Nazwisko	Imię	Zadanie 1	Zadanie 2	Zadanie 3	suma
Bareja	Mirosław	40	40	25	105
Chrzanowska	Elżbieta	7,5	5		12,5
Dudek	Anna	22	25	10	57
Garcarz	Tadeusz	15	16		31
Kosmowska	Anna	0	0	10	10
Kuśmierczyk	Maria	30	40	10	80
Marzycka	Elżbieta	17	7		24
Masikowska	Justyna	30	15		45
Siwkowska	Ewa	10	8	2	20
Skura	Ewa	10	6	15	31
Suchocka	Wiesława	25	8	15	48
Taut	Paweł	30	8	2	40
Wielec	Grażyna	10	14	8	32
Wolska	Elżbieta	10		10	20
Żelazek	Renata	28,5	30	5?	63,5

Wszyscy zaliczyli zadania domowe; osoby, które otrzymały mniej niż 20p są dopuszczone warunkowo do egzaminu. Punkty z zadań domowych i egzaminu będą się sumować. Do zdobycia na egzaminie jest 120 punktów. Nikt nie jest zwolniony z egzaminu.

Puktacja dla zadania "Biuro matrymonialne":

• d kolorów, algorytm O(d*n*log(d)) [cykle Eulera]: 40p (nikt nie podal takiego rozwiazania)
• d kolorów, algorytm O(n^2 d) [przez ścieżki naprzemienne]: 35p (nikt nie podal takiego rozwiazania)
• d kolorów, algorytm O(n^2 d^2) [przez znajdowanie skojarzeń]: 30p (nikt nie podal takiego rozwiazania)
• d kolorów, algorytm O(n^3 d) [przez znajdowanie skojarzeń]: 25p (rozwiązanie p. Barei)
• (2d-1) kolorów, algorytm O(d^2 n) [alg. zachłanny]: 15p (nikt nie podal takiego rozwiazania)
• (2d-1) kolorów, algorytm O(d^3 n), O(n^2 d) i gorsze [alg. zachłanny]: 10p (kilka rozwiązań)

Puktacja dla zadania "Wagony":

• Algorytm O(n^3) -- programowanie dynamiczne: 30+10p
• Algorytm O(n^4) -- programowanie dynamiczne, obliczanie kosztu łączenia dwóch składów w czasie O(n): 23+7p
• Algorytm O(n!), zlozonosc pamieciowa O(n) -- backtracking: 15+5p
• Algorytm O((n+1)!)-- backtracking: 12+4p
• Algorytm O((n-1)!), zlozonosc pamieciowa O((n-1)!) -- backtracking, konstruowanie drzewa możliwości: 11+4p
• heurystyki (algorytmy, ktore czasem cos poprawiaja, ale nie zawsze), np. alg. zachłanne: 6+2p
• naiwne laczenie wagonow po kolei: 2p