Vše
Vše

Co hledáte?

Vše
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Omezené typy výpočtů: algoritmy, modely, složitost

Cíle projektu

V tomto projektu základního výzkumu se soustředíme na roli omezených typů výpočtů v teorii složitosti a v teorii algoritmů. Budeme studovat problémy, pro které zkoumání omezených typů výpočtů může vést k podstatně silnějším a těsnějším dolním a horním odhadům složitosti a kvality algoritmů ve srovnání s tradičním studiem neomezených výpočtů. Ve výpočetní složitosti budeme studovat kombinatorické algoritmy pro problémy jako násobení booleovských matic a 3SUM, což je omezená varianta problému hledání podmnožiny s daným součtem. V algoritmické části projektu se zaměříme na online a aproximační algoritmy pro omezené varianty problému bin packing s omezeným prostorem, rozvrhování s cílem maximalizovat cenu splněných úloh a toky s omezenou délkou.

Klíčová slova

Computational complexitytheory of algorithmsonline algorithmsapproximation algorithmsschedulingcombinatorial algorithmsmatrix multiplicationlower bounds

Veřejná podpora

  • Poskytovatel

    Grantová agentura České republiky

  • Program

    Standardní projekty

  • Veřejná soutěž

    Standardní projekty 18 (SGA0201400001)

  • Hlavní účastníci

    Univerzita Karlova / Matematicko-fyzikální fakulta

  • Druh soutěže

    VS - Veřejná soutěž

  • Číslo smlouvy

    14-10003S

Alternativní jazyk

  • Název projektu anglicky

    Restricted computations: Algorithms, models, complexity

  • Anotace anglicky

    In this project of basic research we focus on the role of restricted models of computation in complexity theory and theory of algorithms. We shall investigate problems for which studying the restricted scenarios may result in significantly stronger and closer lower and upper bounds on the complexity and performance of algorithms, compared to the traditional unrestricted scenarios. In computational complexity we shall study combinatorial algorithms for problems such as Boolean matrix multiplication and 3SUM, which is a restricted variant of the subset sum problem. In the algorithmic part of the project we shall focus on online and approximation algorithms for restricted variants of bounded space bin packing, throughput scheduling and length-bounded flows. The results will be published in high-quality international journals and proceedings of selective conferences in theoretical computer science.

Vědní obory

  • Kategorie VaV

    ZV - Základní výzkum

  • CEP - hlavní obor

    IN - Informatika

  • CEP - vedlejší obor

  • CEP - další vedlejší obor

  • OECD FORD - odpovídající obory
    (dle převodníku)

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Hodnocení dokončeného projektu

  • Hodnocení poskytovatelem

    V - Vynikající výsledky projektu (s mezinárodním významem atd.)

  • Zhodnocení výsledků projektu

    Projekt přinesl několik excelentních vědeckých výsledků na nejvyšší světové úrovni (třebaže klíčový člen týmu souběžně řešil ERC grant) a mnohé další kvalitní a mezinárodně srovnatelné výsledky. Zmíníme především konference STOC, SODA a ESA. Je vidět, že bylo dosaženo významného pokroku ve všech slibovaných směrech a navíc v ještě v přidané oblasti streaming algoritmů.

Termíny řešení

  • Zahájení řešení

    1. 1. 2014

  • Ukončení řešení

    31. 12. 2016

  • Poslední stav řešení

    U - Ukončený projekt

  • Poslední uvolnění podpory

    12. 4. 2016

Dodání dat do CEP

  • Důvěrnost údajů

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

  • Systémové označení dodávky dat

    CEP17-GA0-GA-U/03:1

  • Datum dodání záznamu

    28. 6. 2017

Finance

  • Celkové uznané náklady

    4 300 tis. Kč

  • Výše podpory ze státního rozpočtu

    4 300 tis. Kč

  • Ostatní veřejné zdroje financování

    0 tis. Kč

  • Neveřejné tuz. a zahr. zdroje finan.

    0 tis. Kč

Základní informace

Uznané náklady

4 300 tis. Kč

Statní podpora

4 300 tis. Kč

100%


Poskytovatel

Grantová agentura České republiky

CEP

IN - Informatika

Doba řešení

01. 01. 2014 - 31. 12. 2016