Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Algorytmy tekstowe

Informacje ogólne

Kod przedmiotu: 1000-2N09ALT
Kod Erasmus / ISCED: 11.303 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
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 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

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 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
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Jakub Radoszewski
Prowadzący grup: Arkadiusz Czarkowski, Tomasz Nowak, 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.
Krakowskie Przedmieście 26/28
00-927 Warszawa
tel: +48 22 55 20 000 https://uw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)