Информационные технологии

~ 2 ~ 

 

УДК 004 
 ББК 16.2 
         Ч-88 
 
 
Рецензенты: 
д-р техн. наук, доц., проф. Н.С. Галдин (СибАДИ, г. Омск); 
канд. техн. наук, доц. И.В. Лазута (СибАДИ, г. Омск) 
 
Работа 
утверждена 
редакционно-издательским 
советом 
СибАДИ  
в качестве учебно-методического пособия. 
 
 

Ч-88

Чуканов, Сергей Николаевич.
Информационные 
технологии 
: 
учебно-методическое 
пособие 
/ 

С.Н. Чуканов, Н.Н. Егорова. – Электрон. дан. – Омск : СибАДИ, 2022. – 
Режим доступа: http://bek.sibadi.org/MegaPro, для авторизованных пользователей. – Загл. с экрана. 

Содержит теоретический материал и задания для самостоятельной работы 
студентов. 
Предназначено для обучающихся 1–2-го курсов всех форм обучения,  
изучающих 
дисциплины 
«Информатика», 
«Информационные 
технологии»,  
«Исследование операций», «Современные методы оптимизации». 
Имеет интерактивное оглавление в виде закладок. 
Подготовлено на кафедре «Цифровые технологии». 
 
Текстовое (символьное) издание (2 Мб) 
Системные требования: Intel, 3,4 GHz; 150 МБ; Windows XP/Vista/7/10; 
1 ГБ свободного места на жестком диске; программа для чтения pdf-файлов:  
Adobe Acrobat Reader; Foxit Reader 
 
 
Редактор О.А. Соболева  
Техническая подготовка – А.А. Орловская  
 
 
Издание первое. Дата подписания к использованию 19.12.2022 
 
Издательско-полиграфический комплекс СибАДИ 
644080, г. Омск, пр. Мира, 5 
РИО ИПК СибАДИ 
644080, г. Омск, ул. 2-я Поселковая,1 
 
© ФГБОУ ВО «СибАДИ», 2022 
 

Согласно 436-ФЗ от 29.12.2010 «О защите 
детей от информации, причиняющей вред их 
здоровью и развитию» данная продукция 
маркировке не подлежит 

~ 3 ~ 

 

 
 
 
 
 

ВВЕДЕНИЕ 
 
Многие люди не осознают, что математика обеспечивает основу 
для устройств, которые мы используем для обработки информации в 
современном мире. Большинство думают, что разделы математики 
используются довольно «классически», например, как в анализе 
Фурье и решении дифференциальных уравнений. На самом деле 
большая часть математического ресурса является частью того, что 
раньше называлось «чистой» математикой, указывая, что она была 
создана для того, чтобы решить проблемы, происходящие внутри самой математики. Потребовалось много лет для математиков, чтобы 
прийти к соглашению с этой ситуацией, и некоторые из них до сих 
пор не совсем довольны этим. 
Учебно-методическое пособие представляет собой интегрированное введение в кодирование. Под этим подразумевается замена 
символьной информации, такой как последовательность битов, или 
сообщения, написанного на естественном языке, с помощью другого 
сообщения, используя (возможно) другие символы. Есть три основные причины сделать это: Экономия (сжатие данных), Надежность 
(исправление ошибок) и Безопасность (криптография). Математическая теория вводится таким образом, который позволяет тщательно 
сформулировать основные проблемы, но без ненужной абстракции.  
Пособие адресуется студентам 1–2-го курсов всех форм обучения, изучающих дисциплины «Информатика», «Информационные 
технологии», «Исследование операций», «Современные методы оптимизации». 
 

~ 4 ~ 

 

1. КОДЫ И ИХ ИСПОЛЬЗОВАНИЕ 
 
1.1. Сообщения 
 

Первое задание – настроить простую математическую модель 
сообщений. Мы делаем это, смотря на некоторые примеры и извлекая 
общие особенности из них. 
 
Пример 1.1 
Множество сообщений написано обычным языком. Эти сообщения содержат символы, формирующие слова, которые в свою очередь образуют предложения. Сообщения могут быть отправлены от 
одного человека к другому несколькими путями: в форме рукописной 
заметки или имейла. Текст сообщения по существу один и тот же, но 
он часто выражен неестественным языком. 
 
Пример 1.2 
Устройства, такие как сканеры и цифровые камеры выдают сообщения в форме электронных импульсов. Данные сообщения могут 
быть отправлены от одного устройства к другому по проводам, оптоволокну или по радиоволнам. 
Формальные определения, основанные на этих примерах, будут 
даны в подпункте 1.3. А пока что мы подумаем о сообщении, как о 
последовательности символов, указывающей, что порядок символов 
крайне важен. 
Функция сообщения – передавать информацию от отправителя к 
получателю. Для того, чтобы это было успешно, отправитель и получатель должны согласовать использование одного и того же набора 
символов. Этот набор называется алфавит. 
 
Пример 1.3 
Обозначим за А алфавит, который имеет 27 символов, буквы А, 
В, С,…, Z и пробел, который обозначим " ". Мы будем часто использовать алфавит А, чтобы представить сообщение, написанное на 
английском языке. Это удобно для изложения, но очевидно, что некоторые особенности игнорируются. Так мы игнорируем разницу между 
верхним и нижним регистром букв и пренебрегаем знаками препинания. 

~ 5 ~ 

 

Конечно, могут быть некоторые потери в сокращении сообщения на 
английском в строке символов в этом алфавите. Например, текст 

The word ‘hopefully’is often misused 
сокращен до следующего сообщения из A. 

THE WORD HOPEFULLY IS OFTEN MISUSED
_




 
 
Пример 1.4 
Алфавит В имеет 2 символа, 0 и 1, которые называются двоичными символами или битами. Потому что биты 0 и 1 могут быть реализованы в электронном виде как состояния OFF и ON, это основополагающий алфавит в современных приложениях.  
На практике биты объединяются в большие группы, как например  «32-битные слова». Но любые сообщения, передаваемые в электронном виде, либо созданные как е-мейл от меня либо как изображение от спутника с орбиты земли, все это по существу последовательность битов. 
 
Упражнения 
 
1.1. Следующие сообщения переведены с «чистого английского» на алфавит А. Запишите оригинальные сообщения и прокомментируйте каждую неоднозначность или потерю значения, которая здесь 
имеется. 

CANINE SIX LETTERS AND ENDS IN ΝΙΝΕ






 

ITS HOT SAID ROBERT BROWNING




 
1.2. 32-битное слово-это последовательность 32 символов из алфавита В. Сколько различных 32-битных слов здесь есть? Если бы 
мой принтер мог печатать одно слово каждую секунду, сколько лет 
(приблизительно) потребуется ему, чтобы напечатать их все? 
1.3. В период с 1967 по 1986 год алфавит ASCII широко использовался как стандартный для электронной коммуникации. Он имел 
128 символов, 95 из которых были печатными. Мы уже использовали 
некоторые символы, которых не было в алфавите ASCII. Какие? 
(ASCII аббревиатура Американская стандартная кодировка для обмена информацией произносится как «аски». Алфавит ASCII сейчас – 
это часть гораздо более комплексной системы, известной как Unicode 
(Юникод). 
 

~ 6 ~ 

 

1.2. Кодирование 
 
Кодирование – это правила замены одного сообщения другим. 
Второе сообщение может использовать или не использовать такой же 
алфавит, как и первое. 
 
Пример 1.5 
Простое правило кодирования сообщений из 27-символьного 
алфавита A с использованием аналогичного алфавита: написать каждое слово задом наперед. Итак, получается сообщение 
 
SEE YOU TOMORROW


    становится   EES UOY WORROMOT


 
 
Пример 1.6 
Правило кодирования сообщения из алфавита A с использованием бинарного алфавита B: заменить гласные на 0, а согласные на 1 
и игнорировать пробелы. По этому правилу 
 SEE YOU TOMORROW


    становится   100100110101101 
Эти 2 примера очень искусственные, и правила имеют ограниченный объем.  
Для большего реализма и пользы мы должны посмотреть на цели, для которых используется кодирование, и оценивать предлагаемые правила кодирования в этом контексте. 
Есть три основных причины кодирования сообщений: 
1. Экономия. Во многих ситуациях необходимо или желательно 
использовать алфавит меньший, чем имеющийся в естественном языке. Также часто бывает желательно сделать само сообщение меньше: 
в последнее время это привело к разработке методов сжатия данных. 
2. Надежность. Сообщения могут быть изменены «шумом» в 
процессе передачи. Так существует потребность в кодах, которые 
позволяют корректировать ошибки. 
3. Безопасность. Некоторые сообщения отправляются с требованием, что их поймет только тот человек, которому они предназначены. Исторически секретность была необходима в основном в дипломатических и военных коммуникациях, но сейчас это играет важную роль в ежедневных коммерческих транзакциях. Эта область кодирования известна как криптография.  
 
 

~ 7 ~ 

 

Упражнения 
 
1.5. В следующих сообщениях закодирован смысл английских 
предложений. Объясните правила кодирования и найдите оригинальные сообщения. 
7 15 15 4 27 12 21 3 11 
001110111101111001001101101100101010001101011 
 
1.6. Формально объясните (как если бы вы писали компьютерную программу) правило кодирования писать каждое слово задом 
наперед. (Вы должны объяснить, как конвертировать последовательность символов, такую как TODAY IS MONDAY


 (Сегодня понедельник) в последовательность YADOT SI YADNOM


). 
 
1.3. Основные определения 
 
Сейчас мы готовы дать некоторые точные определения. 
 
Определение 1.1(Алфавит) 
Алфавит – ограниченный набор символов S ; будем называть 
члены S  символами. 
 
Определение 1.2 (Сообщение, строка, слово) 
Сообщение из алфавита S  – это конечная последовательность 
членов множества S : 

1···
;
,1
n
i
x
x
x
S
i
n
∈
≤ ≤
. 
Сообщение часто понимается как строка членов множества S , 
или слово из множества S , n – это длина сообщения, строки или слова. 
Набор всех строк длины n обозначается 
n
S . Например, когда 

S = B и 
3
n = , множество 
3
B  состоит из строк 
000 001 010 011 100101 110 111. 
Набор всех строк из S  обозначается 
*
S : 

*
0
1
2
···
S
S
S
S
=
∪
∪
∪
. 
Отметим, что 
0
S  состоит из строк с длиной 0; в других словах 
строки не содержат никаких символов. Мы включаем это определение, потому что иногда его удобно использовать. 
 
 

~ 8 ~ 

 

Определение 1.3  (Код, кодовое слово)  
Пусть S и T – это алфавиты. Код c для S , использующий множество T, – это инъективная функция :
c S
T ∗
→
. Для каждого символа 

s
S
∈  строка ( )
c s
T ∗
∈
называется кодовым словом для s . Набор всех 

кодовых слов   
 также понимается как код. Когда |
| 2
T =  

код называется бинарным, тогда |T| = 3, – это тройной код.   В общем 
виде, когда  |T|=b, – это b-арный код. 
Например, пусть 
{
}
, ,
,
S
x y z
T
=
= B, определено 
c(x)=0, c(y)=10, c(z)=11. 
Это бинарный код, а набор кодовых слов 
{
}
0,10,11
C =
. 
Согласно определению, код c присваивает каждому символу из 

S  строку символов из T . Строка может иметь переменную длину. 
Например, предположим, что мы пытаемся построить код для 
 27-символьного английского алфавита A с использованием бинарного алфавита B. Мы можем начать с выбора кодовых слов длиной 4, 
как следующее: 
���� → 0000, ���� → 0001, ���� → 0010. 
Определение требует, чтобы  с было инъективной функцией или 
(как мы обычно говорим) инъекцией. Это математическая форма 
очень разумного требования, что c не присваивает двум различным 
символам одно и то же кодовое слово. Другими словами, если 

( )
( )
{
}
{
}
c s
c s
s
s
′
′
=
⇒
=
. Очевидно, что есть только 16 строк длиной 4 из 

B, поэтому 27 символам из A не могут быть присвоены разные значения. 
До сих пор мы рассматривали только кодирование отдельных 
символов. Расширение сообщений (строк или символов) понятно. 
 
Определение 1.4  (Конкатенация) 
Если 
:
c S
T ∗
→
 это код, мы расширяем c до S∗ следующим образом. Дана строка 
1
2··· n
x x
x  в множестве S∗, определим 

(
)
(
)
(
)
1
1
···
···
n
n
c x
x
c x
c x
=
. 
Этот процесс известен как конкатенация. Отметим, что мы обозначаем расширенную функцию S
T
∗
∗
→
 такой же буквой c. 
Не всегда возможно однозначно восстановить оригинальную 
строку из кодированной версии. Например, пусть 
{ , , }
S
x y z
=
,  определим :
c S
∗
→ B  с помощью 

0,
01,
10
x
y
z
→
→
→
. 

( )
{
}
C
c s s
S
=
∈

~ 9 ~ 

 

Предположим, задана строка 010100, которая, как мы сказали, 
является результатом кодирования строки из множества S∗ с использованием c. Методом проб и ошибок мы находим 2 возможности  
(как минимум): 

0 10 10 0 ,
01 01 0 0 
xzzx
yyxx
→
→
. 
Очевидно, таких ситуаций следует по возможности избегать. 
Определение 1.5 (Однозначно декодируемый) 
Код 
:
c S
T ∗
→
 является однозначно декодируемым (или для сокращения UD), если расширенная функция 
:
c S
T
∗
∗
→
 есть инъекция. 
Это значит, что любой строке из множества T ∗ соответствует не более 
одного сообщения из S∗. 
В главе 2-й мы объясним, как UD свойства могут быть гарантированы простыми конструкциями. 
 
Упражнения 
 
1.7. Двоичный код определен правилом  
����1 → 10, ����2 → 010, ����3 → 100. 
Покажите с помощью примера, что этот код не является однозначно декодируемый. 
1.8. Предположим код :
c S
T ∗
→
 такой, что каждое кодовое слово ( )
c s  имеет одинаковую длину n. Является ли этот код однозначно 
декодируемым? 
1.9. Выразите правила кодирования, используемые в упражнении 1.5, как функции :
c S
T ∗
→
, для соответствующих алфавитов S  и T . 
 
1.4. Экономичное кодирование 
 

Когда был впервые введен электрический телеграф, это позволило передавать только простые электрические импульсы. Таким образом, для того, чтобы отправить сообщения на естественном языке, 
было необходимо кодировать его в алфавит с очень маленьким набором символов. Соответствующий код был изобретен Сэмюэлем Морзе (1791–1872). 
Азбука Морзе использовала алфавит из трех символов (точка, 
тире и длинное тире). 
Каждое кодовое слово содержит точки и тире, заканчивающиеся 
паузами. (Строго говоря, также существуют символы для короткой 

~ 10 ~ 

 

паузы, которая отделяет точки и тире внутри кодового слова, и длинной паузы в конце слова, но мы будем игнорировать их для упрощения). 
Здесь приведены примеры кодирования для A, B, C, D, E, F. 
 

•
−
•
•
•
•
•
−
•
−
•
−
•
•
•
−
−
•






F
E
D
C
B
A

 
                
В главе 2, 3 и 4 мы рассмотрим  как теорию экономичного кодирования  можно применять для сжатия данных.  
 
Упражнения  
 
1.10. Поищите в Интернете стандартную версию азбуки Морзе, 
известную как Международная азбука Морзе. Если этот код формально определен как функция S
T ∗
→
, тогда что за алфавиты S  и T ? 
1.11. Предположим, мы рассматриваем версию Азбуки Морзе 
без символа, который показывает конец каждого кодового слова.  
Каким будет код для BAD?  
Найдите другое английской слово с таким же кодом, показывающее, что это неоднозначно декодируемый код. 
1.12. Семафорный код позволяет людям, которые видят друг 
друга, обмениваться сообщениями. У каждого человека по два флага, 
каждый из которых можно представлять в одной из восьми возможных позиций.  
Два флага не могут занимать одинаковые позиции. Сколько 
символов можно декодировать таким путем, не забывая о том, что кодирующая функция должна быть инъекцией? 
 
1.5. Кодирование для повышения надежности передачи  
информации 
 
Зачастую необходимо отправить сообщения через ненадежные 
каналы, и в таких обстоятельствах желательно использовать метод 
кодирования, который уменьшит вероятность ошибки. Очевидно 
нужно просто повторить сообщение.  
Например, предположим, что инвестор общается с брокером с 
помощью отправки символов B и S  (
,
B
Buy S
Sell
=
=
). С использованием кодировки при неправильном отображении символа брокер может совершить ошибку и выполнить неправильное действие. 

~ 11 ~ 

 

Однако, предположим, что инвестор использует код Buy
BB
→
 и 

Sell
SS
→
. Сейчас, если любой из символов отобразится некорректно, 
брокер будет знать, что где-то есть ошибка, потому что BS и SB не 
являются кодовыми словами, и сможет попросить дальнейших указаний. 
Если инвестор использует больше копий, брокер может принять 
взвешенное решение о намерении, даже когда нет возможности попросить дальнейших указаний. Предположим, инвестор использует 
кодовое слово BBB и SSS.  
Таким образом, если брокер получает сообщение SSB, наиболее 
вероятно, что начальное сообщение было SSS, потому что это означает, что имеет место только одна ошибка, в то время как BBB означает, 
что имеет место 2 ошибки. 
Далее мы опишем более эффективные методы кодирования сообщений, чтобы уменьшить вероятность погрешности из-за ошибок 
при передаче информации. 
 
Упражнения 
 
1.14. Предположим, инвестор использует 5-кратное повторение 
кода, так что Buy
BBBBB

, Sell
SSSSS

. Если мы получаем сообщения следующего содержания, то какие инструкции наиболее вероятны 
в каждом случае? 

BBBSB
SBSBS
SSSSB  
1.15. Предположим, мы хотим отправить числа 1, 2, 3, 4, 5, 6, 
представляющие собой результаты броска игральной кости, с использованием бинарных кодовых слов, имеющих одинаковую длину.  
Какова наименьшая возможная длина кодовых слов? Предположим, требуется, чтобы получатель смог заметить ошибочный бит в 
любом кодовом слове.  
Найдите набор кодовых слов с длиной 4-го символа, которые 
обладают такими свойствами. 
 
1.6. Кодирование для безопасной передачи информации 
 
 Один из старейших кодов был использован Юлием Цезарем более двух тысяч лет назад с намерением секретного общения с командующими его армии. Для сообщения из 27-символьного алфавита A 
было принято следующее правило: