Комбинаторика в информатике: Комбинаторные задачи в ЕГЭ

Комбинаторные задачи в ЕГЭ

Комбинаторные методы в ЕГЭ по информатике применяются для решения задачи №10 (бывшая В4). Рассмотрим решение типичных задач, с использованием комбинаторных приемов.

Решим задачу под номером В4 из демонстрационной версии ЕГЭ по информатике 2014 года.

Задача. Для передачи аварийных сигналов договорились использовать специальные цветные сигнальные ракеты, запускаемые последовательно. Одна последовательность ракет – один сигнал; в каком порядке идут цвета – существенно. Какое количество различных сигналов можно передать при помощи запуска ровно пяти таких сигнальных ракет, если в запасе имеются ракеты трёх различных цветов (ракет каждого вида неограниченное количество, цвет ракет в последовательности может повторяться)?

Решение.

Ракеты могут быть трех различных цветов, при этом в одной последовательности пять ракет. Значит, рассматривается выборка объема пять из трех элементов (n = 3, k = 5).

Определим комбинаторную схему. Два положения в условие задачи:

• «в каком порядке идут цвета – существенно»;
• «цвет ракет в последовательности может повторяться»;

указывают на то, что – это размещения с повторениями.

Ответ. 243

Решим задачу №10 из демоверсии ЕГЭ по информатике 2016 года.

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

Решение.

1) буква «П» появляется ровно 1 раз, значит она может находиться на одной из 5 позиций в слове.

2) буквы «И» и «Р» заполнят остальные 4 позиции. Рассмотрим выборки объема 4 из 2 элементов (k = 4, n = 2). Кодовые слова могут отличаться как порядком следования букв, так и составом, значит, комбинаторная схема – размещения с повторениями. Найдем число таких размещений:

3) применим правило произведения: 5 * 16 = 80

Ответ. 80

Типичная тренировочная задача №10 для подготовки к ЕГЭ по информатике.

Задача. Вася составляет 5-буквенные слова из четырехбуквенного алфавита {A, C, R, T}, причём буква А используется в каждом слове ровно 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом, считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Решение.

1) пронумеруем позиции в слове, тогда варианты расположений букв «А» можно представить в качестве неупорядоченного выбора двух цифр из пяти. Значит, комбинаторная схема — сочетания без повторений

2) остальные допустимые символы будут занимать 3 позиции. Эти выборки объемом 3 из 3 элементов будут отличаться как порядком следования, так и набором символов. Очевидно, комбинаторная схема – размещения с повторениями.

3) применим правило произведения: 27 * 10 = 270

Ответ. 270

8 Задание ЕГЭ 2021 | Комбинаторика

 

Лада Есакова, преподаватель информатики и математики, автор книги «Информатика. Полный курс подготовки к ЕГЭ».

Добрый день, дорогие друзья! С вами я, Есакова Лада, преподаватель информатики с 20-летним стажем.
Сегодня разберем основы комбинаторики и буквенные цепочки.

Задача:
«Все 4-буквенные слова, составленные из букв В, Н, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ВВВВ
2. ВВВН
3. ВВВР
4. ВВВТ
5. ВВНВ
………
Запишите слово, которое стоит под номером 251.»

Обозначим В = 0, Н = 1, Р = 2, Т = 3 и получим вот такой ряд:

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

Это числовой ряд в четверичной системе исчисления. Нам нужно найти слово, которое стоит под номером 251.

Здесь важный нюанс, на котором часто ребята теряют балл. На первом месте стоит 0, то есть номер строчки на единицу больше самого числа. Поэтому на 251 месте у нас будет стоять число на единицу меньше – 250, но только в четверичной системе исчисления.

Переведем 250 в четверичную систему. Будем делить столбиком. У нас получается 250 = 3322₄. Теперь переводим цифры в буквы — ТТРР. Вот такой ответ должен получиться.
Вот такие буквенные цепочки – это, по сути, числовые ряды.

Следующая задача:
«Все 6-буквенные слова, составленные из букв С, В, Е, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. ВВВВВВ
2. ВВВВВЕ
3. ВВВВВС
4. ВВВВВТ
5. ВВВВЕВ
………
Под каким номером стоит первое из слов, которое начинается с буквы Т?»

Здесь есть еще одна ловушка: нам сказали, что все 6-буквенные слова составлены из этих букв, и очень хочется пронумеровать букву в том же порядке, в котором они представлены – С = 0, В = 1, Е = 2, Т = 3. Вот здесь-то и ошибка.

Если посмотрим на числовой ряд, то увидим, что на первой строчке у нас стоит В, значит, она будет равна 0. Далее появляется Е, значит, она равна 1, С = 2 и Т = 3.

И снова у нас четверичная система исчисления. Необходимо определить, под каким номером стоит первое из слов, которое начинается с буквы Т. Перефразирую вопрос: под каким номером стоит четверичное число, которое начинается на 3? Значит, оно должно выглядеть как 300000. Это число стоит на месте, которое на единицу больше, чем оно само, но в десятичной записи. Необходимо это число, 300000, из четверичной системы перевести в десятичную.

300000₄=3*4⁵=3*1024=3072

У нас получается число 3072, а номер строки на единицу больше, то есть номер строки будет 3073. Это и есть ответ задачи.

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

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

Мы можем составить 4 комбинации:

Если нам этого не хватает, мы можем добавить флажки еще одного цвета. Допустим, у нас еще есть зеленые флажки, и мы можем составить следующие комбинации:

У нас получилось 9 комбинаций.

Если же все-таки у нас флажки только двух цветов, третьего нет, у нас есть другой путь увеличить количество комбинаций, увеличив количество флагштоков. Получаем следующие комбинации:

и их получилось 8 штук.

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

Количество слов, которые мы можем закодировать, равно количеству букв в нашем алфавите (еще это называется мощностью алфавита) в степени «длина слова» A=aⁱ

«Сколько различных символов можно закодировать, используя код азбуки Морзе длиной не менее четырех и не более пяти сигналов (точек и тире)?»

Если я делаю слово из четырех сигналов, то таких слов я могу сделать 2⁴, если я делаю из пяти сигналов, то таких слов я могу придумать 2⁵. А в задаче как раз этот интервал, то есть и те, и те мне подойдут. Вот столько разных слов я могу составить 2⁴ + 2⁵ = 48.

«Коля составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует свое кодовое слово. В качестве кодовых слов Коля использует 4-буквенные слова, в которых есть буквы А, Б, В, Г, Д, причем буква Д появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Коля?»

Не буду мудрить, придумывать какие-то сложные формулы, а просто распишу, как буква Д может встречаться ровно один раз. Это выглядит так

Д — — —
— Д — —
— — Д —
— — — Д

то есть она может встретиться на каком-то из четырех мест. На остальных трех местах может стоять все, кроме Д, то есть 4 любые буквы по трем позициям, 4³. И так в каждом ряду. Все это сложим и получим 4*4³=4⁴=256

«Паша составляет таблицу кодовых слов для передачи сообщений. В качестве кодовых слов Паша использует 4-буквенные слова, в которых есть только буквы А, Б, В, Г, Д, Е, Ж. При этом первая буква кодового слова – это буква Д, Е или Ж, а далее в кодовом слове буквы Д, Е и Ж не встречаются. Сколько различных кодов может использовать Паша?»

У нас получается такой вид

Д — — —
Е — — —
Ж — — —

А в остальных местах используются остальные буквы, кроме Д, Е и Ж. Получаем 3*4³=3*64=192

«Герасим составляет 7-буквенные коды из букв Г, Е, Р, А, С, И, М. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Герасим?»

Тут немного схитрим. Необходимо обязательно чередовать гласные и согласные, а для этого посмотрим, сколько у нас гласных. 3. А согласных 4. Поэтому на гласную начать слово я не могу, иначе их не хватит на все слово, и согласные где-то обязательно повторятся. Поэтому слово будет выглядеть таким образом: согласная – гласная – согласная – гласная – согласная – гласная – согласная.

Далее каждую букву я должна использовать ровно один раз.

Вначале состава слова согласных у нас 4, гласных – 3, далее согласных остается 3, т.к. одну я уже использовала, а согласных – 2, затем согласных 2, гласных – одна и согласная осталась одна. Теперь мы перемножаем все эти цифры

и получаем 144.

«Ольга составляет 5-буквенные коды из букв О, Л, Ь, Г, А. Каждую букву нужно использовать ровно 1 раз, при этом Ь нельзя ставить первым и нельзя ставить после гласной. Сколько различных кодов может составить Ольга?»

Давайте пойдем от противного: посчитаем все варианты, а потом выбросим те, которые нам запретили, но сразу выкинем вариант с мягким знаком на первом месте. То есть на первом месте мы можем поставить 4 различные буквы. На втором месте могу поставить все, кроме этой буквы, но зато мы можем добавить Ь, то есть тоже 4. Две буквы уже использовали. Осталось 3, 2 и 1. Все это перемножаю и получаю 96. То есть это все возможные слова, где используется буквы по одному разу, но только не начинающиеся на Ь.

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

О Ь — — —
— О Ь — —
— — О Ь —
— — — О Ь

Таких слов 24

О Ь — — — 3*2*1
— О Ь — — 3*2*1
— — О Ь — 3*2*1
— — — О Ь 3*2*1
——
24

Абсолютно такая же ситуация с буквой А

А Ь — — —
— А Ь — —
— — А Ь —
— — — А Ь
———
24

И их тоже 24. То есть 96-48=48.

На этом прощаемся. Если вопросов нет, пока!

Все видео по информатике

мягкий вопрос — какую роль комбинаторика играет в информатике?

спросил 5 лет, 9 месяцев назад

Изменено 5 лет, 9 месяцев назад

Просмотрено 7к раз

$\begingroup$

Я закончил информатику. Мне нужен совет по материалам по комбинаторике, связанным с основными областями информатики. Я уже знаю, что дискретная математика играет ключевую роль в некоторых концепциях, которые мне нужно немного уточнить. В каких областях я мог бы проследить концепции, теоремы и методы комбинаторики?

• комбинаторика
• мягкий вопрос
• совет

$\endgroup$

5

$\begingroup$

Теория графов является чрезвычайно важной частью комбинаторики в информатике. Грубо говоря, это изучение объектов и связей между ними.

Алгоритмы и Структуры данных широко использует комбинаторные методы для анализа и проектирования. Некоторые структуры данных используют идеи теории графов для эффективного хранения и извлечения данных. Рандомизированные алгоритмы и Аппроксимационные алгоритмы требуют комбинаторных методов для анализа.

Они часто быстрее или более «полезны», чем детерминированные.

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

Другие интересные области информатики, в которых важна комбинаторика, включают Теория кодирования (коды с исправлением ошибок по каналам связи), Вычислительная геометрия и т. д.

---

См. также: Почему важно изучать комбинаторику?

$\endgroup$

0

Зарегистрируйтесь или войдите в систему

Зарегистрируйтесь с помощью Google

Зарегистрироваться через Facebook

Зарегистрируйтесь, используя электронную почту и пароль

Опубликовать как гость

Электронная почта

Требуется, но никогда не отображается

Опубликовать как гость

Электронная почта

Требуется, но не отображается

Нажимая «Опубликовать свой ответ», вы соглашаетесь с нашими условиями обслуживания, политикой конфиденциальности и политикой использования файлов cookie

.

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

Комбинаторика и теория графов в информатике
Время и местонахождение: TTh 13:15-14:45, Bloomberg 176.

Инструктор: Синь Ли. Часы работы: Среда с 16:00 до 17:00 или по предварительной записи.

Программа

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

Необходимое условие: Дискретная математика. Очень рекомендуется теория вероятностей и линейная алгебра.

Необходимый учебник: Стасис Юкна, Экстремальная комбинаторика: с приложениями в информатике. 2-е издание.
Errata

Учебник по выбору: Н. Алон и Дж. Х. Спенсер, «Вероятностный метод»

Список предварительных тем:
Базовые техники:
Счет; Принцип голубиной норы; Соответствие и теорема Холла; Цепи и антицепи с приложениями к ЛИС.

Вероятностный метод:
Основной метод; локальная лемма Ловаза и ее конструктивное доказательство; линейность ожидания; метод удаления; Границы концентрации; Случайные блуждания и рандомизированный алгоритм для формул КНФ

Спектральная теория графов:

Основные свойства спектра графа; Неравенство Чигера и аппроксимация расширения графа; Графы-расширители и приложения к суперконцентраторам и псевдослучайности; Коды исправления ошибок и коды расширения.

Теоремы типа Рамсея и конструкции графов Рамсея.

Аддитивная комбинаторика:
Теорема о суммах произведений, теорема Семереди-Троттера, проблема множеств Какея и приложения к экстракторам случайности.

Рассматриваемые темы

• 31 августа и 2 сентября: базовый счет, биномиальная теорема, принцип среднего, двойной счет, включение и исключение.

7 и 9 сентября: Запрещенные подграфы, проблема Заранкевича, Накрытие.

14 и 16 сентября: Система различных представлений и сопоставление, Теорема Холла, Сопоставление в двудольных графах, Покрытие вершин.

21 сентября и 23 сентября: увеличивающий путь, принцип голубятни, теорема Эрдоша-Секереса, теорема Мантеля, теорема Турана, лемма Дилворта, теорема Рэмси.

28 и 30 сентября: Теорема Дирихле, приложения в самой длинной возрастающей подпоследовательности.

5 и 7 октября: вероятностный метод, линейность ожидания.

12 и 14 октября: Доказательство Разборова, что MAJ имеет большой размер цепи AC0, промежуточный экзамен.

19 и 21 октября: Локальная лемма Ловаша и ее приложения.

No related posts.