Propozycje tematów projektów zaliczeniowych

UWAGI OGÓLNE

W celu zaliczenia ćwiczeń z AiSD należy:
(1) zaliczyć 10 zestawów zadań,
(2) zaliczyć dwa kolokwia,
(3) zaliczyć projekt programistyczny w C++ [kod plus dokumentacja (README.md, HTML, PDF); minimum 100 wierszy kodu; nie używać using namespace std;; Makefile do kompilacji z flagami -Wall -std=c++11].

Możliwe sposoby przesyłania rozwiązań zestawów zadań:
(1) email z linkiem do repozytorium w serwisie GitHub, gdzie składowane są kody źródłowe programów,
(2) email z linkiem do archiwum ZIP w chmurze UJ,
(3) email z archiwum ZIP w załączniku.

GRAFY

• Algorytm Boruvki - minimalne drzewo rozpinające dla grafu nieskierowanego ważonego spójnego.
• Algorytm Kruskala - minimalne drzewo rozpinające dla grafu nieskierowanego ważonego spójnego.
• Algorytm Prima - minimalne drzewo rozpinające dla grafu nieskierowanego ważonego spójnego.
• Generowanie labiryntu, np. Wilson, Aldous-Broder, Kruskal, Prim [https://en.wikipedia.org/wiki/Maze_generation_algorithm]. Labirynt rozumiemy jako drzewo rozpinające dla pewnej sieci kwadratowej n × m [https://en.wikipedia.org/wiki/Lattice_graph]. Labirynt należy na końcu wyświetlić na ekranie w formie przyjaznej dla użytkownika lub zapisać do pliku, najlepiej graficznego.
• Podaj efektywny algorytm działający w czasie O(n+m), który znajduje liczbę wszystkich ścieżek w dagu [Cormen]. Ścieżka może się zaczynać i kończyć w dowolnym wierzchołku. Wskazówka: W pierwszym kroku należy wykonać sortowanie topologiczne wierzchołków dagu. Przygotuj pseudokod i implementację w C++. Przetestuj implementację na przygładowym dagu, np. z lekcji 6.

  ---

  | Przykład sortowania topologicznego dagu.
  | 0 --o 1 --o 2   uporządkowanie 1: 0 3 4 1 5 2
  | | \   o     o   uporządkowanie 2: 0 3 4 5 1 2
  | |  \  |     |
  | o   o |     |
  | 3 --o 4 --o 5
  | ścieżki długości 1 to 8 krawędzi,
  | ścieżek długości 2 jest 8 [012, 034, 041, 045, 341, 345, 412, 452],
  | ścieżek długości 3 jest 6 [0341, 0345, 0412, 0452, 3412, 3452],
  | ścieżek długości 4 jest 2 [03412, 03452], RAZEM 24 ścieżki
  

  ---

• Algorytm kolorowania wierzchołków grafu.
• Algorytm kolorowania krawędzi grafu.
• Algorytm znajdowania największego zbioru niezależnego w grafie.
• Algorytm znajdowania najmniejszego zbioru dominującego w grafie.
• Znajdowanie cyklu Eulera (każda krawędź przebyta dokładnie raz).
• Znajdowanie cyklu Hamiltona (każdy wierzchołek odwiedzony dokładnie raz).
• Problem komiwojażera (ang. Traveling Salesman Problem, TSP), np. algorytm najbliższych sąsiadów (z powtórzeniami lub bez), algorytm sortowania krawędzi, algorytm genetyczny, symulowane wyżarzanie.
• Algorytm A* - algorytm heurystyczny znajdowania najkrótszej ścieżki w grafie ważonym.

GEOMETRIA

• Wyznaczanie otoczki wypukłej, np. Graham, Jarvis, quickhull [https://en.wikipedia.org/wiki/Convex_hull].
• Implementacja drzewa czwórkowego [https://en.wikipedia.org/wiki/Quadtree].