П. Г. Демидова Кафедра компьютерной безопасности и математических методов обработки информации М. А. Башкин, О. П. Якимова Дискретная математика Сборник задач Рекомендовано Научно-методическим советом университета для студентов, обучающихся по направлению Математика и компьютерные науки, специальности Компьютерная безопасность Ярославль ЯрГУ 2012 1 УДК 519.854(076.1) ББК В174я73-4 Б 33 Рекомендовано Редакционно-издательским советом университета в качестве учебного издания. <...> Найдите средний член разложения (номер и вид) 6 1.55. <...> Найдите два средних члена разложения (номера и вид) 11 3 y жащий . <...> Производящие функции и рекуррентные уравнения Пусть a0,a1,…,an,– некоторая последовательность чисел (действительных или комплексных). <...> Построим по этой последовательности формальный ряд A(x) последующему правилу: A(x)=a0+a1x+a2x2+…+anxn+… Формальный ряд A(x) называется производящей функцией последовательности { an}n=0,1, …. <...> Для производящих функций A(x)= определим операцию сложения: A(x)+B(x)= ное): pA(x)= , операцию умножения на число (действительное или комплекс, и произведение Коши (коротко:произведение): A(x) ∙B(x)= ,гдеcn=a0bn+a1bn-1+ …+anb0= . <...> Свойства производящих функций: 1) производящей функцией для последовательностиyn=pan+qbnя вляется функция Y(x)=pA(x)+qB(x); 2) производящей функцией для последовательностей являются функцииY(x)=A(x)∙xkиZ(x)=(A(x))∙x-k; 3) производящими функциями для последовательностей yn=n∙an и zn=an/(n+1) являются функции Y(x)=x∙A (x) и Z(x)= yn= соответственно; 4) производящей функцией для последовательности является функция Y(x)=A(x)∙B(x); 17 и B(x)= , функцияY(x)= 5) производящей для последовательностиyn = . wn k F wn k 1,wn k 2 , , ,wn ) является Рекуррентным уравнением (или рекуррентным соотношением) порядка k называется равенство ( дущих значений этой последовательности. <...> Последовательность { } 0,1,nnw <...>
Дискретная_математика__сборник_задач.pdf
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П. Г. Демидова
Кафедра компьютерной безопасности
и математических методов обработки информации
М. А. Башкин, О. П. Якимова
Дискретная математика
Сборник задач
Рекомендовано
Научно-методическим советом университета для студентов,
обучающихся по направлению
Математика и компьютерные науки,
специальности Компьютерная безопасность
Ярославль
ЯрГУ
2012
1
Стр.1
УДК 519.854(076.1)
ББК В174я73-4
Б 33
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2012 года
Рецензент
кафедра компьютерной безопасности
и математических методов обработки информации ЯрГУ
Башкин, М. А. Дискретная математика : сборник
Б 33
задач / М. А. Башкин, О. П. Якимова; Яросл. гос. ун-т
им. П. Г. Демидова. – Ярославль: ЯрГУ, 2012. – 96 с.
Предназначен для студентов, обучающихся по направлению
010200.62 Математика и компьютерные науки,
специальности 090301.65 Компьютерная безопасность
(дисциплина «Дискретная математика», цикл Б3, С2), очной
формы обучения.
УДК 519.854(076.1)
ББК В174я73-4
© ЯрГУ, 2012
2
Стр.2
Оглавление
1. Комбинаторика ................................................................................... 3
1.1. Подмножества множества Е. Правило суммы
и произведения ....................................................................................... 3
1.2. Размещения ............................................................................... 5
1.3. Перестановки и сочетания ....................................................... 7
1.4. Биномиальная теорема.
Свойства биномиальных коэффициентов .......................................... 11
1.5. Формула включений и исключений ..................................... 13
1.6. Производящие функции и рекуррентные уравнения .......... 17
2. Булевы функции ............................................................................... 21
2.1. Определение и способы задания.
Существенные и фиктивные переменные .......................................... 21
2.2. Нормальные формы ............................................................... 28
2.3. Полином Жегалкина (полином по модулю 2) ..................... 32
2.4. Минимизация булевых функций .......................................... 34
2.5. Критерий полноты системы булевых функций.
Базисы ................................................................................................... 40
2.6. Логические элементы в электронных схемах ...................... 45
3. k-значные функции .......................................................................... 47
3.1. Определение и способы задания. Основные понятия ......... 47
3.2. Нормальные формы ............................................................... 51
3.3. Полиномы ............................................................................... 53
3.4. Полнота ................................................................................... 57
4. Конечные автоматы ......................................................................... 60
4.1. Алфавиты. Слова. Языки ....................................................... 60
4.2. Автоматы Мили и Мура ........................................................ 62
4.3. Эквивалентные преобразования автоматов ......................... 77
4.4. Минимизация автоматов ....................................................... 82
4.5. Распознающие автоматы ....................................................... 89
Список литературы .............................................................................. 93
95
Стр.95