Изучение основ комбинаторики и теории вероятностей (стр. 7 из 17)
б)Из-за недостатка времени криптоаналитик может сделать только
1000 попыток для расшифровки сообщения, ключ от которого ему неизвестен. Однако известно, что используется рюкзачный вектор, состоящий из 100 чисел, при этом сумма порождается 4 числами. Требуется оценить вероятность того, что за 1000 попыток вскрыть шифр, он это сумеет сделать.
Определим сначала общее число комбинаций, которые следовало бы перебрать криптоаналитику:
=100!/(4!96!). Однако благоприятной комбинацией является только одна. Следовательно, вероятность вскрытия шифра за одну попыткуР = 24/94109400 = 0,000000255.
Вероятность того, что криптоаналитик вскроет неизвестный шифр за 1000 попыток:
Р(1000) = 1 - (1 - 0,000000255)1000 = 0,0003.
в) Электромонтажник распаивает разъем на 8 контактов, не имея
монтажной схемы, т. е. случайным образом. Определить:
1.Вероятность того, что все провода будут припаяны правильно.
2.Вероятность того, что из 8 проводов ровно 3 провода будут припаяны правильно, а остальные неверно.
Для решения задачи сначала определим общее число перестановок 8 проводов. Оно равно 8! = 40320. Для решения 1-й части задачи отметим, что имеется всего одна благоприятная комбинация, поэтому вероятность распаять разъем правильно, не имея монтажной схемы, равна Р = 1/40320 = 0,0000248. Для решения второй части задачи число благоприятных комбинаций значительно больше и определяется как
Поэтому вероятность припаять правильно ровно 3 провода из 8 равна Р = 2464/40320 = 0,061.
1.5.3. Криптография
При исследовании любых криптографических систем используются комбинаторные методы. Они позволяют найти количество комбинаций для расшифровки сообщения и поэтому являются важным инструментом криптоаналитика.
Рассмотрим, например, простейшую классическую криптографическую систему, называемую системой Цезаря. В этой системе производится замена букв по определенному правилу. Сначала в первой строке выписываются подряд все буквы алфавита. Затем формируется нижняя строка, составленная из тех же букв, расположенных в том же порядке, но со сдвигом на sпозиций. Для оценки затрат криптоаналитика по подбору шифра замены требуется вычислить количество вариантов ключей (т. е. сдвигов). Это число равно количеству букв п в алфавите. Для латинского алфавита п = 26, для русского алфавита п = 33, поэтому криптоаналитик должен перебрать соответствующее число разных ключей, т. е. рассмотреть все шифры замены, получаемые всевозможными сдвигами букв алфавита, т. е. 26 или 33 элемента группы сдвига.
Криптосистема DESоперирует с ключом, состоящими из 56 бит. Криптоаналитик для вскрытия шифра должен перебрать все 256 варианта ключей (если учитывать ключи, состоящие из нулей и единиц). Если же имеется дополнительная информация об используемых характеристиках ключей, перебор может быть существенно уменьшен с помощью комбинаторных методов.
Рюкзачная криптосистема с открытым распределением ключей имеет дело с вектором А = (a1, a2, ..., ап). При шифровании сообщений открыто передаются значения сумм некоторых элементов аi, при этом криптоаналитику часто бывает известно количество элементов и их сумма (но не известны сами элементы). Для вскрытия шифра криптоаналитик должен перебрать число ключей, равное числу сочетаний из п по к.
1.5.4. Экономика
Рассмотрим следующую задачу. Некоторый банк имеет 5 миллионов рублей, которые может выдать клиентам в виде кредитов. Предположим, что кредиты хотят получить 8 клиентов банка (заемщики). Правление решает выдавать кредиты, кратные 0,25 миллиона. Требуется определить, сколько различных способов выдачи кредита существует. Комбинаторика, конечно, не позволяет решить вопрос о том, каким клиентам и какой кредит следует выдать. Она только позволяет подсчитать количество вариантов. Для данного условия задачи найдем сначала количество квот (частей по 0,25 миллиона в каждой), содержащихся в 5 миллионах. Для этого разделим 5 на 0,25, получим 20. Выпишем теперь подряд 20 единиц и справа к ним припишем 7 нулей. Начнем переставлять цифры полученного кода всеми возможными способами. Одна из таких перестановок может выглядеть так: 111110111001001111111110011. Такой перестановке будет соответствовать следующий вариант раздачи кредитов:
| 1-й | Заемщик получит | 1,25 миллиона |
| 2-й | - | 0,75 миллиона |
| 3-й | - | 0, |
| 4-й | - | 0,25 миллиона |
| 5-й | - | 0, |
| 6-й | - | 2,25 миллиона |
| 7-й | - | 0, |
| 8-й | - | 0,5 миллиона |
Заметим, что каждой перестановке будет соответствовать некоторый способ раздачи кредитов и каждому способу раздачи будет соответствовать некоторый код, состоящий из 20 единиц и 7 нулей. Таким образом, число вариантов раздачи кредитов
Р(20, 7) = 27!/(20!7!) = 888030.
Число это достаточно велико и невозможно выписать все варианты для их последующей оценки по другим, уже экономическим критериям. Поэтому следует предварительно сократить число вариантов, используя некоторые простые критерии отбора.
1.5.5. Теория информации
Теория информации исследует математические описания и оценки качества передачи, хранения, извлечения и классификации информации. В 1948 году К. Шеннон (К. Shannon) обосновал целесообразность использования количественной меры информации, что позволило ему сформулировать фундаментальную теорему о нахождении скорости передачи информации по каналам связи, которую можно достичь при некотором оптимальном методе кодирования и декодирования, обеспечив при этом сколь угодно малую вероятность ошибки. Количественная мера информации энтропия является мерой степени неопределенности случайной величины. Пусть некоторая случайная величина
, принимает значения х1 , х2 ,..., хпраспределением вероятностей p1 , р2 ,..., рn. В этом случае энтропия случайной величины , определяется формулой 
.При передаче сообщений в каналах связи применяются различные методы кодирования информации, которые строятся с использованием комбинаторных методов.
Учет вероятностей ошибок типа 0
1 и 1 0 и энтропийная оценка позволяют сравнивать различные методы кодирования и декодирования по достоверности получаемых сообщений.1.5.6. Теория графов
Теория графов относится к области дискретной математики и занимается изучением геометрических связей между объектами. Основным объектом теории является граф, однако при решении многих задач в XX веке широко стали применяться другие термины: карта, сеть, комплекс, диаграмма, лабиринт. Теория графов тесно связана с различными разделами математики: топологией, алгеброй, теорией вероятностей, теорией чисел и, конечно, с комбинаторикой.
Приведем некоторые примеры задач теории графов, которые решаются комбинаторными методами.
1. Имеется п участников шахматного турнира. Сколько партий должно быть сыграно, чтобы каждый участник сыграл со всеми остальными? Любой турнир между п участниками (командами) может быть представлен в виде графа, при этом после окончания турнира граф является полным. Каждый участник (вершина графа) играет со всеми остальными (их число п - 1), а поскольку число участников равно п, то всего игр п(п - 1)/2.
2. Комбинаторные задачи сортировки часто изображаются в виде графов типа "дерево".
3. Не решенная аналитически задача Гамильтона об обходе всех вершин связного графа в точности по одному разу для определения числа шагов упорядоченного перебора использует комбинаторные оценки.
Глава 2. Методические разработки для элективного курса
2.1. Анализ изложения темы в школьных учебниках
При введении любой новой темы, любого нового вопроса в основной курс школы встает проблема изложения данного вопроса в школьных учебниках.
К реализации нового содержания в действующих учебниках авторы подошли по-разному. В одних учебниках элементы стохастики включены в основное содержание отдельными параграфами. Авторы же других учебников издают новое содержание в форме вкладышей – дополнительных глав к своим пособиям.
Попытка построения вероятностно-статистической линии в базовом курсе математики основной школы предпринята в учебниках
Под редакцией Г.В Дорофеева и И.Ф Шарыгина
«Математика5», «Математика6», «Математика7», «Математика8» и «Математика 9».
5 класс начинается с комбинаторики, где на конкретных задачах и примерах рассматривается решение комбинаторных задач методом перебора возможных вариантов. Этот метод иллюстрируется с помощью построение дерева возможных вариантов. Примеры и задачи очень простые, позволяющие на этапе знакомства с комбинаторными задачами, усвоить принцип простого, упорядоченного перебора возможных вариантов.