Algorytmy i struktury danych - Informatyka

Zajęcia laboratoryjne kończą się zaliczeniem, na którego ocenę składają się oceny z 5 zadań (programy, sprawozdania, kodowanie na zajęciach). Zadania studenci wykonują w grupach max 2-osobowych.
Za każdy program można uzyskać max. 3 punkty, za sprawozdanie max. 2 punkty. Spóźnienie z oddaniem programu karane jest -0.5 punkta za każdy tydzień, a z oddaniem sprawozdania -0.1 za każdy dzień spóźnienia.
Obie osoby z grupy muszą być obecne przy oddawaniu każdego zadania (wyjątek - usprawiedliwienie lekarskie). Prowadzący wybiera, która osoba będzie odpowiadala na pytania związane z programem lub/i sprawozdaniem.

Plan zajęć

Wymagania do sprawozdań

Zadania zaliczeniowe

Zadanie pierwsze (Algorytmy sortowania)

• zaimplementuj następujące algorytmy: insertion sort, shell sort (z przyrostami Sedgewicka), selection sort, heap sort oraz rekurencyjny quick sort z wyborem klucza/pivota jako skrajnie lewego oraz jako losowego elementu
• wygeneruj n-elementowe zbiory wejściowe; ciąg danych jest ułożony w sposób losowy, rosnący, malejący, stały, A-kształtny (rosnąco-malejący, np. 1,3,5,7,9,8,6,4,2)

• dla podanej z klawiatury liczby n wyświetl tablicę przed sortowaniem oraz po posortowaniu wybranym algorytmem sortowania
• wybór algorytmu i ciągu wejściowego poprzez menu lub poprzez (sprawne) zakomentowanie kodu

• dla każdego algorytmu porównaj efektywność jego działania w zależności od danych wejściowych (6 wykresów - dla każdego algorytmu)
• wykresy pokaż podczas oddawania programów, oraz umieść w sprawozdaniu

Zadanie drugie (Złożone struktury danych)

• Zaimplementuj algorytm konstruowania drzewa AVL metodą połowienia binarnego oraz algorytm konstruowania drzewa BST z tablicy (bierzemy kolejne elementy ciągu liczbowego i wstawiamy je do drzewa). W trakcie tworzenia zmierz wysokość drzewa (czyli wysokość najdłuższej gałęzi).
• Zaimplementuj procedury obsługujące następujące operacje na obu drzewach:
  
  • wyszukanie w drzewie elementu o najmniejszej i największej wartości i wypisanie ścieżki poszukiwania (od korzenia do elementu szukanego),
  • usunięcie elementu drzewa o wartości klucza podanej przez użytkownika (użytkownik wpisuje ile węzłów chce usunąć i podaje wartości kluczy),
  • wypisanie wszystkich elementów drzewa w porządku in-order oraz pre-order,
  • usunięcie całego drzewa element po elemencie metodą post-order,
  • równoważenie drzewa przez rotacje (algorytm DSW).
• Dane wejściowe: n-elementowy ciąg liczb naturalnych wczytywany z klawiatury (n<=10) oraz generowany przez generator danych będący częścią programu. Proszę zapewnić odporność na błędy.
• Po wykonaniu procedury wybranej przez użytkownika program wraca do menu (w pętli, dopóki użytkownik nie wybierze opcji wyjścia z programu). Program powinien wyświetlać informacje o wyniku zakończonej procedury.

• (i) tworzenie drzewa AVL metodą połowienia binarnego oraz (ii) tworzenie drzewa BST poprzez wstawianie kolejno elementów (drzewo zdegnerowane),
• wyszukiwanie elementu o maksymalnej wartości,
• wypisywanie wszystkich elementów drzewa (in-order),
• równoważenia drzewa BST (algorytm DSW).

Zadanie trzecie (Algorytmy grafowe)

• Wygeneruj spójny skierowany graf acykliczny o n wierzchołkach
  - współczynnik nasycenia łukami w grafie powinien być równy 50% (czyli 50% z n(n-1)/2)
  - najłatwiej jest utworzyć graf acykliczny skierowany poprzez wypełnienie odpowiednią liczbą jedynek górnego trójkąta macierzy sąsiedztwa
• Graf może zostać utworzony również poprzez podanie z klawiatury wierszy macierzy sąsiedztwa
• Graf jest reprezentowany poprzez macierz sąsiedztwa, listę następników oraz tabelę krawędzi - wyświetl je.
• Zaimplementuj funkcje przechodzenia grafu wszerz i w głąb (z wyświetlaniem).
• Zaimplementuj dwa algorytmy sortowania topologicznego dla każdej z reprezentacji zgodnie z:
  
  • Algorytmem Tarjana (w głąb - etykietowanie wierzchołków)
    
  • Algorytmem Kahna (wszerz - usuwanie wierzchołków z zerowym stopniem wejściowym)
    
• Po utworzeniu grafu (losowo lub z klawiatury) użytkownik może dla tego grafu wykonać dowolne procedury przeglądania lub sortowania grafu

• dokonaj pomiaru czasu działania algorytmów dla każdej reprezentacji grafu (przechodzenie grafu wszerz i w głąb oraz sortowanie topologiczne algorytmem Tarjana i Kahna)
  
• ogólne idee algorytmów, mają być takie same dla różnych reprezentacji grafu, różnice wynikają z innej złożoności wyszukiwania następników w grafie
  
• nie należy przekształcać każdej reprezentacji np. w liste następników, a nastepnie sortować
  
• nie należy upraszczać algorytmów ze względu na przygotowanie danych wejściowych (np. macierz sąsiedztwa jest górnotrójkątna i tylko tam sprawdzamy czy są łuki)
  
• Pomiary czasu przedstaw na wykresie t=f(n), dla 10 różnych wartości n

Zadanie czwarte (Algorytmy z powracaniem)

• Utwórz graf spójny nieskierowany o n wierzchołkach i zadanym nasyceniu grafu (wybierz dowolną reprezentację grafu)
• Współczynnik nasycenia krawędziami w grafach powinien być równy odpowiednio 30% i 70%. Utwórz najpierw cykl Hamiltona w grafie (losując kolejne wierzchołki), a nastepnie dopełnij graf krawędziami wg. współczynnika nasycenia w taki sposób, aby stopień każdego wierzchołka był parzysty (np. poprzez losowanie krótkich cykli złożonych z 3 wierzchołków).
• Utwórz graf nieskierowany nie-hamiltonowski o nasyceniu 50% (można utworzyć graf jak powyżej, a na końcu izolować jeden z wierzchołków)
• Zaimplementuj algorytm znajdowania cyklu Eulera w grafie
• Zaimplementuj algorytm z powracaniem znajdowania cyklu Hamiltona w grafie
• Po utworzeniu grafu (losowo lub z klawiatury) użytkownik może dla tego grafu wykonać dowolne procedury wyświetlania grafu lub znajdowania cykli E i H

• Wygeneruj grafy hamiltonowskie nieskierowane dla 10 różnych wartości n oraz dla nasycenia grafu 30% oraz 70%,
• Dokonaj pomiaru czasu działania algorytmów znajdowania cyklu Eulera i Hamiltona dla wygenerowanych grafów wyniki przedstaw na dwóch wykresach t=f(n)
• Wygeneruj grafy nie-hamiltonowskie nieskierowane dla kilku różnych wartości n (n jest małe, ok 20-30) oraz dla nasycenia grafu 50%,
• Dokonaj pomiaru czasu działania algorytmów znajdowania cyklu Hamiltona dla wygenerowanych grafów wyniki przedstaw na wykresie t=f(n)

Zadanie piąte (Problem plecakowy)

Wyjeżdżając na wycieczkę musisz spakować plecak o maksymalnej pojemności C. Do plecaka spakuj takie przedmioty, aby ich wartość była jak największa, a jednocześnie ich objętość nie przekroczyła pojemności plecaka. Wyznacz te elementy za pomocą algorytmu programowania dynamicznego oraz algorytmu brute force.

• Wygeneruj zbiór n przedmiotów, dla każdego podając jego objętość (w_i) i wartość (p_i). Wartości n oraz C dobierz eksperymentalnie. Dane te umieść w pliku, w następujący sposób:
  C
  n
  p₁ w₁
  p₂ w₂
  ...
  p_n w_n
  
• Zaimplementuj algorytm programowania dynamicznego (PD) oraz algorytm siłowy (brute force), które rozwiążą problem poszukiwania najbardziej wartościowego zbioru przedmiotów. Dane do obliczeń mają być wczytywane z plików (przynajmniej na potrzeby zajęć - turniej zaliczeniowy). Zasady turnieju przedstawię w terminie póŸniejszym na slacku.
• Porównaj efektywność działania algorytmów dla tych samych instancji testowych poprzez pomiar czasu obliczeń (dla 10-15 różnych punktów pomiarowych).
• Przedstaw wyniki na wykresach (lub w formie tabelki) t=f(n) (dla stałej pojemnośći plecaka c) oraz t=f(c) (dla stałej liczby przedmiotów n)
• Zastanów się nad wnioskami dotyczącymi zastosowanych metod oraz ich złożoności obliczeniowej. Do jakiej klasy problemów należy rozważany problem?