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.

TEMATY PROJEKTÓW

• Implementacja wielomianów na bazie list powiązanych pojedynczo (szablon, współczynniki typu T). Działania na wielomianach: dodawanie (operator+), odejmowanie (operator-), mnożenie (operator*), obliczanie wartości wielomianu (algorytm Hornera), porównywanie (operator==, operator!=), wyświetlanie (operator<<), konstruktor kopiujący, podstawienie kopiujące (operator=). Wielomiany są równe, gdy ich różnica jest wielomianem zerowym. Klasa Term opisuje węzeł listy powiązanej i przechowuje jeden niezerowy wyraz wielomianu (c*x^n). Klasa Poly przechowuje łącze do posortowanej malejąco listy powiązanej wyrazów i implementuje działania. Przydają się funkcje clear(), is_zero(), operator[] (odczyt współczynnika przy danej potędze x, zwraca referencję), degree() (stopień wielomianu, zerowy wielomian ma stopień zero).
• Implementacja wielomianów na bazie tablic (szablon, współczynniki typu T). Działania na wielomianach: dodawanie (operator+), odejmowanie (operator-), mnożenie (operator*), obliczanie wartości wielomianu (algorytm Hornera), porównywanie (operator==, operator!=), wyświetlanie (operator<<), konstruktor kopiujący, podstawienie kopiujące (operator=). Wielomiany są równe, gdy ich różnica jest wielomianem zerowym. Klasa Poly przechowuje tablicę współczynników i implementuje działania. Przydają się funkcje clear(), is_zero(), operator[] (odczyt współczynnika przy danej potędze x, zwraca referencję), degree() (stopień wielomianu, zerowy wielomian ma stopień zero).
• Implementacja kwaternionów podobnie do std::complex [https://en.wikipedia.org/wiki/Quaternion]. Działania na kwaternionach: dodawanie (operator+), odejmowanie (operator-), mnożenie (operator*), sprzężenie (conjugate lub conj), moduł (abs), kwadrat modułu (norm), porównywanie (operator==, operator!=), wyświetlanie (operator<<), konstruktor kopiujący, podstawienie kopiujące (operator=).
• Obliczanie wielomianu szachowego.
  [https://en.wikipedia.org/wiki/Rook_polynomial]
• Implementacja list z przeskokami (ang. skip list). Ma to być szablon z elementami na liście typu T.
  [https://en.wikipedia.org/wiki/Skip_list]
• Drzewo czerwono-czarne (ang. red-black tree), czyli drzewo BST o dodatkowych właściwościach.
  [https://en.wikipedia.org/wiki/Red%E2%80%93black_tree]
• Drzewo AVL, czyli drzewo BST, w którym dla każdego wezła różnica wysokości leweo i prawego poddrzewa może się różnić co najwyżej o jeden.
  [https://en.wikipedia.org/wiki/AVL_tree]
• Drzewo rozchylane (ang. splay tree), czyli drzewo BST zmieniające swoją strukturę tak, że często wyszukiwane węzły stają się szybsze do znalezienia.
  [https://en.wikipedia.org/wiki/Splay_tree]
• Drzewo ukorzenione o dowolnym stopniu rozgałęzień. Cormen str. 245, reprezentacja na lewo syn, na prawo brat.
• Drzewo przedziałowe (ang. interval tree), czyli drzewo binarne do przechowywania danych o przedziałach na osi liczbowej [Cormen str. 351, jest to wzbogacone drzewo czerwono-czarne]. Dzięki tej strukturze można wydajnie znajdować wszystkie przedziały przekrywające się z danym punktem lub przedziałem.
  [https://en.wikipedia.org/wiki/Interval_tree]
• Drzewo przedziałowe (ang. segment tree), czyli struktura danych do przechowywania informacji o tablicy liczbowej A[0...n-1]. Struktura pozwala na szybkie zapytania O(log n) dotyczące dowolnej podtablicy A[left...right], takie jak suma elementów, wartość najmniejsza/największa. Można też w czasie O(log n) dodawać pewną liczbę do każdego elementu podtablicy.
  [https://cp-algorithms.com/data_structures/segment_tree.html]
• Kopiec trójkowy (ang. ternary heap), czyli kopiec wykorzystujący drzewo trójkowe (węzeł ma najwyżej troje dzieci) zamiast drzewa binarnego [https://en.wikipedia.org/wiki/D-ary_heap].

  ---

  # Obliczanie pozycji rodzica i dzieci w kopcu trójkowym dla węzła o numerze n.
  int heap_parent(int n) { return (n-1) / 3; }
  int heap_left(int n) { return (3 * n + 1); }
  int heap_middle(int n) { return (3 * n + 2); }
  int heap_right(int n) { return (3 * n + 3); }
  

  ---

• Program do obsługi biblioteki (użytkownicy, książki, wypożyczanie). Nie należy używać serwerów dużych baz danych, można użyć biblioteki SQLite.
• Program symulujący konta w banku. Operacje: zakładanie i usuwanie konta, wpłata, wypłata, przelew, zapis i odczyt bazy z pliku. Nie należy używać serwerów dużych baz danych, można użyć biblioteki SQLite.
• Program do rezerwacji biletów lotniczych. Nie należy używać serwerów dużych baz danych, można użyć biblioteki SQLite.
• Baza danych książek, płyt, filmów, itp. (jeden typ elementów, wystarczy jedna tabela). Operacje: dodawanie, usuwanie, wyszukiwanie rekordów, wypisywanie zawartości bazy, zapis i odczyt bazy z pliku. Przy wyszukiwaniu powinno wystarczyć podanie fragmentu danych z rekordu, np. fragmentu nazwiska autora czy tytułu. Wygodne jest wczytywanie bazy przy starcie programu, potem zapisywanie bazy do pliku po każdej zmianie danych (dodanie/usuwanie rekordu). Nie należy używać serwerów dużych baz danych, można użyć biblioteki SQLite.
• Obliczanie mediany kroczącej (ang. running median).
  [https://en.wikipedia.org/wiki/Moving_average#Moving_median]
• Implementacja systemu T9 (predictive text), stosowanego w telefonach komórkowych do łatwiejszego pisania tekstów za pomocą klawiatury 3x4. Używa się 8 przycisków znaczących 2-9. Jeżeli wyświetli się kilka wyrazów, ale pierwszy nie jest tym właściwym, to klawisz '*' daje przejście do następnego wyrazu.
  [https://en.wikipedia.org/wiki/T9_(predictive_text)]

  +------+------+------+
  |1     |2 abc |3 def |
  +------+------+------+
  |4 ghi |5 jkl |6 mno |
  +------+------+------+
  |7 pqrs|8 tuv |9 wxyz|
  +------+------+------+
  | *    | 0    | #    |
  +------+------+------+