Spectrum problem
Problém spektra
bakalářská práce (OBHÁJENO)
Zobrazit/ otevřít
Trvalý odkaz
http://hdl.handle.net/20.500.11956/118876Identifikátory
SIS: 210273
Kolekce
- Kvalifikační práce [10691]
Autor
Vedoucí práce
Oponent práce
Šaroch, Jan
Fakulta / součást
Matematicko-fyzikální fakulta
Obor
Matematika pro informační technologie
Katedra / ústav / klinika
Katedra algebry
Datum obhajoby
29. 6. 2020
Nakladatel
Univerzita Karlova, Matematicko-fyzikální fakultaJazyk
Angličtina
Známka
Výborně
Klíčová slova (česky)
Scholzův problém, spektrum, Asserův problém, zobecněné spektrum, Cobhamova větaKlíčová slova (anglicky)
Scholz's problem, spectrum, Asser's problem, generalized spectrum, Cobham's theoremV této práci se věnujeme spektrům sentencí prvního řádu. Nejprve předvedeme kon- strukci několika zajímavých příkladů spekter a poté ukážeme, že je třída všech spekter uzavřena na několik jednoduchých množinových a algebraických operací. Poté definu- jeme novou třídu definovatelných operací, která zobecní předchozí konstrukce. Hlavním výsledkem práce je důkaz toho, že je třída těchto funkcí uzavřena na určitý druh iterace. Toto nám ve spojení s Cobhamovou charakterizací FP nabízí nový důkaz Faginovy věty a také Jonesovy-Selmenovy charakterizace spekter jako NE množin. 1
We study spectra of first-order sentences. After providing some interesting examples of spectra we show that the class of spectra is closed under some simple set-theoretic and algebraic operations. We then define a new class of definable operations generalizing the earlier constructions. Our main result is that the class of these operations is, in a suitable technical sense, closed under a form of iteration. This in conjunction with Cobham's characterisation of FP offers a new proof of Fagin's theorem and also of the Jones-Selman characterisation of spectra as NE sets. 1
Citace dokumentu
Metadata
Zobrazit celý záznamSouvisející záznamy
Zobrazují se záznamy příbuzné na základě názvu, autora a předmětu.
-
Metody řešení vybraných dopravních problémů a jejich implementace.
Výsledek obhajoby: OBHÁJENODrobný, Michal (Univerzita Karlova, Matematicko-fyzikální fakulta, 2014)Datum obhajoby: 20. 1. 2014S různými typy dopravních problémů se v praxi setkáváme velmi často. Tento problém lze chápat především jako rozvoz zboží od dodavatelů k odběratelům s cílem minimalizace distribučních nákladů. Reálné dopravní problémy se ... -
Promises in Satisfaction Problems
Výsledek obhajoby: OBHÁJENOAsimi, Kristina (Univerzita Karlova, Matematicko-fyzikální fakulta, 2023)Datum obhajoby: 14. 8. 2023Short Abstract This thesis focuses on the complexity of the promise version of Constraint Satisfaction Problem (CSP) and its variants. The first study concerns the Promise Constraint Satisfaction Problem (PCSP), which ... -
Optimization Problems under (max; min) - Linear Constraint and Some Related Topics
Výsledek obhajoby: OBHÁJENOGad, Mahmoud Attya Mohamed (Univerzita Karlova, Matematicko-fyzikální fakulta, 2015)Datum obhajoby: 16. 2. 2015Title: Optimization Problems under (max, min)-Linear Constraints and Some Related Topics. Author: Mahmoud Gad Department/Institue: Department of Probability and Mathematical Statis- tics Supervisor of the doctoral thesis: ...