Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет)
|
Скачать 77.27 Kb.
|
| Министерство образования Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет) Ф.К. Алиев, И.А. Юров КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ И ТЕОРИИ АЛГОРИТМОВ Для студентов, специализирующихся в области защиты информации Москва 2003 Аннотация к учебному пособию «Курс лекций по математической логики и теории алгоритмов для студентов специализирующихся в области защиты информации». В настоящем учебном пособии изложены основы теории двоичных функций, исчисления предикатов, теории моделей, элементов теории алгоритмов и теории сложности вычислительных задач. Книга предназначена для студентов, специализирующихся в областях, связанных с информационной безопасностью, а также для преподавателей дискретной математики. УДК ББК А Алиев Ф.К., Юров И.А. Курс лекций по математической логике и теории алгоритмов: Учебное пособие. М.: МИФИ, 2003. — с. Рецензеты: С.В. Синицын, П.П. Порешин, Г.Н. Поваров Рекомендовано редсоветом МИФИ в качестве учебного пособия Московский инженерно-физический институт (государственный университет), 2003 С О Д Е Р Ж А Н И Е Введение 5 Лекция 1. Основные способы задания двоичных функций 6 1.1. Табличный способ задания 6 1.2. Геометрический способ задания 9 1.3. Задание двоичных функций формулами 10 Лекция 2. Основные способы задания двоичных функций (продолжение) 13 2.1. Нормальные формы двоичных функций 13 2.2. Многочлен Жегалкина и действительный многочлен двоичной функции 17 2.3. Теорема о разложении в ряд Фурье 20 Лекция 3. Полнота и замкнутость. Критерий полноты системы. Функционально полные системы. Замкнутые классы булевых функций 23 3.1. Полнота и замкнутость. Функционально полные системы 23 3.2. Замкнутые классы булевых функций 25 3.3. Критерий полноты системы булевых функций 28 Лекция 4. 30 4.1. Псевдобулевы функции 30 4.2. Функции k-значной логики 32 Лекция 5. 36 5.1. Минимизация двоичных функций 36 5.2. Геометрическая интерпретация минимизации ДНФ 38 Лекция 6. 40 6.1. Метод Квайна — Мак-Класки нахождения сокращенной ДНФ двоичной функции 40 6.2. Метод нахождения тупиковых ДНФ 42 6.3. Метод Петрика нахождения тупиковых ДНФ 42 Лекция 7. Алгебраические системы 45 7.1. Алгебраические системы. Булевы алгебры 45 7.2. Изоморфизм алгебраических систем 48 Лекция 8. Алгебры высказываний. Предикаты и операции над ними 51 8.1. Основные логические операции и их свойства 51 8.2. Предикаты и операции над ними 52 Лекция 9. Исчисление предикатов 57 9.1. Общее понятие о логическом исчислении 57 9.2. Формулы алгебры предикатов 58 9.3. Равносильность формул. Основные отношения равносильности 64 9.4. Использование равносильностей для упрощения формул 69 9.5. Построение исчисления предикатов 71 9.6. Выводимость и доказуемость формул 73 9.7. Семантика исчисления предикатов 82 Лекция 10. Понятие о теории моделей 91 Лекция 11. Элементы теории алгоритмов 99 11.1. Основные требования к алгоритмам 102 11.2. Машина Тьюринга и функции, вычислимые по Тьюрингу 106 11.3. Машины произвольного доступа и вычислимые функции 116 Лекция 12. Частично рекурсивные функции и их вычислимость 123 Лекция 13. Нумерация наборов чисел и слов 133 Лекция 14. Нормальные алгоритмы 139 Лекция 15. Нумерация алгоритмов 144 15.1. Нумерация машин Тьюринга 144 15.2. Нумерация МПД-программ 146 15.3. Универсальные функции 149 Лекция 16. Алгоритмически неразрешимые проблемы 153 16.1. Алгоритмически неразрешимые проблемы 153 16.2. Примечательные алгоритмически неразрешимые проблемы 163 Лекция 17. Характеристики сложности вычислений 166 Лекция 18. Характеристика сложности вычислительных задач 173 18.1. Классы сложности P и NP и их взаимосвязь 173 18.2. NP-полные задачи. Теорема Кука 181 18.3. Основные NP-полные задачи. Сильная NP-полнота 186 Список литературы 197 ВВЕДЕНИЕ Данное учебное пособие является основой для преподавания курса «Математическая логика и теория алгоритмов». Этот курс преподается студентам третьего курса факультета «Информационная безопасность» МИФИ в рамках специальности «Комплексное обеспечение информационной безопасности автоматизированных систем» (шифр 075500). В этом пособии отражены, по мнению авторов, теоретические результаты, лежащие в основе создания устройств криптографической защиты информации и оценки их стойкости. Так, например, один из подходов к анализу и обоснованию стойкости алгоритмов криптографической информации состоит в оценке вычислительной сложности соответствующих преобразований. Кроме того, большое число криптографических алгоритмов строятся на основе преобразований, которые реализованы с помощью булевых функций. Естественным образом возникает необходимость наличия у специалистов в области информационной безопасности навыков использования аппарата булевых функций и теории сложности вычисления для анализа криптографических преобразований. Теоретические основы для возможности реализации этих навыков приведены в данном учебном пособии. Излагаемый материал представлен в виде 18 лекций. Объем лекций различен. Это, прежде всего, связано с тем, что определенные разделы курса предназначены для самостоятельного изучения. Так, например, весьма обширно представлены результаты, связанные с реализацией вычислительных процедур на таких моделях вычислительных устройств, как машины Тьюринга и МПД-машины. При этом изложение этих результатов, в целом, носит описательный характер и в полной мере доступен для успешной самостоятельной работы студентов. В учебном пособии приведено большое количество результатов, связанных с изучением конкретных вычислительных задач, что также может быть изучено самостоятельно. Л е к ц и я 1 Основные способы задания двоичных функций 1.1. Табличный способ задания Определение 1.1. Двоичной функцией от n (n 1) переменных называется функция |
Добавить документ в свой блог или на сайт
Похожие:
 |
Уроках биологии в 7 классе. Группа Министерство образования и науки российской федерации министерство образования московской области государственное образовательное... |
|
Методические рекомендации к выполнению работ по курсу “Биофизический практикум” Московский ордена Трудового Красного Знамени инженерно-физический институт (государственный университет) Министерства высшего и профессионального... |
|
Российской Федерации Министерство образования и науки Российской... Теоретическая и практическая составляющие подготавливают учащихся к изучению других предметов по направлению «коммуникология – наука... |
|
Российской Федерации Министерство образования и науки Российской... Теоретическая и практическая составляющие подготавливают учащихся к изучению других предметов по направлению «коммуникология – наука... |
|
Российской Федерации Министерство образования и науки Российской... Теоретическая и практическая составляющие подготавливают учащихся к изучению других предметов по направлению «коммуникология – наука... |
|
Российской Федерации Министерство образования и науки Российской... Теоретическая и практическая составляющие подготавливают учащихся к изучению других предметов по направлению «коммуникология – наука... |
|
З. Б. Кипкеева Министерство образования российской федерации ставропольский государственный университет |
 |
Министерство образования и науки российской федерации Положения о Министерстве образования и науки Российской Федерации, утверждённого постановлением Правительства Российской Федерации... |
|
Министерство образования и науки российской федерации приказ В соответствии с частью 11 статьи 13 Федерального закона от 29 декабря 2012 г. N 273-фз "Об образовании в Российской Федерации" (Собрание... |
|
Инженерно-геологические изыскания для строительства сп 11-105-97... Государственный комитет российской федерации по строительству и жилищно-коммунальному комплексу |