2. Egzamin - [2000]

Algorytmy i struktury danych egzamin - czerwiec'2000 (studia zaoczne) 1. Scharakteryzuj problem optymalizacyjny i decyzyjny. Podaj zależność w sensie złożoności obliczeniowej pomiędzy problemami optymalizacyjnymi, a decyzyjnyjnymi. 2. Dokonaj kodowania podanej instancji problemu plecakowego: n=4; S=[7,4,8,3]; W=[6,2,9,10]; b=10; y=12, za pomocą "rozsądnej" reguły kodowania. Podaj własności tej reguły. Jaki wpływ na długość łańcucha kodującego ma kodowanie jedynkowe? 3. Co to jest funkcja złożoności obliczeniowej czasowej dla danego algorytmu A? Jakie można wyróżnić dwa główne typy algorytmów w zależności od tej funkcji? 4. Krótko scharakteryzuj realistyczne i nierealistyczne modele obliczeń. 5. Podaj 4 różne reprezentacje dla podanego poniżej grafu. Podaj złożoność pamięciową każdej z wybranych reprezentacji.

6. Podaj algorytm znajdowania minimalnego drzewa rozpinającego w grafie. Określ i uzasadnij złożoność tego algorytmu. 7. Narysuj strukturę klas złożoności dla problemów decyzyjnych. Podaj definicję klas złożoności. 8. Podaj schemat analizy złożoności dla problemów kombinatorycznych. 9. Na czym polega metoda "dziel i zwyciężaj"? Do rozwiązania, jakiego typu problemów może ona być stosowana? 10. Jak definiuje się algorytmy zachłanne? Jakie warunki musi spełniać problem, aby możliwe było jego optymalne rozwiązanie za pomocą tych algorytmów, podaj przykłady? 11. Co to są algorytmy aproksymacyjne? W jaki sposób szacuje się zachowanie takiego algorytmu w średnim i najgorszym przypadku? Jakie znasz typy oszacowania? 12. Jak działa algorytm podziału i ograniczeń? Podaj przykłady problemu rozwiązywanego tą metodą.?