| | |
|---|
| Údaje o projektu |
| Identifikační kód | MEB050817 |
| Důvěrnost údajů | S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů |
| Název v původním jazyce | Algebraický přístup k problému splnitelnosti omezujících podmínek |
| Poskytovatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Program | ME - KONTAKT (1996-2012) |
| Kategorie VaV | ZV - Základní výzkum |
| Hlavní obor | BA - Obecná matematika |
| Vedlejší obor | IN - Informatika |
| Zahájení řešení | 1.1.2008 |
| Ukončení řešení | 31.12.2009 |
| Datum posledního uvolnění účelové podpory | 9.3.2009 |
| Číslo smlouvy | 1484/2009-32 |
| Poslední stav řešení | U - Ukončený projekt, tj. jednoletý nebo víceletý projekt, který skončil v předcházejícím roce, v příslušném roce sběru dat jsou dodány údaje vztahující se k jeho ukončení |
| Finance projektu | |
| Období | 2008 | 2009 | celkem |
|---|
| Výše podpory ze státního rozpočtu | 27 tis. Kč | 58 tis. Kč | 85 tis. Kč |
| Celkové uznané náklady | 32 tis. Kč | 58 tis. Kč | 90 tis. Kč |
| Typ | skutečně čerpané | skutečně čerpané |
|
| Druh soutěže | M2 - Mezinárodní spolupráce podle uzavřených smluv o dvoustranné mezinárodní spolupráci ve VaV |
| Cíle řešení v původním jazyce | Hlavním cílem spolupráce je umožnit českým a polským řešitelům sdílet zkušenosti a myšlenky týkající se problému splnitelnosti omezujících podmínek (CSP), zejména otázky dichotomie. Spolupráce již započala četnými návštěvami polských účastníků v České Republice, které vedly k významným příspěvkům v dané oblasti. Spolupráce se zaměří na algebraický přístup k problému CSP, který se ukázal být velmi plodným. V průběhu řešení chceme rozšířit třídu problémů, pro které je dichotomie známa, zejména se zaměříme na třídy orientovaných grafů. To povede k rozvoji teorie nutné k důkazu (nebo vyvrácení) dichotomické domněky. Prvním krokem je aplikovat algebraické nástroje pro třídy, pro něž je dichotomie známa: orientované cesty, orientované kružnice, turnaje a mnoho dalších. Tento výzkum poskytne východisko k důkazu dichotomie pro širší třídu digrafů a jiných relačních struktur. Velmi důležité je uzpůsobit algebraické nástroje, které se již ukázali být velmi užitečné. Zkoumání malcevských podmínek ve s |
| Klíčová slova v anglickém jazyce | Constraint satisfaction problem |
| Hodnocení výsledků | U - Uspěl podle zadání, tj. byly splněny cíle a jeho předpokládané výsledky uvedené ve smlouvě / rozhodnutí o poskytnutí podpory |
| Zhodnocení výsledků řešení česky | Výsledkem projektu je vyřešení Larose-Zádoriho hypotézy o konečné šířce a nalezení dosud nejsilněšího kritéria pro NP-úplnost CSP. Výsledky byly přijaty do špičkových časopisů a prezentovány na elitních konferencích. |
| Rok dodání údajů do CEP | 2010 |
| Systémové označení dodávky dat | CEP10-MSM-ME-U/01:1 |
| Datum dodání záznamu | 30.6.2010 |
| Účastníci projektu |
| Počet příjemců | 1 |
| Počet dalších účastníků projektu | 0 |
| Příjemce / Organizační jednotka garantující řešení | Univerzita Karlova v Praze / Matematicko-fyzikální fakulta |
| Řešitel | Doc. RNDr. Jiří Tůma, DrSc. (státní příslušnost: CZ - Česká republika) |
| Finance účastníků projektu |
| Poznámka: Finance účastníků projektu jsou sledovány od roku 2007 |
| Výše podpory ze státního rozpočtu | |
| Účastník | 2008 | 2009 |
|---|
| Univerzita Karlova v Praze / Matematicko-fyzikální fakulta | 27 tis. Kč | 58 tis. Kč |
|
| Celkové uznané náklady | |
| Účastník | 2008 | 2009 |
|---|
| Univerzita Karlova v Praze / Matematicko-fyzikální fakulta | 32 tis. Kč | 58 tis. Kč |
|
| Výsledky projektu v RIV |
| Počet výsledků v RIV | 0 |
nebo telefonním čísle 224 234 797 (v pracovních dnech 8-16 hod.).