74
правки
Изменения
→Доказательство корректности
== Доказательство корректности ==
{{УтверждениеЛемма|idstatement=идентификатор Вероятность получить некоторый перфикс <tex> P </tex> равна <tex> S(P)\over{C(n)} </tex>, где <tex> C(необязательноn)</tex> {{---}} число различных комбинаторных объектов данного типа длины <tex> n </tex>, пример: proposal1а <tex> S(P) </tex> {{---}} число различных комбинаторных обьектов длины <tex> n </tex> с таким префиксом. |authorproof=Автор утверждения Докажем по [[Математическая индукция|индукции]]: '''База:''' Заметим, что любой комбинаторный объект имеет пустой перфикс (<tex> \varnothing </tex>), следовательно <tex> S(необязательно\varnothing)|about=О чем утверждение C(n) </tex>. Вероятность получить некоторый префикс <tex> P </tex> длины <tex> 1 </tex> равна <tex> S(P)\over{S(\varnothing)} </tex>, что равно <tex> S(P)\over{C(необязательноn)} </tex> .|statement=утверждение|proof=доказательство '''Переход:''' Пусть вероятность получить префикс <tex> P </tex> длины <tex> l </tex> равна <tex> S(P)\over{C(n)} </tex>. Вероятность получить из <tex> P </tex> некоторый префикс <tex> P' </tex> длины <tex> l+1 </tex> равна <tex> S(P')\over{S(P)} </tex> , следовательно вероятность получить префикс <tex> P' </tex> равна <tex> S(P)\over{C(n)} </tex><tex>\cdot</tex><tex> S(P')\over{S(P)} </tex> что равно <tex> S(P')\over{C(необязательноn)} </tex> . Следовательно предположение индукции верно для всех возможных префиксов любой длины.
}}
