Теорема 1.Над алфавитом мощностью m можно создать ровно mn слов длиною n. Доказательство: Воспользуемся методом полной математической индукции. Пусть - элементы (буквы) алфавита мощностью . Из этого алфавита можно создать слов длиной 1. Такими словами будут буквы этого алфавита. Для данное утверждение является правильным . Допустим, что данное утверждение является правильным для , и покажем, что тогда оно выполняется и для . Предположим, число длины равняется . Чтобы создать все возможные слова длины , достаточно к каждому слову длины добавить в его конце последовательно каждую из букв алфавита. Таким образом, из каждого слова длины образуется разных слов длины . Таким образом, получаем все возможные слова длиною . Поскольку слов длиной является , то общее количество слов длиной будет . Таким образом, предположив истинность утверждения для , доказано, что оно является правильным для . Теорема доказана.
Пример 1. Какой является мощность алфавита, с помощью которого записано сообщение, которое содержит 5120 символов, если его информационный объем составляет 2,5Кб? 1. Переведем информационный объем сообщения в биты: . 2. Определим количество битов, которые приходятся на один символ: . 3. Определяем мощность алфавита по теореме 1:
|