WūranArtīkelinRedigītajs: Ast teīkuns(si) nāunan pāusan "'''Kraftas nilīgibi''' (Kraftas-McMillanas nilīgibi) - nilīgibi: :: $\sum_i p^{-n_i} \le 1$ , kwēi $n_i$ ast $i$ -tas wāngis..."

2021-09-28T16:12:22Z

Ast teīkuns(si) nāunan pāusan "'''Kraftas nilīgibi''' (Kraftas-McMillanas nilīgibi) - nilīgibi: :: <math>\sum_i p^{-n_i} \le 1</math>, kwēi <math>n_i</math> ast <math>i</math>-tas wāngis..."

Nāunan pāusan

'''Kraftas nilīgibi''' (Kraftas-McMillanas nilīgibi) - nilīgibi:
:: <math>\sum_i p^{-n_i} \le 1</math>,
kwēi <math>n_i</math> ast <math>i</math>-tas wāngiskas wīrsas gillisku en <math>p</math>-āriskasmu garrin. Tūls, per eraīnan senrīnksenin stēisan gīrbin <math>\{n_1, \dots, n_N\}</math> sātwintan Kraftas nilīgibin ast mazīngi teīktun stawīdan <math>p</math>-āriskan garrin, kāi šai gīrbjai ast tenēisan wāngiskan wīrsun gilliskwas.

Nilīgibi mazzi būtwei ainawīdai iztarītan en billai stēisan kōdan: Ik <math>\{n_1, \dots, n_N\}</math> ast ilgāi stēisan wīrdan en [[prefiksiskasmu kōdan|prefiksiskas kōds]] kīrsa <math>p</math>-elamēntin alfabētan, staddan tenēi sātwina Kraftas nilīgibin. Ik Kraftas nilīgibi ast sātwintan pēr ainuntan senrīnksenin stēisan gīrbin <math>\{n_1, \dots, n_N\}</math>, staddan ast mazīngi teīktun prefiksiskan kōdan kīrsa <math>p</math>-elamēntin alfabētan, per kawīdan šai gīrbjai ast ilgāi stēisan wīrdan.

Nilīgibi pastāi padrūktintan en 1949 m. ezze L.G. Kraftan. En 1956 m. B.McMillan ast padrūktinuns šan nilīgibin en spārtaišai fōrmulisnan - tenā ast sātwintan ni tēr per prefiksiskans kōdans, adder dīgi per [[ainazentliskai dekōdamins kōds|ainazentliskai dekōdaminans kōdans]].

===Padrūktinsenis===

Padrūktinsenis per <math>p</math>-āriskans garrins.

Per dātan <math>p</math>-āriskan garrin, etrīnkimai gīrbin <math>N</math> mūiseskan adder līgu wisēimans gilliskwans stēisan wāngiskan wīrsun. En eraīnasmu wāngiskan wīrsun sen gilliskwan mazzan nikāi <math>N</math> preidāimai pilnan <math>p</math>-āriskan garrin. Iz <math>i</math>-tan wāngiskan wīrsun sen gilliskwan <math>n_i</math> en ōriginālasmu garrin turrimai en nawwasmu garrin <math>p^{N-n_i}</math> wāngiskans wīrsuns. Garrin, kawīdan asmai zēidusis turri <math>\sum_i p^{N-n_i}</math> wāngiskans wīrsuns be turri gilliskwan <math>N</math>, tītan tennan ni mazzi tūritun tūls nikāi <math>p^N</math> wāngiskans wīrsuns <math>\square</math>

En āntran pāusan, padrūktinimai kāi Kraftas nilīgibi ast sātwintan per gīrbins <math>\{n_1, \dots, n_N\}</math>. Peisāimai nilīgibin sen summan praēntin wissans gilliskwas wērtibins:
::<math>\sum_j k_j p^{-m_j} \le 1</math>,
kwēi <math>k_j</math> ast <math>j</math>-tas gilliskwas wārstisku. Nilīgibi ast dīgi arwi, ik immimai tennan tēr per pirmans <math>n</math> gilliskwans:
::<math>\sum_{j\le n} k_j p^{-m_j} \le 1</math>.
Iz šan reducītan nilīgibin mazzimai izwestun nilīgibin per <math>k_n</math>:
::<math>k_n \le p^{m_n-m_{n-1}}(p^{m_{n-1}}(1-\sum_{i<n-1}k_i p^{-m_i}) - k_{n-1})</math>,
tītat ik <math>k_{n-1} < f(n-1)</math>, staddan <math>k_n \ge 0</math> be <math>k_{n} < f(n)</math>, per rekursīskai definītan funkciōnin:
::<math>f(n) = p^{m_n-m_{n-1}}(f(n-1)-k_j), f(1)=p^{m_1}</math>.
Asmai padrūktinusis, kāi <math>\forall n>0 \ k_n > f(n)</math>. Teinū sūit pazinātun, kāi funkciōni <math>f(n)</math> pertreppa gīrbin stēisan wīrsun en gilliskwai <math>m_n</math> <math>\square</math>

[[Category:Matemātiki]]
[[Category:Infōrmatiki]]

Kraftas nilīgibi - Wersiōnin istōrija

WūranArtīkelinRedigītajs: Ast teīkuns(si) nāunan pāusan "'''Kraftas nilīgibi''' (Kraftas-McMillanas nilīgibi) - nilīgibi: :: \sum_i p^{-n_i} \le 1, kwēi n_i ast i-tas wāngis..."

WūranArtīkelinRedigītajs: Ast teīkuns(si) nāunan pāusan "'''Kraftas nilīgibi''' (Kraftas-McMillanas nilīgibi) - nilīgibi: :: $\sum_i p^{-n_i} \le 1$ , kwēi $n_i$ ast $i$ -tas wāngis..."