34. Коды Хемминга.

Код Хемминга – это блочный код, позволяющий исправлять одиночные и фиксировать двойные ошибки, разработанный Ричардом Хеммингом в сороковых годах прошлого столетия.

Желая застраховаться от возможных сбоев и ускорить процесс обработки данных, Хемминг много работал над построением эффективных алгоритмов, позволяющих быстро обнаруживать и исправлять ошибки, и в 1950 году опубликовал способ кодирования, являющийся одним из самых известных на сегодняшний день.

Идея кодов Хемминга заключается в разбиении данных на блоки фиксированной длины и вводе в эти блоки контрольных бит, дополняющих до четности несколько пересекающихся групп, охватывающих все биты блока.

Ричард Хемминг рассчитал минимальное количество проверочных бит, позволяющих однозначно исправлять однократные ошибки.

Если длина информационного блока, который требуется закодировать - m бит. Количество контрольных бит, используемых для его кодирования, – k, то закодированный блок будет иметь длину: n = m+k бит. Для каждого блока такой длины возможны n различных комбинаций, содержащих ошибку.

Алгоритм кодирования Хэмминга - очень популярен и позволяет значительно повысить надежность передачи и хранения информации. Особенно, он выгоден при кодировании больших блоков данных. Существует большое количество различных способов реализации этого алгоритма.

35. Элементы комбинаторики. Размещения и сочетания.

Комбинаторика – это раздел дискретной математики, в котором изучаются вопросы о том, сколько различных комбинаций можно составить из заданных элементов (объектов) с учетом тех или иных условий. Как самостоятельная ветвь математики комбинаторика возникла в ХVII веке в связи с развитием теории вероятностей, хотя отдельные комбинаторные задачи были сформулированы еще в древности. Название этому математическому направлению дал немецкий языковед, философ и математик Готфрид Вильгельм Лейбниц (1646–1716), опубликовавший в 1666 г. свою работу «Об искусстве комбинаторики», в которой впервые появился термин «комбинаторный».

Исходным в комбинаторике является интуитивно ясное понятие выборки (синонимы – «расстановки», «комбинации», «соединения», как набора m элементов из некоторого исходного множества, причем наборы могут быть как упорядоченными, так и неупорядоченными, с повторениями элементов и без повторений.

В настоящее время комбинаторика представляет собой один из важнейших разделов современной дискретной математики, имеющий многочисленные применения на практике. Следовательно, каждый грамотный человек должен иметь достаточно четкое представление об основных (исходных) понятиях комбинаторики, таких, как размещения, перестановки, сочетания, разбиения и некоторых других, и уметь ими пользоваться хотя бы в несложных практических ситуациях. С этой целью и включен раздел комбинаторики в данный курс дискретной математики.

Кортежи длины k, составленные из элементов п-множества, называют размещениями с повторениями из п элементов по k.

Число размещений с повторениями находится по формуле:

Кортежи длины k, составленные из элементов п-множества, так что все элементы каждого кортежа должны быть различными, называют размещениями без повторений из п элементов по k, а их число обозначают .

Число размещений без повторений находится по формуле:

Сочетаниями без повторений из n элементов по т элементов называются соединения, каждое из которых состоит из m элементов, взятых из данных n элементов.

Число сочетаний из п элементов по m обозначают и читают «С из n по m».

Два сочетания из п элементов по т отличаются друг от друга хотя бы одним элементом. В отличие от размещений, порядок следования элементов здесь не учитывается.

Число сочетаний без повторений равно:

Число сочетаний с повторениями из n элементов по m выражается через число сочетаний без повторений.

Число сочетаний с повторениями обозначается символом .

Формула числа сочетаний из m элементов по n элементов с повторениями имеет вид: