Propozycja pól w katalogu przedmiotów

Nazwa pola	Komentarz	
	
Tytuł	Algorytmy tekstowe	
Jednostka	Wydział Matematyki, Informatyki i Mechaniki UW	
Grupy	przedmioty obieralne dla III roku informatyki 	
Kod wg USOS	<nadawany przez administrację>	
Kod wg Sokratesa	<nadawany przez administrację>	
Rodzaj zajęć	Wykład 30 godzin, Ćwiczenia 30 godzin	
	
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.
Niektóre poprzednie problemy  mają algorytmy wielomianowe (ale zupełnie inne niż poprzednio) a niektóre przechodzą do wyższych klas złożoności. Ma to związek z obliczeniami dla danych o bardzo dużym rozmiarze. Wykład ma charakter przede wszystkim algorytmiczny, ale zawierać też będzie skromny fragment kombinatoryki tekstów.	
Program 	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. 	
Proponowane źródła	1.	M. Crochemore, W. Rytter, Text algorithms, książka dostępna za darmo w: http://www.mimuw.edu.pl/~rytter/BOOKS/text-algorithms.pdf	
Wymagania	Wykład prowadzony od podstaw.	
Założenia	ASD  	
Forma zaliczenia	Egzamin	
	
Teraz informacje o charakterze zmiennym (pole edycji)	
Cykl dydaktyczny	Semestr zimowy 2009/2010	
Prowadzący	Wykład: W. Rytter,  ćwiczenia: W. Rytter