Algorytmy tekstowe
Informacje ogólne
Kod przedmiotu: | 1000-2N09ALT |
Kod Erasmus / ISCED: |
11.303
|
Nazwa przedmiotu: | Algorytmy tekstowe |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
6.00
|
Język prowadzenia: | angielski |
Rodzaj przedmiotu: | monograficzne |
Założenia (lista przedmiotów): | Algorytmy i struktury danych 1000-213bASD |
Skrócony opis: |
Wykład jest poświęcony omówieniu podstawowych metod projektowania i analizowania algorytmów związanych z tekstami. Zasadniczym problemem będzie zrozumienie struktury wielu skomplikowanych algorytmów oraz różnego typu techniki algorytmiczne i struktury danych (drzewa sufiksowe, grafy podsłów). Teksty są prostym a jednocześnie powszechnym typem informacji, ale będą rozważane zarówno standardowe teksty (jako ciągi symboli), jak również bardziej strukturalne formy: teksty dwuwymiarowe (związki z grafiką) i drzewa etykietowane (struktury występujące w XML i biologii obliczeniowej). Klasyczne problemy algorytmiczne związane są z szukaniem (lub wykrywaniem) wzorca, regularnością i kompresją tekstów. Ponadto rozważymy problemy związane z biologią obliczeniową (uliniowienie, drzewa ewolucyjne) oraz ze "stringologią" fraktali dwuwymiarowych. Wiele ciekawych tekstów jest zadanych w formie skompresowanej, rozmiar rzeczywistego tekstu może być wykładniczy w stosunku do rozmiaru n jego opisu. |
Pełny opis: |
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. |
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 |
Efekty uczenia się: |
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. |
Metody i 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. |
Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)
Okres: | 2023-10-01 - 2024-01-28 |
Przejdź do planu
PN WT ŚR CW
CZ PT CW
WYK
|
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Jakub Radoszewski | |
Prowadzący grup: | Arkadiusz Czarkowski, Tomasz Nowak, Jakub Radoszewski, Wojciech Rytter | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "Semestr zimowy 2024/25" (zakończony)
Okres: | 2024-10-01 - 2025-01-26 |
Przejdź do planu
PN CW
WT ŚR CZ PT CW
WYK
|
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Jakub Radoszewski | |
Prowadzący grup: | Jakub Radoszewski, Wojciech Rytter, Wiktor Zuba | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski.