University of Warsaw - Central Authentication System

Algorithmic Model Theory

General data

Course ID:	1000-2M24ATM
Erasmus code / ISCED:	(unknown) / (unknown)
Course title:	Algorithmic Model Theory
Name in Polish:	Algorytmiczna teoria modeli
Organizational unit:	Faculty of Mathematics, Informatics, and Mechanics
Course groups:	Elective courses for Computer Science Subjects for PhD students
ECTS credit allocation (and other scores):	6.00 Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
Language:	English
Requirements:	Discrete mathematics 1000-212bMD
Prerequisites (description):	(in Polish) Wiedza z przedmiotów Logika dla Informatyków 1000-217bLOG oraz Grafy Rzadkie 1000-2M12GRZ będzie pomocna w niektórych częściach materiału, ale nie jest wymagana.
Short description:	The lecture connects elements of structural graph theory, parameterised algorithms, and finite model theory. The main theme are algorithmic results called “algorithmic meta-theorems”, which express that entire families of computation problems can be solved efficiently on inputs enjoying specific structural properties. Typically we will consider graph problems for graphs of a particular form. For instance, every computational problem that can be expressed as a first-order sentence can be solved in linear time, on all planar graphs, or all graphs with maximum degree bounded by a fixed constant. This result can be extended to other graph classes (including nowhere dense graph classes, and monadically stable graph classes), and other logics. Note: Course given in English
Full description:	1. The problem of evaluating logical formulas on graphs – computational complexity 2. Graphs of bounded treewidth and bounded clique-width; evaluation of MSO formulas 3. Locality of First-order logic 4. Graphs of bounded maximum degree; evaluation of first-order formulas 5. Graphs of bounded local treewidth 6. Nowhere dense graph classes; evaluation of first-order formulas 7. Monadically stable and monadically NIP graph classes 8. Elements of combinatorics of set systems – Vapnik-Chervonenkis dimension, Sauer-Shelah Lemma, Welzl orders
Bibliography:	Szymon Toruńczyk, Lecture Notes in Finite Model Theory Martin Grohe, Stephan Kreutzer, Methods for Algorithmic Meta Theorems Notes and publications pointed by the lecturer
Learning outcomes:	(in Polish) 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).
Assessment methods and assessment criteria:	Homework (50%) and oral exam (50%). The course can provide credit for doctoral students as a "methodological course". In that case, there is an additional requirement for passing the course: the student should correctly solve at least one of the more difficult problems from homeworks, designated by the instructors as a "research problem".

Classes in period "Winter semester 2024/25" (future)

Time span:	2024-10-01 - 2025-01-26	Selected timetable range: weekly course term Navigate to timetable
Type of class:	Classes, 30 hours more information Lecture, 30 hours more information
Coordinators:	Szymon Toruńczyk
Group instructors:	Szymon Toruńczyk
Students list:	(inaccessible to you)
Examination:	Examination

Course descriptions are protected by copyright.
Copyright by University of Warsaw.