Dotaz: ako zistit minimalnu mnozinu vzorcov na pokrytie konecnej mnoziny cisel

[sudcadred]

Dobry den,

toto je skor trosku matematicky dotaz, ale zaujimalo by ma, ci existuje nejaka teoria, ako pokryt konecnu mnozinu cisiel prostrednictvom mnoziny vysledkov vzorcov co najefektivnejsie.

Priklad: ------- Chcem pokryt mnozinu konecnych cisiel 0-1024. Vysledky vzorca (2^n) pokryju 11 cisiel (1%) Vysledky vzorca (prvocislo) pokryju 172 cisiel (16.8%) atd. atd. az v konecnom dosledku najdem mnozinu vzorcov, ktorych vysledky najefektivnejsie pokryvaju cisla 0-1024.

PS. tato uvaha vznikla pri rozmyslani o novom algoritme pre komprimacne programy, ale teraz je to uz ciste akademicka zvedavost:)

---

---

Odpovědi

[mc_bizon]

Při tomto zadání je nejefektivnější množina vzorců {n ↦ n}, ale hádám, že to jsi na mysli neměl . Bude to asi lépe chtít definovat to "nejefektivnější pokrytí".

[sudcadred]

Pod najefektivnejsim pokrytim rozumiem minimalnu mnozinu vzorcov, ktora pokryje 100% mnoziny konecnych cisel:)

[Radek Miček]

Teorii se říká Kolmogorovská složitost.

[JS]

A mohl jste mu tam napsat rovnou, ze nikdo nevi, jak to spocitat (a nejspis to pro konecny vstup nepujde lepe nez zkousenim vsech moznosti).

[Radek Miček]

nejspis to pro konecny vstup nepujde lepe nez zkousenim vsech moznosti

Obecně to zkoušením možností nepůjde (problém zastavení). Zkoušení možností by pomohlo v případě, že by ty vzorce byly primitivně rekurzivní funkce.

[JS]

To je pravda. Nicmene, predpokladam, ze kdyz hleda cosi jako dekompresni algoritmus, tak nejspis budou.

[petr_p]

Existuje pojem informace a entropie. Délka bitového řetězce, v kterém je informace kódována, by v ideálním případě (komresního algoritmu) mohla být stejná.

Jenže do délky zkomprinovaných dat musíte započítat i délku dekompresního algoritmu – to je taky informace. Délka programu implementující daný algoritmus záleží na instrukční sadě.

Nicméně i programy lze kódovat do čísel a ty nějak repreznotovat. Zabývá se tím teorie vyčíslelnosti.

Aby to tak ale nebylo jednoduché, tak jako na potvoru, existuje nepřímá závislost mezi velikostí programu a časovou složitostí jeho běhu. Takže čím budete mít dokonalejší kompresi, tím si více počkáte.