Pytania do egzaminu z Algorytmów i Struktur Danych -- Informatyka, studia dzienne, sem 3, (zima 2003/2004)

1. Podać definicje pojęć: rozmiar danych, działanie dominujące, złożoność czasowa algorytmu, złożoność pamięciowa algorytmu. Wymienić typowe funkcje określające złożoności obliczniowe algorytmów. Po co wyznacza się złożoność obliczeniową algorytmu?

2. Podać definicje złożoności pesymistycznej i średniej algorytmu. Udowodnić, że W(n) = a_mn^m + ... + a_1n + a_0 = O(n^m), dla n>0.

3. Jak brzmi definicja O-notacji? Podać trzy dowolne własności rzędu funkcji.

4. Podać algorytmy oraz określić ich złożoności obliczeniowe dla wyznaczania wartości wielomianu dla przypadków: a) korzystając bezpośrednio ze wzoru, b) korzystając ze schematu Hornera.

5. Podać dwa algorytmy (z wartownikiem i bez) znajdowania maksymalnego elementu w tablicy. Wyznaczyć i porównać ich złożoności.

6. Podać algorytmy jednoczesnego znajdowania elementu maksymalnego i minimalnego w zadanym zbiorze dla przypadków: a) kolejne znajdowanie elementu maksymalnego a następnie minimalngo, b) dzielenie zadania na podzadania. Określić złożoności obliczniowe algorytmów.

7. Podać rozwiązania równań rekurencyjnych: T(n) = b, dla n = 1, oraz T(n) = aT(n/c) + bn, dla n > 1. Podać interpretację rozwiązań.

8. Omówić zasadę równoważenia rozmiarów podzadań na przykładzie zadania sortowania, rozważając algorytm sortowania przez wybór prosty oraz rekursywny algorytm sortowania przez łączenie. Określić złożoności obliczeniowe algorytmów.

9. Podać własności kopca oraz omówić sposób jego implementacji. Podać i wyjaśnić działanie procedur: przemieść_w_górę i przemieść_w_dół. Wyznaczyć złożoności procedur.

10. Podać abstrakcyjny opis kolejki priorytetowej. Podać i wyjaśnić działanie procedur zeruj, wstaw i usuń_min dla kolejki implementowanej za pomocą kopca. Jakie są inne możliwe implementacje kolejki? Porównać je ze sobą pod kątem złożoności obliczeniowej.

11. Podać algorytm budowania kopca (faza 1. sortowania przez kopcowanie) oraz jego złożoność pesymistyczną.

12. Podać algorytm sortowania przez kopcowanie oraz określić jego pesymistyczną złożoność obliczeniową.

13. Sformułować zadanie wyszukiwania. Podać algorytmy wyszukiwania liniowego bez wartownika i z wartownikiem oraz określić ich złożoności średnie i pesymistyczne.

14. Podać algorytm wyszukiwania binarnego. Wyznaczyć jego złożoność pesymistyczną.

15. Podać algorytm obliczania wartości współczynnika dwumianowego metodą programowania dynamicznego. Wyznaczyć złożoność obliczeniową algorytmu.

16. Podać algorytm sortowania przez proste wybieranie oraz określić jego złożoność średnią i pesymistyczną.

17. Podać algorytm sortowania przez proste wstawianie z wartownikiem oraz określić jego złożoność średnią i pesymistyczną.

18. Omówić algorytm sortowanie szybkiego - quicksort - oraz określić jego złożoność średnią i pesymistyczną. Co warunkuje szybkie działanie algorytmu?

19. Omówić sposoby reprezentowania grafów w komputerze. Jakie są ich złożoności pamięciowe?

20. Omówić algorytm przeszukiwania grafu w głąb. Jaka jest złożoność algorytmu? Podać zastosowanie tego przeszukiwania do rozwiązywania problemu znajdowania składowych spójności grafu.

21. Omówić algorytm przeszukiwania grafu wszerz. Jaka jest złożoność algorytmu? Podać zastosowanie tego przeszukiwania do rozwiązywania problemu znajdowania najkrótszej drogi w grafie (długość drogi liczona liczbą krawędzi).

22. Podać i omówić algorytm znajdowania cykli fundamentalnych w grafie. Jaka jest jego złożoność?

23. Podać i omówić algorytm Kruskala znajdowania minimalnego drzewa rozpinającego. Jaka jest jego złożoność?

24. Podać i omówić algorytm Prima i Dijkstry znajdowania minimalnego drzewa rozpinającego. Jaka jest jego złożoność?

25. Omówić ideę algorytmu zachłannego na przykładzie problemu wydawania reszty oraz problemu plecakowego. Na czym polega problem kolorowania grafu?

26. Sformułować problem komiwojażera. Podać: a) algorytm typu "sprawdź wszystkie możliwości", b) algorytm heurystyczny oparty na postępowaniu zachłannym. Jakie są złożoności algorytmów?

27. Sformułować i porównać problemy znalezienia marszruty komiwojażera, cyklu Hamiltona i cyklu Eulera.

28. Podać algorytm Dijkstry znajdowania najkrótszych dróg w grafie z ustalonego wierzchołka. Jaka jest jego złożoność?

---