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

Оглавление

Предисловие

Введение

Часть I. ТЕОРИЯ ИНФОРМАЦИИ

1. Исходные понятия информатики
1.1. Начальные определения
1.2. Формы представления информации
1.3. Преобразование сообщений
Контрольные вопросы и задания к гл. 1

2. Понятие информации в теории Шеннона
2.1. Понятие энтропии
2.1.1. Энтропия как мера неопределенности
2.1.2. Свойства энтропии
2.1.3. Условная энтропия
2.2. Энтропия и информация
2.3. Информация и алфавит
Контрольные вопросы и задания к гл. 2

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

4. Представление и обработка чисел в компьютере
4.1. Системы счисления
4.2. Представление чисел в различных системах счисления
4.2.1. Перевод целых чисел из одной системы счисления в другую
4.2.2. Перевод дробных чисел из одной системы счисления в другую
4.2.3. Понятие экономичности системы счисления
4.2.4. Перевод чисел между системами счисления 2 → 8 → 16
4.2.5. Преобразование нормализованных чисел
4.3. Кодирование чисел в компьютере и действия над ними
4.3.1. Кодирование и обработка в компьютере целых чисел без знака
4.3.2. Кодирование и обработка в компьютере целых чисел со знаком
4.3.3. Кодирование и обработка в компьютере вещественных чисел
Контрольные вопросы и задания к гл. 4

5. Передача информации
5.1. Общая схема передачи информации по линии связи
5.2. Характеристики дискретного канала связи
5.3. Влияние шумов на пропускную способность дискретного канала связи
5.3.1. Математическая постановка задачи
5.3.2. Однородный двоичный симметричный канал
5.3.3. Однородный симметричный канал со стиранием
5.4. Передача информации по непрерывному каналу
5.5. Способы передачи информации в компьютерных линиях связи
5.5.1. Канал параллельной передачи
5.5.2. Последовательная передача данных
Контрольные вопросы и задания к гл. 5

6. Обеспечение надежности передачи и хранения информации
6.1. Общие подходы
6.2. Принципы построения (n; k)-кодов
6.2.1. (n; k)-коды, обнаруживающие ошибки
6.2.2. (n; k)-коды, исправляющие ошибки
6.3. Систематический помехоустойчивый код
6.3.1. Общие принципы построения систематических кодов
6.3.2. Канонический систематический код
6.3.3. Кодер и декодер систематического кода
6.4. Код Хемминга
6.5. Матричные коды
Контрольные вопросы и задания к гл. 6

7. Элементы криптографии
7.1. Основные понятия
7.1.1. Терминология криптографии
7.1.2. Обзор криптографических методов
7.1.3. Постановка задачи шифрования
7.2. Симметричное шифрование
7.2.1. Схема криптосистемы с симметричным шифрованием
7.2.2. Некоторые методы шифрования
7.2.3. Совершенная стойкость шифра. Требования, предъявляемые к ключам
7.3. Шифрование с открытым ключом
7.3.1. Общее представление об ассиметричной криптосистеме
7.3.2. Формирование ключей и шифрование в криптосистеме RSA
7.4. Электронная подпись
7.4.1. Общие принципы использования электронной подписи
7.4.2. Вычисление и проверка подлинности электронной подписи
Контрольные вопросы и задания к гл. 7

8. Хранение информации
8.1. Классификация данных. Проблемы представления данных
8.2. Представление элементарных данных в ОЗУ
8.3. Структуры данных и их представление в ОЗУ
8.3.1. Классификация и примеры структур данных
8.3.2. Понятие логической записи
8.3.3. Организация структур данных в ОЗУ
8.4. Представление данных на внешних носителях
8.4.1. Иерархия структур данных на внешних носителях
8.4.2. Особенности устройств хранения информации
Контрольные вопросы и задания к гл. 8

Часть II. АЛГОРИТМЫ. МОДЕЛИ. СИСТЕМЫ

9. Элементы теории алгоритмов
9.1. Нестрогое определение алгоритма
9.2. Рекурсивные функции
9.3. Алгоритм как абстрактная машина
9.3.1. Общие подходы
9.3.2. Алгоритмическая машина Поста
9.3.3. Алгоритмическая машина Тьюринга
9.4. Нормальные алгоритмы Маркова
9.5. Сопоставление алгоритмических моделей
9.6. Проблема алгоритмической разрешимости
9.7. Сложность алгоритма
Контрольные вопросы и задания к гл. 9

10. Формализация представления алгоритмов
10.1. Формальные языки
10.1.1. Формальная грамматика
10.1.2. Способы описания формальных языков
10.2. Способы представления алгоритмов
10.2.1. Исполнитель алгоритма
10.2.2. Строчная словесная запись алгоритма
10.2.3. Графическая форма представления алгоритма
10.2.4. Классификация способов представления алгоритмов
10.3. Структурная теорема
Контрольные вопросы и задания к гл. 10

11. Представления о конечном автомате
11.1. Общие подходы к описанию устройств, предназначенных для автоматической обработки дискретной информации
11.2. Комбинационные схемы
11.3. Конечные автоматы
11.3.1. Способы описания конечного автомата
11.3.2. Схемы из логических элементов и задержек
11.3.3. Эквивалентные автоматы
Контрольные вопросы и задания к гл. 11

12. Модели и системы
12.1. Понятие модели
12.1.1. Общая идея моделирования
12.1.2. Классификация моделей
12.1.3. Понятие математической модели
12.2. Понятие системы
12.2.1. Определение объекта
12.2.2. Определение системы
12.2.3. Формальная система
12.2.4. Значение формализации
12.3. Этапы решения задачи посредством компьютера
12.4. Об объектном подходе в прикладной информатике
Контрольные вопросы и задания к гл. 12

Заключение

Приложение A. Элементы теории вероятностей
А.1. Понятие вероятности
А.2. Сложение и умножение вероятностей
A.3. Условная вероятность
Контрольные вопросы и задания к Приложению А

Приложение B. Некоторые соотношения логики Глоссарий

Литература