Теоретические основы информатики
Рассматриваются вопросы теории информации Шеннона, теории кодирования, элементы теории алгоритмов и теории конечных автоматов, а также общие вопросы моделирования и описания систем. Отбор материала произведен в соответствии с программой подготовки студентов педагогических вузов по специальности «030100-Информатика». Каждая глава содержит многочисленные примеры решения задач, а также вопросы и задания для самоконтроля.
Для студентов педагогических вузов, изучающих информатику в качестве профильной дисциплины, а также школьных учителей информатики. Автор: Стариченко Б. Е....
- Предисловие
- Таким образом - формулировки и наиболее важные утверждения.
- Введение
- Раздел 1. ТЕОРИЯ ИНФОРМАЦИИ
- Начальные определения
- Формы представления информации
- Преобразование сообщений
- Контрольные вопросы и задания
- Энтропия как мера неопределенности
- Пример 2.1
- Свойства энтропии
- Энтропия сложного опыта, состоящего из нескольких независимых, равна сумме энтропии отдельных опытов.
- При прочих равных условиях наибольшую энтропию имеет опыт с равновероятными исходами.
- Условная энтропия
- Пример 2.2
- Пример 2.3
- Энтропия и информация
- Энтропия опыта равна той информации, которую получаем в результате его осуществления.
- Пример 2.5
- Пример 2.7
- Пример 2.8
- Информация и алфавит
- Контрольные вопросы и задания
- Глава 3. Кодирование символьной информации
- Постановка задачи кодирования, Первая теорема Шеннона
- При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.
- При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
- Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды
- Пример 3.1.
- Равномерное алфавитное двоичное кодирование. Байтовый код
- Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе
- Блочное двоичное кодирование
- Пример 3.2.
- Контрольные вопросы и задания
- Глава 4. Представление и обработка чисел в компьютере
- Системы счисления
- Перевод целых чисел из одной системы счисления в другую
- Пример 4.1
- Пример 4.2
- Пример 4.3
- Перевод дробных чисел из одной системы счисления в другую
- Пример 4.4.
- Пример 4.5
- Понятие экономичности системы счисления
- Пример 4.6
- Преобразование нормализованных чисел
- Пример 4.8
- Пример 4.9
- Кодирование чисел в компьютере и действия над ними
- Кодирование и обработка в компьютере целых чисел без знака
- Пример 4.11
- Пример 4.12
- Кодирование и обработка в компьютере целых чисел со знаком
- Пример 4.13
- Пример 4.14
- Пример 4.15
- Кодирование и обработка в компьютере вещественных чисел
- Пример 4.16
- Пример 4.17
- Контрольные вопросы и задания
- Общая схема передачи информации в линии связи
- Характеристики канала связи
- Пример 5.1
- Влияние шумов на пропускную способность канала
- Пример 5.2
- Постановка задачи
- Коды, обнаруживающие ошибку
- Коды, исправляющие одиночную ошибку
- Пример 5.3
- Пример 5.4
- Канал параллельной передачи
- Последовательная передача данных
- Связь компьютеров по телефонным линиям
- Контрольные вопросы и задания
- Классификация данных. Проблемы представления данных
- Представление элементарных данных в ОЗУ
- Структуры данных и их представление в ОЗУ
- Классификация и примеры структур данных
- Понятие логической записи
- Организация структур данных в ОЗУ
- Иерархия структур данных на внешних носителях
- Особенности устройств хранения информации
- Контрольные вопросы и задания
- Раздел 2. АЛГОРИТМЫ. МОДЕЛИ. СИСТЕМЫ
- Нестрогое определение алгоритма
- Рекурсивные функции
- Пример 7.2
- Пример 7.4
- Пример 7.5
- Класс алгоритмически (или машинно-) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций.
- Общие подходы
- Алгоритмическая машина Поста
- Пример 7.6
- Пример 7.7
- Алгоритмическая машина Тьюринга
- Пример 7.8
- Пример 7.9
- Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга.
- Нормальные алгоритмы Маркова
- Пример 7.11
- Пример 7.12
- Сопоставление алгоритмических моделей
- Проблема алгоритмической разрешимости
- Сложность алгоритма
- Контрольные вопросы и задания
- Глава 8. Формализация представления алгоритмов
- Формальная грамматика
- Пример 8.1
- Пример 8.2
- Способы описания формальных языков
- Способы представления алгоритмов
- Исполнитель алгоритма
- Строчная словесная запись алгоритма
- Графическая форма записи
- Классификация способов представления алгоритмов
- Структурная теорема
- Любому неструктурному алгоритму может быть построен эквивалентный ему структурный алгоритм.
- Контрольные вопросы и задания
- Глава 9. Представление о конечном автомате
- Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- Дискретные устройства без памяти
- Пример 9.1
- Способы задания конечного автомата
- Пример 9.2.
- Пример 9.3
- Схемы из логических элементов и задержек
- Пример 9.4
- Эквивалентные автоматы
- Пример 9.5
- Контрольные вопросы и задания
- Глава 10. Модели и системы
- Понятие модели
- Общая идея моделирования
- Классификация моделей
- Модели структурные и функциональные
- Модели натурные и информационные
- Модели проверяемые и непроверяемые
- Модели по назначению
- Понятие математической модели
- Определение объекта
- Определение системы
- Системы статические и динамические
- Системы замкнутые и незамкнутые
- Системы естественные и искусственные
- Формальная система
- Пример 10.1
- Пример 10.4
- Значение формализации
- Этапы решения задачи посредством компьютера
- Об объектном подходе в прикладной информатике
- Контрольные вопросы и задания
- Заключение
- А.1. Понятие вероятности
- Пример А.1
- А.2. Сложение и умножение вероятностей
- Вероятность какого-либо одного из двух исходов независимых и несовместных событий равна сумме их вероятностей
- Пример А.3
- Пример А.4
- A.3. Условная вероятность
- Пример А.5
- Пример А.7
- Контрольные вопросы и задания
- Глоссарий
- Список литературы