Algorytmiczna teoria modeli 1000-2M24ATM
1. Problem ewaluacji formuł logicznych na grafach – złożoność obliczeniowa
2. Grafy o ograniczonej szerokości drzewiastej oraz o ograniczonej szerokości klikowej; ewaluacja formuł logiki MSO
3. Lokalność logiki pierwszego rzędu
4. Grafy o ograniczonym stopniu; ewaluacja formuł logiki pierwszego rzędu
5. Grafy o lokalnie ograniczonej szerokości drzewiastej
6. Klasy nigdziegęste; ewaluacja formuł logiki pierwszego rzędu
7. Klasy monadycznie stabilne i monadycznie NIP
8. Elementy kombinatoryki rodzin zbiorów – wymiar Vapnika-Chervonenkisa, lemat Sauer-Shelah, porządki Welzla
Wymagania (lista przedmiotów)
Założenia (opisowo)
Koordynatorzy przedmiotu
Efekty kształcenia
Wiedza:
Zna różne własności klas grafów oraz ich algorytmiczne meta-twierdzenia: dla klas o ograniczonej szerokości klikowej, dla klas nigdziegęstych, dla klas monadycznie stabilnych; rozumie związki pomiędzy tymi pojęciami. Potrafi wskazać przykładowe zastosowania teorii grafów rzadkich ze szczególnym uwzględnieniem zastosowań w projektowaniu algorytmów parametryzowanych. (K_W01, K_W02)
Umiejętności:
Potrafi zastosować poznane własności kombinatoryczne do rozwiązywania problemów matematycznych oraz algorytmicznych, również pojawiających się w pracy naukowej. (K_U02, K_U09)
Kompetencje:
Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia, w tym zdobywania wiedzy pozadziedzinowej (K_K01). Potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania (K_K02). Rozumie potrzebę systematycznego zapoznawania się z czasopismami naukowymi i popularnonaukowymi w celu poszerzania i pogłębiania wiedzy (K_K08).
Kryteria oceniania
Prace domowe (50%) oraz egzamin ustny (50%).
Przedmiot można zaliczać w ramach studiów doktoranckich jako przedmiot metodologiczny. Wówczas dodatkowym warunkiem zaliczenia jest rozwiązanie co najmniej jednego z trudniejszych zadań z prac domowych, określonych przez prowadzących jako zadania "badawcze".
Literatura
Szymon Toruńczyk, Lecture Notes in Finite Model Theory
Martin Grohe, Stephan Kreutzer, Methods for Algorithmic Meta Theorems
Notatki i artykuły badawcze wskazane przez wykładowcę
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: