Теоретические основы информатики. Стариченко Б.Е.

3-е изд., перераб. и доп. - М.: 2016. — 400 с.

Рассмотрены вопросы теории информации Шеннона, теории кодирования, криптографии, элементы теории алгоритмов и теории конечных автоматов, а также общие вопросы моделирования и описания систем. Отбор материала произведен в соответствии с программой подготовки студентов высших учебных заведений, обучающихся по направлению подготовки "Информационные системы и технологии". Каждая глава содержит многочисленные примеры решения задач, а также вопросы и задания для самоконтроля. Для студентов вузов, изучающих информатику в качестве профильной дисциплины, а также школьных учителей информатики.

Формат: pdf

Размер: 10 Мб

Смотреть, скачать: drive.google

Оглавление
Предисловие 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
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. Перевод чисел между системами счисления 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
5.5. Способы передачи информации в компьютерных линиях связи 142
5.5.1. Канал параллельной передачи 142
5.5.2. Последовательная передача данных 143
Контрольные вопросы и задания к гл. 5 145
6. Обеспечение надежности передачи и хранения информации 147
6.1. Общие подходы 147
6.2. Принципы построения (п, /г)-кодов 155
6.2.1. (п, /г)-коды, обнаруживающие ошибки 155
6.2.2. (п, /г)-коды, исправляющие ошибки 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
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
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
Приложение А. Элементы теории вероятностей 366
АЛ. Понятие вероятности 366
А.2. Сложение и умножение вероятностей 369
А.З. Условная вероятность 373
Контрольные вопросы и задания к Приложению А 378
Приложение В. Некоторые соотношения логики 380
Глоссарий 383
Литература 391