Лекции Русакова (1021002), страница 22
Текст из файла (страница 22)
Обозначаем Сnk206ТеоремаЧисло Сnk =n!k! ( n − k )!ДоказательствоРассмотрим перестановку из n элементов по k . Если не считаться спорядком элементов, то существует k ! Перестановок, которые не различимы.СледовательноAnkk!. Упрощая эту формулу, получим искомую.ОпределениеРазмещением с повторением из n элементов по k элементов k ≤ nназываются k -элементные подмножества множества A , отличающиеся одинот другого или самими элементами или их порядком . При этом допускаетсякратное вхождение элементов множества A .ТеоремаЧисло размещений с повторениями из n элементов по k равно Rnk = n kДоказательствоРассуждения очень похожи на доказательство числа размещения безповторений. Значение, которое стоит на «первом» месте можно выбрать nспособами.
Значение, стоящее на «втором» месте также можно выбрать nспособами (т.к. они могут повторяться, элементы после выбора не удаляютсяиз множества, из которого выбирают). И т.д. процедура повторяется k раз.Определение.Сочетаниямисповторениями,содержащимиkэлементов,выбранных из n элементов заданного множества, называются всевозможныемножества из k элементов, отличающиеся хоть одним элементов (порядок не207учитывается), при этом допускается неединичное вхождение элементов.Обозначаем S nkТеоремаЧисло S nk = C nk+k −1 =( n + k − 1)!k!( n − 1)!7.02. Декартово произведение множеств.Определение.Декартовым произведением множества X и Y называется множество,обозначенное X × Y , элементами которого являются упорядоченные пары(x; y ) ,где x ∈ X , y ∈ Y .
Равенство упорядоченных пар понимается вследующем смысле:пустьz 1 = ( x1 ; y1 ) è z 2 = ( x 2 ; y 2 )(z1 , z 2 ∈ X × Y )defz1 = z 2 ⇔( x1 = x 2 ) & ( y1 = y 2 ).Теорема.Если X и Y – конечные множества, то X × Y – конечное множество иX ×Y = X ⋅ Y .Доказательство.Ясно, что в случае, когда одно из множествX , Y пусто, то иX × Y пусто и тривиально выполнено. Рассмотрим случай, когда X и Y –непустые множества. Зафиксируем в X нумерацию{}X = x1 , x2 , , x x .208Ясно, чтоXX × Y = {xi }× Yи множестваi =1{xi }× Yпопарно непересекаются, тогда по правилу суммы имеем:X ×Y =X{xi }× Y(*).i =1Рассмотрим отображение f i : {xi }× Y → Y , действующее по правилуf i (( xi , y )) = y .Ясно, что f i – биективное отображение, тогда по основному принципукомбинаторики получаем{xi }× Y= Y (**).Подставляя (**) в (*), получим:XX ×Y = Y = X ⋅ Y .i =17.03.
Примеры задач и упражнений.Пример 1.Определить,сколькотрехзначныхчиселможносоставитьизмножества цифр 1,2,3,4,5 без повторений.Решение.n = 5; k = 3;A53 = 60Пример 2.К кассе за получением денег одновременно подошли 4 человека.Сколькими способами они могут выстроиться в очередь.Решение.209Очередь состоит из 4 различных человек, поэтому эти очередиотличаются только порядком элементов.
Это перестановки без повторений.P4 = 4! = 24Пример 3Имеется 6 штаммов бактерий. Для определения скорости их ростанеобходимо выбрать 3 штамма. Сколькими способами можно это сделать?РешениеСпособыотбораразличаются,есликаждаягруппаштаммовразличаются хотя бы одним элементом. Это числоС63 =6!= 203! (6 − 3)!Пример 4Выбрать из 20 человек в группе 8 человек для сдачи зачета досрочно.Решение8С20=20!= 1259708! ( 20 − 8)!Пример 5В ящике 20 шаров, среди них 12 белых, остальные зелёные. Отбираетсянаугад 2. Сколькими способами можно отобрать а) два белых шара, б) двазелёных, в) один белый и один зелёный.Решение2а) С12=12!= 662!10!б) С82 =8!= 282!6!210в) 12 ⋅ 8 = 96Пример 6n ( n > 2) человек садятся за круглый стол. Два размещения по местамбудем считать совпадающими, если каждый человек имеет одних и тех жесоседей в обоих случаях.
Сколько существует способов сесть за стол.РешениеОбщее число перестановок равно n! . Но отношение соседствасохраняется при циклических перестановках (повороте) их n для каждогоразличного размещения и при симметричном отображении (их 2).Следовательноn!.2⋅nПример 7Из колоды в 52 карты вынули 10 карт. В скольких случаях среди этихкарт окажется а) хотя бы один туз; б) ровно один туз; в) не менее двух тузов;г) ровно два туза.Решение.10а) Существует С5210способов вынуть 10 карт из 52. При этом в С481010случаях в этой выборке не окажется ни одного туза. Следовательно С52 − С489б) С41С48в) С5210 – С4810 – С41 С4898г) С42С48Пример 8Сколькими способами можно посадить за круглый стол n мужчин и nженщин так, чтобы никакие два лица одного пола не сидели рядом.211РешениеВыбрать места для мужчин и женщин можно двумя способами.
Послеэтого рассадить мужчин на выбранные места можно n! способами. Наостальных местах n! способами можно посадить женщин. Всего 2( n! ) 2способов.Пример 10Сколькими способами можно составить 3 пары из n шахматистов?РешениеВыбираем 6 шахматистов Сn6 способами. В каждой из этих выборокрассмотрим количество перестановок их 6!. Считая, что в первой пареэлементы с 1 – ого и 2 – го места перестановки и т.д. Но при этомнесущественен порядок в каждой паре 23 и порядок пар 3!. Следовательно,Сn6 6!количество перестановок равно 6!/ (23 3!). Итого23 ⋅ 3!7.04.
Задачи для самостоятельного решения.1. Имеется 5 видов конвертов и 4 вида марок. Сколькими способамиможно выбрать конверт с маркой?2. Сколько словарей нужно издать, чтобы переводить с любого из 5языков на любой другой?3. Есть пятиразрядный цифровой замок, каждый диск которогосодержит цифры от0 до 5. Сколько комбинаций таких цифр?4. Сколькими способами можно упорядочить множество цифр от 1до 2n так, чтобы все четные числа стояли на четных местах.2125. Сколькими способами можно упорядочить множество цифр от 1до n так, чтобы числа 1,2,3 стояли рядом и в порядке возрастания.6. Какое количество различных символов можно передать не болеечем 5 знаками «.» и «-».7. Автомобильные номера состоят из 3 букв и 4 цифр. Найтиколичество возможных номеров, если используются 32 букврусского алфавита.8.
Сколько машинных слов можно составить из букв словаКОЛОКОЛ.9. Сколько машинных слов можно составить из букв словаВОДОРОД.10.Сколькими способами 9 одинаковых конфет можно разложить по5 пакетам, если ни один из пакетов не должен быть пустым. Тотже вопрос, но пакеты могут быть пустыми.Глава 8.
Основнаячасть:практическаяработастудентовПрактическоесинтаксическихзанятие№1.анализаторовдляРазработкарегулярныхязыков.8.01. Общие указания к выполнению практическойработы.Практические работы выполняются с использованием персональныхкомпьютеров. Указания по технике безопасности совпадают с требованиями,предъявляемымикпользователюЭВМ.отсутствуют.213Другиеопасныефакторы8.02. Цель работыНаписание, отладка и проверка работоспособности синтаксическогоанализатора на основе графа детерминированного конечного автомата,соответствующего заданному регулярному выражению, порождающемуконкретный язык.8.03.
Постановка задачи7.03.1. Описание грамматики.Рассмотримрегулярноевыражение(221b)*(b21)*(22)*.Этовыражение порождает предложения языка:L = {(221b)m (b21)n (22)p: m, n, p > 0}.Языку L соответствует регулярная порождающая грамматика: G = ({1,2, b}, (А, В, С, D, Е, F, К, L, M, S}, P, S), где Р={S→2A; А→2В; В→1C;С→bS; S→ε; S→2D; D→2Е; Е→IF; F→bD; F→ε; F→2K; K→2L; L→2M;M→2L; L→ε; В→ε; В→2K} — порождающие правила; {1, 2, b} —множество терминальных символов; {А, В, С, D, Е, F, К, L, M, S} —множество нетерминальных символов; S — аксиома; ε — пустая строка.Для каждой регулярной грамматики существует детерминированныйконечный автомат.
Грамматике G соответствует автомат:M = ({А, В, С, S, D, Е, F, К, L, М), {1, 2, b}, d, {S}, (S, В, F, L}), где {А,В, С, S, D, Е, F, К, L, М} — конечное множество состояний; {1, 2, Ь} —конечный входной алфавит; d — множество переходов:{d(S, 2) = A;d(S, b) = D; d(F, 2) = K;d(A,2) = B; d(D,2) = E; d(B,2) = K;d(B, 1) = C; d(E,l) = F; d(K,2) = L;d(C, b) = S; d(F, b) = D; d(L, 2) = M;d(M,2) = L};S - начальное состояние (S ∈{A, B, C, S, D, E, F, K, L, M});{S, B, F, L} - множество последних состояний214({S, В, F, L}∈ {A, B, C, S, D, E, F, K, L, M}).Множество переходов d может быть эквивалентно представленотаблицей переходов:Здесь ∅ — пустое множество.Здесь состояния S, В, F, L являются последними.Множество переходов также может быть представлено графически спомощью графа переходов из одного состояния детерминированногоконечного автомата в другое.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
