Автор получил от читателей ряд замечаний, касавшихся содержания, изменилась учебная программа дисциплины, возникла необходимость рассмотреть некоторые новые разделы (например, элементы криптографии) — все это послужило причинами переработки, исправления и дополнения материала. <...> Шеннон опубликовал знаменитую работу «Математическая теория связи», где изложил математические принципы кодирования и передачи информации, а также предложил метод объективного измерения количества информации — именно эти идеи и составили основу новой науки — ин∗ Ранее, в 1943 году, британскими инженерами Т. <...> Теоретическая информатика объединяет следующие дисциплины: теория информации, теория алгоритмов, теория кодирования, теория систем и моделей, теория конечных автоматов, вычислительная математика, математическое программирование и целый ряд других. <...> Строится теория информации подобно другим теориям в математике: сначала аксиоматически определяются исходные понятия, а затем из них путем рассуждений доказывается справедливость новых положений или теорем — именно таким путем шел основоположник данной теории Клод Шеннон. <...> Теория информации основой — без нее информация не может проявиться, передаваться и сохраняться, например восприниматься и запоминаться нами. <...> Исходные понятия информатики 25 Таким образом, понятия «знак», «буква» и «символ» нельзя считать тождественными, хотя весьма часто различия между ними не проводят, поэтому в информатике существуют понятия «символьная переменная», «кодировка символов алфавита», «символьная информация» — во всех приведенных примерах вместо термина «символьный» корректнее было бы использовать «знаковый» или «буквенный». <...> Теория информации Последнее качество—универсальность—оказывается следствием того обстоятельства, что любые дискретные сообщения, составленные в различных алфавитах, посредством обратимого кодирования можно привести к единому алфавиту <...>
Теоретические_основы_информатики._Учебник_для_вузов._(1).pdf
УДК 004:621.391(075)
ББК 32.81
С77
Стариченко Б. Е.
С77 Теоретические основы информатики. Учебник для вузов. –
3-е изд. перераб. и доп. – М.: Горячая линия – Телеком,
2016. – 400 с.: ил.
ISBN 978-5-9912-0462-0.
Рассмотрены вопросы теории информации Шеннона, теории
кодирования, криптографии, элементы теории алгоритмов
и теории конечных автоматов, а также общие вопросы моделирования
и описания систем. Отбор материала произведен в соответствии
с программой подготовки студентов высших учебных
заведений, обучающихся по направлению подготовки
«Информационные системы и технологии». Каждая глава содержит
многочисленные примеры решения задач, а также вопросы
и задания для самоконтроля.
Для студентов вузов, изучающих информатику в качестве
профильной дисциплины, а также школьных учителей информатики.
ББК
32.81
ISBN 978-5-9912-0462-0
© Б. Е. Стариченко, 2014, 2016
© Издательство «Горячая линия – Телеком», 2016
Адрес
издат
е
л
ь
ст
ва
в
И
н
т
е
рн
ет
WWW.TE
CH
BO
OK
.RU
Стр.2
Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
6
Часть I. ТЕОРИЯ ИНФОРМАЦИИ. . . . . . . . . . . . . . . . . . . . . 12
1. Исходные понятия информатики . . . . . . . . . . . . . . . . . . . . 16
1.1. Начальные определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2. Формы представления информации . . . . . . . . . . . . . . . . . 22
1.3. Преобразование сообщений . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Контрольные вопросы и задания к гл. 1. . . . . . . . . . 31
2. Понятие информации в теории Шеннона . . . . . . . . . 33
2.1. Понятие энтропии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.1.1. Энтропия как мера неопределенности . . . . . . . . . . 33
2.1.2. Свойства энтропии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.3. Условная энтропия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2. Энтропия и информация . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3. Информация и алфавит . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Контрольные вопросы и задания к гл. 2. . . . . . . . . . 58
3. Кодирование символьной информации . . . . . . . . . . . . 60
3.1. Постановка задачи первичного кодирования. Первая
теорема Шеннона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2. Способы построения двоичных кодов . . . . . . . . . . . . . . . 67
3.2.1. Равномерное алфавитное двоичное кодирование.
Байтовый код. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.2.2. Алфавитное неравномерное двоичное кодирование
сигналами равной длительности. Коды с разделителем
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Стр.394
Оглавление
395
3.2.3. Алфавитное неравномерное двоичное кодирование
сигналами равной длительности. Префиксные
коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.2.4. Алфавитное кодирование с неравной длительностью
элементарных сигналов. Код Морзе. . . . . . . 80
3.2.5. Блочное двоичное кодирование . . . . . . . . . . . . . . . . . 81
Контрольные вопросы и задания к гл. 3. . . . . . . . . . 83
4. Представление и обработка чисел в компьютере . 85
4.1. Системы счисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.2. Представление чисел в различных системах счисления
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.2.1. Перевод целых чисел из одной системы счисления
в другую . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.2.2. Перевод дробных чисел из одной системы счисления
в другую . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.2.3. Понятие экономичности системы счисления . . . 96
4.2.4. Перевод чисел между системами счисления 2 →
8 → 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.2.5. Преобразование нормализованных чисел . . . . . . . 105
4.3. Кодирование чисел в компьютере и действия над
ними . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.3.1. Кодирование и обработка в компьютере целых
чисел без знака . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.3.2. Кодирование и обработка в компьютере целых
чисел со знаком . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.3.3. Кодирование и обработка в компьютере вещественных
чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Контрольные вопросы и задания к гл. 4. . . . . . . . . . 120
5. Передача информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.1. Общая схема передачи информации по линии связи 123
5.2. Характеристики дискретного канала связи . . . . . . . . . 127
5.3. Влияние шумов на пропускную способность дискретного
канала связи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.3.1. Математическая постановка задачи. . . . . . . . . . . . . 132
5.3.2. Однородный двоичный симметричный канал . . 134
5.3.3. Однородный симметричный канал со стиранием 137
5.4. Передача информации по непрерывному каналу . . . . 139
Стр.395
396
Оглавление
5.5. Способы передачи информации в компьютерных линиях
связи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
5.5.1. Канал параллельной передачи . . . . . . . . . . . . . . . . . . 142
5.5.2. Последовательная передача данных . . . . . . . . . . . . 143
Контрольные вопросы и задания к гл. 5. . . . . . . . . . 145
6. Обеспечение надежности передачи и хранения информации
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.1. Общие подходы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.2. Принципы построения (n, k)-кодов . . . . . . . . . . . . . . . . . . . 155
6.2.1. (n, k)-коды, обнаруживающие ошибки . . . . . . . . . . 155
6.2.2. (n, k)-коды, исправляющие ошибки . . . . . . . . . . . . . 158
6.3. Систематический помехоустойчивый код . . . . . . . . . . . . 161
6.3.1. Общие принципы построения систематических
кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.3.2. Канонический систематический код . . . . . . . . . . . . 163
6.3.3. Кодер и декодер систематического кода . . . . . . . . 167
6.4. Код Хемминга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
6.5. Матричные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
Контрольные вопросы и задания к гл. 6. . . . . . . . . . 174
7. Элементы криптографии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
7.1.1. Терминология криптографии . . . . . . . . . . . . . . . . . . . 177
7.1.2. Обзор криптографических методов . . . . . . . . . . . . 179
7.1.3. Постановка задачи шифрования . . . . . . . . . . . . . . . . 180
7.2. Симметричное шифрование . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.2.1. Схема криптосистемы с симметричным шифрованием
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.2.2. Некоторые методы шифрования . . . . . . . . . . . . . . . . 184
7.2.3. Совершенная стойкость шифра. Требования, предъявляемые
к ключам . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.3. Шифрование с открытым ключом . . . . . . . . . . . . . . . . . . 194
7.3.1. Общее представление об ассиметричной криптосистеме
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
7.3.2. Формирование ключей и шифрование в криптосистеме
RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
Стр.396
Оглавление
397
7.4. Электронная подпись . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
7.4.1. Общие принципы использования электронной
подписи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
7.4.2. Вычисление и проверка подлинности электронной
подписи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
Контрольные вопросы и задания к гл. 7. . . . . . . . . . 206
8. Хранение информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
8.1. Классификация данных. Проблемы представления
данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
8.2. Представление элементарных данных в ОЗУ . . . . . . . 212
8.3. Структуры данных и их представление в ОЗУ . . . . . 216
8.3.1. Классификация и примеры структур данных . . 217
8.3.2. Понятие логической записи . . . . . . . . . . . . . . . . . . . . . 222
8.3.3. Организация структур данных в ОЗУ . . . . . . . . . . 224
8.4. Представление данных на внешних носителях . . . . . . 227
8.4.1. Иерархия структур данных на внешних носителях
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
8.4.2. Особенности устройств хранения информации . 229
Контрольные вопросы и задания к гл. 8. . . . . . . . . . 232
Часть II. АЛГОРИТМЫ. ÌÎÄÅËÈ. СИСТЕМЫ . . . . . . 233
9. Элементы теории алгоритмов . . . . . . . . . . . . . . . . . . . . . . . 234
9.1. Нестрогое определение алгоритма . . . . . . . . . . . . . . . . . . . 234
9.2. Рекурсивные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
9.3. Алгоритм как абстрактная машина. . . . . . . . . . . . . . . . . . 247
9.3.1. Общие подходы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
9.3.2. Алгоритмическая машина Поста . . . . . . . . . . . . . . . 249
9.3.3. Алгоритмическая машина Тьюринга . . . . . . . . . . . 252
9.4. Нормальные алгоритмы Маркова . . . . . . . . . . . . . . . . . . . 259
9.5. Сопоставление алгоритмических моделей. . . . . . . . . . . . 261
9.6. Проблема алгоритмической разрешимости . . . . . . . . . . 263
9.7. Сложность алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
Контрольные вопросы и задания к гл. 9. . . . . . . . . . 269
10.Ôîðìàëèçàöèÿ представления алгоритмов . . . . . . . . 271
10.1. Формальные языки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
10.1.1. Формальная грамматика . . . . . . . . . . . . . . . . . . . . . . . 271
Стр.397
398
Оглавление
10.1.2. Способы описания формальных языков . . . . . . . . 274
10.2. Способы представления алгоритмов . . . . . . . . . . . . . . . . . 279
10.2.1. Исполнитель алгоритма . . . . . . . . . . . . . . . . . . . . . . . . 280
10.2.2. Строчная словесная запись алгоритма . . . . . . . . . 282
10.2.3. Графическая форма представления алгоритма 289
10.2.4. Классификация способов представления алгоритмов
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
10.3. Структурная теорема . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
Контрольные вопросы и задания к гл. 10. . . . . . . . . 294
11.Ïðåäñòàâëåíèÿ о конечном автомате . . . . . . . . . . . . . . . 296
11.1. Общие подходы к описанию устройств, предназначенных
для автоматической обработки дискретной информации
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
11.2. Комбинационные схемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
11.3. Конечные автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
11.3.1. Способы описания конечного автомата . . . . . . . . . 306
11.3.2. Схемы из логических элементов и задержек . . . 309
11.3.3. Эквивалентные автоматы . . . . . . . . . . . . . . . . . . . . . . . 317
Контрольные вопросы и задания к гл. 11. . . . . . . . . 320
12.Ìîäåëè и системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
12.1. Понятие модели . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
12.1.1. Общая идея моделирования . . . . . . . . . . . . . . . . . . . . 324
12.1.2. Классификация моделей . . . . . . . . . . . . . . . . . . . . . . . . 327
12.1.3. Понятие математической модели . . . . . . . . . . . . . . . 333
12.2. Понятие системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
12.2.1. Определение объекта . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
12.2.2. Определение системы . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
12.2.3. Формальная система . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
12.2.4. Значение формализации . . . . . . . . . . . . . . . . . . . . . . . . 351
12.3. Этапы решения задачи посредством компьютера . . . 352
12.4. Об объектном подходе в прикладной информатике . 357
Контрольные вопросы и задания к гл. 12. . . . . . . . . 362
Заключение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
Приложение A. Элементы теории вероятностей . . 366
Стр.398
Оглавление
399
A.1. Понятие вероятности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
A.2. Сложение и умножение вероятностей . . . . . . . . . . . . . . . 369
A.3. Условная вероятность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
Контрольные вопросы и задания к Приложению
А. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
Приложение B. Некоторые соотношения логики . . 380
Глоссарий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
Стр.399