| Meno: | Vincent
|
|---|
| Priezvisko: | Hlaváč
|
|---|
| Názov: | Varianty pojmu užitočnosti informácie
|
|---|
| Vedúci: | prof. RNDr. Branislav Rovan, PhD.
|
|---|
| Rok: | 2023
|
|---|
| Kľúčové slová: | užitočnosť informácie, rada, unárny deterministický konečný automat, rozložiteľnosť, rozklad, kvalita rozkladu, stavová zložitosť
|
|---|
| Abstrakt: | V tejto práci pokračujeme v skúmaní pojmu užitočnosti informácie pri riešení prob-
lému. Berieme problémy formalizované regulárnym jazykom L nad unárnou abecedou
a za zložitosť problému považujeme stavovovú zložitosť minimálneho automatu A
akceptujúceho jazyk L. Zisťujeme či existuje dodatočná informácia Ladv , ktorá nám
umožní riešiť problém ľahšie, teda nájsť nový problém Lnew taký, že Ladv ∩ Lnew = L,
pričom pre automaty Aadv a Anew akceptujúce jazyky Ladv a Lnew musí platiť, že
majú menšiu stavovú zložitosť ako automat A. Na toto sa pozeráme ako na rozklad
automatu A na Aadv a Anew . Zavádzame možnosť druhej dodatočnej informácie Ladv2
a skúmame rozklad automatu A na tri nové automaty Aadv , Aadv2 a Anew , kde Aadv2
akceptuje jazyk Ladv2 a opäť je menšej stavovej zložitosti ako automat A. Ďalej
skúmame kvalitu rozkladov, za ktorú berieme súčet stavových zložitostí automatov
rozkladu. Ukážeme horné a dolné hranice kvality pre jednotlivé rozklady a porovnáme
kvalitu rozkladov automatu A na dva a tri nové automaty.
|
|---|