Prowadzący
Bartłomiej Surma
bartlomiej.surma(at)grinvest.pl
Opis
WWW jest pełne ciekawych warsztatów, ale nie możesz pójść na wszystkie, więc jak wybrać? Jeżeli tylko do każdych warsztatów przyporządkujesz stopień w jakim Cię interesują, z każdego bloku wybierasz te, o najwyższym stopniu. A co jeśli warsztaty nachodziłyby się częściowo? Albo jedne trwały dłużej drugie krócej, a trzecie wymagane były jako wstęp do czwartych? Wtedy problem robi się trudny. NP trudny. Wiele takich problemów wymaga rozwiązywania i nawet jeśli przez wzgląd na ich złożoność nie jesteśmy w stanie znaleźć najlepszego rozwiązania, możemy szukać najbardziej optymalnego. To właśnie metody wyszukiwania takich rozwiązań będą tematem warsztatów z optymalizacji dyskretnej.
Program zajęć
Trzy podstawowe metody optymalizacji:
- Constraint programming
- Linear / Integer Programming
- Local Search
Każdą metodą rozwiążemy pewien trudny problem.
Wymagania
- Choćby średnia znajomość dowolnego języka programowania.
- Własny komputer
Zadania kwalifikacyjne
1. W Sealandii jest sieć stoków narciarskich wśród której rozrzucone są knajpki. Każde dwa bary łączy albo stok, albo wyciąg. Udowodnij, że istnieje miejsce (bar), z którego da się dostać do każdego innego (baru) (używając zarówno stoków jak i wyciągów).
2. Na tej stronie dostępna jest siec dróg w Nowym Yorku (interesuje nas graf odległości). Plik sformatowany jest w następujący sposób:
c kazda linijka rozpoczynajaca sie od c jest komentarzem
p sp 4 7
c (p)roblem (s)hortest (p)ath, zawiera 4 miasta i 7 dróg (jednokierunkowych)
c
a 1 4 47
c droga z miasta 1 do miasta 4 o koszcie 47
Proszę powiedzieć, jaki będzie najmniejszy koszt dotarcia:
- z miasta 1 do miasta 47474,
- z miasta 5 do miasta 11,
- z miasta 2014 do miasta 606.
Proszę także powiedzieć, w jaki sposób rozwiązaliście problem (i jak długo trwało znajdowanie odpowiedzi).
3. Mamy $n$ mężczyzn: $M = {m_1, \dots , m_n}$ i $n$ kobiet: $K = {k_1, \dots , k_n}$. Każdy człowiek (mężczyzna lub kobieta) ma zdefiniowaną kolejność w której preferuje osoby płci przeciwnej. Małżeństwo $(m,k)$ jest stabilne wtedy i tylko wtedy, gdy dla każdego mężczyzny $a$, którego kobieta $k$ preferuje bardziej od swojego męża $m$, temu ($a$) bardziej podoba się jego żona niż kobieta $k$.
Dla następujących danych, połącz węzłem małżeńskim wszystkie osoby (w konfiguracji mężczyzna-kobieta) tak, aby każde małżeństwo było stabilne.
$$m_1: 3, 4, 2, 1 \qquad k_1: 4, 2, 1, 3 \\ m_2: 3, 2, 1, 4 \qquad k_2: 4, 2, 1, 3 \\ m_3: 1, 2, 3, 4 \qquad k_3: 3, 1, 2, 4\\ m_4: 2, 4, 3, 1 \qquad k_4: 1, 3, 2, 4$$
Śmiało piszcie z wszelkimi pytaniami, skargami, wnioskami, zażaleniami.