MiASD/L/z1

From WikiZMSI

Na zajęciach

Problem (PDP): dla pewnego fragmentu genomu dany jest wielozbiór wszystkich odległości parami pomiędzy miejscami restrykcyjnymi:

przykład (a): L = {2, 4, 9, 11, 11, 13, 13, 17, 17, 19, 20, 24, 28, 28, 30, 30, 37, 39, 41, 41, 47, 48, 50, 52, 54, 58, 67, 71}.

przykład (b): L = {3, 7, 12, 16, 18, 23, 24, 24, 26, 26, 30, 33, 33, 34, 35, 36, 39, 44, 46, 47, 49, 51, 54, 57, 58, 59, 60, 61, 68, 70, 71, 80, 83, 85, 85, 86, 87, 90, 93, 102, 104, 105, 109, 112, 119, 123, 128, 128, 131, 135, 144, 147, 149, 151, 158, 161, 162, 163, 167, 167, 170, 171, 174, 174, 187, 188, 196, 197, 200, 200, 205, 206, 207, 208, 216, 217, 218, 220, 221, 221, 223, 230, 232, 233, 234, 246, 252, 254, 254, 254, 256, 257, 258, 266, 267, 270, 272, 276, 287, 290, 293, 293, 302, 303, 305, 306, 309, 311, 319, 325, 328, 332, 335, 337, 356, 358, 358, 363, 370, 374, 379, 382, 387, 389, 392, 393, 394, 395, 405, 415, 417, 417, 418, 421, 421, 423, 428, 428, 433, 439, 440, 441, 450, 451, 453, 454, 460, 463, 472, 472, 474, 475, 477, 479, 486, 487, 502, 508, 511, 520, 521, 523, 526, 545, 559, 562, 579, 591, 595, 602, 621, 625, 628, 630, 639, 646, 649, 651, 669, 675, 682, 685, 693, 708, 711, 726, 729, 753, 779, 797}

Należy odtworzyć zbiór miejsc restrykcyjnych X (taki że delta X = L).

Wskazówki programistyczne:

• Napisać funkcję pomocniczą, która dla danego zbioru miejsc restrykcyjnych X, wyznacza wszystkie odległości parami tj. delta X.

• Napisać funkcję pomoczniczą, która dla danego zbioru oraz liczby (2 argumenty) wyznacza odległości tej liczby od poszczególnych elementów podanego zbioru.

• Napisać funkcję pomoczniczą obliczającą różnicę wielozbiorów.

• Napisać funkcje pomoczniczą sprawdzającą, czy jeden wielozbiór zawiera się w innym (zwracana flaga logiczna).

• Zaprogramować algorytm wyczerpujący przeglądający wszystkie (n-2)-elementowe kombinacje ze zbioru L. Wskazówka - w Mathematica użyć funkcji KSubsets po wczytaniu pakietu kombinatorycznego (wpis: << Combinatorica`). Zwrócić pierwsze napotkane rozwiązanie.

• Zaprogramować algorytm Skienny. Przewidzieć przełącznik pozwalający na zwrócenie pierwszego napotkanego rozwiązania lub wszystkich.

• Dla przykładu (a) porównać czasy działania obu algorytmów, przykład (b) nie wykona się w rozsądnym czasie dla algorytmu wyczerpującego.

Do domu

• Poczytać w dokumentacji do Mathematica o funkcjach kompilowanych (polecenie Compile).

• Przepisać w/w funkcje pomocnicze na postać skompilowaną i wpleść ich wywołania do modułu z algorytmem Skieny (sam moduł może pozostać nieskompilowany).

• Porównać czasy obliczeń wersji skompilowanej i nieskompilowanej.

• Wykonać kilka "dużych" eksperyment: wylosować zbiór np. n = 100, 200, 300 miejsc restrykcyjnych wykorzystując polecenie RandomInteger (wskazówka: w celu uniknięcia duplikacji miejsc restrykcyjnych podać duży zasięg losowania, np. od 1 do 1 000 000), wyznaczyć rozwiązanie algorytmem Skieny (w wersji skompilowanej).

• Wykonać zbiorczy eksperyment wyznaczający średnie czasy pracy algorytmu Skieny dla rosnącego rozmiaru problemu. Tj. należy napisać dwie zagnieżdżone pętle - zewnętrzna zmieniająca rozmiar problemu n = 1, 2, ..., 100, wewnętrzna wykonująca 10 powtórzeń dla ustalonego n (10 losowych problemów). Czasy mierzyć i zczytywać poleceniem Timing. Ostatecznie sporządzić wykres średniego czasu obliczeń od rozmiaru problemu (polecenie ListPlot).