Publikace na Matematicko-fyzikální fakulta |
2007
Abstrakt
Intervalové funkce tvoří speciální třídu booleovských funkcí, pro které lze velmi snadno a rychle zjistit funkční hodnotu na zadaném vstupním vektoru. Hodnota intervalové funkce na n proměnných zadané pomocí intervalu [a,b] (kde a a b jsou n-bitová celá čísla) je 1, právě když vstupní vektor nahlížený jako n-bitové celé číslo, náleží do intervalu [a,b].
Skrytě intervalové funkce mohou být transformovány na intervalové přepnutím polarit některých proměnných. V tomto článku studujeme problém nalezení skrytě intervalového rozčíření dané částečně definované booleovské funkce.
Prezentujeme polynomiální algoritmus řešící tento problém.