Теоретические основы информатики

Оглавление

Предисловие 6

Введение 9
Раздел 1. Теория информации 15
Глава 1. Исходные понятия информатики 18
1.1. Начальные определения 18
1.2. Формы представления информации 23
1.3. Преобразование сообщений 26

Глава 2. Понятие информации в теории Шеннона 33
2.1. Понятие энтропии 33
2.1.1. Энтропия как мера неопределенности 33
2.1.2. Свойства энтропии 37
2.1.3. Условная энтропия 39
2.2. Энтропия и информация 43
2.3. Информация и алфавит 50

Глава 3. Кодирование символьной информации 58
3.1. Постановка задачи кодирования. Первая теорема Шеннона. 58
3.2. Способы построения двоичных кодов 64
3.2.1. Алфавитное неравномерное двоичное кодирование. Префиксный код. Код Хаффмана. 64
3.2.2. Равномерное алфавитное двоичное кодирование. Байтовый код. 71
3.2.3. Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе. 74
3.2.4. Блочное двоичное кодирование 76

Глава 4. Представление и обработка чисел в компьютере 80
4.1. Системы счисления 81
4.2. Представление чисел в различных системах счисления 84
4.2.1. Перевод целых чисел из одной системы счисления в другую 84
4.2.2. Перевод дробных чисел из одной системы счисления в другую 88
4.2.3. Понятие экономичности системы счисления 90
4.2.4. Перевод чисел между системами счисления 2 « 8 « 16 93
4.2.5. Преобразование нормализованных чисел 96
4.3. Кодирование чисел в компьютере и действия над ними 101
4.3.1. Кодирование и обработка в компьютере целых чисел без знака 102
4.3.2. Кодирование и обработка в компьютере целых чисел со знаком 104
4.3.3. Кодирование и обработка в компьютере вещественных чисел 109

Глава 5. Передача информации 117
5.1. Общая схема передачи информации в линии связи 117
5.2. Характеристики канала связи 120
5.3. Влияние шумов на пропускную способность канала 123
5.4. Обеспечение надежности передачи и хранения информации 126
5.4.1. Постановка задачи 126
5.4.2. Коды, обнаруживающие ошибку 128
5.4.3. Коды, исправляющие одиночную ошибку 129
5.5. Способы передачи информации в компьютерных линиях связи 133
5.5.1. Канал параллельной передачи 133
5.5.2. Последовательная передача данных 134
5.5.3. Связь компьютеров по телефонным линиям 136

Глава 6. Хранение информации 140
6.1. Классификация данных. Проблемы представления данных. 140
6.2. Представление элементарных данных в ОЗУ 144
6.3. Структуры данных и их представление в ОЗУ 148
6.3.1. Классификация и примеры структур данных 149
6.3.2. Понятие логической записи 155
6.3.3. Организация структур данных в ОЗУ 156
6.4. Представление данных на внешних носителях 160
6.4.1. Иерархия структур данных на внешних носителях 160
6.4.2. Особенности устройств хранения информации 162
Раздел 2. Алгоритмы. Модели. Системы 166

Глава 7. Элементы теории алгоритмов 167
7.1. Нестрогое определение алгоритма 167
7.2. Рекурсивные функции 173
7.3. Алгоритм как абстрактная машина 179
7.3.1. Общие подходы 179
7.3.2. Алгоритмическая машина Поста 181
7.3.3. Алгоритмическая машина Тьюринга 184
7.4. Нормальные алгоритмы Маркова 192
7.5. Сопоставление алгоритмических моделей 193
7.6. Проблема алгоритмической разрешимости 196
7.7. Сложность алгоритма 198

Глава 8. Формализация представления алгоритмов 203
8.1. Формальные языки 203
8.1.1. Формальная грамматика 203
8.1.2. Способы описания формальных языков 206
8.2. Способы представления алгоритмов 210
8.2.1. Исполнитель алгоритма 211
8.2.2. Строчная словесная запись алгоритма 213
8.2.3. Графическая форма записи 219
8.2.4. Классификация способов представления алгоритмов 221
8.3. Структурная теорема 222

Глава 9. Представление о конечном автомате 227
9.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации 227
9.2. Дискретные устройства без памяти 231
9.3. Конечные автоматы 235
9.3.1. Способы задания конечного автомата 235
9.3.2. Схемы из логических элементов и задержек 239
9.3.3. Эквивалентные автоматы 243

Глава 10. Модели и системы 248
10.1. Понятие модели 248
10.1.1. Общая идея моделирования 249
10.1.2. Классификация моделей 252
10.1.3. Понятие математической модели 258
10.2. Понятие системы 261
10.2.1. Определение объекта 261
10.2.2. Определение системы 264
10.2.3. Формальная система 270
10.2.4. Значение формализации 275
10.3. Этапы решения задачи посредством компьютера 276
10.4. Об объектном подходе в прикладной информатике 281
Заключение 287

Приложение A. Элементы теории вероятностей 289
A.1. Понятие вероятности 289
A.2. Сложение и умножение вероятностей 292
A.3. Условная вероятность 296

Приложение Б. Некоторые соотношения логики 301
Глоссарий 303
Список литературы 309