1. Egzamin - [2000]

Algorytmy i struktury danych egzamin - czerwiec'2000 I. Wykazać NP-trudność następującego problemu szeregowania zadań: Dany jest zbiór n zadań Z1, Z2, ..., Zn (niepodzielnych i niezależnych) o czasach wykonywania p1, p2, ..., pn i zbiór 2 procesorów. Kryterium: długość uszeregowania.

Jako znany problem NP-zupełny przyjąć problem PODZIAŁU ZBIORU: Parametry: Zbiór C elementów, C={c1,c2,...,cn}, każdy o wadze s(cj)∈Z+. Pytanie: Czy istnieje podzbiór C'∈C, taki że: Σs(cj)= Σ s(cj) cj∈C' cj∈C-C' II. 1. Opisać mechanizm niedeterminizmu i zdefiniować funkcję złożoności obliczeń niedeterministycznych. 2. Zdefiniować klasę problemów NP-zupełnych, jakie sâ praktyczne konsekwencje wykazania przynależności problemu do tej klasy? 3. Co to jest rozmiar instancji i jak wpływa na niego kodowanie binarne, a jak jedynkowe? 4. Opisać krótko standardową regułę kodowania. 5. Opisać krótko związki zachodzące między klasami P i NP problemów decyzyjnych. III.

1. Dla podanego grafu należy zbudować reprezentującą go macierz grafu (poszczególne wierzchołki należy analizować w kolejności rosnących etykiet). 2. Podać zalety macierzy grafu. 3. Dokonać sortowania topologicznego. Podać graf wynikowy. (Poszczególne wierzchołki należy analizować w kolejności rosnących etykiet). IV. Zilustruj działanie następujących procedur sortowania: a) sortowania szybkiego (QuickSort - QS) (zaznaczając środkowy element wyboru) b) przez kopcowanie (HeapSort - HS) dla danej poniżej tablicy A. Pokaż działanie tych metod "krok po kroku", dla metody HS graficznie (budowa i przywracanie struktury kopca). Uporządkowanie tablicy powinno być niemalejące. Jaka jest złożoność obliczeniowa QS i HS w najgorszym przypadku - krótko uzasadnij. Podaj przykłady danych wejściowych dla najgorszego przypadku każdego z powyższych algorytmów - krótko uzasadnij swój wybór. Tablica A={22,11,55,34,45,3,2,55,14,10,11,2,13}

V. Cykle Eulera i Hamiltona w grafie nieskierowanym. 1. Podać, jeżeli jest znany warunek konieczny i wystarczający istnienia w grafie: a) cyklu Eulera, b) cyklu Hamiltona. 2. Podać dwie klasy złożoności obliczeniowej problemów decyzyjnych, do których należy decyzyjna wersja problemu znajdowania w grafie nieskierowanym: a) cyklu Eulera, b) cyklu Hamiltona. 3. Podać złożoność obliczeniową najlepszego znanego algorytmu znajdowania cyklu Eulera w grafie nieskierowanym. 4. Czy w grafie przedstawionym poniżej istnieje cykl Eulera? Jeżeli tak, to podać go zaczynając od wierzchołka 1.

5. Czy w grafie przedstawionym poniżej istnieje cykl Hamiltona? Jeżeli tak, to podać go zaczynając od wierzchołka a.