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że być nowszy standard C++)].

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

• Stworzyć funkcje do zapisu i odczytu grafu z pliku JSON w formacie zbliżonym do pythonowej biblioteki NetworkX. Funkcje powinny korzystać z interfejsu grafów podanego na zajęciach. Można skorzystać z wybranej biblioteki C++, np. boost.JSON.
  Plan minimum to obsługa grafów z wierzchołkami typu int.
  Plan maksimum to dodatkowo obsługa grafów z wierzchołkami typu std::string, bo JSON nie rozróżnia typów char i std::string. Jeżeli okaże się, że wszystkie wierzchołki są stringami jednoznakowymi, to można próbować użyć typu char.
  [https://en.wikipedia.org/wiki/JSON]

  ---

  Przykładowy graf prosty skierowany ważony:
  wierzchołki: 'A', 'B', 'C'
  krawędzie: Edge('A', 'B', 1.1), Edge('B', 'C', 2.2)
  postać pliku JSON:
  {
      "directed": true,
      "multigraph": false,
      "nodes": [ {"id": "A"}, {"id": "B"}, {"id": "C"} ],
      "edges": [
          {"source": "A", "target": "B", "weight": 1.1},
          {"source": "B", "target": "C", "weight": 2.2}
      ]
  }
  

  ---

• 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. Labirynt rozumiemy jako drzewo rozpinające dla pewnej sieci kwadratowej n × m. Labirynt należy na końcu wyświetlić na ekranie w formie przyjaznej dla użytkownika lub zapisać do pliku, najlepiej graficznego.
  [https://en.wikipedia.org/wiki/Maze_generation_algorithm]
  [https://en.wikipedia.org/wiki/Lattice_graph]
• 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]

PRZEMYTNICY (Olimpiada Informatyczna 2003)

Bajtocja słynie z bogatych złóż złota, dlatego przez długie lata kwitła sprzedaż tego kruszcu do sąsiedniego królestwa, Bitlandii. Niestety, powiększająca się ostatnio dziura budżetowa zmusiła króla Bitlandii do wprowadzenia zaporowych ceł na metale i minerały. Handlarze przekraczający granicę muszą zapłacić 50% wartości przewożonego ładunku. Bajtockim kupcom grozi bankructwo.

Na szczęście bajtoccy alchemicy opracowali sposoby pozwalające zamieniać pewne metale w inne. Pomysł kupców polega na tym, aby z pomocą alchemików zamieniać złoto w pewien tani metal, a następnie, po przewiezieniu go przez granicę i zapłaceniu niewielkiego cła, znowu otrzymywać z niego złoto. Niestety alchemicy nie znaleźli sposobu na zamianę dowolnego metalu w dowolny inny. Może się więc zdarzyć, że proces otrzymywania danego metalu ze złota musi przebiegać wielostopniowo i że na każdym etapie uzyskiwany będzie inny metal. Alchemicy każą sobie słono płacić za swoje usługi i dla każdego znanego sobie procesu zamiany metalu A w metal B wyznaczyli cenę za przemianę 1kg surowca. Handlarze zastanawiają się, w jakiej postaci należy przewozić złoto przez granicę oraz jaki ciąg procesów alchemicznych należy zastosować, aby zyski były możliwie największe.

Zadanie. Pomóż uzdrowić bajtocką gospodarkę! Napisz program, który:

(1) Wczyta tabelę cen wszystkich metali, a także ceny przemian oferowanych przez alchemików.

(2) Wyznaczy taki ciąg metali m_0, m_1, ..., m_k, że:
(a) m_0 = m_k to złoto,
(b) dla każdego i = 1, 2, ..., k alchemicy potrafią otrzymać metal m_i z metalu m_{i-1}, oraz
(c) koszt wykonania całego ciągu procesów alchemicznych dla 1kg złota powiększony o płacone na granicy cło (50% ceny 1kg najtańszego z metali m_i, dla i = 0, 1, ..., k) jest najmniejszy z możliwych.
Zakładamy, że podczas procesów alchemicznych waga metali nie zmienia się.

(3) Wypisze koszt wykonania wyznaczonego ciągu procesów alchemicznych powiększony o płacone na granicy cło.

Wejście. W pierwszym wierszu standardowego wejścia znajduje się jedna dodatnia liczba całkowita n oznaczająca liczbę rodzajów metali, 1 ≤ n ≤ 5000.
W wierszu o numerze k+1, dla 1 ≤ k ≤ n, znajduje się nieujemna parzysta liczba całkowita p_k - cena 1kg metalu oznaczonego numerem k, 0 ≤ p_k ≤ 10^9. Przyjmujemy, że złoto ma numer 1.
W wierszu o numerze n+2 znajduje się jedna nieujemna liczba całkowita m równa liczbie procesów przemiany znanych alchemikom, 0 ≤ m ≤ 100000.
W każdym z kolejnych m wierszy znajdują się po trzy liczby naturalne, pooddzielane pojedynczymi odstępami, opisujące kolejne przemiany. Trójka liczb a,b,c oznacza, że alchemicy potrafią z metalu o numerze a otrzymać metal o numerze b i za zamianę 1kg surowca każą płacić c bajtalarów, 1 ≤ a,b ≤ n, 0 ≤ c ≤ 10000. Uporządkowana para liczb a i b może się pojawić w danych co najwyżej jeden raz.

Wyjście. Twój program powinien pisać na standardowe wyjście. W pierszym wierszu powinna zostać wypisana jedna liczba całkowita - koszt wykonania wyznaczonego ciągu procesów alchemicznych powiększony o płacone na granicy cło.

Przykład.

# Dla danych wejściowych:
4
200
100
40
2
6
1 2 10
1 3 5
2 1 25
3 2 10
3 4 5
4 1 50
# poprawnym wynikiem jest:
60