92
правки
Изменения
м
→Примеры применения экспандеров
==Примеры применения экспандеров==
===Коды, исправляющие ошибки===
С помощью расширяющего графа можно посторить линейный код, позволяющий исправлять ошибки в доле <tex>\delta = 1/(2000d)</tex> битов. Чтобы задать линейный код с длиной кодового слова n, достаточно описать его проверочную матрицу <tex>H</tex> <tex>(</tex>слово <tex>x \in \{0, 1\}^n</tex> является кодовым словом если и только если <tex>Hx^t = 0)</tex>. Другими словами, нужно задать систему линейных уравнений для переменных <tex>x_1, . . . \ldots , x_n;</tex> решения этой системы и будут кодовыми словами.
===Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел===
{{Определение
|definition=Язык <tex>L</tex> принадлежит сложностному [[RP|классу <tex>RP</tex>]], если существует полиномиальный алгоритм <tex>A</tex> такой что
1. для <tex>x \in L</tex> для всех <tex>r \in \{0, 1\}^{poly(n)}</tex> <tex>A(x, r) = 1</tex>
2. для <tex>x \notin L</tex> не более чем для 1/2000 всех <tex>r \in \{0, 1\}^{poly(n)}</tex> может выполняться <tex>A(x, r) = 1</tex>
