Tematy projektów

Projekt polega na przeanalizowaniu wybranego złożonego algorytmy lub przeprowadzeniu analizy porównawczej dwóch prostszych algorytmów. W tym celu należy napisać program, który na przykładzie niewielkiej liczby elementów losowych pokazuje działanie algorytmu/algorytmów, np. wyświetlanie danych po każdym znaczącym kroku algorytmu z zaznaczeniem elementów charakterystycznych.

Zmieniając liczbę danych (przy losowym uporządkowaniu) i uporządkowanie danych (przy stałej ich liczbie) w programie należy zliczyć liczbę kluczowych operacji (np. liczbę porównań liczb, liczbę zamian liczb, liczbę odwiedzonych węzłów grafu, liczbę iteracji przejść listy, itp.). Analizę można uzupełnić pomiarem czasu wykonywania operacji. Wyniki zaprezentować w sprawozdaniu w formie tabel i wykresów (w zależności od liczby danych oraz ich uporządkowania), uzupełniając wnioskami.

Propozycje tematów projektowych:

Na ocenę 3: 

1. Algorytmy sortowania tablic:
a) Sortowanie przez proste wstawianie, proste wybieranie i prostą zamianę
b) Sortowanie przez proste wstawianie i wstawianie połówkowe
c) Sortowanie bąbelkowe ze wszystkimi jego udoskonaleniami (bez quicksort)
d) Sortowanie przez proste wstawianie i metodą Shella
e) Sortowanie przez proste wybieranie i przez kopcowanie
f) Sortowanie bąbelkowe i quicksort
g) Sortowanie metodą Shella i przez kopcowanie
h) Sortowanie metodą Shella i quicksort
2. Algorytmy sortowania plików:
a) Sortowanie polifazowe plików
3. Algorytmy kompresji:
a) Metoda Huffmana
b) LZ77
c) LZ78

Na ocenę 4:

4. Szyfr Cezara i szyfr Vigenère'a;
5. Algorytm konika szachowego;
6. Odwrotna notacja polska;
7. Algorytmy mieszania:
a) Składanie z przesuwaniem i składanie brzegami
b) Środek kwadratu i wycinanie
c) Zamiana podstawy i dzielenie
8. Algorytmy zapobiegania kolizji:
a) Metoda łańcuchów osobnych i łańcuchów połączonych
b) Szukanie liniowe i mieszanie podwójne
c) Szukanie liniowe i metoda łańcuchów połączonych
d) Metoda łańcuchów połączonych z obszarem nadmiarowym i bez obszaru nadmiarowego
e) Adresowanie kubełkowe z obszarem nadmiarowym i bez obszaru nadmiarowego

Na ocenę 5:

9. Obliczanie wyrażeń arytmetycznych z użyciem drzewa;
10. Algorytmy działające na grafach:
a) Problem trwałego małżeństwa;
b) Problem komiwojażera;
c) Algorytm Floyda;
d) Algorytm Fluery'ego;
e) Metoda DFS przeszukiwania grafu;
f) Metoda BFS przeszukiwania grafu;
11. Drzewach wyższych rzędów:
a) Uniwersalna struktura słownikowa - wstawianie, usuwanie, wyszukiwanie
b) Drzewo trie - wstawianie, usuwanie, wyszukiwanie
c) Drzewo wielokierunkowe - wstawianie, usuwanie, wyszukiwanie
d) B drzewo - wstawianie, usuwanie, wyszukiwanie
e) B+ drzewo - wstawianie, usuwanie, wyszukiwanie
f) Drzewo BST - wstawianie, usuwanie, wyszukiwanie
12. Algorytmy z grafiki komputerowej:
a) Metoda z punktem środkowym rysowania odcinków
b) Metoda z punktem środkowym rysowania okręgów
c) Algorytm wypełniania rekurencyjnego 2D