Ostatnia aktualizacja:
September 25. 2017 20:32:33
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ów
24/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