Optymalizacja dyskretna

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:

Każdą metodą rozwiążemy pewien trudny problem.

Wymagania

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 sieć 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:

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}, m_{2}, ... , m_{n}\) i \(n\) kobiet: \(K = k_{1}, k_{2}, ..., 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 \\ m_{2}: 3,2,1,4\\ m_{3}:1,2,3,4\\ m_{4}:2,4,3,1\)         \(k_{1}:4,2,1,3\\ k_{2}:4,2,1,3\\ k_{3}:3,1,2,4\\ k_{4}:1,3,2,4\)

 

Śmiało piszcie z wszelkimi pytaniami, skargami, wnioskami, zażaleniami.