Algorytmy równoległe 2010/11

Egzamin ustny, z przygotowaniem odpowiedzi na kartce - pytania egzaminacyjne

Obowiązuje znajomość poniższych zagadnień w zakresie omawianym na zajęciach. Prezentacja algorytmu ma zawierać uzasadnienie poprawności jeśli nie jest oczywista, model obliczeń dla którego algorytm jest skonstruowany, analizę złożoności czasowej, liczby procesorów oraz wykonywanej pracy, a także komentarz na temat optymalności w sensie wykonywanej pracy.

  1. Lemat Brenta, równolegle obliczanie prefiksów, list ranking (wersja prosta, z pracą nlgn), tworzenie podlisty zawierającej elementy oznakowane
  2. List ranking z pracą liniową, w czasie lgn lglgn
  3. Technika ścieżki Eulera, przykłady: numeracja węzłów drzewa w preorder, obliczanie wielkości poddrzew
  4. Algorytm kontrakcji drzewa i zastosowanie do obliczania wyrażeń arytmetycznych (przykład z dodawaniem i mnożeniem); wartościowanie podwyrażeń (idea)
  5. Łamanie symetrii (kolorowanie cyklu): algorytm nieoptymalny log*n.
  6. Łamanie symetrii (kolorowanie cyklu): algorytm optymalny log n oraz zawarty w nim algorytm sortowania liczb (równoległy countsort)
  7. Scalanie ciągów posortowanych w czasie lglgn oraz wykorzystany w nim algorytm szybkiego wyszukiwania w tablicy posortowanej
  8. Znajdowanie spójnych składowych, uzasadnienie poprawności, złożoność
  9. Znajdowanie minimalnego drzewa rozpinającego
  10. Najkrótsze ścieżki, BFS, przechodnie domknięcie relacji - związek z mnożeniem macierzy, złożoność w modelu PRAM
  11. Dwuspójne składowe: idea metody, definicja i własności obliczanej relacji
  12. Dwuspójne składowe: reprezentacja drzewa, funkcje obliczane dla wierzchołków, zależność wyniku od wartości tych funkcji
  13. Sieć sortująca odd-even, twierdzenie o poprawności, wizualizacja (np. dla n=8)
  14. Sieć sortowania bitonicznego, własność unikalnego przecięcia (dowód dla wybranego przypadku), twierdzenie o poprawności, wizualizacja
  15. Lemat 0-1, sortowanie na liście procesorów i jego poprawność, sortowanie wężowe na kracie procesorów
  16. Algorytm Warshalla-Floyda (przechodnie domknięcie relacji) w kracie procesorów; usprawnienie przez resynchronizację (szkic algorytmu)
  17. P-zupełność problemu generowania dla działania trójargumentowego – redukcja z użyciem modelu taśmowego maszyny Turinga
  18. P-zupełność problemu wartości obwodu logicznego