Комбинаторика в информатике егэ теория

Скачать материал

Скачать материал

Описание презентации по отдельным слайдам:

• 

  1 слайд

  Элементы комбинаторики
  Введение в теорию вероятностей
  Применение комбинаторики

• 

  2 слайд

  Комбинато́рика  — это область математики, прежде всего связанная с подсчетом, как средство и цель получения результатов, так и с определением свойств конечных структур. Она тесно связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей и применяется в различных областях знаний (например, в генетике, информатике, статистической физике).
  Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».
  Полный охват комбинаторики не является общепризнанным. Согласно Х. Дж. Райзеру, определение предмета трудно, потому что она пересекает много математических разделов.

• 

  3 слайд

  Поскольку область может быть описана типами задач, которые она решает, комбинаторика связана с:
  перечислением (подсчет) определенных структур, иногда упоминаемых аранжировками или конфигурациями в самом общем смысле, связанными с конечными системами;
  существованием таких структур, которые удовлетворяют определенным заданным критериям;
  построением таких структур; возможно, несколькими способами;
  оптимизацией, поиском «наилучшей» структуры или решения из нескольких возможных, будь то «наибольшая», «наименьшая» или удовлетворяющая какому-либо другому критерию оптимальности.

• 

  4 слайд

  Правило сложения (правило «или») — одно из основных правил комбинаторики, утверждающее, что,

  если элемент A можно выбрать n способами,
  а элемент B можно выбрать m способами,

  то выбрать A или B можно n + m способами.

• 

  5 слайд

  Правило умножения (правило «и») — одно из основных правил комбинаторных принципов. Согласно ему, если элемент A можно выбрать n способами,
  и при любом выборе A элемент B можно выбрать m способами,
  то пару (A, B) можно выбрать n·m способами Естественным образом обобщается на произвольное количество независимо выбираемых элементов.
  Данное правило обычно принимается за аксиому, как и правило суммы.

• 

  6 слайд

  В комбинаторике
   размеще́нием (из n по k) называется упорядоченный набор из k различных элементов
  из некоторого множества различных n элементов.

• 

  7 слайд

  Правило умножения. Простой
   Выбрать книгу и диск из 10 книг и 12 дисков можно    10*12=120       способами.

  Количество размещений с повторениями
  Если есть множество из n типов элементов, и нужно на каждом из m мест расположить элемент какого-либо типа (типы элементов могут совпадать на разных местах), то количество вариантов этого будет nm.
  k k
  An =n
  Порядок важен
  Есть повтор

• 

  8 слайд

  Правило умножения. Составной
  Пусть требуется найти количество слов, составленных не более, чем из 3-x букв алфавита {a, b, c}. Количество n-буквенных слов равно количеству размещений из 4 букв на n мест с повторениями — оно равно  4n        . Количество всех слов (так как нужно учитывать любое из слов) будет складываться из количеств одно-, двух- и трёхбуквенных слов.
  Тогда ответ на первоначальный вопрос будет 
  41+42+43 = 84        .

• 

  9 слайд

  Размеще́ние без повторений (из n по k) называется упорядоченный набор из k различных элементов
  из некоторого множества различных n элементов.
  Пример 1:
  <1,3,2,5>— это 4-элементное размещение
  из 6-элементного множества {1,2,3,4,5,6}
  k
  An =n!/(n-k)!
  Порядок важен
  Нет повтора

• 

  10 слайд

  СОЧЕТАНИЯ
  В комбинаторике сочетанием из  n     по  k     называется набор    k   элементов, выбранных из данного множества, содержащего  n      различных элементов.
  Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

  Так, например, наборы (3-элементные сочетания, подмножества,  k=3 ) {2, 1, 3} и {3, 2, 1} 6-элементного множества {1, 2, 3, 4, 5, 6} ( n=6 ) являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.

• 

  11 слайд

  Число сочетаний из  n  по  k  равно 

  k
  Cn =n!/k!(n-k)!
  n – множество, из которого выбираем
  k – количество выборок

• 

  12 слайд

  При решении задач лучше всего начинать с построения схем.
  Потому что задачи всегда разные

• 

  13 слайд

  Задача 1
  Сколько различных слов длины 6 можно составить из букв С,О.К, которые содержат ровно одну букву С. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая последовательность букв.

• 

  14 слайд

  Рисуем схему
  2 2 2 2 2 2*2*2*2*2=32
  С * * * * *
  * С * * * *
  * * С * * * Всего вариантов 6,
  * * * С * * тогда 32*6=192
  * * * * С *
  * * * * * С

• 

  15 слайд

  Задача 2
  Сколько различных слов длины 6 можно составить из букв С,О,К, которые содержат ровно две буквы С. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая последовательность букв.

• 

  16 слайд

  Расписывать схему сложно, так как буквы С может быть где угодно в слове. Поэтому здесь лучше использовать формулу сочетаний из 6 по 2. То есть , сколько вариантов размещения двух букв С существует в слове длиной 6. При этом не играет роль перестановок
  То есть это будет равно количеству сочетаний из 6 по 2

  2
  С6=n!/k!(n-k)!=

  6*5*4*3*2/2*4*3*2=15
  Где n – число элементов, из которых выбираем
  k – число элементов, которое выбираем

• 

  17 слайд

  Рассмотрим одну из схем размещения. Допустим

  С С * * * * (не важно, где находятся С)
  Получается С С 2 2 2 2
  перемножаем, получаем 16 вариантов
  С учётом того, что количество размещений равно 15, получаем, что всего вариантов различных слов длины 6 можно составить из букв С,О,К, которые содержат ровно две буквы С будет
  15*16=240
  15 вариантов

• 

  18 слайд

  Задача 3
  Сколько различных слов длины 5 можно составить из букв М, Ы, Ш, Ь, которые содержат ровно одну букву М и одну букву Ш. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая последовательность букв.

• 

  19 слайд

  Слово пятибуквенное
  * * * * *
  В предыдущей задаче было не важно какие места занимают С С. Здесь буквы разные. Поэтому здесь применяя формулу размещений из 5 по 2, получим количество вариантов для размещений букв М и Ш
  k
  A n=n!/(n-1)!=5!/3!=20
  А для остальных букв (их осталось 2) применяем схему
  20 * 2 * 2* 2
  Всё перемножаем, получаем 160. Ответ 160 вариантов

• 

  20 слайд

  Задача 3
  Сколько различных слов длины 5 можно составить из букв М, Ы, Ш, Ь, которые содержат ровно одну букву М и одну букву Ш. Причём, эти буквы должны стоять рядом. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая последовательность букв

• 

  21 слайд

  Рисуем схему
  2 2 2 2*2*2=8
  М Ш * * *
  * М Ш * *
  * * М Ш * Всего вариантов 4,
  * * * М Ш тогда 8*4=32

  Но может быть и вариант
  Ш М * * *
  * Ш М * *
  * * Ш М *
  * * * Ш М

  Их тоже 32 варианта. Таким образом,
  Ответ: 32*2=64

• 

  22 слайд

  Задача 4
  Тимофей составляет 5-буквенные коды из букв Т, И, М, О, Ф, Е, Й. Буква Й может использоваться в коде не более одного раза, при этом она не может стоять на первом месте, на последнем месте и рядом с буквой И. Все остальные буквы могут встречаться произвольное количество раз или не встречаться совсем. Сколько различных кодов может составить Тимофей?

• 

  23 слайд

  Задача 5
  Для передачи сообщений, составленных из заглавных букв русского алфавита, используется неравномерный двоичный код, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова, назначенные для некоторых букв: Б – 01, В – 001, Е – 0001, Ш – 111. Какое наименьшее количество двоичных знаков может содержать сообщение, кодирующее слово КУКУШКА?
  КУКУШКА
  Задание по условию Фано
  «с ловушкой»!!!
  У- 2 раза (110)
  К- 3 раза (10)
  А — 1 раз – но не 0000!!! (поскольку надо иметь возможность закодировать остальные буквы русского алфавита)
  2*3+3*2+3+5=20

  Итог: 20

• 

  24 слайд

  Задача 6

  При регистрации на сервере каждый пользователь получает уникальный персональный код, состоящий из двух частей. Первая часть кода содержит 12 символов, каждый из которых может быть одной из 26 заглавных латинских букв. Вторая часть кода содержит 5 символов, каждый из которых может быть одной из 9 цифр (цифра 0 не используется). При этом в базе данных сервера формируется запись, содержащая этот код и дополнительную информацию о пользователе. Для представления кода используют посимвольное кодирование, все символы в пределах одной части кода кодируют одинаковым минимально возможным для этой части количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Для хранения данных о 30 пользователях потребовалось 2100 байт. Сколько байтов выделено для хранения дополнительной информации об одном пользователе? В ответе запишите только целое число – количество байтов.
  25>26 5 бит/символ, 24>9 4 бита/цифра
  12*5+4*5=80 бит=10 байт
  2100 / 30 = 70 байт/пользователь
  70 – 10 = 60 байт на допол. сведения

  Итог: 60

• 

  25 слайд

  Задача 6

  На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П, Р, С. По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт С, проходящих через пункт К?

• 

  26 слайд

  Перерисуем граф с учетом проезда через К
  С=П+М+Р=16+16+16=48
  П=М=16
  Р=М=16
  М=К+Л=8+8=16
  Л=К=8
  К=Д=Б+Е=5+3=8
  Б=А+В+Е=1+1+3=5
  Е=В+А+Г=3
  Итог: 48

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 153 913 материалов в базе

• Выберите категорию:

• Выберите учебник и тему

• Выберите класс:

• Тип материала:

  • Все материалы

  • Статьи

  • Научные работы

  • Видеоуроки

  • Презентации

  • Конспекты

  • Тесты

  • Рабочие программы

  • Другие методич. материалы

Найти материалы

Вам будут интересны эти курсы:

• Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»

• Курс повышения квалификации «Сетевые и дистанционные (электронные) формы обучения в условиях реализации ФГОС по ТОП-50»

• Курс повышения квалификации «Использование компьютерных технологий в процессе обучения в условиях реализации ФГОС»

• Курс повышения квалификации «Применение MS Word, Excel в финансовых расчетах»

• Курс повышения квалификации «Введение в программирование на языке С (СИ)»

• Курс профессиональной переподготовки «Управление в сфере информационных технологий в образовательной организации»

• Курс профессиональной переподготовки «Математика и информатика: теория и методика преподавания в образовательной организации»

• Курс повышения квалификации «Современные тенденции цифровизации образования»

• Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»

Сегодня на повестке дня 8 задание из ЕГЭ по информатике 2021. Данный тип заданий включает в себя нахождение количества вариантов, элементы комбинаторики и другие математические понятия.

Перейдём к практике решения задач задания 8 ЕГЭ по информатике 2021.

Задача (Классика)

Все 4-буквенные слова, составленные из букв А, Е, И, О записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. АААА
2. АААЕ
3. АААИ
4. АААО
5. ААЕА
…

Запишите слово, стоящее на 248-м месте от начала списка.

Решение:

Обозначим условно А — 0, Е — 1, И — 2, О — 3.

Важно: Нужно буквам присваивать цифры именно в том порядке, в котором они идут в самом правом столбце, потому что буквы могут дать в «перепутанном порядке» (например Е, А, И, О), и тогда ничего не получится.

Теперь запишем список с помощью цифр.

1. 0000
2. 0001
3. 0002
4. 0003
5. 0010
…

Получился обычный счёт в четверичной системе!! (всего используются 4 цифры: 0, 1, 2, 3). А слева нумерация показывает соответствие нашей десятичной системе. Но все числа десятичной системы в этой таблице соответствия сдвинуты на 1, ведь мы должны были начать с нуля.

Нас просят записать слово стоящее на 248, т.е. если была обычная таблица соответствия чисел десятичной системы и четверичной системы, слово стоящее на 248 месте, находилось бы на 247 (248 — 1) месте. Значит, наше искомое четверичное число соответствует 247 в десятичной системе.

Переведём число 247 в четверичную систему!

Получилось число 3313₄ в четверичной системе. Сделаем обратное декодирование в буквы. Таким образом, ответ будет ООЕО.

Ответы: ООЕО

Ещё одна похожая задача 8 задания из примерных вариантов ЕГЭ по информатике, но другой вариации.

Задача (Классика, Другая вариация)

Все 5-буквенные слова, составленные из букв А, Р, У, К записаны в алфавитном порядке. Вот начало списка:

1. ААААА
2. ААААК
3. ААААР
4. ААААУ
5. АААКА
……
Укажите номер слова УКАРА

Решение:

Закодируем буквы цифрами: А — 0, К — 1, Р — 2, У — 3. Здесь как раз буквы даны не в том порядке, как они идут в самом правом столбце. Но мы должны кодировать именно в том порядке, как буквы идут в самом правом столбце.

У нас получилось четыре цифры! Значит снова можно слова превратить в таблицу соответствия между десятичной системой и четверичной системой. Но десятичная система смещена на 1 позицию.

1. 00000
2. 00001
3. 00002
4. 00003
5. 00010
……

Выписываем данное нам слово и посмотрим, какое число в четверичной системе было бы, если бы у нас были в место слов числа в четверичной системе!

Получили число в четверичной системе 31020₄. Узнаем, какое число в десятичной системе соответствовало этому числу, если бы была обычная таблица соответствия. Для этого переведём число 31020₄ из четверичной системы в десятичную. Перевод делаем по аналогии перевода из двоичной системы в десятичную.

Но помним, что у нас нумерация идёт на 1 быстрее, нежели мы бы поставили десятичные числа, как в таблице соответствия, потому что нумерация начинается не с нуля, а с 1. Поэтому к числу 840 нужно прибавить 1, и в ответе будет 841

Ответ: 841

Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)

Все 4-буквенные слова, в составе которых могут быть буквы Н, О, Т, К, И,
записаны в алфавитном порядке и пронумерованы, начиная с 1.
Ниже приведено начало списка.

1. ИИИИ
2. ИИИК
3. ИИИН
4. ИИИО
5. ИИИТ
6. ИИКИ
…

Под каким номером в списке идёт первое слово, которое начинается
с буквы О?

Решение:

Закодируем буквы цифрами.

Получилось 5 цифр ( 0, 1, 2, 3, 4 ), значит, будем работать в пятеричной системе.

Нужно найти номер первого слова, которое начинается с буквы О. Если говорить на языке пятеричных чисел, то нужно найти номер числа 3000₅. Мы «забиваем нулями», чтобы число было четырёхразрядное, т.к. слова 4-х буквенные. Именно нулями, потому что нужно именно первое слово найти.

Теперь, как в предыдущей задаче, переведём число 3000₅ из пятеричной системы в десятичную.

0 * 5 ⁰ + 0 * 5 ¹ + 0 * 5 ² +
3 * 5 ³ = 375 (в десят. системе)

Но опять же должны прибавить 1 к числу 375, т.к. нумерация отличается от десятичных чисел на 1 в большую сторону.

Ответ: 376

Задача (Досрочная волна 2020 ЕГЭ по информатике, вариант 1)

Вася составляет 5-буквенные слова, в которых есть только буквы В, О, Л, К,
причём буква В используется в каждом слове ровно 1 раз. Каждая из других
допустимых букв может встречаться в слове любое количество раз или
не встречаться совсем. Словом считается любая допустимая
последовательность букв, не обязательно осмысленная. Сколько существует
таких слов, которые может написать Вася?

Решение:

Для начала решим вводную подзадачу.

Пусть у нас есть те же буквы В, О, Л, К, каждая из букв может встречаться в слове любое количество раз или
не встречаться совсем. Сколько можно составить 5-буквенных слов ?

Т.е буквы могут повторяться!

Например

Такая конструкция сильно напоминает перебор чисел, где вместо цифр используются буквы.

Рассмотрим перебор трёхразрядных чисел. Вместо 5 букв теперь можно использовать 10 цифр ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ). Цифры так же могут повторяться. Сколько получится вариантов ?

Выведем общую формулу для количества вариантов, когда символы могут повторяться!

Для трёхразрядных чисел от 000 до 999:

N = 10³ = 1000 вариантов.

Вернёмся к пятибуквенным словам и нашей подзадаче. Здесь количество букв (разрядов) в слове равно 5, количество допустимых символов равно 4 ( В, О, Л, К ).

N = 4⁵ = 1024 вариантов.

Вернёмся к изначальной задаче. Сначала найдём количество вариантов, когда буква В находится в самой левой ячейке!

Применим формулу! Здесь слово сократилось до четырёхразрядного. А количество букв для использования 3 (О, Л, К).

N = 3⁴ = 81 комбинация.

Но буква В так же может стоять во второй ячейке слева. Этот случай тоже даст 81 других комбинаций. Буква В может стоять в каждой из 5-ти ячеек, и везде будет получатся 81 комбинация.

Таким образом, окончательный ответ будет:

N = 81 * 5 = 405 различных вариантов.

Ответ: 405

Разобравшись с этой задачей, больше половины тренировочных задач десятого задания из различных книг и сайтов по подготовке к ЕГЭ по информатике будут решаться, как по маслу!

Задача(Закрепление формулы)

Рассматриваются символьные последовательности длины 5 в шестибуквенном алфавите {У, Ч, Е, Н, И, К}. Сколько существует таких последовательностей, которые начинаются с буквы У и заканчиваются буквой К?

Решение:

Применим главную формулу 8 задания из ЕГЭ по информатике

N = mⁱ = 6³ = 216

Здесь буквы могут изменяться на 3 ячейках! Значит, в формуле i=3. Количество допустимых символов, которые можно поставить в каждую ячейку равно 6. Значит, в формуле m=6.

В ответе будет 216.

Примечание: Здесь можно использовать все буквы в каждой ячейке, включая У и К. В некоторых задачах их уже использовать нельзя, т.е. сказано, что буквы У и К используются один раз в слове. Тогда в формуле m, будет на 2 единицы меньше. Нужно внимательно читать задачу!

Ответ: 216

Задача (Демонстрационный вариант ЕГЭ по информатике, 2019)

Вася составляет 5-буквенные слова, в которых есть только буквы З, И, М, А,
причём в каждом слове есть ровно одна гласная буква и она встречается
ровно 1 раз. Каждая из допустимых согласных букв может встречаться
в слове любое количество раз или не встречаться совсем. Словом считается
любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Вася?

Решение:

Рассмотрим количество вариантов, когда гласная И стоит в первом месте!

Подсчитаем количество слов с помощью супер-формулы

N = mⁱ = 2⁴ = 16

Длина изменяющихся ячеек равна 4, а количество допустимых букв равно 2.

Но буква И может стоять не только на первом месте. Она так же может стоять и на 2, и на 3, и на 4, и на 5 месте. Каждый такое случай добавляет столько же новых слов.

Значит, при использовании только буквы И будет количество слов 16 * 5 = 80. Ещё столько же слов добавится, если в словах вместо буквы И будет использоваться буква А. Поэтому окончательный ответ будет 80 * 2 = 160

Ответ: 160

Отработаем главную формулу 8 задания из ЕГЭ по информатике.

Задача (Развиваем понимание формулы!)

Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв З, И, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Решение:

Рассмотрим, какие варианты могут быть, если у нас на первом месте стоит согласная, а на последнем месте гласная

Получилось 4 разных случая. Подсчитаем, сколько слов можно составить при одном случае.

N = mⁱ = 4³ = 64

Длина изменяющихся ячеек равна 3, а количество возможных букв 4.

Но т.к. таких случая у нас четыре, то ответ будет 4 * 64 = 256

Ответ: 256

Рассмотрим важнейший «метод умножения» при решении 8 задания из ЕГЭ по информатике.

Задача (Другой метод решения!!)

Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз , при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?

Решение:

Эта задача отличается от уже разобранных тем, что каждую букву можно использовать один раз. В этой задаче удобнее воспользоваться немного другим методом решения! «Методом умножения»!

Решим вводную подзадачу (без дополнительных ограничений).

Сколькими способами можно составить 6-x буквенное слово из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз .

Чтобы найти возможные варианты, перемножаем для каждой ячейки количество букв из которых у нас есть выбор!

N = 6 * 5 * 4 * 3 * 2 * 1 = 720

Вернёмся к изначальной задаче!

В начале подсчитаем «методом умножения» количество слов, не обращая внимание, на условие, в котором сказано, что слово не может содержать сочетание АЕ.

N = 5 * 5 * 4 * 3 * 2 * 1 = 600

В формуле стоят почти все те же самые числа, как и в вводном примере, только первый множитель не 6, а 5. Это произошло из-за того, что у нас в задаче слово не может начинаться на букву Й. Значит, выбор на первую позицию будет не из 6 букв, а из 5.

Но в 600 комбинаций входят и те случаи, когда в слове присутствует сочетание АЕ. Теперь найдём сколько таких слов, где присутствует сочетание АЕ

Узнаем количество вариантов в каждом таком случае.

N1 = 4 * 3 * 2 * 1 = 24

На первом месте мы не можем использовать букву Й, поэтому мы на первом месте выбираем из 3 букв.

N2 = 3 * 3 * 2 * 1 = 18

Аналогично предыдущему случаю.

N3 = 3 * 3 * 2 * 1 = 18



N4 = 3 * 3 * 2 * 1 = 18

N5 = 3 * 3 * 2 * 1 = 18

24 + 18 + 18 + 18 + 18 = 96

Значит, всего слов, которые удовлетворяют условию задаче будет

N = 600 — 96 = 504

Примечание: Метод умножения можно было использовать и в задачах, которые мы рассмотрели ранее. Например, в задаче «Закрепление формулы» в первой свободной ячейке выбираем из 6 букв, во второй свободной ячейке тоже из 6 букв, и в третий свободной ячейке тоже можно использовать 6 букв. Значит, по методу умножения получается N = 6 * 6 * 6 = 6³ = 216

Ответ: 504

Задача (Закрепления «метода умножения»)

Полина составляет 6-буквенные коды из букв П, О, Л, И, Н, А. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Полина?

Решение:

Опять сказано, что каждая буква используется 1 раз, следовательно, нужно применять «метод умножения».

На первое место можно выбрать из 6 букв, предположим, мы выберем согласную. Тогда на второе место нужно выбирать из 3 гласных. Потом опять должна идти согласная, но их у нас осталось только 2. Далее, на следующее место выбираем из 2 гласных букв. И на предпоследнее место выбирается 1 согласная, а на последнее место остаётся 1 гласная.

Т.к. количество гласных букв и согласных одинаковое, и равно трём, то если мы бы начали делать «метод умножения» с гласной буквы, количество вариантов бы не поменялось.

N = 6 * 3 * 2 * 2 * 1 * 1 = 72

Ответ: 72

Задача (Азбука Морзе)

Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код Морзе длиной не менее трёх и не более четырёх сигналов (точек и тире) ?

Решение:

Зная формулу, без проблем решим данную примерную задачу из ЕГЭ по информатике.

У нас есть 2 символа, которые можно использовать: точка и тире. Фраза, что сообщение может иметь «не менее трёх и не более четырёх сигналов», означает, что сообщения могут быть длиною 3 символа и длиною 4 символа.

Подсчитаем общее количество вариантов.

N = 2³ + 2⁴ = 8 + 16 = 24 комбинаций.

Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?

Решение:

Нам нужно закодировать 300 различных вариантов! Имеются 4 различных лампочки! (Они имеют смысл, как количество допустимых символов!) На этот раз нужно узнать количество лампочек (количество разрядов, «длину слова»). Применяем формулу.

N = 4^x = 300

Не найдётся такое целое x, чтобы равенство стало верным. Поэтому берём целое минимальное x такое, чтобы 4^x больше 300.

4⁵ = 1024

Пять лампочек на табло хватит, чтобы закодировать 300 сигналов, но, к сожалению, много комбинаций просто не пригодится!

Ответ: 5

Задача (Важная!)

Нужно выбрать в подарок 3 книги из 5. Сколькими способами можно выбрать ?

Решение:

На рисунке показано две комбинации, как можно выбрать в подарок 3 книги из 5.

Данную задачку нужно решать используя формулу сочетаний из раздела комбинаторика.

n — количество книг, из которых мы выбираем подарок, m — количество книг, которое мы хотим выбрать, C — количество вариантов (способов).

Восклицательный знак — это факториал!

Факториалом числа «n» (условное обозначение n!- читается как «эн» — факториал) называется произведение чисел от 1 до «n»

Примечание: При использовании формулы сочетаний, не важен порядок, в котором мы выбираем одни и те же книги. Это будет один и тот же вариант.

Ответ: 10

Следующая задача часто встречается в книгах по подготовке к ЕГЭ по информатике.

Задача (Главная формула + сочетания)

Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 5. Сколько различных вариантов шифра можно задать, если известно, что цифра 1 встречается ровно три раза, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?

Решение:

В начале нужно посчитать, сколькими способами на 5-ти ячейках можно расположить 3 единицы!

Обратите внимание, как будто мы выбираем 3 книги в подарок из 5 возможных! Значит, опять применяем формулу сочетаний из комбинаторики. Мы вычисляли уже её точно с такими же числами в прошлой задаче, количество вариантов равно 10.

Подсчитаем, сколько вариантов кодового замка можно составить при одном определённом расположении трёх единиц.

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

N = mⁱ = 4² = 16

Т.к. различных вариантов, как расположить единицы на 5 ячейках равно 10, то ответ будет 16 * 10 = 160

Ответ: 160

Ещё одна задача из примерных вариантов по подготовке к ЕГЭ по информатике.

Задача (Таблица соревнований)

Для записи результатов соревнований используется таблица, в которой для каждой из 20-ти команд по каждому из 10-ти видов состязаний записано 1, 2 или 3 (если команда заняла соответствующее место в этом состязании) или прочерк (если не заняла призовое место или не участвовала). Какое количество информации (бит) содержит таблица ?

Решение:

Есть таблица с 20 командами и для каждой команды есть результат по 10-ти видам состязаний.

	1 команда	2 команда	3 команда	…	20 команда
1 дисциплина	1	—	1	…	3
2 дисциплина	—	2	1	…	2
…	…	…	…	…	…
10 дисциплина	1	1	2	…	—

Сделав рисунок, задача обрела привычные очертания.

Как будто мы решаем задачу с перебором слов. Но здесь длина слова неизвестна, а количество вариантов, которое должно получится уже дано и равно 4 (четырём). Применим главную формулу из 10 задания из ЕГЭ по информатике.

N = mⁱ = 2ⁱ = 4

i=2 бита (длина равна «2 буквам», если воспринимать задачу, как со словами.)

Одна ячейка таблицы весит 2 бита. Найдём количество ячеек во всей таблице соревнований.

Всего ячеек = 20 * 10 = 200

Тогда вся таблица будет весит:

V = 2 бита * 200 = 400 бит.

Ответ: 400

Формула Шеннона

Задача (Формула Шеннона)

В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?

Решение:

Найдём вероятность p того, что вытащили чёрный шарик.

p = (количество чёрных шаров) / (количество всех шаров) = 8 / (24 + = 8 / 32 = 1 /4

p = 1 / 4

Применим формулу Шеннона.

x = log₂(4)
2^x = 4

x = 2 бита

Ответ: 2

На этой странице вы узнаете

• Как и для чего информатика использует целый раздел математики?
• Как работают безопасные пароли?
• Зачем считать, если можно не считать? 

Что общего у автомобильного номера, карточной игры и расписания школьных занятий? Наука, их изучающая, — комбинаторика. 

Применение комбинаторики

Комбинаторика — это раздел математики, который занимается решением задач, связанных с выбором и расположением элементов какого-либо множества по заданным параметрам.

Что может служить примерами таких данных?

• автомобильные номера — набор букв и цифр в определенном порядке;
• карточные игры — наборы карт, которые могут находиться у вас на руках;
• расписание занятий — варианты порядка проведения уроков. 

Собственно, комбинаторика может помочь нам:

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

Размещения и перестановки

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

• Размещения — элементы набора могут использоваться в последовательности определенной длины любое количество раз (в том числе ни разу).

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

• Перестановки — возможные последовательности образуются изменением порядка следования элементов друг за другом. Каждый элемент набора используется ровно 1 раз.

Пример: распределение 5 человек на дежурства в течение 5 дней. Было бы справедливо, если бы один человек дежурил только один раз, но вот в какой из дней — уже есть выбор.

Подсчет количества комбинаций

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

В размещениях каждый элемент может быть на любой позиции и может встретиться любое количество раз. То есть на каждой из k позиций может быть любой из n символов, тогда всего размещений может быть N=n^k.

В перестановках последовательности отличаются только порядком следования элементов. Значит, каждый из элементов будет использоваться ровно 1 раз.

• На первой позиции может стоять любой из n символов;
• На второй — любой из оставшихся n − 1 символов;
• На третьей — любой из еще не использовавшихся, то есть n − 2;
• В конце концов — на самой последней позиции может использоваться только 1 оставшийся символ.

Поэтому количество комбинаций перестановок рассчитывается как факториал количества символов: произведение всех чисел от 1 до количества.

В остальных случаях — составляем выражение согласно требованиям:

• Считаем, какое количество символов может находиться на каждой позиции.
• Перемножаем полученные значения.

Например, мы выбираем пароль по следующим условиям:

• длина пароля — 6 символов;
• используются только символы “P”, “A”, “S”, “W”, “O”, “R”, “D”, “1”, “2”, “3”;
• “Р” должен быть на первом месте и больше не встречаться в пароле;
• “3” должен быть на последнем месте и больше не встречаться в пароле.

Определим, какие символы на каких позициях могут находиться:

Теперь можем составить выражение, чтобы найти количество всех возможных вариантов пароля. Перемножим количество возможных символов на каждой позиции:

N = 1 * 8 * 8 * 8 * 8 * 1 = 4096.

Размещения и перестановки в программе Python

Для облегчения работы с ними в Python существует модуль itertools, который содержит инструменты для их создания:

• permutations(набор символов) — создает перестановки переданного набора

---

from itertools import permutations
for i in permutations(“abc”):
    print(i)

Вывод:
('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')

---

• product(набор символов, repeat = длина последовательности) — создает размещения заданной длины из заданного набора символов

---

from itertools import product
for i in product("abcd", repeat = 2):
    print(i)

Вывод:
('a', 'a')
('a', 'b')
('a', 'c')
('a', 'd')
('b', 'a')
('b', 'b')
('b', 'c')
('b', 'd')
('c', 'a')
('c', 'b')
('c', 'c')
('c', 'd')
('d', 'a')
('d', 'b')
('d', 'c')
('d', 'd')

---

Все комбинации будут возвращены в виде списка символов.

Пример.

Допустим, мы будем составлять пароли длиной 6 символов из того же набора символов “P”, “A”, “S”, “W”, “O”, “R”, “D”, “1”, “2”, “3”, но с дополненными условиями:

• символ “Р” может использоваться в пароле любое количество раз, но обязательно должен быть на первом месте;
• символ “3” должен быть использован в пароле ровно 3 раза;
• в пароле не должно быть сочетания “123”.

Пошагово наш код должен состоять из следующих элементов:

1. Для создания всех вариаций пароля будем использовать product модуля itertools, все пароли будем перебирать циклом for. Также предварительно создадим переменную-счетчик подходящих паролей.
2. Нам нужно проверить все условия задачи. Элемент комбинации с индексом 0 равен “Р”, “3” встречается в ней ровно 3 раза, а также в списке символов комбинации не должно быть набора (“1”, “2”, “3”).
3. При нахождении подходящего пароля будем увеличивать наш счетчик на 1, в конце программы выведем его значение на экран.

---

from itertools import product

cnt = 0
for i in product("PASWORD123", repeat = 6):
    if i[0] == "P" and i.count("3") == 3 and ("1", "2", "3") not in i:
        cnt += 1
print(cnt)

Вывод: 810

---

Фактчек

• Размещения — наборы последовательностей определенной длины, состоящие из определенных символов, которые могут встречаться в последовательности сколько угодно раз. Количество размещений N зависит от длины последовательности k и количества символов n как N=n^k.
• Перестановки — наборы последовательностей, отличающиеся только порядком следования символов друг за другом. Количество перестановок N зависит от количества символов в них n как N = n!.
• В общем виде количество комбинаций высчитывается как произведение количества возможных символов на каждой позиции.
• Для записи перестановок в Python используется permutations из модуля itertools, для записи размещений — product из того же модуля.

Проверь себя

Задание 1.
Сколько будет размещений длинной 5, состоящих из набора “123”?

1. 243
2. 125
3. 120
4. 6

Задание 2.
Что такое перестановки?

1. Комбинации, состоящие из символов определенного набора, разной длины.
2. Комбинации, состоящие из символов определенного набора, одной длины.
3. Комбинации, состоящие из символов определенного набора и отличающиеся только порядком следования символов друг за другом.
4. Комбинации, состоящие из символов определенного набора и отличающиеся только длиной.

Задание 3.
Сколько может быть паролей длиной 4, состоящих из набора символов “ПАРОЛЬ”, в которых любой символ может использоваться сколько угодно раз, кроме “Ь” (используется только один раз и только на последнем месте)?

1. 15
2. 20
3. 125
4. 625

Задание 4.
Какая из записей на языке Python создаст размещения набора “ПАРОЛЬ” длинной 4?

1. itertools(“ПАРОЛЬ”, repeat = 4)
2. product(4, repeat = “ПАРОЛЬ”)
3. permutations(“ПАРОЛЬ”, repeat = 4)
4. product(“ПАРОЛЬ”, repeat = 4)

Ответы: 1. — 1; 2. — 3; 3. — 3; 4. — 4.

11.05.2013

В файле содержится вся необходимая теория для подготовки к ЕГЭ по информатике для задания B4.

Изучив предложенный материал, вы обретёте знания и навык для решения этого типа заданий B4.

СКАЧАТЬ в формате DOC