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

Учебное пособие. — Симферополь: Куб, 2016. — 232 с.: ил. — ISBN 978-5-9908044-1-8.Введение. Измерение информации. Энтропия и её свойства. Энтропия источника дискретной информации. Свойства энтропии источника дискретной информации. Совместная и условная энтропия. Информация и её свойства. Энтропия непрерывной информации. Передача дискретной информации, пропускная способность канала и теорема Шеннона. Скорость передачи и пропускная способность канала. Основная теорема Шеннона о кодировании. Передача непрерывной информации 41. Сигналы и их спектры. Дискретизация сигналов. Теорема Котельникова. Аналого-цифровое и цифро-аналоговое преобразование информации. Пропускная способность непрерывного канала с аддитивной помехой с учётом дискретизации сигнала. Алгоритмическая обработка информации. Логические основания математики и алгоритмы. Рекурсивные функции. Формальные (аксиоматические) теории. Формальный вывод теорем и алгоритмы. Теорема Гёделя о неполноте формальной арифметики. Алгоритмическая модель (машина) Тьюринга. Машины Тьюринга и рекурсивные функции. Алгоритмическая модель А. А. Маркова. Алгоритмическая разрешимость. Неразрешимые формальные теории. Теоремы Чёрча. Алгоритмическая модель RAM с равнодоступными ячейками памяти. Сложность алгоритмов и вычислительных проблем 121. Временная и пространственная сложность алгоритмических моделей. Временная и пространственная сложность вычислительных проблем. Класс P. Проблемы вычисления свойств, недетерминированные вычисления, классы NP и NPC. Установление NP-полноты вычислительных проблем распознавания свойств. NP-трудные проблемы. Полиномиальная сводимость и класс co-NP в терминах языков. Псевдополиномиальная сводимость и сильная NP-полнота. Другие классы сложности. Матроиды, жадные алгоритмы и сложность алгоритмического решения задач. Колмогоровская сложность и количество информации. Введение. Основные понятия колмогоровской теории сложности. Колмогоровский подход к определению количества информации. Приложение A. Префиксные коды и неравенство Крафта-Макмиллана. Код Хаффмана. Приложение B: Доказательство теоремы Шеннона о блоковом кодировании. Приложение С: Универсальные частично рекурсивные функции. Литература.