Aktualności / News > Dydaktyka / Teaching > Historia / History > Wybrane Zagadnienia Optymalizacji Dyskretnej, lato 08/09
Wybrane Zagadnienia Optymalizacji Dyskretnej, lato 08/09
Wykład prowadzi dr inż. Konstanty Junosza - Szaniawski.
Strona przedmiotu
Wyniki
Harmonogram przedmiotu
10/12.03 - wybór tematów projektów24/26.03 - dokumentacja wstępna
21/23.04 - kontrola postępu prac nad aplikacją
05/07.05 - oddanie aplikacji
12/14.05 - dokumentacja końcowa
19/21.05 - ostatnia możliwość doniesienia czegoś
26.05 - wyniki
Warunki oceniania
Studenci przygotowują projekty w zespołach dwuosobowych.Na projekt składa się:
1. Dokumentacja wstępna (10 punktów)
- opis problemu
- sformalizowanie problemu
- projekt algorytmów (pseudokod)
- analiza algorytmów (złożoność, poprawność)
2. Aplikacja + przykłady do testów (20 punktów)
3. Dokumentacja końcowa (10 punktów)
- zmiany w stosunku do dokumentacji wstępnej
- wyniki testów (w porównaniu z szacunkami)
- instrukcja użytkownika
Uwagi:
- Warunkiem zaliczenia projektu jest uzyskanie ponad 20 punktów.
- Zaliczenie projektu jest obowiązkowe do zaliczenia przedmiotu (ocena z projektu stanowi 0.4 oceny z przedmiotu)
- Harmonogram może ulec niewielkim zmianom.
- Warunkiem koniecznym do uzyskania punktów za dokumentację finalną jest oddanie aplikacji
- W szczególnych usprawiedliwionych przypadkach spóźnienia mogą być rozpatrywane indywidualnie (na korzyść studenta)
- Ostatnim terminem, kiedy można złożyć którąkolwiek część jest 26/28.05. Po tym terminie za każdą niezłożoną część student otrzymuje 0 punktów
Lista projektów
| Nr grupy | Imię | Nazwisko | Temat |
| 1 | Maciej | Szczepański | Sprzątanie norki jeża |
| Ewa | Łaniewska | ||
| 2 | Dominika | Krawczyk | Planowanie wyprawy łupieżczej po Karaibach |
| Anastasiya | Zygmantovich | ||
| 3 | Anna | Starczewska | Dobór więźniów do pracy |
| Ewelina | Wołek | ||
| 4 | Marcin | Piwko | Wybór miejsca spotkania plemion indiańskich |
| Łukasz | Sikora | ||
| 5 | Przemysław | Wenus | Planowanie wycieczki górskiej |
| Sławomir | Porębski | ||
| 6 | Piotr | Zalewski | Optymalny zakup napojów |
| Dawid | A witała | ||
| 7 | Adam | Pytel | Wybór ekipy na wyprawę na biegun |
| Krzysztof | Węsek | ||
| 8 | Krzysztof | Suchoński | Optymalne kodowanie tekstu |
| Łukasz | Wólczyński | ||
| 9 | Patrycja | Kaczyńska | Zatrucie wodociągów w kraju |
| Aleksandra | Dąbrowska | ||
| 10 | Natalia |
Krzystoszek |
Znajdowanie kolejności ubierania/rozbierania się |
| Paweł |
Ładyżyński |
||
| 11 | Urszula |
Rzechuła |
Grodzenie lasu |
| Artur |
Stanios |
||
| 12 | Szymon |
Zabrocki |
Wybór oddziału komandosów |
| 13 | Wróżenie z kości małych zwierząt futerkowych | ||
| 14 | Upychanie śmieci na szafę | ||
| 15 | Podział projektów na WZOD | ||
| 16 | (nie wymyślilem bajki :( ) | ||
Opis projektów
1. Sprzątanie norki jeża
Dany jest układ korytarzy tworzących norkę jeża.
Każdy korytarz ma też daną długość, określoną czasem potrzebnym na przejście i posprzątanie go. Przejście prze korytarz wcześniej posprzątany zajmuje 1/2 tego czasu.
Celem jest znalezienie jak najkrótszej trasy pozwalającej posprzątać wszystkie korytarze i wrócić do miejsca startu (czyli przed telewizor).
2. Planowanie łupieżczej wyprawy po Karaibach
Dana jest mapa pewnej części Karaibów - wysp z zaznaczonymi miastami.
Celem jest splądrowanie wszystkich miast, każdego dokładnie raz i powrót do miejsca startu (jaskini ze skarbami). Obrana trasa musi być jak najkrótsza (pływanie statkiem obciążonym kosztownościami jest trudne).
Uwagi:
Należy zaimplementować przynajmniej jeden z klasycznych algorytmów aproksymacyjnych oraz własną modyfikację, uwzględniającą specyficzne dane (umieszczenie miast na wyspach) oraz porównać działanie tych algorytmów.
3. Dobór więźniów do pracy
Dana jest grupa więźniów danego więzienia. Każdy z więźniów może znać każdego innego więźnia (np. siedzieli razem w celi). Potrzebujemy grupy k więźniów do pracy w kamieniołomie.
Celem jest wybór wszystkich k-więźniowych grup takich, że żadna para więźniów w grupie nie zna się (wtedy na pewnie próbowaliby uciec).
Uwagi:
Relacja znania jest symetryczna.
4. Wybór miejsca spotkania plemion indiańskich
Plemiona indiańskie żyją w dorzeczu dużej rzeki (stanowi je rzeka wraz z dopływami). Każde plemię żyje nad rzeką, dodatkowo każde miejsce, gdzie dorzecze wpada do rzeki jest idealnym miejscem na wioskę i jest zajęte. Odległości między sąsiednimi wioskami wzdłuż rzeki są równe.
Plemiona postanowiły zwołać wielkie spotkanie.
Celem jest wybór miejsca spotkania tak, by ten Indianin, który ma najdalej, miał jak najbliżej.
5. Planowanie wycieczki górskiej
Dana jest mapa z zaznaczonymi wysokościami poszczególnych punktów. Znajdujemy się w miejscu A (miejsce spania), chcemy dotrzeć do miejsca B (miejsce jedzenia).
Każde 100m różnicy wysokości pod górę wydłuża czas przejścia między punktami o 10% w stosunku do czasu bazowego.
Każde 100m różnicy w dół wydłuża czas przejścia między punktami o 5% w stosunku do czasu bazowego.
Celem jest znalezienie trasy między punktami A i B, która zajmie jak najmniej czasu.
6. Optymalny zakup napojów
Udajemy się do sklepu z napojami mając pewną kwotę. W sklepie znajdują różne napoje, o różnej zawartości cukru (liczonej w mililitrach).
Celem jest taki zakup napojów, by nie przekroczyć kwoty, którą posiadamy, ale by w sumie zakupy zawierały jak najwięcej cukru.
Uwagi:
Algorytm aproksymacyjny
7. Wybór ekipy na wyprawę na biegun
Dana jest grupa ludzi. Każde dwie osoby mogą ufać sobie nawzajem.
Celem jest znalezienie największej grupy ludzi, z których każde dwie ufają sobie nawzajem (bo muszą sobie ufać jeśli chcą razem jechać na biegun).
Uwagi:
Algorytm aproksymacyjny.
8. Optymalne kodowanie tekstu
Dany jest tekst.
Celem jest takie zakodowanie znaków w tym tekście, by w sumie zajmował on minimalną liczbę bitów.
Należy porównać długość zapisu przy znalezionym kodowaniu z kodowaniem standardowym.
Uwagi:
Program ma umożliwiać załadowanie tekstu, kodować go kodem o stałej długości, kodować go kodem o zmiennej długości. Powinien też umożliwiać zakodowanie tekstu kodem uzyskanym dla innego tekstu.
9. Zatrucie wodociągów w kraju
Dana jest sieć kanalizacyjna łącząca Fabrykę Wody i Morze Bałtyckie. Sieć składa się z rur z zastawkami (jednokierunkowych) o określonej przepustowości (w litrach na minutę).
Celem jest znalezienie maksymalnej ilości trucizny, którą możemy wlewać do systemu przez Fabrykę Wody tak, aby nie rozsadzić rur.
10. Znajdowanie kolejności ubierania/rozbierania się
Dane są ubrania wraz z oznaczeniem, które powinny być zakładane (zdejmowane) po innych (np. przed założeniem butów musimy założyć skarpetki).
Celem jest znalezienie prawidłowej kolejności ubierania/rozbierania się.
11. Grodzenie lasu
Jesteśmy posiadaczami lasu - dane jest rozmieszczenie drzew w tym lesie. Celem jest ogrodzenie lasu siatką rozciągniętą między drzewami tak, aby:
1. Wszystkie drzewa znajdowały się wewnątrz siatki
2. Siatka miała najkrótszą długość
12,13,14,15,16 - trzeba było wybrać :-P