- Артикул:00-01059030
- Автор: М.М. Глухов, А.Б. Шишков
- ISBN: 978-5-8114-1344-7
- Тираж: 1500 экз.
- Обложка: Твердая обложка
- Издательство: Лань (все книги издательства)
- Город: Санкт-Петербург-Москва-Краснодар
- Страниц: 416
- Формат: 84х108 1/32
- Год: 2012
- Вес: 595 г
- Серия: Учебное пособие для ВУЗов (все книги серии)
Развернуть ▼
Учебное пособие содержит полное изложение материала учебных дисциплин «Математическая логика и теория алгоритмов» и «Дискретные функции» Государственного образовательного стандарта высшего профессионального образования по специальностям и направлениям «Компьютерная безопасность», «Информационная безопасность автоматизированных систем» и некоторым другим смежным специальностям.
Пособие состоит из трех взаимосвязанных частей, представляющих основы математической логики, теории дискретных функций и теории алгоритмов.
Предназначено для студентов вузов, обучающихся по специальностям и направлениям в области информационной безопасности, а также для аспирантов и студентов вузов других технических специальностей и направлений, изучающих дискретную математику.
Содержание
Предисловие
Часть I. Математическая логика
Глава 1. Множества с отношениями и операциями
1.1. Множества и операции над ними
1.2. Отображения множеств
1.3. Отношения на множестве. Отношения эквивалентности и порядка
1.4. Множества с операциями
1.5. Аксиоматическое построение системы натуральных чисел
1.6. Мощность множества. Конечные и бесконечные множества
Глава 2. Алгебра высказываний
2.1. Основные логические операции и их свойства
2.2. Формулы алгебры высказываний
2.3. Эквивалентные формулы
2.4. Приведенные формулы и нормальные формы
2.5. Выполнимые и тождественно истинные формулы
2.6. Сокращенные, тупиковые и минимальные ДНФ
2.7. Алгоритм нахождения тупиковых ДНФ по сокращенной ДНФ
Глава 3. Исчисление высказываний
3.1. Общее понятие о логическом исчислении
3.2. Язык, аксиомы и правила вывода исчисления высказываний
3.3. Доказуемые формулы исчисления высказываний
3.4. Вспомогательные правила вывода
3.5. Полнота и непротиворечивость исчисления высказываний
Глава 4. Алгебра предикатов
4.1. Предикаты и операции над ними
4.2. Формулы алгебры предикатов
4.3. Эквивалентность формул. Основные соотношения эквивалентности
4.4. Приведенные и предваренные формулы
Глава 5. Исчисление предикатов
5.1. Язык, аксиомы и правила вывода исчисления предикатов
5.2. Выводимость и доказуемость формул
5.3. Семантика исчисления предикатов
5.4. Понятие о теории моделей
5.5. Проблема разрешимости в логике предикатов
Часть II. Дискретные функции
Глава 1. Дискретные функции и способы их задания
1.1. Способы задания булевых функций
1.2. Полные системы и замкнутые классы булевых функций
1.3. Функции k-значной логики и способы их задания. Полные системы
1.4. Критерии полноты систем функций k-значной логики
1.5. Полиномиальное представление функций k-значной логики
Глава 2. Представление дискретных функций в базисах функциональных пространств
2.1. Базисы линейных функциональных пространств. Базис характеров
2.2. Преобразование Фурье. Коэффициенты Фурье и Уолша-Адамара
2.3. Матричный подход к представлению булевых функций
Глава 3. Классификация дискретных функций с помощью групп преобразований
3.1. Эквивалентность функций. Группы инерции
3.2. Функции, инвариантные относительно группы
3.3. Функции с тривиальной группой инерции в аффинной группе
3.4. Перечисление G-типов. Лемма Бернсайда
3.5. Инварианты. Нахождение групп инерции и проверка эквивалентности
Глава 4. Вероятностные и комбинаторные свойства и параметры дискретных функций
4.1. Вероятностная функция булевой функции
4.2. Линейные приближения (аппроксимации) булевых функций
4.3. Коэффициент аддитивности дискретных функций
Глава 5. Некоторые специальные классы дискретных функций
5.1. Корреляционно-иммунные функции
5.2. k-устойчивые функции
5.3. Бент-функции
5.4. Бент-отображения
Глава 6. Декомпозиция булевых функций
6.1. Простая декомпозиция
6.2. Разложимые функции
6.3. Сложные декомпозиции
6.4. Группы инерции суперпозиции булевых функций в группах Еn, Sn, Qn
Часть III. Теория алгоритмов
Глава 1. Элементы теории алгоритмов
1.1. Нормальные алгоритмы
1.2. Принцип нормализации алгоритмов
1.3. Машины Тьюринга
1.4. Нумерация слов и арифметизация алгоритмов
1.5. Рекурсивные функции
1.6. Примеры алгоритмически неразрешимых проблем
Глава 2. Сложность алгоритмов и вычислений
2.1. Сложность нормальных алгоритмов, вычисляющих булевы функции
2.2. Сложности вычислений на машинах Тьюринга
2.3. Классификации задач по сложности их решения на машинах Тьюринга
2.4. О сложностной классификации систем булевых уравнений
2.5. Асимптотические оценки сложности алгоритмов
2.6. Дискретные преобразования Фурье
2.7. Понятие о вероятностных алгоритмах
Приложение. Методические рекомендации по организации изучения математической логики, теории алгоритмов, теории дискретных функций
Литература
Рекомендуем
