О выполнении Декрета Президента;doc

«Теоретические основы информатики»
3,4 курс
Преподаватели: д.ф.-м.н., профессор Маренич Е.Е., к.ф.-м.н., доцент Муравьева О.В.
Структура и содержание дисциплины
Общая трудоемкость дисциплины составляет 4 зачетные единицы (144 часа, в том
числе 84 часа аудиторной работы и 60 часов самостоятельной работы).
Таблица 2. Содержание дисциплины
Наименование
Содержание раздела
раздела дисциплины
(дидактические единицы)
1. Основные понятия
Процесс передачи информации. Измерение информации.
теории информации
Комбинаторный подход. Вероятностный подход.
2. Теория кодирования
Основные понятия. Побуквенное кодирование. Разделимые коды.
Префиксные коды. Критерий однозначности декодирования.
Неравенство Крафта–Макмиллана для разделимых кодов. Условие
существования разделимого кода с заданными длинами кодовых
слов. Оптимальные коды. Методы построения оптимальных кодов.
Метод Хафмана. Методы сжатия. Самокорректирующиеся коды.
Коды Хэмминга. Коды Хэмминга, исправляющие единичную
ошибку. Методы шифрования.
3. Теория автоматов
Конечные автоматы. Автоматные функции. Состояния автомата.
Эквивалентность состояний. Теорема об эквивалентности состояний
конечного автомата. Детерминированные функции. Задание
детерминированных функций при помощи деревьев, вес функций.
Ограниченно-детерминированные функции. Задание ограниченнодетерминированных функций диаграммами переходов и
каноническими уравнениями.
Автоматы без выхода. Автоматы как распознаватели. Представимые
и регулярные собятия. Теорема Клини.
Примерный перечень вопросов к зачету (6 семестр):
1. Измерение информации. Формула Хартли.
2. Измерение информации. Формула Шеннона.
3. Кодирование и декодирование. Основные понятия.
1
4. Алфавитное кодирование. Префиксная схема кодирования, разделимая схема
кодирования.
5. Оптимальное алфавитное кодирование. Свойства. Схема алфавитного кодирования
Хаффмана.
6. Код Фано.
7. Помехоустойчивое кодирование. Основные понятия
8. Код Хемминга.
9. Методы сжатия. Методы RLE и Зива–Лемпела.
10. Метод арифметического сжатия.
11. Криптографические методы. Шифрование с закрытым ключом.
12. Шифрование с открытым ключом. Метод RSA.
Примерный перечень вопросов к экзамену (7 семестр):
13. Понятие конечного автомата. Основные способы задания конечных автоматов.
Примеры.
14. Детерминированные функции. Задание детерминированных функций при помощи
деревьев, вес функций.
15. Задание ограниченно-детерминированных функций диаграммами переходов и
каноническими уравнениями. Преобразование автоматными функциями периодических
последовательностей.
16. Задачи диагностики конечных автоматов. Синтез конечных автоматов.
17. Отличимые состояния конечного автомата. Построение приведенного конечного
автомата.
18. Изоморфные и неотличимые конечные автоматы.
19. Использование
конечных
автоматов
для
решения
задач
распознавания.
Представимые события.
20. Регулярные события. Теорема Клини.
Основная литература:
1. Теоретические основы информатики: Учеб. пособие для студентов высших учебных
заведений / В. Л. Матросов, В. А. Горелик, С. А. Жданов и др. – М.: Академия, 2009.
2. Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию
вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и
криптографию. – СПб.: БХВ-Петербург, 2010.
3. Матросов В. Л., Угольникова Б. З. Введение в теорию автоматов. – М.: Прометей,
2
2000.
4. Новиков Ф. А. Дискретная математика для программистов. – СПб.: Питер, 2002.
Дополнительная литература
5. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. – М.:
Диалог-МИФИ, 2002.
6. Введение в криптографию / Под ред. В. В. Ященко. – М.: Изд-во МЦНМО, 2000.
7. Верещагин Н. К., Щепин Е. В. Информация, кодирование и предсказание. – М.: Издво МЦНМО, 2012.
8. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. –
М.: Физматлит, 2005.
9. Карпов Ю. Г. Теория автоматов. – СПб.: Питер, 2002.
10. Кудрявцев В. Б., Алешин С. В., Подколезин А. С. Введение в теорию автоматов. – М.:
Наука, 1985.
11. Лидовский В. В. Теория информации. – М.: Компания Спутник+, 2004.
12. Марченков C. C. Конечные автоматы. – М.: Физматлит, 2008.
13. Романовский И. В. Дискретный анализ. – СПб.: Невский диалект; БХВ-Петербург,
2004.
14. Ромащенко А. Е., Румянцев А. Ю., Шень А. Заметки по теории кодирования. – М.:
Изд-во МЦНМО, 2011.
15. Сэломон Д. Сжатие данных, изображений и звука. – М.: Техносфера, 2006.
16. Ту Дж., Гонсалес Р. Принципы распознавания образов. – М.: Мир, 1978.
17. Чечета С. И. Введение в дискретную теорию информации и кодирования. – М.:
Изд-во МЦНМО, 2011.
18. Шеннон К. Работы по теории информации и кибернетике. – М.: ИЛ, 1963.
19. Ширяев А. Н. Вероятностно-статистические методы в теории принятия решений. –
М.: Изд-во МЦНМО, 2011.
20. Яблонский С. В. Введение в дискретную математику. – М.: Высшая школа, 2010.
3