- •Н.А. Ююкин
- •Введение
- •1. Элементы комбинаторики
- •1.1. Простейшие комбинаторные конфигурации
- •Основные правила комбинаторики
- •Выборки элементов без повторений
- •Выборки элементов с повторениями
- •Латинские прямоугольники, конечные проективные плоскости и блок-схемы
- •1.2.1. Латинские прямоугольники
- •1.2.2. Конечные проективные плоскости
- •1.2.3. Блок-схемы
- •Формула включений и исключений
- •1.3.1. Объединение комбинаторных конфигураций
- •1.3.2. Принцип включения и исключения
- •1.3.3. Число булевых функций, существенно зависящих от всех своих переменных
- •1.3.4. Решето Эратосфена
- •1.4. Рекуррентные уравнения
- •1.4.1. Определение рекуррентного уравнения
- •1.4.2. Решение линейного однородного рекуррентного уравнения
- •1 (2).4.3. Решение линейного неоднородного рекуррентного уравнения
- •1.5. Производящие функции
- •1.5.1. Общие сведения о производящих функциях
- •1.5.2. Производящая функция для биноминальных коэффициентов
- •1.5.3. Производящая функция для чисел Фибоначчи
- •1.6.1. Определение z– преобразования
- •1.6.2. Обратное преобразование
- •В правой части этого равенства стоит контурный интеграл в z-плоскости по любому замкнутому контуру в области сходимости, охватывающему начало координат.
- •1.6.3. СвойстваZ-преобразования
- •1.6.4. Использование z-преобразований для решения рекуррентных уравнений
- •1.6.5. Таблица односторонних z-преобразований
- •1.7.Трансверсали и перманенты
- •1.7.1. Множества и мультимножества
- •1.7.2. Трансверсали
- •1.7.3. Пермамент матрицы
- •1.7.4. Число трансверсалей
- •1.8. Матрицы Адамара
- •1.8.1. Определение матрицы Адамара и ее свойства
- •1.8.2. Эквивалентные преобразования матриц Адамара
- •1.8.3. Построение матриц Адамара
- •2. Теория автоматов
- •2.1. Понятие конечного автомата
- •2.1.1. Общие сведения о конечных автоматах
- •2.1.2. Абстрактное определение конечного автомата
- •2.2. Эквивалентности в автоматах
- •2.2.1. Основные определения
- •2.2.2. Покрытия и морфизмы
- •2.2.3. Эквивалентные состояния автоматов
- •2.3. Процедура минимизации конечных автоматов
- •2.4. Автоматные функции и эксперименты с автоматами
- •2.4.2. Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •2.4.3. Эксперименты с автоматами
- •2.5. Автоматные языки
- •2.5.1. Представление о формальных языках
- •2.5.2. Алфавит, слово, язык
- •2.5.3. Классификация грамматик и языков
- •2.5.4. Понятие формальной грамматики
- •2.5.5. Автоматные грамматики.
- •2.6. Модификации конечных автоматов
- •2.6.1. Не полностью описанные (частичные) автоматы
- •2.6.2. Понятия недетерминированного и вероятностного автомата
- •2.7. Процедура минимизации не полностью описанного автомата
- •2.7.1. Совместимые состояния
- •2.7.2. Техника определения совместимых состояний.
- •2.7.3. Построение минимального автомата
- •3. Введение в нечеткую математику
- •3.1. Нечёткие множества
- •3.2. Нечеткие отношения
- •3.3. Нечеткая логика
- •Заключение
- •Библиографический список
- •Оглавление
- •1. Элементы комбинаторики 7
- •2. Теория автоматов 58
- •3. Введение в нечеткую математику 106
Н.А. Ююкин
ДИСКРЕТНАЯ МАТЕМАТИКА
ЧАСТЬ 2
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ И ТЕОРИИ КОНЕЧНЫХ АВТОМАТОВ
Учебное пособие
Воронеж 2011
ГОУВПО «Воронежский государственный
технический университет»
Н.А. Ююкин
ДИСКРЕТНАЯ МАТЕМАТИКА
ЧАСТЬ 2
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ И
ТЕОРИИ КОНЕЧНЫХ АВТОМАТОВ
Утверждено Редакционно-издательским советом
университета в качестве учебного пособия
Воронеж 2011
УДК 519.17
Ююкин Н.А. Дискретная математика. Ч. 2: Элементы комбинаторики и теории конечных автоматов: учеб. пособие /Н.А. Ююкин/ Воронеж: ГОУВПО «Воронежский государственный технический университет», 2011. 98 с.
В учебном пособии рассматриваются краткие теоретические сведения об основных комбинаторных конфигурациях и задачах по их перечислению; о рекуррентных уравнениях и методах их решения. В теории конечных автоматов даётся их формальное определение, классификация,различные варианты представления, тестирование и применение. Кроме того, в пособии представлен материал по нечеткой математике.
Учебное пособие соответствует требованиям Государственного образовательного стандарта высшего профессионального образования по направлению 090100 «Информационная безопасность», специальностям 090102 «Компьютерная безопасность», 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем», 090106 «Информационная безопасность телекоммуникационных систем», дисциплины «Дискретная математика».
Учебное пособие подготовлено в электронном виде в текстовом редакторе MSWORD и содержится в файле «Теория автоматов»
Ил. 58. Библиогр.: 8 назв.
Научный редактор д-р физ.-мат. наук, проф. И.Л. Батаронов
Рецензенты: кафедра высшей математики Воронежского института МВД России (начальник кафедры д-р физ.- мат. наук, проф. В.В. Меньших); канд. физ.-мат. наук, доц. С.П. Майорова
© Ююкин Н.А., 2010
© Оформление. ГОУВПО
«Воронежский
государственныйтехнический университет»,
201
Введение
Данное пособие может быть использовано в курсе “Дискретная математика” студентами ВГТУ, обучающимися по специальностям:
090102 – Компьютерная безопасность;
090105 – Комплексное обеспечение информационной безопасности автоматизированных систем;
090106 - Информационная безопасность телекоммуникационных систем.
Дисциплина “Дискретная математика” обеспечивает приобретение знаний и умений в соответствии с Государственным, общеобразовательным стандартом, и при этом содействует фундаментализации образования, формированию мировоззрения и развитию логического мышления.
Дискретная математика является эффективным аппаратом формализации современных инженерных задач, связанных с дискретными объектами. Она используется при проектировании интегральных схем и схем управления, исследовании автоматов и логических цепей, в системном анализе, автоматизированном управлении производством, при разработке вычислительных и информационных сетей, в схемотехническом и конструкторско-топологическом проектировании и т.д.
В учебном пособии излагаются основы, базовые методы и алгоритмы теории: принцип включения-исключения; рекуррентные соотношения и производящие функции; трансверсали; латинские прямоугольники и квадраты; комбинаторные конфигурации, блок-схемы; конечные проективные плоскости; ортогональные латинские квадраты; матрицы Адамара. Здесь представлены конечные автоматы; автоматные базисы и проблема полноты; эквивалентность в автоматах; автоматные языки; понятие формальной грамматики; эксперименты с автоматами; тестирование автоматов; вероятностные автоматы, а также вырабатываются практические навыки по использованию вышеприведенных понятий.
Целью курса является формирование у студентов теоретических знаний, практических умений и навыков в области моделирования процессов и явлений в естествознании и технике, с возможностью употребления математических символов для выражения количественных и качественных отношений объектов, необходимых для выполнения служебной деятельности в области защиты информации на высоком профессиональном уровне.
Достижению данной цели служат следующие задачи:
изучить максимально широкий круг понятий теории;
получить навыки решения учебных и практических задач;
овладеть методами оптимизации;
выработать навыки постановки и решения информационных задач, моделирования и анализа информации с помощью комбинаторных методов и конечных автоматов.
Дисциплина “Дискретная математика” относится к числу прикладных математических дисциплин. Она основывается на знаниях, приобретенных студентами при изучении дисциплин “Алгебра” и “Математическая логика и теория алгоритмов”. Знания и навыки, полученные при изучении дисциплины “Дискретная математика” используются при изучении обще профессиональных и специальных дисциплин.