Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет)




Скачать 77.27 Kb.
НазваниеРоссийской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет)
Дата публикации14.05.2014
Размер77.27 Kb.
ТипКнига
literature-edu.ru > Лекции > Книга
Министерство образования Российской Федерации
Министерство Российской Федерации по атомной энергии
Московский инженерно-физический институт

(государственный университет)

Ф.К. Алиев, И.А. Юров
КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

И ТЕОРИИ АЛГОРИТМОВ


Для студентов, специализирующихся в области

защиты информации

Москва 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) переменных называется функция

Добавить документ в свой блог или на сайт

Похожие:

Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет) iconУроках биологии в 7 классе. Группа
Министерство образования и науки российской федерации министерство образования московской области государственное образовательное...

Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет) iconМетодические рекомендации к выполнению работ по курсу “Биофизический практикум”
Московский ордена Трудового Красного Знамени инженерно-физический институт (государственный университет) Министерства высшего и профессионального...

Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет) iconРоссийской Федерации Министерство образования и науки Российской...
Теоретическая и практическая составляющие подготавливают учащихся к изучению других предметов по направлению «коммуникология – наука...

Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет) iconРоссийской Федерации Министерство образования и науки Российской...
Теоретическая и практическая составляющие подготавливают учащихся к изучению других предметов по направлению «коммуникология – наука...

Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет) iconРоссийской Федерации Министерство образования и науки Российской...
Теоретическая и практическая составляющие подготавливают учащихся к изучению других предметов по направлению «коммуникология – наука...

Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет) iconРоссийской Федерации Министерство образования и науки Российской...
Теоретическая и практическая составляющие подготавливают учащихся к изучению других предметов по направлению «коммуникология – наука...

Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет) iconЗ. Б. Кипкеева
Министерство образования российской федерации ставропольский государственный университет

Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет) iconМинистерство образования и науки российской федерации
Положения о Министерстве образования и науки Российской Федерации, утверждённого постановлением Правительства Российской Федерации...

Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет) iconМинистерство образования и науки российской федерации приказ
В соответствии с частью 11 статьи 13 Федерального закона от 29 декабря 2012 г. N 273-фз "Об образовании в Российской Федерации" (Собрание...

Российской Федерации Министерство Российской Федерации по атомной энергии Московский инженерно-физический институт (государственный университет) iconИнженерно-геологические изыскания для строительства сп 11-105-97...
Государственный комитет российской федерации по строительству и жилищно-коммунальному комплексу

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции