Propozycje tematów prac dyplomowych
inżynierskich
na rok akademicki 2023 / 2024
1.
Program grający w
tryktraka z wykorzystaniem uczenia ze wzmocnieniem
(A backgammon playing program based on reinforcement learning)
TEMAT ZAREZERWOWANY
Informacje
o grze:
https://pl.wikipedia.org/wiki/Tryktrak
https://en.wikipedia.org/wiki/Backgammon
Podstawy
RL:
https://pduch.kis.p.lodz.pl/UzW/Wyklad.pdf
https://pduch.kis.p.lodz.pl/GUzW/Wyklad.pdf
2.
Równoległe
warianty sortowania pozycyjnego
(Parallel radix sort variants)
Podstawowym celem części praktycznej pracy jest
implementacja równoległa (tj. na wątkach) algorytmu LSD radix
sort (idea jest opisana pod
https://cs.stackexchange.com/questions/6871/how-does-the-parallel-radix-sort-work),
w języku C++ oraz jego testy wydajnościowe.
Sortowanie ma działać dla kilku podstawowych typów
danych, m.in. int/int32_t, unsigned
int/uint64_t, int/int64_t, unsigned int/uint64_t, float, double.
3.
Reprezentacje
tekstu i wybrane algorytmy tekstowe w Javie
(Text representations and selected text algorithms in Java)
Tekst (napis) w Javie przechowywany w jest
strukturze niemutowalnej (String)
lub mutowanej (StringBuilder, StringBuffer).
Zaletą np. StringBuilder jest efektywność modyfikacji
napisu przy operacji dodania znaków na końcu (append),
ale czas modyfikacji napisu w jego
środku ma złożoność liniową. Alternatywą pozbawioną tej wady jest struktura
drzewiasta typu „rope”.
W pracy należałoby zrealizować uproszczoną (tylko
2-poziomową) wersję „rope” (w skrócie ArrayList obiektów typu StringBuilder),
o API przystającym do JDK (np. struktura ta powinna implementować interfejs CharSequence). Dodatkowe zadania to implementacja kilku
szybkich algorytmów wyszukiwania dokładnego i przybliżonego w tekście.
Istotną część pracy powinny stanowić testy
poprawnościowe i wydajnościowe, a także porównanie funkcjonalności i wydajności
z rozwiązaniami z zewn. bibliotek, np.
4.
Porównanie
eksperymentalne algorytmów wykorzystujących kolejkę priorytetową
(An experimental
comparison of priority queue based algorithms)
Chodzi
głównie o problem sortowania (z wykorzystaniem różnych implementacji kolejki
priorytetowej) oraz algorytm Dijkstry.
Podstawowa
literatura:
https://epubs.siam.org/doi/epdf/10.1137/1.9781611973198.7
5.
Biblioteka
szybkich operacji listowych w Pythonie
(A Python library with fast list operations)
Lista
(typ „list”) jest podstawową sekwencyjną strukturą danych w języku Python, implementowaną jako dynamiczna tablica. Ma ona
jednak kilka wad:
·
przechowuje
dowolne obiekty, co nie sprzyja szybkości ani oszczędności pamięci (wady tej
nie ma numpy.ndarray),
·
modyfikacja listy
„w środku” (wstawienie lub usunięcie elementu) ma złożoność O(n),
gdyż wymaga przesunięcia dużej liczby elementów,
·
nie jest
domyślnie posortowana, co nieraz byłoby pożądane (można wprawdzie wywołać
metodę sort lub funkcję globalną sorted, ale czas
tej operacji to O(n log n) i po każdej modyfikacji trzeba ponownie sortować). Sortowanie
umożliwia np. znajdowanie następnika/poprzednika w czasie O(log n).
Celem
projektu jest zaimplementowanie kolekcji listowej usuwającej co najmniej dwie z
trzech powyższych wad zwykłej listy. Zalecana realizacja w C (C-extension). Testy wydajnościowe powinny obejmować
konkurencję, m.in.
·
https://grantjenks.com/docs/sortedcontainers/
·
https://pypi.org/project/blist/
·
tablicę (1D) numpy (tj. numpy.ndarray)
·
oraz wybrane
implementacje wyliczone pod https://grantjenks.com/docs/sortedcontainers/performance.html
Zalecane
narzędzie do pomiaru zużycia pamięci to
https://github.com/pympler/pympler
(Sugestie
odnośnie realizacji (szczegółów struktury danych) – w indywidualnej rozmowie.)
6.
Program do
rozwiązywania wybranych typów zadań z treścią z kombinatoryki
(A program for solving selected types of word problems in combinatorics)
Zakładamy
np. ograniczenie do zadań „karcianych”. Czyli zadania typu (np.): Z talii 52 kart wylosowano bez zwracania 4
karty. Jakie jest prawdopodobieństwo, że jest wśród nich dokładnie jeden walet,
pod warunkiem, że co najmniej 3 karty są czerwone?
Wersja
ambitniejsza problemu: program dostaje na wejściu sformułowania (w języku
polskim), podobne do opisanego, ale przy założeniu dużej formalizacji
sformułowań (np. dopuszczamy „Z talii [52|32|24] kart”, ale nie: „Z talii,
która liczy 52 karty”), a następnie demonstruje rozwiązanie krok po kroku w
sposób „dydaktyczny” (np. wprowadzając oznaczenia pośrednie i odpowiednio je
opisując). Program może stwierdzić: „nie zrozumiałem treści zadania” (byle nie
robił tego zbyt często ;-).
Wersja
mniej ambitna: cel podobny, ale nie wprowadzamy treści zdania w postaci
tekstowej, ale korzystamy z kreatora (GUI), w którym wybieramy kryteria (np.
ile wylosowanych kart, czy ze zwracaniem, czy bez zwracania, o który kolor czy
którą wartość kart chodzi, czy są dodatkowe warunki, czy połączone spójnikiem
I, czy LUB, etc.). Na podstawie danych
wprowadzonych do kreatora program mógłby też generować treść zadania (w języku
polskim).
Problematyka
zadań: kombinacje, permutacje, prawdopodobieństwo warunkowe etc. (ogólnie
biorąc, kombinatoryka z zakresu szkoły średniej). Ograniczenie tematyki treści zadań do kart
pozwala na formalizację sformułowań – ale możliwa ewent. inna tematyka.
7.
Estymacja
entropii partii szachowej
(Entropy estimation for a chess game)
Entropia to stopień niepewności wystąpienia danego
zdarzenia elementarnego.
Celem pracy jest implementacja kompresora ruchów
partii szachowej (w wersji trochę ambitniejszej: kompresora formatu PGN)
korzystającego przy predykcji z silnika szachowego, zwracającego w danej
pozycji dozwolone ruchy od najsilniejszego (tj. również jednego z najbardziej
prawdopodobnych, przy założeniu, że partia jest rozgrywana przez silnych
graczy) do najsłabszego (więc również najmniej prawdopodobnego). Otrzymane
wyniki kompresji powinny być porównane z analogiczną kompresją zapisu partii
przy użyciu kompresorów ogólnego przeznaczenia (np. 7z/LZMA czy zstd) lub też prostego kompresora specjalizowanego.
(Informacje dodatkowe w indywidualnej rozmowie.)
8.
OCR dla obiektów
geometrycznych
(OCR for geometric
primitives)
Schematy,
diagramy czy rysunki poglądowe często robimy na kartce (zamiast w dedykowanym
oprogramowaniu jak MS Visio). Celem pracy jest
·
rozpoznanie
podstawowych obiektów geometrycznych (linii prostych, kół, prostokątów,
trójkątów etc.) na zdjęciu takiej kartki,
·
rozpoznanie ich
właściwości i wzajemnych relacji (np. prostokąt: równoległy do osi XY czy
obrócony? jakie proporcje boków? Czy linia prosta przechodzi nad kołem, pod
kołem, z lewej, z prawej, jest do niego styczna (np. od góry), przechodzi przez
koło jako (pewna) cięciwa, przechodzi przez koło jako średnica?),
·
zapis do postaci
wektorowej (preferowany SVG), opcjonalnie również w postaci rastrowej (PNG),
·
zapewnienie
możliwości konfiguracyjnych (np. ustawienie domyślnego stylu i koloru linii).
W
realizacji zalecane klasyczne techniki przetwarzania obrazów (zmniejszenie
rozdzielczości, pocienianie (thinning), transformata Hougha etc.).
(Informacje
dodatkowe w indywidualnej rozmowie.)
9.
Program
rozwiązujący wypełnianki słowne
(A tool for solving fill-in crossword puzzles)
Inspiracją pracy jest artykuł
https://arxiv.org/abs/2109.11203
Przykładowy problem ilustruje poniższy obrazek z
cytowanej pracy:
Zakładamy język polski lub angielski, spośród
którego mają być dozwolone wstawiane słowa. Aplikacja ma pozwalać na utworzenie
układu krzyżówki, ustawienie wag liter (pod kątem danego języka) oraz progu
sumy wag – następnie szuka (co najmniej jednego) rozwiązania, metodami
heurystycznymi.
10. Program do układania krzyżówek panoramicznych
(A tool for creating clues-in-squares
crossword puzzles)
Krzyżówka panoramiczna to krzyżówka, w której
definicje haseł znajdują się w obrębie prostokątnego diagramu krzyżówki (muszą
one być dość krótkie). Celem pracy jest napisanie generatora krzyżówek dla
języka polskiego. Baza definicji dla słów (w tym nazw własnych) różnej długości
będzie dostarczona przez prowadzącego; może ona jednak wymagać pewnego preprocessingu czy filtracji (np. eliminacji/skrócenia zbyt
długich definicji).
Parametry wejściowe generatora: rozmiar krzyżówki X
na Y (być może: od-do), być może: liczba haseł (mniejsza liczba dla danego
rozmiaru oznacza, że hasła są zwykle krótsze).
Oczywiście przy pewnych parametrach krzyżówka może być „nie do ułożenia”
(przynajmniej w rozsądnym czasie), wtedy trzeba przerwać generację.
Wygenerowaną krzyżówkę należy zapisać nie tylko w postaci obrazka (np. PNG) czy
PDF-a, ale także tekstowo, w dogodnym formacie.
Sugerowana platforma / technologie: aplikacja
desktopowa, Python + PyQt
(ale mogą być też inne).
11.
Biblioteka
programistyczna wspierająca wizualizację struktur drzewiastych
(A programming library supporting tree data structure visualization)
Technologia
dowolna (np. JavaFX, PyQt, Matplotlib, WPF). Cel aplikacji dydaktyczny. Biblioteka ma
umożliwiać:
· wygodne definiowanie kształtu drzewa (najlepiej
niekoniecznie binarnego),
· łatwe przekształcanie sekwencji danych na drzewo BST
(wstawianych w podanej kolejności),
· wizualizację drzewa, zgodnie z konfiguracją (np.
kształt węzłów, styl/kolor linii krawędzi etc.),
· wykonywanie podstawowych transformacji na drzewie (np.
usunięcie liścia, rotacja),
· zapis obrazu do popularnych formatów wyjściowych
(najlepiej także wektorowych, jak SVG).
Mile
widziane: wsparcie dla animacji.
12.
Ekstrakcja i
zarządzanie użyteczną wiedzą z serwisu Stack Overflow
(Extraction and management of useful snippets of knowledge from the
Stack Overflow service)
Przy
korzystaniu ze Stack Overflow
wygodnie byłoby zapisać (w celu np. przejrzenia w przyszłości) informację,
która nam istotnie pomogła, wydała się bardzo trafna czy zwięźle ujmująca jakąś
kwestię. Ręczne skopiowanie jest dość kłopotliwe. Przykład: chcemy dowiedzieć
się „na szybko” czym jest serializacja w Javie,
trafiamy na stronę
https://stackoverflow.com/questions/3429921/what-does-serializable-mean
i tam spodobało nam się
zdanie: „Serialization involves saving the current
state of an object to a stream, and restoring an equivalent object from that
stream.”
Chcemy
w możliwie wygodny sposób zapisać: pytanie, znaczniki (tu: java,
serializable; to ważne, bo czasem odpowiedź może
dotyczyć innego języka/technologii i tym samym być myląca), datę pytania i
odpowiedzi, autora odpowiedzi, jego reputację, jak i stan głosów na konkretną
wypowiedź zawierającą dany cytat. Być może również dyskusję pod tą odpowiedzią,
jeśli istnieje.
Aplikacja
może być dodatkiem do przeglądarki internetowej (np. Firefox,
Chrome), ale projekt można też zrealizować w inny sposób. Plugin
może zresztą tylko kopiować daną odpowiedź, która będzie zapisywana w osobnej
aplikacji, która z kolei „wyciągnie” (parsując HTML)
wskazane wyżej fragmenty/metadane i zapisze w postaci
odpowiedniej bazy (niekoniecznie SQL-owej), umożliwiającej wyszukiwanie,
filtrowanie/sortowanie w odpowiedni sposób (np.: pokaż wszystkie wpisy ze znacznikiem
„android”), etc.
13.
Zapis partii
szachowej na podstawie analizy obrazów szachownicy
(Keeping score of a chess game based
on the chessboard video sequence)
TEMAT ZAREZERWOWANY
Celem
pracy jest utworzenie aplikacji korzystającej z obrazów szachownicy w trakcie
partii (granej „tradycyjnie”, bez użycia komputera), rejestrowanych z góry (np.
telefon komórkowy na statywie) i zapisującej zmiany po każdym wykonanym ruchu.
Aplikacja ta ma tworzyć na bieżąco zapis partii, np.:
1.
e2-e4 Sg8-f6
2.
e4-e5 Sf6-e4
...
Główna
idea jest prosta: dany ruch (*) przemieszcza tylko jedną bierkę, stąd zmiany
następują tylko na dwóch polach: startowym i docelowym. Nie trzeba rozpoznawać typu (kształtu) bierki, ale istotny jest
kolor (bez tego nie można by rozpoznać niektórych bić).
(*)
Zdarzają się – rzadko – trudniejsze ruchy specjalne: roszada, bicie w
przelocie, promocja (tu najtrudniejszy przypadek: promocja w inną figurę niż
hetman).
14.
Wykrywanie i
prezentacja typowych błędów w partiach szachowych
(Detecting and visualizing common blunders in chess games)
Serwis
zawiera
(luty 2022 r.) ponad 3 miliardy (!) partii szachowych, rozegranych online, zwykle przez amatorów. Wiele z tych partii było
granych przy bardzo krótkim czasie, co sprzyja elementarnym błędom, np.
podstawkom figury w debiucie. Celem pracy jest wykrycie i wizualizacja tego
typu popularnych sytuacji.
Ok.
6% partii w bazie jest opatrzonych ewaluacją posunięć (dokonaną przez silnik
szachowy).
Inspiracją
jest film:
https://www.youtube.com/watch?v=7eevSgJqV7o
ale
w pracy trzeba zrobić więcej:
·
przefiltrować
zestaw partii (wg rankingu graczy, czasu na partię etc.),
·
zaprezentować
partie/ich fragmenty zawierające popularne duże błędy,
·
(NAJTRUDNIEJSZE)
dokonać klasteryzacji, czyli pogrupować bardzo
podobne, ale nie identyczne sytuacje, zawierające ten sam motyw błędu.
Parsowanie:
https://github.com/niklasf/python-chess
15.
Projekt i
implementacja algorytmu kompresji wykorzystującego ideę narzędzia copMEM
(Design and implementation
of a compression algorithm based on the copMEM
tool idea)
Literatura:
https://arxiv.org/abs/1805.08816
lub (prawie to samo):
Kody źródłowe:
https://github.com/wbieniec/copmem
Chodzi o projekt i implementację b. szybkiego
kompresora z rodziny LZ77, który jednak znajduje tylko długie „matche” (przykładowe zastosowanie: deduplikacja).
16.
Rozwiązywanie
łamigłówki „2048” metodami sztucznej inteligencji
(Solving the 2048 puzzle with AI methods)
TEMAT ZAREZERWOWANY
2048 jest popularną łamigłówką:
Celem pracy jest zaimplementowanie i porównanie
kilku prostych strategii osiągania możliwie dobrego wyniku.
Przykładowo, strona
http://ronzil.github.io/2048-AI/
(oraz dyskusja http://stackoverflow.com/a/23853848/632039)
opisuje bardzo prostą (a ponoć skuteczną) strategię
typu Monte Carlo.
Inne odnośniki:
https://github.com/silverstar194/2048-ai-monte-carlo
https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048
17.
Elektroniczne
kolokwium z płynną oceną odpowiedzi dla wybranych typów pytań
(Online test with a grade scale in selected question types)
W przypadku niektórych zadań (np. z matematyki,
fizyki, algorytmiki) nauczyciel potrafi rozróżnić pomiędzy drobnym błędem (np.
rachunkowym) a nieznajomością zagadnienia przez studenta. Automatyczna ocena
takiego zadania jest jednak trudna.
W proponowanym projekcie koncentrujemy się na
wybranych typach zadań/pytań „półotwartych”, gdzie odpowiedź przystaje do
założonego schematu, ale może być (częściowo) błędna – trzeba to wykryć.
Przykłady z algorytmiki:
1) Posortuj podane funkcje (oznaczmy je przez: 1, 2,
3, 4, 5, 6) od najwolniej do najszybciej rosnącej.
Powiedzmy, że prawidłowa odp. to: 2 4 1 6 5 3. Jeśli jednak student wpisze: 2 1 4 6 5 3, to mógłby
otrzymać np. 50% poprawnej odpowiedzi. A
zatem potrzebna jest pewna miara podobieństwa (bliskości) permutacji.
2) Do tablicy o zadanym rozmiarze należy wstawić
podane elementy, w kolejności, używając konkretnego wariantu haszowania (np. z
rozstrzyganiem kolizji metodą próbkowania liniowego) i zadanej funkcji
haszującej.
Tutaj jeden błąd w obliczeniach może skutkować
(zwłaszcza dla elementu blisko początku) całkiem innym układem końcowym. System powinien wyznaczać pozycję każdego
wstawionego elementu i również przy błędzie studenta liczyć dalej w dobrej
wierze. Końcową oceną za zadanie nie musi być więc tylko 100% lub 0% punktów,
ale też np. 25%, 50% czy 75%.
3) Test wielokrotnego wyboru – np. z trzech
poprawnych odpowiedzi student wskazał dwie, obie poprawnie (albo wskazał dobrze
dwie, a trzecią błędną).
Idealne rozwiązanie (być może trudne): system pluginów dla różnych typów zadań. Wtedy egzaminator, bez
ingerencji w kod, może rozszerzyć funkcjonalność aplikacji.
Akceptowalne rozwiązanie: zestaw typów zadań i
algorytmów dla nich zaszyty „na sztywno” w kodzie.
18.
Wizualizacja
podstawowych struktur danych dla celów dydaktycznych
(Visualization of basic data structures for didactic purposes)
– opiekun pomocniczy: dr inż. W. Bieniecki
Działanie niektórych algorytmów / struktur danych
można dość łatwo przedstawić w konsoli, oto przykład kompresji/parsingu LZ78.
Tekst do skompresowania:
a_cat_sat_on_a_mat
Kolejne frazy dodawane do słownika (pary: id,
fraza):
1 a
2 _
3 c
4 at
5 _s
6 at_
7 o
8 n
9 _a
10 _m
Zbiór par wyjściowych (id poprzedzającej frazy ze
słownika, nowy znak - na końcu string pusty):
[(0, 'a'), (0, '_'), (0,
'c'), (1, 't'), (2, 's'), (4, '_'), (0, 'o'), (0, 'n'), (2, 'a'), (2, 'm'), (4,
'')]
Sparsowany tekst, z separatorami (|
oraz spacja):
|a |_ |c a|t _|s at|_ |o |n _|a _|m at|
Niemniej, taka forma nie jest zbyt atrakcyjna
wizualnie. Dla celów dydaktycznych pożądane jest GUI, użycie kolorów, „pudełek”
przechowujących elementy struktury etc.
Animacje nie są konieczne.
Celem pracy byłoby napisanie narzędzia, które we
wskazanym pliku txt (forma być może jak powyżej)
rozpozna i na tej postawie odpowiednio zwizualizuje
takie elementy jak listy (obiektów prostych lub bardziej złożonych), zbiory,
słowniki etc. W przykładzie powyższym,
trzeba wykryć, że zbiór par wyjściowych to lista krotek 2-elementowych typu (int, char), przy założeniu że pusty string
na końcu zastąpimy jakimś specjalnym znakiem.
19.
Rozpoznawanie
pisma maszynowego z użyciem morfologicznego przetwarzania obrazu
(Printed text recognition with morphological image processing)
– opiekun
pomocniczy: dr inż. W. Bieniecki
Proszę
obejrzeć
https://web.stanford.edu/class/ee368/Handouts/Lectures/2016_Autumn/7-Morphological_16x9.pdf
slajdy
20–25.
Celem pracy jest sprawdzenie możliwości wykorzystania przedstawionej techniki
do rozpoznawania wyrazów w tekście maszynowym. Nawet jeśli część liter alfabetu
powoduje problemy, to ich kontekst powinien umożliwić (z pomocą słownika)
odgadnięcie danego słowa.
20.
Narzędzie do
konwersji tabel HTML do postaci systemu LaTeX
(An HTML
to LaTeX table conversion tool)
„Ręczne”
tworzenie tabel w LaTeXu jest procesem dość żmudnym.
Celem pracy jest napisanie np. dodatku do Firefoxa,
który wygeneruje kod LaTeXowy wskazanej tabeli.
Możliwe opcje konfiguracyjne: kopiuj całość tabeli lub tylko jej layout; kopiuj tylko dane z wiersza nagłówkowego, etc.
Lektura
podstawowa:
https://pl.wikibooks.org/wiki/LaTeX/Tabele
https://en.wikibooks.org/wiki/LaTeX/Tables
21. Ulepszanie funkcjonalności schowka
(Improving the clipboard mechanism)
22.
Narzędzie do
raportowania i poprawy literówek w książkach elektronicznych
(A tool for reporting and fixing typos in e-books)
23.
Spersonalizowana
przeglądarka dokumentacji klas Javy
(A personalized
Javadoc viewer)
24.
Projekt i
implementacja biblioteki algorytmów tekstowych w języku Julia
(Design
and implementation of a string matching library
in Julia programming language)
Julia
(http://julialang.org) jest względnie nowym
interesującym językiem programowania do obliczeń naukowych i inżynierskich.
Siłą tego języka jest połączenie prostej składni (przypominającej trochę Pythona) z wydajnością bliską językom C i C++. Celem pracy
jest zaimplementowanie kilku algorytmów wyszukiwania dokładnego i przybliżonego
wzorca tekstowego, również z użyciem indeksu. Istotną częścią pracy będą
również testy wydajnościowe.
25.
Efektywna
implementacja operacji odszumiających na
współczesnych platformach sprzętowych
(Effective implementation of
image noise reduction techniques on modern
hardware platforms)
Zadanie: Jak wykorzystać SSE / AVX oraz rdzenie
procesora (inne aspekty wpływające na wydajność: unikanie warunków (branchless code),
wykorzystanie cache’a L1 i L2 procesora) do
przyspieszenia wykonywania operacji odszumiających
(m.in. standardowego filtru medianowego) na obrazach. Kod w C lub C++.
Przykładowa literatura lub istniejące implementacje:
http://www.cse.cuhk.edu.hk/leojia/projects/fastwmedian/index.html
https://arxiv.org/abs/1406.1717
https://github.com/suomela/median-filter
https://github.com/timypik/Fast-Median-Filter
https://github.com/detel/Median-Filtering-GPU
https://github.com/antingshen/Weighted-Median-Filter
https://github.com/aglenis/gpu_medfilter
https://github.com/ShreyasSkandan/cuda-image-filters
26.
Efektywna
implementacja operacji morfologicznych na współczesnych platformach sprzętowych
(Effective implementation of
image morphology operators
on modern hardware platforms)
Zadanie: Jak wykorzystać SSE / AVX oraz
rdzenie procesora (a może i cache L1 lub L2) do
przyspieszenia wykonywania operacji morfologicznych na obrazach.
27.
Wizualizacja
prostych algorytmów metodą analizy kodu źródłowego
(Visualization of simple algorithms via source code analysis)
28.
Narzędzie do
automatycznej generacji tabel w systemie LaTeX na
podstawie wyników eksperymentów naukowych
(A tool for LaTeX tables generation
from scientific experimental
results)
29.
Jaka to melodia?
Projekt i implementacja quizu muzycznego
(Name that tune. Design and
implementation of a musical quiz)
30.
Efektywna
reprezentacja statystyk n-gramów Google Books z obsługą zapytań
(Efficient representation of
Google Books n-grams with query support)
Należy
ściągnąć wybrane zbiory (1-gramów, 2-gramów, …, 5-gramów) z kolekcji:
http://storage.googleapis.com/books/ngrams/books/datasetsv2.html
i zaimplementować
specjalizowany (ale nietrudny) algorytm kompresji tych danych oraz algorytmy
wyszukiwania n-gramów
(być może na podstawie ich fragmentów).
Kompresja posłuży do przechowywania możliwie dużego podzbioru całej bazy
w pamięci RAM.
Aplikacja
GUI.
31. Efekty wizualne na stronach
WWW z wykorzystaniem wtyczek biblioteki programistycznej jQuery
(Visual effects on web pages using jQuery
programming library plugins)
TEMAT ZAREZERWOWANY
32.
Rozszerzanie funkcjonalności tablicy
sufiksowej
(Extending functionalities of the suffix array)
33. Automatyczne sprawdzanie
testów wyboru z wykorzystaniem OCR
(OCR-based multiple-choice
assessment evaluation)
– opiekun
pomocniczy: dr inż. W. Bieniecki
34. Miary podobieństwa napisów
uwzględniające percepcję człowieka
(Perception-based string similarity measures)
Lektura podstawowa:
Kondrak G. (2005), N-gram
similarity and distance,
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.2441