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