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.

Proponowane tematy projektów:

Tematy na ocenę 4.0:

1. Szyfr Cezara i szyfr Vigenère'a;
2. 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,
i) sortowanie metodą kopcowanie i Quicksort,
j) sortowanie przez scalanie i kopcowanie.

Tematy na ocenę 4.5:

1. Algorytmy sortowania plików:
a) Sortowanie polifazowe plików
2. Algorytmy (metody) kompresji:
a) metoda Huffmana,
b) ByteRun i RLE (Run Length Encoding).
3. Odwrotna notacja polska;
4. Algorytmy (funkcje) mieszające (haszujące):
a) Składanie z przesuwaniem i składanie brzegami,
b) dzielenie i środek kwadratu,
c) Zamiana podstawy i wycinanie.

Tematy na ocenę 5.0:

1. Algorytmy kompresji słownikowej:
a) LZ77,
b) LZ78,
c) LZW.
2. Algorytm konika szachowego;
3. Algorytmy zapobiegania (usuwania) kolizji:
a) metoda łańcuchów osobnych i łańcuchów połączonych,
b) próbkowanie liniowe i mieszanie podwójne,
c) próbkowanie kwadratowe i mieszanie podwójne,
d) próbkowanie liniowe i metoda łańcuchów połączonych,
e) metoda łańcuchów połączonych z obszarem nadmiarowym i bez obszaru nadmiarowego,
f) adresowanie kubełkowe z obszarem nadmiarowym i bez obszaru nadmiarowego.
4. 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.
5. 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
6. 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.

Możliwe jest również zgłaszanie własnych tematów projektów.