Проектная работа по информатике на тему "Восьмое задание в КИМах ЕГЭ по информатике”"

МУНИЦИПАЛЬНОЕ АВТОНОМНОЕ ОБЩЕБРАЗОВАТЕЛЬНОE УЧРЕЖДЕНИЕ

МУНИЦИПАЛЬНОГО ОБРАЗОВАНИЕ ГОРОД КРАСНОДАР ЛИЦЕЙ № 90

ИМЕНИ МИХАИЛА ЛЕРМОНТОВА

ПРОЕКТ по информатике

Тема: «Восьмое задание в КИМах ЕГЭ по информатике”

Ученика 11” В” класса

МАОУ Лицей №90

г. Краснодара

Прутский Дмитрий

Руководитель проекта:

Савина Р. Р.

2021–2023 учебный год

Оглавление

Введение. 2

Глава первая. 3

Комбинаторика - правила, формулы и примеры с решением.. 3

Комбинаторика на Python. 8

Глава вторая. 15

Заключение. 17

Список литературы.. 18

Введение

В наше время, многие выбирают в виде экзамена для сдачи в 11 классе информатику. В некоторых номерах экзамена используется метод комбинаторики. Комбинаторика зачастую вызывает сложность у сдающих. Существует множество видов решения комбинаторных задач.

Актуальность проекта:

В 8 номере ЕГЭ используется метод комбинаторики. Я хочу ознакомиться с ним и показать различные методы решения этого номера.

Цель работы:

 Упрощение решения ЕГЭ.

Значимость проекта:

 Данная работа упростит решение 8 номера ЕГЭ, продемонстрирует различные способы решения. Каждый из нас сможет выбрать свой способ решения.

Задачи:

·         проанализировать номера ЕГЭ по информатике

·         подготовить несколько решений номера 8 и организовать их

Предмет исследования — контрольно-измерительный материал экзамена по информатике

Глава первая.

Комбинаторика - правила, формулы и примеры с решением

Комбинаторика — это раздел математики, в котором изучаются способы выбора и размещения элементов некоторого конечного множества на основании определенных условий. Выбранные (или выбранные и размещенные) группы элементов называются соединениями. Если все элементы полученного множества разные, получаем соединения без повторений, а если элементы повторяются — соединения с повторениями.

Перестановки

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

Пример:

Количество различных шестизначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, не повторяя эти цифры в одном числе, равно Комбинаторика - правила, формулы и примеры с решением.

Размещения

Размещением из n элементов по k называется любое упорядоченное множество из k элементов, состоящее из элементов данного n-элементного множества. Формулы для нахождения количества соединений с повторениями обязательны только для классов физико-математического профиля. Формула числа размещений Комбинаторика - правила, формулы и примеры с решением Комбинаторика - правила, формулы и примеры с решением

Пример:

Количество различных трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, если цифры не могут повторяться, равно Комбинаторика - правила, формулы и примеры с решением

Сочетания

Сочетанием без повторений из n элементов по k называется любое k-элементное подмножество данного n-элементного множества. Формула числа сочетаний Комбинаторика - правила, формулы и примеры с решением Комбинаторика - правила, формулы и примеры с решением (по определению считают, что Комбинаторика - правила, формулы и примеры с решением

Пример:

Из 25 учащихся одного класса можно выделить пятерых для дежурства по школе Комбинаторика - правила, формулы и примеры с решением способами, то есть Комбинаторика - правила, формулы и примеры с решением способами. Некоторые свойства числа сочетаний без повторений Комбинаторика - правила, формулы и примеры с решением (в частности, Комбинаторика - правила, формулы и примеры с решением) Комбинаторика - правила, формулы и примеры с решением

Понятие соединения. Правило суммы и произведения

При решении многих практических задач приходится выбирать из определенной совокупности объектов элементы, имеющие те или иные свойства, размещать их в определенном порядке и т. д. Поскольку в этих задачах речь идет о тех или иных комбинациях объектов, то такие задачи называют комбинаторными. Раздел математики, в котором рассматриваются методы решения комбинаторных задач, называется комбинаторикой. В комбинаторике рассматривается выбор и размещение элементов некоторого конечного множества на основании определенных условий. Выбранные (или выбранные и размещенные) группы элементов называют соединениями. Если все элементы полученного множества разные, получаем размещения без повторений, а если элементы могут повторяться — размещения с повторениями. В этом параграфе мы рассмотрим соединения без повторений. Решение многих комбинаторных задач базируется на двух основных правилах — правиле суммы и правиле произведения. Правило суммы. Если на тарелке лежат 5 груш и 4 яблока, то выбрать один фрукт (грушу или яблоко) можно 9 способами (5 + 4 = 9). В общем виде справедливо такое утверждение: если элемент А можно выбрать m способами, а элемент В — n способами (при этом выбор элемента А исключает одновременный выбор элемента В), то А или В можно выбрать m + n способами. Уточним содержание этого правила, используя понятие множеств и операций над ними. Пусть множество А состоит из m элементов, а множество В -из n элементов. Если множества А и В не пересекаются (то есть Комбинаторика - правила, формулы и примеры с решением), то множество А Комбинаторика - правила, формулы и примеры с решением В состоит из Комбинаторика - правила, формулы и примеры с решением элементов. Правило произведения. Если в киоске продают ручки 5 видов и тетради 4 видов, то выбрать набор из ручки и тетради (то есть пару — ручка и тетрадь) можно 5æ4 = 20 способами (поскольку с каждой из 5 ручек можно взять любую из 4 тетрадей). В общем виде имеет место такое утверждение: если элемент А можно выбрать m способами, а после этого элемент В — n способами, то А и В можно выбрать Комбинаторика - правила, формулы и примеры с решением способами. Это утверждение означает, что если для каждого из m элементов А можно взять в пару любой из n элементов В, то количество пар равно произведению Комбинаторика - правила, формулы и примеры с решением. В терминах множеств полученный результат можно сформулировать следующим образом. Если множество А состоит из т элементов, а множество В — из n элементов, то множество всех упорядоченных пар* (а; b), где первый элемент принадлежит множеству А (а ∈ А), а второй  множеству В (b ∈ В), состоит из Комбинаторика - правила, формулы и примеры с решением элементов. Повторяя приведенные рассуждения несколько раз (или, более строго, используя метод математической индукции), получаем, что правила суммы и произведения можно применять при выборе произвольного конечного количества элементов. 

Упорядоченные множества:

При решении комбинаторных задач приходится рассматривать не только множества, в которых элементы можно записывать в любом порядке, но и так называемые упорядоченные множества. Для упорядоченных множеств существенным является порядок следования их элементов, то есть то, какой элемент записан на первом месте, какой на втором и т. д. В частности, если одни и те же элементы записать в разном порядке, то мы получим различные упорядоченные множества. Чтобы различить записи упорядоченного и неупорядоченного множеств, элементы упорядоченного множества часто записывают в круглых скобках, например (1; 2; 3) ≠ (1; 3; 2). Рассматривая упорядоченные множества, следует учитывать, что одно и то же множество можно упорядочить по-разному. Например, множество из трех чисел {–5; 1; 3} можно упорядочить по возрастанию: (–5; 1; 3), по убыванию: (3; 1; –5), по возрастанию абсолютной величины числа: (1; 3; –5) и т. д.* Множество всех упорядоченных пар (а; b), где первый элемент принадлежит множеству А (а ∈ А), а второй - множеству В (b ∈ В), называют декартовым произведением множеств А и В и обозначают А × В. Отметим, что декартово произведение В × А также состоит из m*n элементов. Заметим следующее: для того, чтобы задать конечное упорядоченное множество из n элементов, достаточно указать, какой элемент находится на первом месте, какой на втором, ..., какой на n-м.

Размещения:

Размещением из n элементов по k называется любое упорядоченное множество из k элементов, состоящее из элементов заданного n-элементного множества. Например, из множества, содержащего три цифры {1; 5; 7}, можно составить следующие размещения из двух элементов без повторений:

(1; 5), (1; 7), (5; 7), (5; 1), (7; 1), (7; 5).

Количество размещений из n элементов по k обозначается Комбинаторика - правила, формулы и примеры с решением (читается: «А из n по k», A — первая буква французского слова arrangement, что означает «размещение, приведение в порядок»). Как видим, Комбинаторика - правила, формулы и примеры с решением. Выясним, сколько всего можно составить размещений из n элементов по k без повторений. Составление размещения представим себе как последовательное заполнение k мест, которые будем изображать в виде клеточек (рис. 21.1). На первое место можем выбрать один из n элементов данного множества (то есть элемент для первой клеточки можно выбрать n способами). Если элементы нельзя повторять, то на второе место можно выбрать только один элемент из оставшихся, то есть из n – 1 элементов. Теперь уже два элемента использованы и на третье место можно выбрать только один из n – 2 элементов и т. д. На k-е место можно выбрать только один из n – (k –1) = n – k +1 элементов (см. рис. 21.1). Комбинаторика - правила, формулы и примеры с решением. Поскольку требуется выбрать элементы и на первое место, и на второе, ..., и на k-е, то используем правило произведения и получим следующую формулу числа размещений из n элементов по k: Комбинаторика - правила, формулы и примеры с решением.

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

·         Учитывается ли порядок следования элементов в соединении?

·         Все ли заданные элементы входят в полученное соединение?

Если, например, порядок следования элементов учитывается и из n данных элементов в соединении используется только k элементов, то по определению это — размещение из n элементов по k. После определения вида соединения следует также выяснить, могут ли элементы в соединении повторяться, то есть выяснить, какую формулу необходимо использовать — для количества соединений без повторений или с повторениями.

Комбинаторика на Python

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

Модуль itertools находится в стандартной библиотеке Python.

Модуль представляет следующие типы итераторов:

·         Бесконечные итераторы;

·         Конечные итераторы;

·         Комбинаторные генераторы.

Возвращаемый объект также будет итератором. Мы можем проходиться по итератору с помощью:

·         функции «next»

·         цикла for

·         конвертации в список с помощью list ()

Комбинаторные генераторы:

1. prоduct()

Декартово произведение итерируемых объектов, подаваемых на вход.

Определение декартова произведения: произведение множества X и множества Y – это множество, содержащее все упорядоченные пары (x, y), в которых x принадлежит множеству X, а y принадлежит множеству Y.

Чтобы вычислить произведение итерируемого объекта умноженного самого на себя, нужно указать количество повторений с помощью опционального аргумента с ключевым словом repeat. Например, product (A, repeat=4) – тоже самое, что и product (A, A, A, A).

itertools.product(*iterables,repeat)

import itertools

#Only one iterable is given

l1=itertools.product("ABCD")

print (list(l1))#Output:[('A',), ('B',), ('C',), ('D',)]

#two iterables are given

l2=itertools.product("ABC",[1,2])

print (list(l2))#Output:[('A', 1), ('A', 2), ('B', 1), ('B', 2), ('C', 1), ('C', 2)]

#one iterable and repeat is mentioned.

l3=itertools.product("xy",repeat=2)

print (list(l3))#Output:[('x', 'x'), ('x', 'y'), ('y', 'x'), ('y', 'y')]

l4=itertools.product("aa",repeat=2)

print (list(l4))#Output:[('a', 'a'), ('a', 'a'), ('a', 'a'), ('a', 'a')]

#More than two iterables is mentioned

l5=itertools.product([1,2],[3,4],[5,6])

print (list(l5))#Output:[(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]

2. permutations()

Возвращает последовательные r перестановок элементов в итерируемом объекте. Если параметр r не указан или стоит в значении None, то по умолчанию r принимает длину итерируемого объекта и генерирует все возможные полноценные перестановки. Кортежи перестановок выдаются в лексикографическим порядке в соответствии с порядком итерации входных данных. Таким образом, если входные данные итерируемого объекта отсортированы, то комбинация кортежей будет выдаваться в отсортированном порядке.

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

itertools.permutations(iterable,r=None)

import itertools

l1=itertools.permutations("ABC")

print (list(l1))#Output:[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

l2=itertools.permutations([3,2,1])

print (list(l2))#Output:[(3, 2, 1), (3, 1, 2), (2, 3, 1), (2, 1, 3), (1, 3, 2), (1, 2, 3)]

#elements are treated as unique based on their position and not by their value.

l3=itertools.permutations([1,1])

print (list(l3))#Output:[(1, 1), (1, 1)]

l4=itertools.permutations(["ABC"])

print (list(l4))#Output:[('ABC',)]

#r value is mentioned as 2. It will return all different permutations in 2 values.

l5=itertools.permutations([1,2,3,4],2)

print (list(l5))#Output:[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

Примечание: в перестановках порядок элементов имеет значение.

3. combinations()

Возвращает подпоследовательности длины r из элементов итерируемого объекта, подаваемого на вход.

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

Лексикографический порядок – способ упорядочивания слов в алфавитном порядке.

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

itertools.combinations(iterable, r)

4. combinations_with_replacement():

Возвращает подпоследовательности длины r из элементов итерируемого объекта, подаваемого на вход, при этом отдельные элементы могут повторяться больше одного раза.

itertools.combinations_with_replacement (iterable, r)

import itertools

l1=itertools.combinations("ABC",2)

print (list(l1))#Output:[('A', 'B'), ('A', 'C'), ('B', 'C')]

l1=itertools.combinations_with_replacement("ABC",2)

print (list(l1))#Output:[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

l2=itertools.combinations([3,2,1],3)

print (list(l2))#Output:[(3, 2, 1)]

l2=itertools.combinations_with_replacement([3,2,1],3)

print(list(l2))#Output:[(3, 3, 3), (3, 3, 2), (3, 3, 1), (3, 2, 2), (3, 2, 1), (3, 1, 1), (2, 2, 2), (2, 2, 1), (2, 1, 1), (1, 1, 1)]

#elements are treated as unique based on their position and not by their value.

l3=itertools.combinations([1,1],2)

print (list(l3))#Output:[(1, 1)]

l3=itertools.combinations_with_replacement([1,1],2)

print (list(l3))#Output:[(1, 1), (1, 1), (1, 1)]

#since list contains only one element, given r value is 2. So it returns empty list.

l4=itertools.combinations(["ABC"],2)

print (list(l4))#Output:[]

#In combinations_with_replacement,it allows repeated element.

l4=itertools.combinations_with_replacement(["ABC"],2)

print (list(l4))#Output:[('ABC', 'ABC')]

#r value is not mentioned. It will raise TypeError

#l5=itertools.combinations([1,2,3,4])

#print (list(l5))#Output:TypeError: combinations() missing required argument 'r' (pos 2)

l5=itertools.combinations_with_replacement([1,2,3,4])

print (list(l5))#Output:TypeError: combinations_with_replacement() missing required argument '

Глава вторая.

Практическая часть

№1

Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X может появиться на первом месте или не появиться вовсе. Сколько различных кодовых слов может использовать Алексей?

Решение 1

На первой позиции в слове могут быть все четыре буквы А, В, С и Х, а со второй по пятую — 3. Значит, всего можно составить 4 · 3 · 3 · 3 · 3 = 324 слова

Решение 2

В решение два мы прогоняем через цикл сразу с выполнением выше поставленных условий и считаем , все возможные варианты

Решение 3

В решение 3 мы используем встроенный модуль itertools, а именно prоduct. Прогоняем через цикл получая картеж, потом преобразовываем картеж в список, и выполняем все выше поставленные условия. Считаем все возможные варианты исхода

№2

Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 4-буквенные слова, в которых есть только буквы A, B, C, D, X, Y, Z, причём буквы X, Y и Z встречаются только на двух первых позициях, а буквы A, B, C, D  — только на двух последних. Сколько различных кодовых слов может использовать Олег?

Решение 1

Составляем четырехбуквенные слова. На первые два места можно поставить одну из трех букв X, Y или Z. Это можно сделать 3*3=9 вариантами. На два последних места берем букву из четырех букв A, B, C или D. Получаем 4*4=16 вариантов. Таким образом, всего 9*16 = 144 варианта.

Решение 2

В решение 3 мы используем встроенный модуль itertools, а именно prоduct. Прогоняем через цикл получая картеж, потом преобразовываем картеж в список, и выполняем все выше поставленные условия. Считаем все возможные варианты исхода

Решение 3

В решение два мы прогоняем через цикл сразу с выполнением выше поставленных условий и считаем , все возможные варианты

Заключение.

В ходе данного проекта нам удалось познакомиться с методом комбинаторики, и благодаря этому мы смогли лучше понимать эту тему. Также, нам предоставилась возможность изучить различные варианты решения 8 номера по предмету информатики для единого государственного экзамена. Хотелось бы добавить, что мы также узнали новый метод на языке программирования Phyton, и вдобавок показали различные решения довольно сложных задач по комбинаторике.

Список литературы

1.        https://www.evkova.org/kombinatorika#Комбинаторика

2.        https://mosmetod.ru/files/Informatika/KEGE-2021/Задание_8_Кодирование_данных_Павлова_ИБ.pdf

3.        Райгородский, А. М. Вероятность и алгебра в комбинаторике / А.М. Райгородский. - М.: МЦНМО, 2008. - 48 c.

4.        Райгородский, А. М. Вероятность и алгебра в комбинаторике / А.М. Райгородский. - М.: МЦНМО, 2010. - 48 c.

5.        Райгородский, А. М. Линейно-алгебраический метод в комбинаторике / А.М. Райгородский. - М.: МЦНМО, 2007. - 136 c.

6.        Савельев, Л. Я. Комбинаторика и вероятность / Л.Я. Савельев. - М.: Наука. Сибирское отделение, 1975. - 424 c.

7.        Шахмейстер, А. Х. Комбинаторика. Статистика. Вероятность / А.Х. Шахмейстер. - М.: КДУ, Петроглиф, МЦНМО, 2014. - 296 c.

8.        Шахмейстер, А. Х. Комбинаторика. Статистика. Вероятность / А.Х. Шахмейстер. - М.: МЦНМО, Петроглиф, Виктория плюс, 2010. - 296 c.

9.        Шахмейстер, А. Х. Комбинаторика. Статистика. Вероятность / А.Х. Шихтмейстер. - М.: Петроглиф, Виктория плюс, МЦНМО, 2015. - 296 c.

10.    Эрдеш, П. Вероятностные методы в комбинаторике / П. Эрдеш, Дж. Спенсер. - М.: Мир, 1976. - 136 c.

11.    Яковлев, И. В. Комбинаторика для олимпиад ников / И.В. Яковлев. - М.: МЦНМО, 2016. - 80 c.