Algorytmy kombinatoryczne w bioinformatyce − Zadanie I

Treść zadania:

Należy sformułować problem "z życia wzięty", niezwiązany z biologią molekularną, i zaproponować dla niego reprezentację grafową wraz z rozwiązaniem w tym grafie. Przykładowe zestawienia zawiera slajd 13 z pierwszego wykładu, przy czym teraz należy wybrać inny problem i opisać szerzej każdą z sekcji problem-reprezentacja-rozwiązanie. Po wprowadzeniu problemu, który nie powinien być kopią problemu powszechnie znanego z literatury, proszę szczegółowo zdefiniować, jak graf jest konstruowany na podstawie danych z problemu oraz co w tym grafie ma być odpowiedzią na postawiony problem i dlaczego. Rozwiązanie w grafie należy określić jako pewien obiekt w tym grafie bądź wartość związaną z obiektem, nie poprzez algorytm. Opis proszę zilustrować przykładem. Dodatkowo należy rozważyć, jaka może być złożoność obliczeniowa tego problemu i uzasadnić dlaczego (to nie ma być formalny dowód złożoności). Błędnie oszacowana złożoność nie spowoduje obniżenia oceny.

W sprawozdaniu (na ok. 2 strony) należy zamieścić opis powyższej pracy koncepcyjnej. Oceniana będzie inwencja i wkład własny w to opracowanie. W przypadku korzystania z zewnętrznych źródeł należy zawsze powołać się na źródło, obowiązuje to także podczas realizacji kolejnych zadań w semestrze.

Termin realizacji:

Omówienie zadania: 7 października (grupa wtorkowa) i 2 października (grupy czwartkowe).
Oddanie sprawozdania: 14 października (grupa wtorkowa) i 9 października (grupy czwartkowe).