Учебное пособие содержит полное изложение материала учебных дисциплин «Математическая логика и теория алгоритмов» и «Дискретные функции» Государственного образовательного стандарта высшего профессионального образования по специальностям «Компьютерная безопасность», «Информационная безопасность автоматизированных систем» и некоторым другим смежным специальностям. Пособие состоит из трех взаимосвязанных частей, составляющих соответственно основы математической логики, теории дискретных функций и теории алгоритмов. Предназначено для студентов вузов, обучающихся по специальностям в области информационной безопасности, а также для аспирантов и студентов вузов других технических специальностей, изучающих дискретную математику.
Математическая логика Множества с отношениями и операциями Множества и операции над ними Отображения множеств Отношения на множестве Отношения эквивалентности и порядка Множества с операциями Аксиоматическое построение системынатуральных чисел Мощность множества Конечные и бесконечные множества
Алгебра высказываний Основные логические операции и их свойства Формулы алгебры высказываний Эквивалентные формулы Приведенные формулы и нормальные формы Выполнимые и тождественно истинные формулы Сокращенные, тупиковые и минимальные ДНФ Алгоритм нахождения тупиковых ДНФ по сокращенной ДНФ
Исчисление высказываний Общее понятие о логическом исчислении Язык, аксиомы и правила вывода исчисления высказываний Доказуемые формулы исчисления высказываний Вспомогательные правила вывода Полнота и непротиворечивость исчисления высказываний
Алгебра предикатов Предикатыи операции над ними Формулы алгебры предикатов Эквивалентность формул Основные соотношения эквивалентности Приведенные и предваренные формулы
Исчисление предикатов Язык, аксиомы и правила вывода исчисления предикатов Выводимость и доказуемость формул Семантика исчисления предикатов Понятие о теории моделей Проблема разрешимости в логике предикатов
Дискретные функции Дискретные функции и способы их задания Способы задания булевых функций Полные системы и замкнутые классы булевых функций Функции k-значной логики и способы их задания Полные системы Критерии полноты систем функций k-значной логики Полиномиальное представление функций k-значной логики
Представление дискретных функций в базисах функциональных пространств Базисы линейных функциональных пространств Базис характеров Преобразование Фурье Коэффициенты Фурье и Уолша–Адамара Матричный подход к представлению булевых функций
Классификация дискретных функций с помощью групп преобразований Эквивалентность функций Группы инерции Функции, инвариантные относительно группы Функции c тривиальной группой инерции в аффинной группе Перечисление G-типов Лемма Бернсайда Инварианты Нахождение групп инерции и проверка эквивалентности
Вероятностные и комбинаторные свойства и параметры дискретных функций Вероятностная функция булевой функции Линейные приближения (аппроксимации) булевы хфункций Коэффициент аддитивности дискретных функций Некоторые специальные классы дискретных функций Корреляционно-иммунные функции k-устойчивы ефункции Бент-функции Бент-отображения
Декомпозиция булевых функций Простая декомпозиция Разложимые функции Сложные декомпозиции Группы инерции суперпозиции булевых функций в группах
Теория алгоритмов Элементы теории алгоритмов Нормальные алгоритмы Принцип нормализации алгоритмов Машины Тьюринга Нумерация слов и арифметизация алгоритмов Рекурсивные функции Примеры алгоритмически неразрешимых проблем
Сложность алгоритмов и вычислений Сложность нормальных алгоритмов, вычисляющих булевы функции Сложности вычислений на машинах Тьюринга Классификации задач по сложности их решения на машинах Тьюринга О сложностной классификации систем булевых уравнений Асимптотические оценки сложности алгоритмов Дискретные преобразования Фурье Понятие о вероятностных алгоритмах Приложение Методические рекомендации по организации изучения математической логики, теории алгоритмов, теории дискретны хфункций
Внимание
Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.
