Заключение

Данное пособие восполняет имеющиеся пробелы в учебной литературе по курсу дискретной математики.

Издание рекомендуется для работы студентов при самостоятельном изучении теоретического материала, на практических занятиях в качестве справочного пособия, а также при выполнении типовых расчетов и подготовки к зачетам и экзаменам, предусмотренных учебными планами по указанной дисциплине.

Пособие поможет более глубокому и полному усвоению студентами ученого материала разделов комбинаторики и теории конечных автоматов и будет способствовать эффективной организации учебного процесса по этой дисциплине.

Библиографический список

1. Яблонский С.В. Введение в дискретную математику: учеб.пособие для вузов/С.В. Яблонский.– 3-е изд. М.: Высш. шк., 2002.– 384 с.

2. Судоплатов С.В. Элементы дискретной математики: учебник/С.В. Судоплатов, Е.В. Овчинникова. – М.: ИНФРА-М, Новосибирск, Изд-во НГТУ, 2002. - 280 с.

3. Новиков Ф.А. Дискретная математика для программистов: учебник/Ф.А. Новиков. - СПб.: Питер, 2002.- 304с.

4. Шелупанов А.А. Математическая логика и теория алгоритмов: учеб.пособие/А.А. Шелупанов, В.М. Зюльков. - Томск: STT, 2001. - 176 с.

5. Столл Р. Множества, логика, аксиоматические теории/Р. Столл. - М.: Просвещение, 1968.- 231с.

6. Криницкий Н.А. Алгоритмы вокруг нас/Н.А. Криницкий. –2-е. изд. - М.: Наука, 1984. – 224с.

7. Биркгоф Г. Современная прикладная алгебра/Г. Биркгоф, Т. Барти. - М.: Мир, 1976. - 400с.

8. Карпов Ю.Г. Теория автоматов: учебник для вузов / Ю.Г. Карпов. - СПб.: Питер, 2003.- 208с.

Оглавление

1. ВВЕДЕНИЕ 5

2. 1. Элементы комбинаторики 7

1.1. Простейшие комбинаторные конфигурации 7

1.1.1.Основные правила комбинаторики 7

1.1.2.Выборки элементов без повторений 9

1.1.3.Выборки элементов с повторениями 11

1.2.Латинские прямоугольники, конечные проективные плоскости и блок-схемы 12

1.2.1. Латинские прямоугольники 12

1.2.2. Конечные проективные плоскости 16

1.2.3. Блок-схемы 18

1.3.Формула включений и исключений 19

1.3.1. Объединение комбинаторных конфигураций 19

1.3.2. Принцип включения и исключения 21

1.3.4. Решето Эратосфена 26

1.4. Рекуррентные уравнения 28

1.4.1. Определение рекуррентного уравнения 28

1.5. Производящие функции 33

1.5.1. Общие сведения о производящих функциях 33

1.5.2. Производящая функция для биноминальных коэффициентов 34

1.5.3. Производящая функция для чисел Фибоначчи 37

1.6. Z - преобразование 39

1.6.1. Определение Z – преобразования 39

1.6.2. Обратное преобразование 41

В правой части этого равенства стоит контурный интеграл в Z-плоскости по любому замкнутому контуру в области сходимости, охватывающему начало координат. 41

1.6.3. Свойства Z-преобразования 42

1.6.4. Использование Z-преобразований для решения рекуррентных уравнений 43

1.6.5. Таблица односторонних Z-преобразований 44

1.7. Трансверсали и перманенты 45

1.7.1. Множества и мультимножества 45

1.7.2. Трансверсали 48

1.7.3. Пермамент матрицы 49

1.7.4. Число трансверсалей 51

1.8. Матрицы Адамара 53

1.8.1. Определение матрицы Адамара и ее свойства 53

1.8.2. Эквивалентные преобразования матриц Адамара 54

1.8.3. Построение матриц Адамара 56