Здравствуйте, Гость!
Мы просим вас войти или зарегистрироваться у нас на сайте.
Это откроет для вас дополнительные возможности
и раскроет весь потенциал нашего сайта.


Обновления сайта:

Статистика
» Зарег. на сайте
» Всего: 6029
» Новых за месяц: 170
» Новых за неделю: 19
» Новых вчера: 1
» Новых сегодня: 0



Онлайн всего: 2
Гостей: 2
Пользователей: 0


Облако тегов

Наш партнер
Реальность жизни

В основе каждого текста лежит алфавит – конечное множество символов. В основе текстов на русском языке лежит алфавит, называемый кириллицей, состоящий из 33 строчных и 33 заглавных букв алфавита. Тексты английского языка построены на основе латиницы – алфавита, содержащего 26 строчных и 26 заглавных букв. Конечно алфавит, на основе которого строятся тексты на естественных языках, содержит не только буквы, но и цифры, знаки операций и множество других специальных символов.

Пусть задан алфавит T, содержащий m символов:

T = \{ t_{1}, t_{2}, …t_{m} \}

Словом S в алфавите T называют любую последовательность символов алфавита:

S = s_{1}s_{2}…s_{k},

где s_{i} – это символы алфавита. Число символов в слове – k называют длиной слова.

Справедливо утверждение:

Число различных слов длины k, которые можно построить в алфавите из m символов, равно: N = m^k

Справедливость утверждения легко доказывается по индукции.

Базис индукции: при k = 1, утверждение справедливо, поскольку словами длины 1 являются m символов алфавита.

Шаг индукции: Пусть утверждение справедливо при некотором k. Это означает, что построено m^k слов длины k. Из каждого слова можно построить m новых слов длины k + 1, приписывая к слову поочерёдно m символов алфавита. Таким образом, слов длины k + 1 будет:

N = m^k * m = m^{k+1}

Это простое, но важное утверждение, которое в том или ином виде используется при решении различных задач.

Алфавит компьютера

Тексты, которые хранятся в памяти компьютера, используют один из самых примитивных алфавитов, состоящий всего из двух символов:

T_{2} = /{0, 1/}

С другой стороны мы знаем, что в памяти компьютера можно хранить не только тексты на различных естественных языках, но и графику, музыку и другую информацию различного вида. Как такое возможно? Разберемся с текстами. Пусть есть два алфавита – T, состоящий из m символов и алфавит T_{2}. Представление текстов в алфавите T текстами в алфавите T_{2} называется кодированием. Простейший способ кодирования состоит в том, чтобы символы алфавита T кодировать словами конечной длины алфавита T_{2}. Умея кодировать каждый символ, можно кодировать любой текст символ за символом.

Какова должна быть минимальная длина слов в алфавите T_{2}, чтобы было возможно этими словами закодировать алфавит из m символов? Очевидно, что длина может быть определена из условия:

2^k >= m

Если, например, m = 30, то наименьшее возможное значение k равно 5.

Долгое время при работе с текстами, сохраняемыми в компьютере, использовался код ASCII, в котором каждый символ алфавита кодировался словом из 8 бит (одним байтом). Такой алфавит, содержащий 256 различных символов, мог включать латиницу и кириллицу, цифры, знаки операций, знаки препинания, скобки и другие символы. Но все-таки этого алфавита явно недостаточно, чтобы можно было хранить в памяти компьютера тексты на любых естественных языках. Чтобы такое было возможно, необходимо, чтобы алфавит включал алфавиты всех известных естественных языков, в том числе алфавит украинского языка, готику, греческий алфавит, алфавит языка иврит, арабского языка, китайские и японские иероглифы.

В сегодняшних компьютерах для хранения текстов используется кодировка из двух байтов, называемая UNICODE кодировкой, позволяющая словами из 16 битов кодировать алфавит, содержащий 2^{16} = 65536 символов. Для большинства существующих естественных языков такого алфавита хватает для представления текстов, записанных на этих языках.

Задача 9:

Автомобильный номер состоит из 7 символов. В качестве символов используются 30 букв и 10 цифр. Символ кодируется минимально возможным набором битов. Номер представляется целым числом байтов. Какую память требуется иметь для хранения 1000 номеров.

Ответ: Примерно 6 Кб.

Решение: Алфавит для записи текстов, представляющих номера автомобилей, содержит 40 символов (30 букв и 10 цифр). Для кодировки такого алфавита потребуются двоичные слова длины 6 (2^6 > 40). Для кодировки всего номера потребуется 6 * 7 = 42 бита. Округляя в большую сторону до целого числа байтов, получим, что для хранения одного номера потребуется 6 байтов. Для хранения 1000 номеров достаточно 6 Кб.

Задача 10:

В командной олимпиаде по информатике участвуют ученики из школ, номера которых заданы двузначными цифрами. В команде может быть не более 7 учеников. Какой минимальный объем памяти потребуется для хранения 500 номеров участников олимпиады, если каждый номер представляется целым числом байтов?

Ответ: Достаточно 1 Кб.

Решение: Номер участника может состоять из номера школы и номера участника в данной школе. Для 100 номеров школ достаточно 7-и битов (2^7 > 100). Для номера участника в школе достаточно 3-х битов (2^3 > 7). Поэтому для хранения номера участника достаточно 10 битов. Округляя в большую сторону до целого числа байтов, получим, что 2-х байтов достаточно для хранения номера. Для хранения 500 номеров достаточно одного килобайта.

Задача 11:

Алфавит состоит из 4-х букв {М, У, Х, А} Слова длины 5 перечисляются в лексикографическом порядке. Нумерация слов начинается с единицы. Какое слово в этом перечислении стоит под номером 1016, под номером 365?

Ответ: ХХХМХ; ММУХА

Решение: Число различных слов длины 5 в 4-х буквенном алфавите равно 4^5 = 2^{10}= 1024. При перечислении их в алфавитном (лексикографическом) порядке под номером 1 стоит слово ААААА, под номером 1024 – слово ХХХХХ. В задачах экзамена ЕГЭ обычно требуется указать слово, стоящее близко к концу перечисления, что имеет место в нашей задаче, в которой требуется назвать слово под номером 1016, стоящее в первом десятке с конца перечисления. Поэтому для решения задачи достаточно выписать десять слов в обратном лексикографическом порядке, что и дает слово ХХХМХ.

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

Поставим в соответствие буквам алфавита цифры (А – 0, М – 1, У – 2, Х -3). При задании этого соответствия учитывается принятый порядок следования букв в алфавите. Число букв задает число используемых цифр, а тем самым задает основание системы счисления. Введенное соответствие букв и цифр порождает соответствие между словами в алфавите и числами в соответствующей системе счисления, в нашем случае – четверичной системе счисления. При лексикографическом перечислении слов длины k слову, стоящему под номером N, соответствует число N-1 в четверичной системе счисления, содержащее k цифр, включая незначащие нули. Так, слову под номером 1, состоящему из 5 букв, соответствует число 0, записанное как 00000, или, после замены цифр буквами, - ААААА. Поэтому для решения задачи, зная N, достаточно получить запись числа N-1 в четверичной системе, а затем заменить цифры буквами.

Получим решение задачи этим способом для N = 1016 и N = 365.

N - 1 = 1015 = 3 * 4^4 + 3 * 4^3 + 3 * 4^2 + 1 * 4^1 + 3 = 33313_{4} = ХХХМХ
N - 1 = 364 = 1 * 4^4 + 1 * 4^3 + 2 * 4^2 + 3 * 4^1 + 0 = 11230_{4} = ММУХА

Задача 12:

Алфавит состоит из 3-х букв {А,М, П} Слова длины 4 перечисляются в лексикографическом порядке. Нумерация слов начинается с единицы. Под каким номером стоит слово МАМА, слово - ПАПА?

Ответ: 31; 61

Решение: В троичной системе слову МАМА соответствует число 1010_{3} = 3^3 + 3 = 30. В перечислении, где нумерация начинается с 1, номер этого слова равен 31.

Слову ПАПА соответствует число 2020_{3} = 60.

Кодирование словами переменной длины

Кодировка символов алфавита T словами алфавита Т_{2} фиксированной длины k имеет то преимущество, что закодированный текст легко поддается расшифровке – декодированию. Действительно, достаточно закодированный текст разбить на группы длины k, и каждой группе поставить в соответствие символ алфавита. Недостатком такого способа является некоторая неэффективность процедуры кодирования, - каждому символу алфавита всегда соответствует k битов алфавита Т_{2}. Память компьютера достаточно дешевая, поэтому жертвуют неэффективностью использования памяти ради удобства декодирования.

В других ситуациях эффективность важнее удобства декодирования. Примерами являются азбука Брайля, азбука Морзе. В азбуке Морзе, где для передачи информации используется алфавит из двух символов – точки и тире, для однозначного декодирования вводится третий символ – пауза. При передаче данных по телеграфу, использующему азбуку Морзе, точке, тире и паузе соответствуют сигналы разной длительности.

Рассмотрим пример неоднозначного кодирования. Пусть у нас есть алфавит из 3-х символов – А, М, П. Введем следующую кодировку: А – 0, М – 1, П – 10. Рассмотрим закодированный текст: 1010. Этому тексту соответствуют два слова – МАМА и ПП. Как видите, введенная кодировка не обеспечивает однозначное декодирование.

Можно ли при использования кодировки словами переменной длины наложить ограничения на способ кодирования, чтобы декодирование было однозначным? Ответ положителен. Если при кодировании выполняется условие Фано, то декодирование однозначно. Кодирование называется префиксным, если при кодировании существует пара символов, такая, что код одного символа является префиксом кода другого символа. В нашем примере кодирование является префиксным, поскольку для символов М и П код символа М является префиксом (началом) кода символа П. Условие Фано выполняется, если кодирование не является префиксным. Условие Фано является достаточным условием для однозначного декодирования. Оно не является необходимым условием.

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

Задача 13:

Для трехбуквенного алфавита {А, М, П} используется кодировка А – 01, М – 10, П – 001. Какой код минимальной длины следует задать для кодировки буквы Т, добавляемой в алфавит?

Ответ: Т – 11.

Решение: Используемая кодировка удовлетворяет условию Фано, - ни один код не является префиксом другого кода, что гарантирует однозначность декодирования. Для нового символа, добавляемого в алфавит, нельзя использовать код, состоящий из одного символа, поскольку будет нарушено условие Фано. Для кода, состоящего из двух символов, возможен только один вариант, удовлетворяющий условию Фано, - Т – 11.

Задача 14:

Для четырехбуквенного алфавита {А, М, П, Т} используется кодировка А – 01, М – 10, П – 001, Т - 11. Можно ли уменьшить длину кода одного из символов, сохраняя однозначность декодирования?

Ответ: Можно. П – 00.

Решение: Используемая кодировка удовлетворяет условию Фано, - ни один код не является префиксом другого кода, что гарантирует однозначность декодирования. Не нарушая условия Фано, для кодирования буквы П можно использовать код 00. Заметьте, в этом случае все символы кодируются словами постоянной длины. Для такой кодировки условие Фано выполняется автоматически, поскольку все слова различны и имеют одинаковую длину, так что ни одно из них не может быть префиксом другого слова.

Форма входа
Логин:
Пароль:

Это важно!








Календарь
«  Сентябрь 2017  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
252627282930


Язык сайта

Счетчик материалов
Сообщений на форуме: 0/0 Банк материалов: 97
Комментариев: 9
Гостевая книга: 19
Банк статей: 59
Вакансии: 7
Новости: 24
Сайтов: 5
Тесты: 4
FAQ: 4



Мы рады приветствовать Вас на Российском информационно-образовательном портале!

Данный проект позволяет сделать образовательный процесс более «прозрачным» для родителей учеников и
более эффективным и насыщенным для детей и педагогов.
В различных разделах настоящего портала Вы можете:
поучаствовать в опросе, высказать свое мнение о качестве предоставляемых услуг   
разместить свои методические разработки в "Банке материалов", получив именной сертификат;
разместить свои статьи в "Банке статей", получив именной сертификат;
стать активным участником нашего форума, получив сертификат;
обменяться мнениями и полезной информацией и многое другое!
www.obr-rus.ru © 2017