Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Algorytmy parametryzowane

Informacje ogólne

Kod przedmiotu: 1000-2M12APW
Kod Erasmus / ISCED: 11.3 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 parametryzowane
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
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

Skrócony opis:

Wykład poświęcony będzie ponadwielomianowym algorytmom dla problemów NP-trudnych, ze szczególnym uwzględnieniem algorytmów parametryzowanych.

Wykład jest pomyślany dla studentów i doktorantów zainteresowanych algorytmiką i kombinatoryką, i rozważających pracę naukową (choćby na poziomie pracy magisterskiej).

Pełny opis:

Wykład poświęcony będzie ponadwielomianowym algorytmom dla problemów NP-trudnych, ze szczególnym uwzględnieniem algorytmów parametryzowanych.

Planujemy następujące tematy:

1. Algorytmy parametryzowane: definicja i motywacja.

2. Algorytmy rozgałęziające się. Analiza Mierz i Zwyciężaj.

3. Przegląd technik stosowanych w algorytmach ponadwielomianowych:

iterative compression, color coding, split&list, dziel i zwyciężaj, ważne separatory.

4. Zastosowania zasady włączeń i wyłączeń, algorytmy szybkiego splotu podzbiorów.

5. Techniki algebraiczne (Schwarz-Zippel oraz lemat o izolacji).

6. Algorytmy w grafach o ograniczonej szerokości drzewiastej.

7. Algorytmy podwykładnicze w grafach planarnych: bidimensionality.

8. Ograniczenia dolne: hierarchia W oraz Hipoteza Czasu Wykładniczego.

Literatura:

- Marek Cygan, Fedor Fomin, Łukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer, 2015.

- Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010.

- Rolf Niedermeier, Invitation to Fixed Parameter Algorithms, Oxford University Press, 2006.

- Jorg Flum, Martin Grohe, Parameterized Complexity Theory, Springer, 2006.

- Rod Downey, Mike Fellows, Parameterized Complexity, Springer, 1999.

Efekty uczenia się:

Wiedza:

Ma zaawansowaną wiedzę z zakresu projektowania i analizy algorytmów dokładnych dla problemów NP-trudnych oraz wyznaczania granic ich możliwości (K_W01, K_W02). W szczególności, po zajęciach student jest w stanie rozpocząć (samodzielną lub w zespole) pracę naukową nad ww. zagadnieniami.

Umiejętności:

* potrafi opracować dokładny algorytm dla średnio-trudnego problemu kombinatorycznego NP-trudnego (K_U04)

* potrafi (w rygorystyczny, formalny sposób) zanalizować algorytm, dowodząc jego poprawność i określając złożoność (K_U04)

* rozumie bardziej szczegółowe klasy złożoności wewnątrz klasy NP, w tym W-hierarchię, potrafi umieścić w niej zadany problem i przeprowadzić prostą redukcję trudności (K_U05)

* potrafi korzystać z tekstów źródłowych i podręczników w języku angielskim (K_U14)

* potrafi przygotować krótkie opracowanie wykładu w języku angielskim (K_U13)

Kompetencje

* rozumie potrzebę systematycznego zapoznawania się z czasopismami naukowymi i popularnonaukowymi w celu poszerzania i pogłębiania wiedzy (K_K08).

* potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania (K_K02).

Metody i kryteria oceniania:

Testy po każdym wykładzie (przez Moodle, na zaliczenie, 75% quizów daje modyfikator 0.5 do oceny z egzaminu ustnego), prace domowe z zadaniami (łączna suma punktów daje modyfikator do oceny z egzaminu ustnego) oraz egzamin ustny (na ocenę). Szczegółowe zasady w sekcji ogólnej w moodle.

Zajęcia w cyklu "Semestr zimowy 2022/23" (w trakcie)

Okres: 2022-10-01 - 2023-01-29
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Łukasz Kowalik, Michał Pilipczuk
Prowadzący grup: Łukasz Kowalik, Konrad Majewski, Michał Pilipczuk
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.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 6.8.0.0-e459be735 (2022-11-16)