Zawartość:

• Zestaw 0
• Zestaw 1
• Zestaw 2

Zestaw 0

Proszę zaimplementować typ danych setSimple reprezentujący matematyczny zbiór oraz operacje które dla dwóch zbiorów \(A\), \(B\) realizują:

• sumę zbiorów \(A \cup B\)
• część wspólną zbiorów \(A \cap B\)
• różnicę zbiorów \(A - B\)
• sprawdzanie identyczności zbiorów \(A \equiv B\)

oraz dla elementu \(x\) i zbioru \(A\) realizują:

• wstawianie \(x\) do zbioru \(A\)
• usuwanie \(x\) ze zbioru \(A\)
• sprawdzanie czy \(x \in A\)

Proszę założyć, że istnieje skończona liczba \(N\) możliwych elementów. Można sobie na przykład wyobrazić, że wszystkie rozpatrywane przez nas zbiory są podzbiorami pewnego zbioru \(\Omega\) zawierającego \(N\) elementów. Dzięki takiemu założeniu implementacja każdego z rozpytywanych zbiorów może być oparta na jednowymiarowej tablicy o rozmiarze \(N\). Każdy index \(i = 1 \ldots N\) (lub \(i = 0 \ldots N-1\)) tej tablicy odpowiadałby jednemu z elementów \(\Omega\). Wartość przechowywana w tablicy pod indeksem \(i\) (lub \(i - 1\)) wskazuje na to czy dany element należy (np. true , 1) do rozpatrywanego zbioru czy nie (np. false , 0).

• Implementacje proszę wykorzystać w programach, które badają złożoność obliczeniową poszczególnych operacji.
• Proszę opisać podejście wykorzystane do badania złożoności obliczeniowej. Jak wygląda zależność czasu wykonania od rozmiaru problemu. Jak to się ma (czy to się ma) do teoretycznej złożoności obliczeniowej?
• Proszę przetestować działanie wszystkich operacji:
  • wystarczy wyniki testów wypisywać na standardowe wyjście
  • nie trzeba korzystać z systemów do unit testów
• W większości zadań nie jest określony typ danych elementów zbioru. Można korzystać na przykład z liczb całkowitych. Nie powinno mieć to większego znaczenia jeżeli pewne warunki są spełnione. Jakie to warunki?

• notacja \(O\), uwaga w poniższych linkach dla niektórych przypadków są inne wyniki, proszę się zastanowic, która informacja jest prawidłowa:
  • geeks for geeks
  • mathematics stack exchange
• prosty przykład

Zestaw 1

Proszę zaimplementować typ danych setLinked reprezentujący matematyczny zbiór oraz wszystkie operacje z zadania A. Tym razem w implementacji proszę wykorzystać posortowane listy łączone.

Korzystając z wyników zadań A oraz B proszę się zastanowić która implementacja jest lepsza i w jakiej sytuacji. Uwaga: to zadanie może być zaliczone pod warunkiem prawidłowego wykonania A oraz B.

Proszę zaimplementować typ danych będący uproszczoną wersją zbioru, posiadającą jedynie trzy operacje:

• wstawianie \(x\) do zbioru \(A\)
• usuwanie \(x\) ze zbioru \(A\)
• sprawdzanie czy \(x \in A\)

Tym razem w zbiorze przechowywane będą ciągi znaków o długości \(50\). W implementacji proszę wykorzystać jednowymiarową tablicę, której elementy są ciągami znaków.

• Implementacje proszę wykorzystać w programach, które badają złożoność obliczeniową poszczególnych operacji.
• Proszę opisać podejście wykorzystane do badania złożoności obliczeniowej i skonfrontować Państwa wyniki z oczekiwaniami teoretycznymi.
• Proszę przetestować działanie wszystkich operacji:
  • wystarczy wyniki testów wypisywać na standardowe wyjście
  • nie trzeba korzystać z zaawansowanych systemów do unit testów
• W większości zadań nie jest określony typ danych elementów zbioru. Można korzystać na przykład z liczb całkowitych. Nie powinno mieć to większego znaczenia jeżeli pewne warunki są spełnione. Jakie to warunki?

• notacja \(O\), uwaga w poniższych linkach dla niektórych przypadków są inne wyniki, proszę się zastanowic, która informacja jest prawidłowa:
  • geeks for geeks
  • mathematics stack exchange
• prosty przykład z posortowanymi listami łączonymi

Zestaw 2

Implementacja zbioru wykorzystująca jednowymiarowe tablice o skończonym rozmiarze z zadania A w zestawie 0 zakłada, że każdemu elementowi zbioru można przypisać liczbę naturalną \(1 \ldots N\). Proszę zaimplementować funkcje implementujące takie przyporządkowanie dla zbiorów:

• liczb całkowitych \(n , n + 1 , n + 2 , \ldots , m\) gdzie \(n < m\)
• liczb całkowitych \(n , n + 2 , n + 4 , \ldots , m\) gdzie \(n < m\)
• liter \(a , b , c , \ldots , z\), bez polskich znaków ęóąśłżźć
• dwuliterowych napisów, gdzie każda litera jest z zakresu \(a - z\) bez polskich znaków ęóąśłżźć

Proszę zaimplementować typ danych setHashed reprezentujący matematyczny zbiór oraz operacje które dla dwóch zbiorów \(A\), \(B\) realizują:

• sumę zbiorów \(A \cup B\)
• część wspólną zbiorów \(A \cap B\)
• różnicę zbiorów \(A - B\)
• sprawdzanie identyczności zbiorów \(A \equiv B\)

oraz dla elementu \(x\) i zbioru \(A\) realizują:

• wstawianie \(x\) do zbioru \(A\)
• usuwanie \(x\) ze zbioru \(A\)
• sprawdzanie czy \(x \in A\)

Tym razem proszę wykrzystać następujący sposób hashowania:

• Każdy z elementów \(x\) wpada do jednego z \(N\) “kubełków”.
• Każdy “kubełek” zawiera zbiór zaimplementowany z wykorzystaniem posortowanej listy łączonej.
• Jeżeli założymy, że wrzucamy liczby całkowite, numer “kubełka” do którego wpada \(x\) jest określony przez resztę z dzielenia \(mod(x , N)\).

Przykład dostępny jest tutaj. Państwa implementację proszę wykorzystać w programie, który bada złożoność obliczeniową poszczególnych operacji. Dla każdej z zaimplementowanych operacji program powinien produkować jeden plik, który może być uruchomiony z wykorzystaniem programu gnuplot. W wiadomości e-mail proszę opisać podejście wykorzystane do badania złożoności obliczeniowej i skonfrontować Państwa wyniki z wartościami teoretycznymi.

Korzystając z wyników zadań A oraz B z zestawu 1 oraz zadania B z obecnego zestawu proszę się zastanowić która implementacja jest lepsza i w jakiej sytuacji. Swoją odpowiedź (popartą odpowiednimi wykresami) proszę przesłać za pośrednictwem e-mail.

Aby ułatwić Państwu zadanie, proszę założyć, że elementami przechowywanymi we wszystkich zbiorach są słowa składające się z 4 liter (bez polskich znaków). Można wykorzystać zadanie A.

• Dla każdej implementacji typu danych oraz dla każdej zaimplementowanej operacji proszę dodatkowo:
  • zamieścić w Państwa programie test sprawdzający czy operacje są zaimplementowane prawidłowo
  • aby ułatwic Państwu pracę możemy się umówić, że w teście będzie sprawdzana niewielka ilość przypadków - na tyle mała aby można było je wypisać na ekranie komputera i przeanalizować
• Badając złożoność obliczeniową operacji, proszę się zastanowić jak powina wyglądać zależność \(t(n)\) czasu wykonania problemu (\(t\)) od rozmiaru problemu (\(n\)) i nanieść tą hipotezę na odpowiedni wykres. Wystarczy jeden wykres dla wybranej operacji w danym problemie.
• Kilka wykresów dla zadania B z różną liczbą “klas” albo “porcji” na które może wskazywać funkcja haszująca: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …, 100
• W większości zadań nie jest określony typ danych elementów zbioru. Można korzystać na przykład z liczb całkowitych. Nie powinno mieć to większego znaczenia