Algorytmy tekstowe 1000-2N09ALT
1. Wprowadzenie do podstawowych własności tekstów.
2. Prosta kombinatoryka okresowości
3. Zaawansowane algorytmy wyszukiwania dokładnych wystąpień wzorca.
4. Drzewa sufiksowe.
5. Grafy podsłow.
6. Powtórzenia w tekstach.
7. Symetrie w tekstach.
8. Kompresja.
9. Teksty dwuwymiarowe.
10. Problemy związane z biologia obliczeniową.
11. Problemy tekstowe związane z generacją fraktali dwuwymiarowych.
12. Zaawansowane algorytmy wyszukiwania przybliżonych wystąpień wzorca.
13. Równania na tekstach.
14. Algorytmy na skompresowanych tekstach.
Rodzaj przedmiotu
Założenia (lista przedmiotów)
Koordynatorzy przedmiotu
Efekty kształcenia
Student ma wiedzę o podstawowych problemach i technikach algorytmiki tekstów, w szczególności:
1. Ma uporządkowaną wiedzę w zakresie dowodzenia poprawności algorytmów i konstrukcji algorytmów efektywnych
2. Zna najważniejsze własności kombinatoryki słów
3. Ma podstawową wiedzę w zakresie podstawowych struktur danych związanych z tekstami
4. Zna podstawowe algorytmy takie jak Knutha-Morrisa-Pratta Boyera-Moore'a i Karkainena Sandersa
5. Potrafi zaprojektowac szybki algorytm związany z ciągami, tekstami i drzewami
Umiejętności (K_U07):
Potrafi samodzielnie zrozumieć problem algorytmiczny z tej dziedziny, dokonać jego analizy i zaproponować wydajne rozwiązanie algorytmiczne.
Kompetencje społeczne (K_K01-K_K09):
Potrafi wyszukiwać informację fachową w dostępnych źródłach i oceniać ich wiarygodność i przydatność.
Rozumie znaczenie własności intelektualnej w korzystaniu z cudzych wyników.
Kryteria oceniania
Ocena końcowa jest wynikiem z egzaminu pisemnego. Najbardziej aktywne osoby na ćwiczeniach będą zwolnione z egzaminu.
W przypadku zaliczania przedmiotu przez doktoranta, dodatkowym elementem zaliczenia będzie zapoznanie się z oryginalnym, będącym blisko aktualnego frontu badań, artykułem naukowym i rozmowa z wykładowcą na temat tego artykułu.
Literatura
1. M. Crochemore, W. Rytter, Text algorithms, książka dostępna za darmo w: http://www.mimuw.edu.pl/~rytter/BOOKS/text-algorithms.pdf
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: