Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Algorytmy tekstowe

Informacje ogólne

Kod przedmiotu: 1000-2N09ALT Kod Erasmus / ISCED: 11.303 / (0612) Database and network design and administration
Nazwa przedmiotu: Algorytmy tekstowe
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Przedmioty obieralne stałe dla informatyki
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
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 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.

Metody i kryteria oceniania:

Ocena końcowa na podstawie egzaminu pisemnego oraz aktywności na ćwiczeniach.

Zajęcia w cyklu "Semestr zimowy 2016/17" (zakończony)

Okres: 2016-10-01 - 2017-01-27
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Wojciech Rytter
Prowadzący grup: Jakub Radoszewski, Wojciech Rytter
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr zimowy 2017/18" (jeszcze nie rozpoczęty)

Okres: 2017-10-01 - 2018-01-27

Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Wojciech Rytter
Prowadzący grup: Jakub Radoszewski, Wojciech Rytter
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.