FMT: tematy egzaminacyjne

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Poniżej jest lista tematów egzaminacyjnych obowiązująca na egzaminie ustnym z Teorii Modeli Skończonych.

  1. Twierdzenie Trakhtenbrota
  2. Złożoność obliczeniowa ewaluacji (model checking) logiki FO na strukturach Skończonych
  3. Twierdzenie Fagina, dowód
  4. Gry Ehrenfeuchta-Fraisse dla FO i rodziny homomorfizmów częściowych, przykłady zastosowań.
  5. Lokalność Hanfa a lokalność Gaifmana. Przyklady zastosowań.
  6. Twierzenie Hanfa i Gaifmana. Przykłady zastosowań.
  7. Prawo 0-1 z dowodem.
  8. Logiki stałopunktowe – definicje, złożoność ewaluacji
  9. Równoważność logik stałopunktowych i klas złożoności (PTime, LogSpace, NLogSpace, PSpace), na strukturach liniowo uporządkowanych, dowody
  10. Separacja logik na klasach struktur nieuporządkowanych (IFP≠ESO, TCL≠DTCL, tw. Abiteboul-Vianu)
  11. Twierdzenie CFI, szkic dowodu
  12. Definicja “logic capturing PTime”, przykłady logik które chwytają Ptime na pewnych klasach struktur
  13. Związki istnienia wielomianowej/definiowalnej kanonizacji z istnieniem logiki chytającej PTime
  14. Algorytm color-refininement
  15. Inkluzja i minimalizacja zapytań koniunkcyjnych – z dowodami.
  16. CSP – równoważne definicje, złożoność, hipoteza Feder-Vardi
  17. Przykłady wzorców (template) CSP o różnych złożonościach
  18. Polimorfizmy – definicje, przykłady,
  19. Algorytm (k,l)-konsystencji
  20. Sformułowanie twierdzenia “majority→PTime”, przykłady wzorców które mają majority i które nie mają
  21. Złączenia acykliczne: warunki równoważne acykliczności
  22. Wielomianowy algorytm obliczania złączeń na podstawie drzewa złączeniowego.

 

Leave a Reply

Your email address will not be published. Required fields are marked *