Zagadnienia



Pobieranie 40.92 Kb.
Data07.05.2016
Rozmiar40.92 Kb.
Zagadnienia



  1. Drzewa AVL. Rotacje, wstawianie i usuwanie w czasie O(log n).

  2. Sortowanie przez scalanie, rozwiązywanie prostych równań rekurencyjnych.

  3. Sortowanie szybkie (Quick-Sort), wersje deterministyczna i randomizacyjna. Szybka selekcja.

  4. Oszacowanie dolne na złożoność sortowania przez porównania.

  5. Sortowanie kubełkowe (Bucket-Sort) w czasie liniowym. Przypadek średni.

  6. Grafy. Terminologia i reprezentacja grafów.

  7. Algorytm DFS przeszukiwania grafu w głąb (dla grafów skierowanych i nieskierowanych). Drzewa DFS.

  8. Wykorzystanie DFS do sortowania topologicznego grafów acyklicznych oraz wyznaczania silnie spójnych składowych.

  9. Minimalne drzewa rozpinające dla grafów spójnych i nieskierowanych. Krawędzie bezpieczne, ogólny algorytm MST.

  10. Algorytmy Kruskala i Prima znajdowania MST, jako przykłady algorytmów zachłannych.

  11. Najkrótsze ścieżki z jednego źródła. Relaksacja. Algorytmy Dijkstry (dla wag dodatnich) i Bellmana-Forda (dla wag dowolnych). Przypadek grafów acyklicznych.

  12. Najkrótsze ścieżki między wszystkimi parami wierzchołków, algorytm Floyda-Warshalla.

  13. Sieci przepływowe. Przepływy, sieci residualne, ścieżki powiększające, przekroje.

  14. Ogólny algorytm Forda-Fulkersona dla maksymalnego przepływu, wersja Edmondsa-Karpa.

  15. Języki formalne i automaty skończone. Minimalne automaty skończone.


PRZYKŁADOWE problemy


  1. Wykaż, że jeśli T(n) = T(n/2) + 1, gdzie n = 2k, to T(n) = O(log n).

  2. Podaj rozwiązanie (w terminach “O”) równania T(n) = 4T(n/2) + n.

  3. Zilustruj działanie deterministycznej procedury PARTITION dla tablicy A=[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21], pokazując zawartość tablicy po każdej zamianie jej elementów.

  4. Jaką wartość zwraca PARTITION gdy wszystkie elementy tablicy mają taką samą wartość?

  5. Jak zmodyfikować procedurę QUICK-SORT, aby sortowała ona w porządku nierosnącym.

  6. Dlaczego analizujemy oczekiwany czas działania algorytmu randomizacyjnego, a nie jego czas pesymistyczny.

  7. Napisz w Pascalu nie-rekurencyjną wersję procedury RANDOMIZED-SELECT.

  8. Podaj nie-trywialne ograniczenie dolne na pesymistyczną liczbę porównań w algorytmie sortowania opartego na porównaniach, który poprawnie sortuje każde 11 liczb całkowitych.

  9. Pokaż, np. wykonując odpowiednie rysunki, zawartość początkowo pustego drzewa AVL po wykonaniu każdej z ciągu poniższych operacji: Insert(20), Insert(30), Insert(50), Insert(40), Insert(60), Insert(45), Insert(70), Remove(50), Insert(80), Remove(30), Insert(75).

  10. Pokaż, że jeśli graf (skierowany lub nie-skierowany) zawiera ścieżkę między wierzchołkami u i v to zawiera również prostą ścieżkę między tymi wierzchołkami.

  11. Pokaż, że dowolny spójny graf nieskierowany ma co najmniej n-1 krawędzi, gdzie n jest liczbą wierzchołków.

  12. Pokaż, jeśli graf nie-skierowany ma n > 1 wierzchołków to istnieją dwa różne wierzchołki z których wychodzi tyle samo krawędzi.

  13. Pokaż, że w grupie sześciu ludzi trójka wzajemnie sobie znajomych albo wzajemnie sobie nieznajomych.

  14. Dany jest graf skierowany G = (V, E), gdzie V = {q, r, s, t, u, v, w, x, y, z} i E = {(q,s), (q,t), (q,w), (r,u), (r,y), (s,v), (t,x), (t,y), (u,y), (v,w), (w,s), (x,z), (y,q), (z,x)}. Zilustruj działanie przeszukiwania w głąb dla tego grafu zakładając, że w głównej pętli wierzchołki brane są w kolejności alfabetycznej. Podaj dla każdego wierzchołka czas jego odwiedzenia i przetworzenia oraz sklasyfikuj każdą krawędź. Ponadto, podaj odpowiednią strukturę nawiasów.

  15. Podaj wszystkie silnie spójne składowe grafu z zadania 14.

  16. Wykaż, że krawędź (u,v) jest (a) krawędzią drzewową lub “w przód” wtedy i tylko wtedy gdy d[u] < d[v] < f[v] < f[u] (b) krawędzią powrotną wtedy i tylko wtedy gdy d[v] < d[u] < f[u] < f[v] (c) krawędzią poprzeczną wtedy i tylko wtedy gdy d[v] < f[v] < d[u] < f[u].

  17. Jak wykorzystać algorytm przeszukiwania grafu w głąb dla znalezienia spójnych składowych grafu nie-skierowanego.

  18. Podaj algorytm sprawdzania, czy dany graf skierowany ma cykl. Algorytm ma działać w czasie O(n), gdzie n jest liczbą wierzchołków. Wykaż poprawność Twojego algorytmu.

  19. Zapisz w Pascalu algorytm sortowania topologicznego wynikający z dowodu lematu, że wierzchołki można posortować topologicznie wtedy i tylko wtedy gdy graf jest acykliczny.

  20. O ile może zmienić się liczba silnie spójnych składowych w grafie skierowanym w wyniku dodania nowej krawędzi?

  21. Przedstaw działanie algorytmu obliczającego silnie spójne składowe dla grafu z zadania 14, przyjmując alfabetyczny porządek wierzchołków.

  22. Wykaż, że wierzchołki grafu skierowanego można uporządkować tak, że jedno wywołanie DFS daje silnie spójne składowe tego grafu (jako drzewa w odpowiednim lesie DFS).

  23. Wykaż, że jeśli dana krawędź należy do pewnego drzewa MST grafu spójnego i nie-skierowanego, to jest ona najlżejszym pomostem pewnego przekroju.

  24. Czy krawędź o najmniejszej wadze należy do każdego drzewa MST?

  25. Niech G = (V, E) będzie grafem nieskierowanym, w którym V = {a, b, c, d, e, f, g, h}, E = {(a,b), (a,h), (b,c), (b,h), (c,d), (c,f), (c,i), (d,e), (d,f), (e,f), (f,g), (g,i), (g,h), (h,i)} odpowiednio z wagami 4, 8, 8, 11, 7, 4, 2, 9, 14, 10, 2, 1, 6, 7. Zilustruj działanie algorytmu Kruskala pokazując kolejne krawędzie bezpieczne i rozrastanie się lasu MST.

  26. Zilustruj działanie algorytmu Prima dla grafu z zadania 25 pokazując kolejne krawędzie bezpieczne i rozrastanie się drzewa MST.

  27. Opracuj algorytm znajdowania drzewa rozpinającego, w którym zamiast sumę wag jego krawędzi minimalizujemy maksymalną wagę krawędzi.

  28. Zilustruj działanie algorytmu Dijkstry dla grafu nie-skierowanego z zadania 25, przyjmując za źródło wierzchołek a. Pokaż rozrastanie się drzewa najkrótszych ścieżek wykonując odpowiednie rysunki po każdym dołączeniu nowej krawędzi.

  29. Niech T będzie jednym z drzew najkrótszych ścieżek w grafie skierowanym G. Wykaż, że istnieje taki porządek wierzchołków i krawędzi w listach sąsiedztwa grafu G, że drzewo najkrótszych ścieżek będące wynikiem działania algorytmu Dijkstry jest równe T.

  30. Dany jest graf skierowany, w którym z każdą krawędzią e związane jest prawdopodobieństwo p(e) jej niezawodności. Podaj algorytm znajdowania najbardziej niezawodnej ścieżki między dwoma danymi wierzchołkami.

  31. Zmodyfikuj algorytm Bellmana-Forda tak, aby dla wszystkich wierzchołków v, dla których istnieje cykl o ujemnej wadze na pewnej ścieżce ze źródła s do v, zmiennej d[v] była przypisana wartość

  32. Niech G = (V, E) będzie grafem skierowanym, w którym V = {1, 2, 3, 4, 5, 6}, E = {(1,5), (2,1), (2,4), (3,2), (3,6), (4,1), (4,5), (5,2), (6,2), (6,3)} odpowiednio z wagami -1, 1, 2, 2, -8, -4, 3, 7, 5, 10. Zilustruj działanie algorytmu Floyda-Warshalla dla danego grafu zmieniając zawartość tablic D[,] oraz [,].

  33. Czy możliwe jest odtworzenia tablicy [,] najkrótszych ścieżek na podstawie tablicy D[,] pokazującej ich długości, w problemie najkrótszych ścieżek między wszystkimi parami wierzchołków.

  34. Pokaż, że przepływy w danej sieci przepływowej tworzą zbiór wypukły.

  35. Niech G będzie siecią przepływową, a f przepływem w G. Wykaż, że sieć residualna Gf ma co najwyżej dwa razy więcej wierzchołków niż G.

  36. Rozpatrzmy sieć przepływową G=(V,E) o wierzchołkach vk, 0<=k<=5, ze źródłem s=v0 i ujściem t=v5, oraz przepustowościami c(s,v1)=16, c(s,v2)=13, c(v1,v2)=10, c(v1,v3)=12, c(v2,v1)=4, c(v2,v4)=14, c(v3,v2)=9, c(v3,t)=20, c(v4,v3)=7, c(v4,t)=4. Znajdź wartość maksymalnego przepływu w tej sieci poprzez znalezienie przekroju o minimalnej przepustowości.

  37. Zilustruj działanie algorytmu Edmondsa-Karpa dla sieci z zadania 36. Wskaż kolejne ścieżki powiększające.

  38. Wykaż, że dla każdej pary wierzchołków u i v oraz przepływu f mamy cf(u,v) + cf(v,u) = c(u,v) + c(v,u).

  39. Udowodnij, że maksymalny przepływ w danej sieci można zawsze znaleźć za pomocą ciągu co najwyżej m ścieżek powiększających, gdzie m jest liczbą krawędzi w sieci.

  40. Podaj minimalny automat skończony akceptujący język składający się ze słów należących do {0,1}*, w których drugą i przedostatnią literą jest jedynka.

  41. Wykaż, że język słów postaci ww, gdzie w{0,1}* nie jest regularny.

  42. Znajdź minimalny automat skończony akceptujący języki:

  1. L = { x{0,1}*: x zawiera podciąg 010 }

  2. L = { x{0,1}*: x nie zawiera podciągu 010 }

43.Dla danego języka L*, niech

S = { x*: x nie jest prefiksem żadnego słowa w L }.



Wykaż, że jeśli S to S jest klasą abstrakcji relacji IL.


©absta.pl 2016
wyślij wiadomość

    Strona główna