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
|
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 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Szymon Toruńczyk | |
Group instructors: | Szymon Toruńczyk | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Copyright by University of Warsaw.