Исследовательская работа "Кодирование и комбинаторика"
творческая работа учащихся (9 класс) по теме

Муниципальное образовательное учреждение

«Средняя общеобразовательная школа № 24»

Исследовательская работа

КОДИРОВАНИЕ И КОМБИНАТОРИКА

Работу выполнили:

ученики 9 «б» класса

Каменев Илья

Ложкин Андрей

Руководители:

Матюшева В.И.

Малыш Н.Ю.

Сыктывкар, 2010

 «Не нужно нам владеть клинком,

Не ищем славы громкой.

Тот побеждает, кто знаком

С искусством мыслить тонким»

Из истории комбинаторики

Термин «комбинаторика» происходит от латинского слова combina - сочетать, соединять. Комбинаторика занимается различного рода сочетаниями (соединениями), которые можно образовать из элементов некоторого конечного множества.

Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры, в карты и кости выигрывались и проигрывались золото и бриллианты, дворцы и имения, породистые кони и дорогие украшения. Широко были распространены всевозможные лотереи. Понятно, что первоначально комбинаторные задачи касались в основном азартных игр – вопросов, сколькими способами можно выбросить данное число очков, бросая две или три кости, или несколькими способами можно получить двух королей в данной карточной игре. Эти и другие проблемы азартных игр явились движущей силой в развитии комбинаторики и развивавшейся одновременно с ней теории вероятностей.

Теоретические исследования вопросов комбинаторики предприняли в XVII веке французские ученые Паскаль и Ферма. Исходным пунктом их исследований тоже были проблемы азартных игр. Особенно большую роль сыграла здесь задача о разделе ставки, которую предложил Паскалю его друг шевалье де Мере, страстный игрок. Проблема состояла в следующем: «матч» в орлянку ведется до шести выигранных партий; он был прерван, когда один игрок выиграл 5 партий, а другой 4; как разделить ставку? Было ясно, что раздел в отношении 5 : 4 несправедлив. Применив методы комбинаторики, Паскаль решил задачу в общем случае, когда одному игроку остается до выигрыша r партий, а второму s партий. Другое решение задачи дал Ферма.

Дальнейшее развитие комбинаторики связанно с именами Якова Бернулли, Лейбница и Эйлера. У них основную роль играли приложения к различным играм (лото, солитер и др.). Комбинаторные методы проникли в другие науки, в частности, теорию чисел, алгебру, теорию вероятностей, геометрию, теорию графов. Они стали активно использоваться в психологии, медицине, космической технике и радиосвязи. Они же используются для решения транспортных задач, в частности задач по составлению расписаний; для составления планов производства и реализации продукции. Установлены связи между комбинаторикой и задачами линейного программирования, статистики и т. д. Комбинаторика используется для составления и декодирования шифров и для решения других проблем теории информации.

Шифры и анаграммы

Не только азартные игры давали пищу для комбинаторных размышлений математиков. Дипломаты, стремясь к тайне переписки, изобретали все более и более сложные шифры, а секретные службы других государств пытались это шифры разгадать. Одним из простейших шифров была «тарабарская грамота», в которой буквы заменились другими  по определенным правилам. Однако такие шифры легко разгадывались по характерным сочетаниям букв. Поэтому стали применять шифры, основанные на комбинаторных принципах, например, на  различных  перестановках  букв, заменах  букв с использованием  ключевых слов и т. д. Классический пример с шифром Цезаря: не доверяя гонцам, Юлий Цезарь шифровал свои депеши, используя способ, который впоследствии получит название шифра прямой замены. В своих письмах он заменял каждую A на D, каждую B на E, и т. д. И его послание мог дешифровать только тот, кто знал правило «смещения на 3». Известна также система шифрования под названием «квадрат Полибия», в которой каждая буква заменяется парой чисел — ее координатами в квадрате 5x5, куда предварительно в заранее заданном порядке вписаны буквы алфавита.

Для кодирования и расшифровки привлекались математики. Еще в конце XVI веке расшифровкой переписки между противниками французского короля Генриха III и испанцами занимался один из создателей современной алгебры Франсуа Виет. А в Англии XVIIв. монархистские заговорщики поражались быстроте, с которой Кромвель проникал в их замыслы. Монархисты считали шифры, которыми они пользовались при переписке не разгадываемыми, и считали, что ключи к ним были выданы кем-то из участников заговора.  И лишь после падения республики выяснилось, что все их шифры разгадывал одни из лучших английских математиков того времени, профессор Оксфордского университета Уоллис, обладавший исключительными комбинаторными способностями. Он назвал себя основателем новой науки «криптографии» (тайнописи).

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

апельсин — спаниель,

равновесие — своенравие,

полковник — клоповник,

антиквар – травинка,

просветитель — терпеливость.

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

Хитросплетения разума

В глубокой древности тайнопись считалась одним из 64-х искусств, которым следует владеть как мужчинам, так и женщинам. Сведения о способах шифрованного письма можно обнаружить уже в документах древних цивилизаций Индии, Египта, Месопотамии. Среди самых простых — иероглифическое письмо, написание знаков не по порядку, а вразброс по некоторому правилу.

Навыки в разгадке сложных шифров помогли ученым, когда археологи стали откапывать камни и черепки с таинственными знаками — письменностью, замолкшей несколько тысячелетий тому назад. При расшифровке буквенной письменности оказывается весьма важным отделение знаков, обозначающих гласные буквы, от знаков, обозначающих согласные буквы. И здесь на помощь приходит комбинаторика. Советский ученый В. В. Шеворошкин установил метод, основанный на комбинаторном сравнении частоты различных сочетании пар знаков. Хорошо известно, что в языках гласные и согласные определенным образом чередуются друг о другом. Это позволяет разделить все знаки на две группы так, что, как правило, знаки одной группы перемежаются в тексте знаками другой группы. Тогда знаки, входящие в меньшую группу, будут обозначать гласные, а входящие в большую группу,— согласные. Этот метод дал исследователю ключ к чтению карийских надписей.

Кортежи

«Опять восьмерка!» — горестно воскликнул велосипедист, взглянув на погнутое колесо своего велосипеда. «А все почему? Да потому, что мне выдали номер 888. И теперь месяца не проходит, чтобы то на одном, то на другом колесе не появилась восьмерка. Надо менять номер».

А сколько существует трехзначных номеров, не содержащих ни одной восьмерки? Для решения этой задачи определим сначала, сколько однозначных номеров не содержит восьмерку. Ясно, что таких номеров девять 0, 1, 2, 3, 4, 5, 6, 7, 9 (номер 8 пропускается). А теперь найдем все двузначные номера, не содержащие восьмерок. Их можно составить так: взять любой из найденных однозначных номеров и написать после него любую из девяти допустимых цифр. В результате из каждого однозначного номера получится девять двузначных. А так как однозначных  номеров тоже 9, то получится 92 = 81 двузначный номер без восьмерок. Но за каждым из них снова можно поставить любую из девяти допустимых цифр. В результате получим 93 = 729 трехзначных номеров не содержит цифру 8. Суеверный велосипедист мог отказаться и от цифры 0, т.к. она похожа на вытянутое колесо. В этом случае останется 83 = 512 трехзначных номеров.

Любой номер, составленный из трех цифр, нельзя рассматривать как множество из трех элементов, так как:

1) в номерах цифры могут повторяться (например, 775), а во множествах элементы не повторяются;

2) в номерах важен порядок цифр (175 и 571 - совсем разные номера), а во множествах порядок элементов роли не играет.

Поэтому при изучении таких объектов, как номера или слова (в них буквы могут повторяться, а от перестановки букв слово меняется), используется математическое понятие «кортеж». Пусть имеется несколько множеств Х1, ..., Хk. Представим себе, что их элементы сложены в мешки, а мешки пронумерованы. Вытащим из первого мешка какой-нибудь элемент (то есть возьмем какой-нибудь элемент а1 множества Х1), затем вытащим элемент а2 из мешка Х2 и будем продолжать этот процесс до тех пор, пока из мешка Хk не будет вытащен элемент аk. После этого расставим полученные элементы в том порядке, в каком они появились из мешков (а1, а2, ..., аk). Это и будет кортеж длины k, составленный из элементов множеств Х1, ..., Хk. Элементы кортежа могут повторяться.

Примером кортежа длины 6 являются номера телефонов в г.Сыктывкаре, они составлены из элементов множества X = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Слова русского языка (точнее, их запись) — кортежи различной длины, составленные из букв русского алфавита, а предложения — кортежи, составленные из русских слов.

Множества Х1, ..., Хk, из элементов которых составляются кортежи, могут иметь общие элементы. В частности, все они могут совпадать с одним и тем же множеством X, состоящим из n элементов. Кортежи длины k, составленные из элементов n-множества X, называют размещениями с повторениями из n элементов по k, а их число обозначают = nk.

В задаче о велосипедистах n = 9, а в каждое размещение входило по 3 элемента. Число размещений с повторениями равно= 93 = 729 .

Азбука Морзе

Для передачи сообщений по телеграфу используют различные коды, позволяющие представлять буквы, цифры и знаки препинания в виде кортежей из точек и тире. Первый такой код был предложен в 1838 г. американским изобретателем Сэмюэлем Морзе (1791-1872). За единицу времени принимается длительность одной точки. Длительность тире равна трём точкам. Пауза между элементами одного знака — одна точка, между знаками в слове — 3 точки, между словами — 7 точек. Принцип кодирования азбуки Морзе исходит из того, что буквы, которые чаще употребляются в языке, кодируются более простыми сочетаниями точек и тире. Это делает освоение азбуки Морзе проще, а передачи — компактнее. Для передачи русских букв использовались коды сходных латинских букв.

При этом для одних букв используется один знак, например Е — , а для некоторых приходится использовать пять знаков, например Э —  • — • •. Откуда же взялось число 5? Нельзя ли обойтись меньшим числом знаков, скажем, передавать все сообщения с помощью комбинаций, содержащих не более четырех знаков? Оказывается, что нельзя, и ответ этот дает формула для числа размещений с повторениями = nk.

Из формулы следует, что из точки и тире можно построить два кортежа длины 1. Иными словами, только две буквы можно передать с помощью одного знака (Е • и Г —), С помощью двух знаков можно передать  = 22 = 4 буквы, трех знаков — = 23 = 8 букв  и четырех знаков —  = 24 = 16. Поэтому общее число букв, которые можно передать кортежами точек и тире длиной от 1 до 4, равно 2 + 4 + 8 + 16 = 30.

А в русском алфавите 32 буквы, да еще надо передавать цифры и знаки препинания. Ясно, что символов из четырех знаков не хватает. А если брать и символы из 5 знаков, то к полученным 30 прибавится еще 25=32 символа. Полученных 62 символов вполне достаточно для телеграфирования.

В 2004г. Международный союз электросвязи ввёл в азбуку Морзе новый код для символа @, для удобства передачи адресов электронной почты.

На практике вместо заучивания количества точек и тире и их последовательности запоминают так называемый «напев» (мнемоническую словесную форму), соответствующий каждому знаку кода Морзе. При этом слоги, в состав которых входят гласные а, о, ы, соответствуют тире, а все остальные слоги и слог ай — точке.

Часто для ускорения радиообмена используются аббревиатуры и специальные «Q-коды».

! — выражение недовольства работой корреспондента;

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

73 — наилучшие пожелания;

55 — дружеское «рукопожатие»;

88 — любовь и поцелуй (обычно адресуется женщинам-радистам, в противном случае отвечается фразой «в усы»);

99 — не желаю с Вами работать.

Русская семафорная азбука

Существующую сегодня на флоте русскую семафорную азбуку разработал в 1895 году вице-адмирал Степан Осипович Макаров. Русская семафорная азбука составлена в соответствии с русским алфавитом, включает 29 буквенных и 3 служебных знака. Она не содержит цифр и знаков препинания. Их передача производится по буквам, словами. Например, цифра «7» будет передана словом «семь», а знак «,» — словом «запятая». Каждой букве и условному знаку соответствует определенное положением рук с флажками. Семафорное сообщение состоит из слов, составленных из букв, изображаемых соответствующим положением флажков. Как правило, флажки находятся по разные стороны от тела сигнальщика. Однако при передаче некоторых букв (б, д, к, х, ю, я) оба флажка расположены по одну и ту же сторону. Почему пришлось сделать такое исключение? Ответ на этот вопрос дает та же формула размещений с повторениями. Дело в том, что различных положений каждого флажка пять — вниз отвесно, вниз наклонно, горизонтально, вверх наклонно и вверх отвесно. Так как у нас два флажка, то общее число комбинаций основных положений равно  = 52 = 25. При этом еще надо отбросить положение, когда оба флажка направлены вниз — оно служит для разделения слов. Всего получаем 24 комбинации, а этого недостаточно для передачи всех букв русского алфавита. Поэтому для некоторых букв и пришлось направить оба флажка в одну сторону.

Секретные замки

Для запирания сейфов применяют секретные замки, которые открываются лишь тогда, когда набрано «тайное слово» (или набор цифр). Это слово набирают с помощью одного или нескольких дисков, на которых изображены буквы (или цифры). Пусть число букв на каждом диске равно 12, а число дисков равно 5. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова. Из условия задачи видно, что важен порядок выбираемых букв. Поэтому мы имеем здесь дело с кортежами. Так как по условию каждая буква может быть выбрана 12 способами, а длина кортежей равна 5, то комбинаций равно 125 = 248 832. Значит, неудачных попыток может быть 248 831.

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

Для решения задачи используем правило произведения: Если элемент а1 можно выбрать n1 способами, после каждого выбора этого элемента следующий за ним элемент а2 можно выбрать n2 способами ... после выбора элементов а1, ..., аk-1, элемент аk выбирается nk способами, то кортеж (а1, а2, ..., аk) можно выбрать n1 ∙ n2 ∙... ∙ nk способами.

 = 103 = 1000;  = 261 = 26

1000 · 26 = 26000 комбинаций

26000 · 10 = 260000 секунд ≈ 72 часа = 3 суток может потребоваться посетителю для поиска нужной комбинации.

Заключение

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

Литература

1. Виленкин Н. Я. Популярная комбинаторика.- «Наука», 1975.
2. Виленкин Н. Я.Комбинаторика.- «Наука», 1969.
3. Перельман Я. И. Занимательна алгебра.- М.:АО «СТОЛЕТИЕ», 1994.
4. Глейзер Г. И. История математики в средней школе. Пособие для учителей. М., «Просвещение», 1970.
5. Макарычев Ю.Н., Миндюк Н.Г. Элементы статистики и теории вероятностей. Пособие для учащихся 7—9 классов. - М.: Просвещение, 2003.
6. Интернет