Text
                    ВЫХОДИТ РАЗ В ДВЕ НЕДЕЛИ
Рекомендуемая розничная цена: 279 руб.
Розничная цена: 49,90 грн, 990 тенге
занимательные
ГОЛОВОЛОМКИ

------------------------—. «ЗАНИМАТЕЛЬНЫЕ ГОЛОВОЛОМКИ» Издание выходит раз в две недели Выпуск №28,2013 РОССИЯ занимательные ГОЛОВОЛОМКИ КОЛЛЕКЦИЯ ЛОГИЧЕСКИХ ИГР ОТ EKAGOCTINI В этом выпуске: ИЗДАТЕЛЬ. УЧРЕДИТЕЛЬ, РЕДАКЦИЯ: ООО «Де Агостини», Россия ЮРИДИЧЕСКИЙ АДРЕС 105 066, г Москад, ул. Александра Лукьянова, д.Згстр.1 Письма читателей по данному адресу не принимаются. ГЕНЕРАЛЬНЫЙ ДИРЕКТОР' Николасе Скилакис ГЛАВНЫЙ РЕДАКТОР: Анастасия Жаркова ФИНАНСОВЫЙ ДИРЕКТОР: Наталия Василенко КОММЕРЧЕСКИЙ ДИРЕКТОР Александр Якутов МЕНЕДЖЕР ПО МАРКЕТИНГУ: Михаил Ткачук МЛАДШИЙ МЕНЕДЖЕР ПО ПРОДУКТУ; Любовь Мартынова Свидетельство о регистрации средства массовой информации в Федеральной службе по надзору я сфере связи, информационных технологий и массовых коммуникаций <Роскомнвд50р) ПИ № ФС77-433 Ю от 28.122010 г Для злказа пропущенных номеров и по всем вопросам, касающимся информации о коллекции, заходите на сайт www.deagostini.ru По остальным во просим обращайтесь по телефону бесплатной горячей линии» к России: С 8-800-200-02-01 Тепефои горячайлинии» для читателей Москы, С 8 -595 660-02 02 АДРЕС ДЛЯ ПИСЕМ ЧИТАТЕЛЕЙ: Россия, 170 ЮТ, г, Тверь, почтамт, а/я 245, Де Агостини , «Занимательные головоломки* РАСПРОСТРАНЕНИЕ: COG Бурда Дистрибьюшен Сернисиг УКРАИНА ИЗДАТЕЛЬ И УЧРЕДИТЕЛЬ» ООО *Де Агостини Паблишиигч Украина ЮРИДИЧЕСКИИ АДРЕС. 01032, Украина, г Киев, у п. Сакса ганского, д 119 ГЕНЕРАЛЬНЫЙ ДИРЕКТОР: Екатерина Клименко Свидетельство о государственной регистрации печатного СМИ Министерства юстиции Украины КВ №17502 6252Рот0103 2011 АДРЕС ДЛЯ ПИСЕМ ЧИТАТЕЛЕЙ Украина, 01033, г. Киев, a/я -<Де Агостини и. Занимательные головоломки Укражд, D1G33, м. Ки«в, а/с Де Агосннк Для заказа пропущенных номеров и по всем вопросам, касающимся Информации о коллекции, заходите на сайт www.deagostin Lua По остальным вопросам обращайтесь по телефону бесплатной «горячей линии- в Украине: f 0-800-500-8-40 БЕЛАРУСЬ ИМПОРТЕР И ДИСТРИБЬЮТОР В Р6; ООО «Росчерк», 220037, г Минск, ул. Авангардная, д. 40а, литер 8/к, тел./фмс +375 17 2-999-260. Телефон горячей линии» в Беларуси; f +37517279-87-87 шн ш.9.00-2100j АДРЕС ДЛЯ ПИСЕА' ЧИТАТЕЛЕЙ: Республика Беларусь, 220040. г. Минск, а/я 224, ООО «Росчерки. чДе Агостини-, ^Занимательные головоломки» КАЗАХСТАН РАСПРОСТРАНЕНИЕ-ТОО яКГЛ Бурда-Ал атау-Лрессс РЕКОМЕНДУЕМАЯ РОЗНИЧНАЯ ЦЕНА 279 руб. РОЗНИЧНАЯ ЦЕНА: 49,90 грн, 990 тенге ОТПЕЧАТ АНО В ТИПОГРАФИИ: G. Canale & С S.p.A Sos. Сегпю 47, Висиге5Щ Panldimon -1 Nov, Romania. ТИРАЖ. 68 000 экэ. Издатель оставляет за собой право изменять последовательность номеров и их содержание И ада гель оставляет за собой право увеличить рекомендуемую цену выпусков. Неотъемлемой частью каждого выпуска является приложение. •’/ОСС «,Де Агостини», 2013 RBA Cotecaonables. 2011 ISSN 2225 1782 ДАТА ВЫХОДА В РОССИИ: 26.02.2013 Математическая вселенная Мощный математический инструмент Понятие алгоритма как набора инструкций в ти данной последовательности восходит к вре- менам Древней Греции, в частности, к алгоритму Евклида В настоя- щее время в теории алгоритмов проводятся интенсивные исследова- ния. За обра’сц часто берутся процессы, происходящие в природе, живыч органи )мы также выполняют определенную программу, запи- санную в их генетическим коле. Блистательные умы fi iuj.uu лрлискин члтеилтчк По мнению многих, дль-Хорезми был величайшим математиком своего времени. Именно от названий его книг произошли слова «алгебра» п «алгоритм». Благодаря ему западной цивилизации стала известна система счисления, которую мы используем сейчас. Аль-Хорезми систематизировал знания о математи- ке, разработанные греками и индийцами, и составил астрономические таблицы значений синуса и котангенса. Также он внес важный вклад в историю и п рграфию. Математика на каждый день Эпоха коммуникаций Коммуникации составляют основу современ- ных технологий и культуры в целом. J 1х функционирование зависит не только от чисто технологических аспектов, но и от теоретического аппарата математическое теории информации. Эту теорию разрабо- тал амергкаш кий инженер и математик Клод Шеннон во время ра- боты в исследовательском центре Bell I abf. Он же определил и еди- ницу измерения информации. Математические задачи* Задачи на разрезание Сегодня величайший английский головолом- шик Генри Э. Дьюдени предлагает нам взяться за нож п разрезать рождественский пирог, да гак, чтобы нс пострадала ин одна; крншаю- щая его черносливина. После решения подобных задач вы будете го- товы разрезать такие нс созданные для .ттого вещи, как подковы, и да- же великую монаду. Головоломки Бо сьшой взрыв Эта головоломка полечила свое название благода- ря тому, что при разборке она «расширяется» подобно Вселенной после Большого взрыва. Ее форма — шестиконечная звезда, также известная как гексаграмма, и.ш звечда Давида — представляет со- бой единство противоположностей, яв хяется символом гармонии н совершенства.
Слово «АЛГОРИТМ» ПЕРВОНАЧАЛЬНО ОЗНАЧАЛО ИСПОЛЬЗОВАНИЕ ИНДИЙСКИХ ЦИФР 0, 1,2, 3, 4, 5, б, 7, 8 И 9. СЕГОД11Я алгоритм — это математическое понятие, которое ИСПОЛЬЗУЕТСЯ и В ВЫСОКИХ ТЕХНОЛОГИЯХ, И В ПОВСЕДНЕВНОЙ ЖИЗНИ. Алгорит мы Мощный математический инструмент Понятие алгоритма как множества однознач- на определенных; инструкций в заданной последовательности восходит к временам Древней Греции, в частности, к алгоритму Евкли- да. С созданием первых компьютеров пояни\ось ноняше ал! аритмической машины, способной самое гоя I ильмо выполнять все этапы алгоритма, предназначенного для решения какой-то задачи. В настоящее время в теории алгоритмов прово- дятся интенсивные исследования. За образец ча- сто берутся процессы, происходящие в природе, так как живые организмы также выполняют опре- деленную программу, записанную в их генетиче- ском коде. Инструкции и рецепты Чтобы постирать блузки, рубашки, халаты п другую одежду, лежащую в Оельевой корзине, нсоЬходимо: 1. Помести гь одежду в барабан с тральной ма- шины и закрыть ее. 2. Загрузить порошок в выдвижной ящик. 3, Повернуть колесо выбора режимов темпера- туры до отметки 40 "С, 4. Переместить переключатель выбора про- грамм в положение 3 (предварительная стирка — стирка — четыре споласкивания). 5. Когда стира зьная машина завершит работу и погаснет световой индикатор, извлечь чистую одежду из стиральной машины. Это аморитм. Рецепт приготовления блюда, в котором после- довательно перечислены все важные этапы, также может служить примерим але ори i ма. Алгори гмом Л ► Пос trcitMtitm&twiocitif} действий. необхода,ыых дя.Ч CO.uhlHU ¥ *W0U deKcJpiI- тивной свечи. донусклст выбор си стопных- члетей в {^Ответствии Г rt.JUIU U эстетически и вкусом. Гек клкэшо в шлчите 1ьной сте- пени влияет нл итоговый реэу.сьтлт и вносит неодно- значность. то этот процесс не и, кч на цялть ллгорижмом. интересе к алгоритмам у большинства людей обз.- ясняет, почему большая часть возможностей бы- тоной техники обычно не используется. ' 1нже- V /о Кйд.грч алгоритм гл<, првдетлл г и w гобой по- еледоытыьноеть Айгадяий, Mt.-, например, в иш трупный к <нырлаыюб ш- по ч говить бытивую пихни ку очень ирт »ю. также является ине tpvi ция к видеомагнитофону, В которой перечислены действия, необходимые, например, для записи интересной про i оаммы, Котору к» вы не з сисваезс посмотрс гь. Отсу тетвпе неры, техники и программисты ломают голову над выбором режимов для стиральной машины, ио большинство людей использует лишь два и i них — стирку в горячей или в холодной воде. До- ля людей, которые знают, как записать телепере- дача, тоже удивительно мала. Несмотря на это, без алгоритмов наша повседневная л изнь преврати- лась бы в сущий ад.
235 + 726 ”96? Алгоритмы В чем разница между алгоритмом и множеством инструкции по выполнению определенной зада чи* 11о сути. ни в чем Когда для сложения двух чисел, например 235 и -2б, вы ыиисывастс их в столбик и деист весте так, как вас л чили в школе, на самом де- ле вы следуете алгоритму сло- жения 11нымы словами, вы вы- полняете ряд определенных действий, и вам не нужно ду- мать, прави льны ли они с гео рстичсскппточки зрения. Применение алгоритма Нс требует каких-либо рассуждений, здесь нужна тишь определенная сноровка, так как все необхо- димые рассуждения еже были выполнены при со- ставлении алгоритма. 11так, алгоритм — это конечная последова- тельность одно тачных инструкций, позволяю- щая решить определенную задачу в общем ви- де. Формулировка «в общем виде» гарантирует, что алгоритм сложения чисел будет корректным вне ывнсимости оттого, какие именно числа мы складываем. Мы не приводим примеры алгоритмов деле- нии чисел или извлечения квадратного корня, так как ИХ почти никто не помнит. Большинство людей забывают эти алгоритмы, так как существу- ют удивительные устройства — калькуляторы, ко торые решают эти задачи точнее и быстрее. Цель р (работки алгоритмов — мзбежягь выполнения рутинных действий, с которыми может прекрас- но справиться машина. Подобно тому каклвтомо- ► . / iCOgU w и у инолсения Г ПО- мощью таблиц, описанный в итальянском источнике 1478лйг. Ucfifopetotljf tu MunichebeГоповТм n oft re rioInpLicare per <cjcSrro:h qtuli lafljro л! РнЛ» с («оно rrrndo i exempt f« (Ыапипге in foimg* tvmr pojai ptdttt qi и fotro 0t rQ(jb w farefopiedrrofcacMrro. foc.3 14. fie .9 44-eiwtart iiloperUquarrcmodico'.ir фН ы fotco. ▼ Jill thCUKUl, ивтцел тнк Иоанн Сакробоекл (119> — ок. 12S6) в XIII веке напили книгу De algerifHCo, в пос еедующеек иеданигл по.учившую на- квание De .ilgf»ecmu> rulgaiia n IraetatusdearieHumerandi. На рисунке u отражена ииниатюра .'ы ятей книги. Iруд ( ‘.ikpOVOe ко OK.tJ.U огре иное влияние на рас- пршмранение индо арабских цифр на. Цнлде. В пен еедую- щие сто и тия pa Угоре. ни ь нейрине торы между «аба кис та чи •» (у нюронника чк «< пи сьгования абака} и - а е горит мостами выступав - шипи м использование Си- ер. 41 •иных арифметических алеяеритмов. В итоге послед- ние одерма <ирешите и ную победу. Церковь, которая ытротивля еась прогрессу, объявила аалгоришмистов ко едунами и еретика ия биль избавляет нас or необходимости проходить большие расстояния пешком, машины освобож- дают нас от необходимости выполнять трудоем- кие вычисления вручную. Но у всего есть обрат- ная сторона. Некоторые считают, что В буд) ЩёМ нам придется заниматься «интеллектуальной гимнастикой» и выполнять упражнения на сло- жение и умножение, нодооно тому как сейчас НАМ приходится выполнять физические упражнения. чтоОы поддерживать мышцы в форме. Алгоритм Евклида Хотя термин «алгоритм» связан с именем <на- меиитого математика аль-Хорсчми, первые алго- ритмы как минимум на тысячу лет старше. Один из первых алгоритмов — известный алгоритм Евклида (ок. 365 — 300 г. до н э.), предназначен- ный для вычисления наибольшего общего дели- теля (НОД1 двух чисел. Пусть даны два любых числа, например ч2 и 18. и нужно найти наиболь- шее число, на которое будут делиться оба этих числа. В нашем случае это число 6. Это можно за- писать так: 1 ЮД Гч8, 12) = 6. Алгоритм Евклида позволяет найти НОД двух чисел А и В следую- щим образом: I. Разделить А на В. Записать остаток от деле- ния R. 2. Выполнить деление снова, заменив А на В и В На R. 3. Повторять шя1 1, пока остаток от деления нс станет равен нулю.
Мощный математический инструмент Последний остаток or деления, отличный or нуля, и будет искомым НОД. Например, для вы- числения наибольшего общего делителя чисел ч389 и 3420 алгоритм будет выглядеть так: Делимое Делите" Остаток 4389 3420 969 3420 969 513 969 513 456 513 456 57 456 57 0 Получим НОД (4389,3*120) — 57. ▲ Страниц, j книги <*Кипмб ДЛ -Awaop Л1 - f-Ag. ПдрддаКГЛЛЬМО' но нераля о мире книга гю алгебре иг i ни тЗнпги мт^ M.tnntwni)iti fMMfftn i.i ну mfxt ки/иирыг испиамуютсл cestui* ич a oe i которых иеиыелпма ссюремеюедл алгебра. Существует ли способ определения эффектив- ности этого алгоритма? То сеть можно ли узнать число его шагов или, что равносильно, число ря- дов н предыдущей таблице до начала вычислений? Можно доказан,, что максимальное число шагов этого алгоритма будет примерно в пять раз боль- 1 2 3 4 б 7 В 9 10 I ИСХОДНОЕ ЧИСЛО ___C U J _4 _5 6_J J J 00 123456789 1 9 0 1 2 3 4 5 6 7 В о 2 8 901234567 §37890123456 §46789012345 S 5 5 6 7 8 9 0 1 2 3 4 § 6 4 5 6 7 8 9 0 1 23 37'3456789012 “82345678901 91 234567890 2 - 3 * Zo Z? - 1 4 3 8 1 6 0 9 РАЗНОСТЬ 41 - / лгоритм яычитани ч двух чисел г достаточно под- робен, поэтому при его мг- нольлованни не требуются дополнительные рассужде- ния. 1йкЖе не требуется понимать лначенне каягдосо шага алгоритма. ше количества цифр в наибольшем из двух исход- ных чисел. В предыдущем примере большее из чисел. 4389, имеет 4 цифры ( ледоват^льно, максималь- ным числом шагов алгоритма будет 20, но нам оказалось достаточно пяти. В школах изучают другой способ вычисления наибольшего общего делителя, основанный на разложении обоих чисел на простые множители. Для нахождения НОД необходимо разложить оба числа на простые множители, затем выбрать общие множители с наименьшим показателем степени. Например, разл< >жение чисел ч2 и 48 на простые множители вьп сидит так: 42 = 2-3-7, 48 = 21 3- Общими множителями являются 2 и 3, наи- меньший показатель степени, который имеют эти множители в обоих разложениях, равен едмни- це. Поэтому НОД (42.48) = 2-3 = 6. Этот метод удобнее для расчета наибольшего общего делителя нескольких чисел, но имеет серьезный недостаток; разложение большого числа на простые множите- ли может оказаться очень трудоемкой, а я неко- торых случаях и невыполнимой операцией. Воз- никает вопрос об эффективности определенных алгоритмов, что особенно важно, если эти алго- ритмы необходимо выполнить на компьютере Алгоритмические машины Между алгоритмом стирки в стиральной маши- не н алгоритмом полета космической ракеты су- ществует два принципиальных отличия: эти алго- ритмы имеют разную сложность и выполняются на разных устройствах. Эти отличия тесно связа- ны между собой. Алгоритм может быть очень эф- ф< ктмвным при выполнении на компьютере, но его будет невозможно выполнить с помощью ка- рандаша п бумаги Яркин пример, показываю- щий. сколь тесно связаны алгоритм и устрой- ство, на котором он выполняется, — неудачная попытка английского математика Чарльза Бэб- биджа (1791 —1871) создать первую вычисли- тельную машину. Бэббидж)'удалось разработать нужный алгоритм, но он нс располагал техноло- гиями, чтобы сконструировать придуманную им машину. Устройства, способные выполнить алго- ритм, называются алгоритмическими машинами, В ряд)' всех вычислительных машин особняком стоя г компьютеры. В информатике алгоритмы записываются в виде программ на языке, понят- ном компьютеру (по сути, на единственном по- нятном ему языке). Не стоит забывать о тесной связи между алгоритмами и алгоритмическими машинами. Оптимизация алгоритмов позволяет добиться впечатляющих результатов, но компью- теры далеко нс всемогущи. Алгоритмы
A К.грпшнл Blessed Stott (I 988) — ALWrVrfWf ДОМЫЙ при vep weopwt пш Kt/м Масгргйлъ я группу j-teopttrnvitcmoe, fM.HD&lHHy№ S . /оГ-ЯкЛж£ДГГГ в / 995 году. Bte рМюшы •t.fttovB зтоп группы созд.шы C НвПЫЦЬЮ ОСобыХ ХиМПЫО- тсрных л лгорит нов. PmNP Для некоторых задач класса NP были найдены алгоритмы решения, ко- торые выполняются за полиномиальное время (задачи такого типа на- зываются NP-полными). К таким задачам относится задача коммивоях ера, также называемая задачей поиска гамильтонова пути (англ. TSP-. Travelling Salesman Problem]. Залтча формулируется так: даны N городов, которые должен объехать продавец; нужно найти кратчайший путь, проходящий через все города ровно по одному разу с после дующим возвратом в исход- ный город. С ростом числа городов число возможных маршрутов возрас- тает очень быстро. Число городов Число маршрутов 10 181440 20 60822550204416000 50 Около З Ю62 Эффективность алгоритма Существует взаимосвязь между объемом данных, введенных в компьютер, и временем, необходи- мым компьютеру для выполнения определенно- го алгоритма на основе этих данных. Мижни ска- ыть, что время выполнения алгоритма и число действии, выполняемых 1 омпьюгером, пропор- циональны объему исходных данных. Соотно- шение между этими параметрами и определяет эффективность алгоритма. Говорят, чю алгоритм выполняется sa полиномпллыюс время, если для исходных данных объемом р время раоогы ал- горитма будет зависеть от г в заданной степени. Например, существуют алгоритмы, для которых при объеме исходных данных р время работы равно с2. Это означает, ч.о выполнение алгорит- ма для 10 чисел займе! 10* = 100 единиц времени, для 20 чисел — 20* = 400 единиц и т. д. В друтих случаях время работы может равняться ₽* или в* 1’, нп алгоритм всегда будет выполняться га полино- миальное время. Если же время работы алгоритма описывается формулой 2' и боаее, то говорят, что алгоритм выполняет m экспоненциальное время. В этом случае с ростом объема исходных данных время работы алгоритма возрастает очень быстро. Задачами класса Р называют задачи, д хч ко- торых су щсству ст алгоритм решения, выполняе- мый за полиномиальное время. Для сравнитель- но небольших исходных значений такие задачи могут быть решены на компьютере. Также суще- ствует класс задач NP, алгоритм решения кото- рых выполняется за недетерминированное поли- номиальное время. Описать природу таких <>адач достаточно сложно. Очевидно, что любая задача класса Р также является задачей класса NP, но до- казать обратное (равенство Р = NP' пока нс уда- лось. Чтобы опровергнуть это равенство, нужно найти задачу класса NP. иерешаемхю за полино- миальное время. Рассмотрим пример. Для 50 горидпв число маршрутов будет записываться единицей с 62 ну- лями. В общем виде число маршрутов для N городов определяется по формуле N!/2N, где М = N • W -1) (N - 2) • (W - 3) •... • 3 • 2 • 1. Это класси- ческая задача оптимизации, так как необходимо наити путь, в котором пройденное расстояние будет наименьшим. Рассмотрим пример с пятью городами. Расстояние в километрах между ними приведено в таблице, схема расположения городов показана на рисунке слева: А В С D Е А О 25 35 75 35 В 25 0 55 80 55 С 35 55 0 55 50 D 75 80 55 0 55 Е 35 55 50 55 0 С В© О D АО О О Е Всего существует 12 возможных маршрутов. Три из них приведены на рисунке справа. Маршрут 1 яв- ляется кратчайшим. Задачу комми- вояжера можно решить с помощью алгоритмов на так называемых нейронных сетях.
Мощный математический инструмент Возьмем число, которое является произведе- нием двух простых чисел, например 77 = 7 • 11. Попросим кого-нибудь разложить число 77 на простые множители. После нескольких попыток ему удастся найти решение. Если нам потребует- ся разложить на простые множи гели число 221, то, запасись терпением и вооружившись кальку- лятором, через некоторое время мы получим от- вет: 221 = 13 • 17. Но для числа 41946943 (оно равно 5 297 7919) задача неимоверно усложня- ется. Если дать эту задачу программисту, то он по- пытается решить ее с помощью программы, по- зволяющей разло» ить на два простых множителя любое число. В конце концов, именно для это- го предназначены алгоритмы и программы. Ес- ли нашему программисту удастся создать такой алгоритм, то он мгновенно сможет взломать си- стемы шифрования данных всех банков и даже са- мые защищенные компьютерные системы всех ар- мий мира. Алгоритм шифрования RSA, который сегодня является одним из самых распростра- ненных, основан на невозможности разложения очень больших чисел на произведение двух про- стых сомножителей. Пока еще никому не удалось найти алгоритм решения этой задачи, но это во- все нс означает, что такого алгоритма не существу- ет. В этом заключается основная сложность дока- зательства равенства Р = NP: чтоОы доказать, что задача ьсрешаема за полиномиальное время, нуж- но провсри гь все возможные алгоритмы, включая еще нс извес гныс. Автор доказательства гипотезы Р = NP по- лучит нс только признание научного сообще ства, но и премию в миллион долларов, учреж- денную Институтом Клэя. Чтобы претендовать на эту премию, необязательно быть профессио- нальным математиком. Необязательно быть ма- тематиком вообще, не имеет значения и возраст, главное, чтобы доказательство прошло тщатель- ную проверку международного математического сообщества. Алгоритмы и биология Задачи реального мира подразумевают опреде- ленную неточность и неопределенность. Для их решения неприменимы классические алгорит- мы, жестки определенные в силу своей природы. В 80-е годы XX века в информатике сформирова- лось новое направление: в нем пи-новому рассма- триваются задачи, которые нельзя решить с помо- щью традиционных алгоритмов. В р, иках этою подхода имитируется поведение биологических систем, так как большинство процессов, проис- ходящих в природе, можно рассматривать как ре- зультат работы некоего алгоритма. Так появились новые методы моделирования, на основе ко горыу были созданы клеточные автоматы, нейронные сети и генетические алгоритмы Клеточные автоматы Клеточный автомат работает на множестве ячеек. В нашем примере они имеют форму квадратов. Чтобы продемонстрировать принцип его работы, оассмо.-рим сетку ячеек. Правила работы клеточного автомат а очень про- сты: ячейки автоматически переходят из одного состояния в другое соглас- но следующим правилам. □□□ □ 0 0 0 1 1 1 1 0 Каждая ячейка- черная или белая, генерирует черную или белую ячейку на следующей строке сетки в зависимости от цвета ячеек, расположенных слева и справа. Существует восемь воз- можных случаев. Цвет ячейки, располо- женной ниже, определяется согласно правилам, представленным на рисунке сверху, Эволюцию клеточного автомата увидеть нетрудно: так, на рисунке справа — состояние кле- точного автомата после 20 шагов Клеточные автоматы, подобные изображенному выше, называются би- нарными, так как их я чейки могут принимать лишь одно из двух возмож них значений (в нашем примере — один из двух цветов). Такие автоматы очень примитивны, так как их ячейки являются плоскими (в данном случае квадратными), и возможно всего восемь начальных состояний. Однако существуют и не бинарные клеточные автоматы, ячейки которых могут на- ходиться в одном из множества состояний (обычно они обозначаются раз- ными цветами). Кле1 энные автоматы необязательно являются плоскими: к примеру, их начальное состояние может быть задано на трехмерной ре- шетке Оки могут выглядеть так, как представлено на иглюстоации ниже. Алгоритмы
У муравья в муравейнике отсутствует простор для импровизации. [ 1рограмма жизни муравей- ника основана на поведении всех ею обитателей, в частности на их способности действовать сооб- ща. Для каждой касты муравьев определен '-.ре- гламент» действий, в котором четко описыва- ется, какие действия нужно вшх унять в тс или иные моменты. В природе существует множе- ство подобных: сообществ (взять хотя бы труп- f ft ripnffHMf ftvm a tn ион- ной ирнигнчютея яpHww.iv ШЦУ'Л/ННЮ HUyKWWHIKW Jiftr/ltA tCK№M It HyjMW fh.4 pJCHOJHJft.tHH-4 QVfhl iOH. •IШ4ИЖГ IfFHO.tмул/wr.y №< /ipon^oi\ mac th чрписнал ^tthv aiu*нфнк.щии, w тими^щнн it KaumpGAji. TfOpt t IfX WAUtfMfb№ wcmww ivt&tmb очень i.w- Mitf МДОНМНЛМ'Ы. /ыпримгр чг юлекопо&ншых роботов aptxJc тех, что и юьражены л fptt.tr> w ( matft'H.i С)Щ нкр- лг « / /гкк* стленн/ т рл*у. и ** ли И41КРК41О । Алгоритмы, основанные на нейронных сетях, с определенным успехом применяются для прогнозирования на финансовых рынках и предсказания биржевых индексов, курсов ак- ций, ценных бумаг с фиксированным доходом, облигаций, фьючерсов, а также используются при управлении рисками на предприя.иях. । Генерация списков случайных чисел на компьютере требует использования сложных ал- горитмов и является неотъемлемым элементом множества задач, например задач формиро- вания ключей шифрования. Любопытно, что венгерский математик Пол Эрдёш (1913—1996), который считался гуру алгоритмов этого типа, ни разу в жизни не пользовался компьютером. Алгоритм вычисления квадратного корня Для извлечения квадратного корня без помо- щи калькулятора можно использовать алго- ритм, подобный приведенному ниже. V 5,54,61 235 -4 154 -129 2561 -2325 23600 4705 X 5 = 23525 Но это не единственный возмож- ный алгоритм. Гениальный Исаак Ньютон придумал алгоритм, этапы которого выполняются последова- тельно, причем результат, получае- мый на каждом шаге этого алгорит- ма, точнее, чем на предыдущем. Допустим, мы хотим вычислить v'N. Сначала найдем в уме прибли- женное значение х, такое, что Л]2 = N. В действительности х, может быть любым, но если х, будет близко к VKl, это позволит уменьшить количество расчетов. Последова- тельно вычисляя х2 = 1/2{х, + N/xJ, х3 = 1/2(хг + М/хг), x„ = 1/2 (x„-i + N/x„ ,)„ мы получим значения хь х2, xlt..., х„, которые будут все ближе и ближе к истинному значе- нию TFT пы клеток жилых организмов). По их образцу был создан особый гип алгоритмов — лак назы- ваемые клеточные автоматы, содержащие стати- ческую структуру данных и конечное множество правил, применяемых к каждой ячейке или эле менту этой структуры. 11нтсрес к подобным ал- горитмам вы зван их просгогой. легкостью созда- ния моделей и быстротой выполнения. Этими же особенностями отличаются и алгоритмы гак на- зываемых нейронных сетей, имитирующих пове- дение нейронов нервной системы. Нервная си- стема живых существ отвечает за централизацию различны л биологических функций, упр 1ВАЯС Г действиями н непредвиденных ситуациях и энер- гообеспечением организма (обменом веществ). Теоретически нейронную сеть можно рассма- тривать как некую фу нкцию, которая определен- ным образом преобразует входной сигнал сети в выходной сигнал. Алгоритмы такого типа при- меняются в работах по созданию нс.кусственно- го интеллекта 1IH I п служат для распознавания обра юв, а также мёпользуюгся н t произволе! вс для решения задач классификации, оптимиза- ции и контроля. Генетические алгоритмы, нанро- гив, основаны на различных адаптационных меха- низмах толюции живых существ к используются главным образом в решении задач оптимизации. Принцип их района таков: создастся начальная популяция, ко гора» пред положительно является решением поставленной задачи, затем на компью- тере икни прус гея эволюция лой популяции. Все последующие поколения начальной популяции оцениваются с помощью так называемой функ- ции приспособленное гн. В ходе работы алгорит- ма некоторые поколения «пошбают», другие «выживают», и в итоге наиболее приспособлен иыс «особи» формируют оптимальное решение.
Аль-Хорезми, арабский математик первой половины IX века, по мнению многих, был величайшим мате- матиком своего времени. От названий его книг произошли слова «алгебра» и «алгоритм». Благодаря ЕМУ ЗАПАДНОЙ ЦИВИЛИЗАЦИИ СТАЛА ИЗВЕСТНА СИСТЕМА СЧИСЛЕНИЯ, КОТОРУЮ МЫ ИСПОЛЬЗУЕМ СЕЙЧАС. Великий арабски! математик Аль-Хорезми О жизни аль-Хорезмм практически ничего нс известно. Его полное имя — Абу Джа- фар Мухаммед ибн Муса аль-Хорсзми. что в переводе с арабского означает «Му .^аммед. сын Монсея, отец Джафара, родом из Хорезма» Гот факт, что в его имени упоминается город, 1де он родился, указывает на го, что аль-Хорсзми был известным человеком. Хорезм и настоящее вре- мя Хина) — город в Узбекистане к юго-востоку от Аральского моря. Червя этот регион проходил древний шелковый пт гь. В VIII веке город был захвачен арабами. Аль-Хорезми родился между 80 и 800 гг. н.э. Гарун аль-Рашид, известный по араоским сказкам «Тысяча и одна ночь», спосоо- ствовал развитию арабской науки; н Багдаде, сто- лице империи, простиравшейся от Сре диземно- го моря ло 11н \iiii. он основал Академию наук по образу и подобию Александрийской библио теки. В свое время Академия, получившая название \ом му прости, была культурным центром, ока- завшим огромное влияние на западную кугьпру. В Академии переводились на арабский язык гре- ческие и ин лийскис налчныс и философские тру- ды, в том числе р юты Птолемея, Е вк лида и Брах- магупты. В ней также располагалась обсерватория. Примерно в 820 году халиф аль-Мамун, второй сын Гаруна аль-Рашида, пригласи л лдь-Хорезми в Дом мудрости, где тог получил должность би- блиотекаря. Аль-Хоре см и систематнзирова л зна- ния о математике, сохранившиеся от греков и ин- дийцев, и составил астрономические таблицы значений тригонометрических функций синуса и котангенса, получившие широкое распростра- нение Он также внес важный вклад в математику, историю н географию. 1 Imlhho из Дома мудрости отправилась в путь первая арабская экспедиция по вычислению диаметра Земли. В своей книге по географии « Китаб Сурат аль-Ар л» (“ Книга кар- тины Земли») аль Хорезми уточнил и дополнил труды 1 Колемся, посвященные Востоку и Африке. 11звестно. что аль-Хорезм и совершил путеше- ствие в Афганистан, на юг России и в Византию. Считается, что он умер в Багдаде около 850 г. н.э. ► А/аркл СССР. кыпущеы' нал fr' гаию ео дяя раме^ення ллъ-Хоркама. Портрет, изображенный ил марке. шлаi.vewt.4 подлинным. Пшорят, что за &t кону был взят портрет Чар лтвкл Л* l гноил в образе А/оиеел. A CuqLUfc-lrt/VJWW му>н- Hfi.-ta его кипел •• .4рнфм< гон- ка », и которая ннш ынл> mt л к лл гштциимтея t га тема < w ie/ш-ч но нсяолл- ни го Hi, ,i MAAf трактат ни aaeetrpe, от на <aimv Катараja и иргш или i<i ffiM« нонянте <г л- t А су '* J «_ Алгебра Его книга «Арифметика» (вортлналс «Ки- таб аль джама валь-тафрик») дошла до нас лишг в переводе на латинский язык, выполненном в XII веке, под названием De numero Indorum. Единственный л целейший экземпляр находится в Кеа бридже. Важность этой книги аключается в том, что в ней аль-Хорсзми описывает индий- скую позиционную систему счисления по осно- ванию 10, которую мы псполыхем сейчас, а так- же впервые использует цифру ноль. Несомненно, важнейшим его тру ^ом является кни- га по алгебре «Китаб ал-джабр ва-.л- МУкабала». Сохранился один экзем- пляр этой книги иа арапском я паке, а т акже перевод иа латынь под назва- нием Liber Algcbrae et almuchabaia. выпо шениый Герардом Кремонским ,111-1—1 IS71). 11менно от слова «ал джабр » npoi 1зош ло слово « а чсбра », которым стали называть науку о ре тении уравнений Кинга носит ди- дактический характер, о чем говорит и сам аль-Хорезми: « Мне придало смелости го. что Аллах, даровав има- му ал-Маллну сан халифа, достав- шийся ему по наследству, оказаь ему милость, облачив ею и украсив этим саном, вместе с гем вложил в нею 1 ль-Хорезми (ок. ~80 — ок. 880) 53
любовь к науке и стремление приближать к себе ученых, простирая над ними крыло своего покро- вительства и помогая им в разъяснении того, что для них неясно, и в облегчении того, что для них затруднительно. Поэтому я составил краткую кни- гу об исчислении алгебры и алмукабалы, заключа- ющую в себе простые и слож- ные вопросы арифметики, ибо это необходимо людям при дележе наследств, со- ставлении завещании, раз- деле имущества и судеб- ных делах, в торговле j и всевозможных сделках, ' а также при измерении - зсмсль, проведении ка- налов, строительстве и про- чих разновидностях подобных дсл/>. V Л 9~6гаду ВигП" г<{ № монмтыря сечтого Мартина и Мшании и ,вагч КО М KufifKif", КО- тирый ГГНЧ^Г XpilHUmfS в МО- пагтырг 3, корнал, прями говорит о том, что цифры от П до У л чгют индийское нротхокд! чш. ЭТО ШЛХР«410 । Когда труды аль-Хорезм и были вгврвые пере- ведены на латьыь, система счисления, в ксттороп использовались десятичные цифрь, стала называться арабской, хотя в действительности она имеет индийско,* ьроисхождени'». Ее называли исвой системой счислек ия аль-Хорезми. Затем wo имя стало заг исы- ваться как algorisrvi, algorism?; нам, нец от него произошло слово «алгоритм», которое не имеет ничего общего с описанном аль- Хорезми системен СЧИСЛе имя. Истоки алгебры В алгебре аль-Хорезми использовались не абстрактные сим- волы, а слова, которыми подробно объяснялись все матема- тические действия. Так как отрицательные числа в то время не использовались, а ль-Хорезми ввел действия, позволявшие привести уравнение к виду, необходимому для его решения. Эти действия назывались «ал-джабр» (отсюда происходит слово «алгебра»), «ал-хатт» и «ал-мукабала». Хотя значения этих слов точно не известны, нетрудно понять, каким пре- образованиям они соответствуют. Например, в уравнении (ж1 - 4х + 2 - 4х2 - 2х + б эти действия выглядят так: Таким образом, площадь фигуры, выделенной белым цве- том, будет равна сумме п лощадей четырех прямоугольников 4 • (2,5 х) ~ 10хплюс площадь центрального квадрата, рав- ная № Согласно уравнению, х1 + 1 Ох = 39. Следовательно, об- щая площадь большого квадрата будет равна 39 плюс площадь четырех красных квадратов, равная 4 - 6,25 = 25. 39 + 25 = 64. Общая площадь квадрата равна 64, значит, его сторона равна 8. Отсюда можно получить значение зс бх2 + 2х + 2 = 4х2 + 4х +6 ал-джабр сделать так чтобы в обеих частях остались только положительные члены Зх2 + х + 1 = 2х2 + 2х +3 ал-хатт разделить все члены уравнения на одно и то же число х2 = х +2 ал мукабала привести подобные слагаемые 2,5 + х + 2,5 = 8, то есть 5 + х=8,х = 3. После выполнения этих действии решение производилось методами геометрии, в чем можно усмотреть явное влияние греческой математики. Например, аль-Хорезми решал уравне- ние № +10х = 39 так: Очевидно, что это один из методов решения, но ни в коем случае не алгоритм, позволяю щий решить любое уравнение второй степени подобно извест- ной формуле -Ь ± у Ь2 - 4ас х =--------------• 2а Применив эту формулу 1. Построить квадрат со стороной х. 2. На каждой стороне квадрата построить прямоугольник со стороной 2,5.2,5 — это значение коэффициента прих, разде- ленное на 4, то есть 10/4 = 2,5. 3. Построить новый квадрат, расположив по бокам от прямо- куравнению х2 + 10х-39 = 0. получим два решения: 3 и -13. Второе из этих решений нель- A H.t книги МГОрЛ” ,LTh-.Vtfp«Wjr, ягргог^еиной на i атыНь, угольников четыре квадрата (выделены красным цветом). Они будут иметь сторону 2,5, следовательно, площадь каждого из них будет оаеча 2,5 2,5 = 6,25. зя получить методом аль-Хорезми, по- скольку ему было неизвестно о суще- ствовании отрицательных чисел.
Коммуникации составляют основу современных технологий и культуры в целом. Ил ФУНК! [ИОНИРОВАНИЕ ЗАВИСИТ НЕ ТОЛЬКО ОТ ЧИСТО ТЕХНОЛОГИЧЕСКИХ АСПЕКТОВ, НО И ОТ ТЕОРЕТИЧЕСКОГО АППАРАТА МАТЕМАТИЧЕСКОЙ ТЕОРИИ ИНФОРМАЦИИ. МАТЕМАТИКА Теория информации Эпоха коммуникаций С распространением проводного и беспро- водного телеграфа, радио п телевидения встала псиблоднмосп. оптимизации i а палов связи. С появлением новых технологий, в частности интернета, спутниковой и моби ль ной связи, эта необходимость только yen лилась. В любой из этих систем обязательно присутству- ет канал связи, по которому передастся информа- ция. В этом канале в сн м « о природы неизбежно образу ются шумы. Позднее, в дополнение ко всем вышеупомянутым средствам СВЯЗИ появились средства хранения данных, например СО или DVD, которые также можно считать каналами пе- Хлод Элвуд Шеннон (1916—2001) Этот инженер и математик считается создате- лем электронных коммуникаций. Он получил степень бакалавра в Мичиганском универси- тете, защитил докторскую в Массачусетском технологическом институте (MIT) в 1940 году. Шеннон разработал знаменитую теорию ин- формации во время работы в исследователь- ском центре Bell Labs. Умер в возрасте 84 лет после продолжительной борьбы с болезнью Альцгеймера. А VlnirnWtfU 6 матеианшчес Кенс шеарин информации ета со при- знание иомены ти клиоян перначи данных и wo&- ifftiri чаемр ними иизяцни его Параметров. Н XX веке т по. 1 сине с н ут ин но- вых коммуникаций t tH.i Ю сю смежны н оыгодаря ма- те м, ини ческой опра пптке «сред иые мой информации. Ня рисунке и юпражен еиут- мял le кшяр-1 — первый к мире спутник ееяш. рсдачп информации. В этом случае понятие шума эквивалентно возможным дефектам носителей, которые приводят к появлении# нежелательных ошибок. Высокое качество музыки на компакт- диске достигается частично благодаря процессу исправления возможных ошибок записи. По вышеуказанным причинам информация подвергается кодированию, которое изменяет се природу и делает возможной се обработку с по- мощью чисто математических метопон. Канал передачи информации Любая информация должна передаваться по ка- кому-либо каналу, будь то медный кабель, опто- волокно пли даже канал спутниковой связи. Ка- налы передачи данных обладают опрс леленными физическими ограничениями, одним из кото- рых является пропускная способность. Рассмо- трим аналогию с гндран анкон. На скорость во- ды в трубе влияют сс объем, скорость течения, а также длина и ширина трубы. Мы живем в так называемую цифровую эпоху, и это о тачает, что большая часть информации представлю на в виде битов, принимающих значения 0 пли 1 Однако
мы используем н< цифровые, а ана ютовые кана- лы. Например, электронная почта — это разно- видность информации, представ денной в ком- пьютере в виде последовательности бит. Она имеет цифровую природу. Когда мы отправляем электронную почту, она передается по аналого- вому кан 1ду — медному кабелю телефонной се- ти. Для передачи биты информации доли ны быть преобразоьлны в электрические импульсы с по- мощью устройства, называемого модулятором. В точке назначения сообщение необходимо за- ново преобразовать в последовательность бит. то есть деме, д'лировать. Следовательно, необходимо дополнительное устройство — модулятор ,демо- дулятор (модем). Весь процесс передачи инфор- мации представлен на схеме: шум Однако в канале пере дачи информации возни- кают различные помехи. Идеального канала нс существует, поэтому в передаваемых сообщени- ях возникают ошибки вызванные присутствием так на.ываемою шума. Чтобы контролировать не- желательные эффс кты, вызываемые ирису тел висм ш" «а, необходимо еще одно у етройство, на ^ывае мое шифратором. Он добавляет к сообщению данные, с помощью которых можно исправить возникающие ошибки Таким образом, схема пе- ре дачи .данных будет выглядеть так: шум Корректировка передаваемых данных В 192 1 году Гарри Найквист (1889—1976) сфор мдлировал теорему, согласно которой максималь- но возможная скорость передачи данных в канале ограничена свойством канала, называемым поло- сой пропускания. Однако в то время не сущее гво вало способа и 1мсрения информации, передавае- мой по каналу. Это было равносильно попытке измерить скорость течения виды, не располагая единицей измерения ее объема., будь то литр или JW'Wtf-W‘ItMH Vft tL.Ui шеирим Шейнина и Уинера. unyir.tuiL&fiaHHiiJi в университете штлмл ZJ.lihhphc в / tfh S *moti выдающет-Ч кннее .мим гг t f 7 страниц fиJepjtiiiraLJi иножа men ttdeii к&т^рые произвели ревалюцта e ьачмунныцнн и Мрмчгтке данных. любая другая единица. Первым единица изме- рения информации определил К дод Шеннон (1916—2001), который считается создателем тео- рии информации Он впервые изложил свою тео- рию в 1948 году а книге The Mathematical Theory of Communication («Математическая теория свя- зи»), которая стала отправной точкой для совре- менной математической теории связи. Шеннон доказал что можно избежать искажений при пе- редаче сигнала путем сю кодировки с помощью системы лвтикоррскцип, а также сформулирс вал критерий измерения информации. Шенной пришел к любопытному выводу: чем менее ве- роятно сообщение, тем больше информации оно содержи г. Измерение количества информации Маге магическую теорию информации нельзя бы- ло сформировать, нс определив единицу измере- ния, которая позволила бы однозначно оценить количество информации, передаваемо!: по кана- ле В основе сс опрс деления лежит очень простая идея, „сгорая на первый взгляд может показаться неожиданней: чем менее вероятно событие, тем больший объем информации ему соответствует. Человек кусает собаку Представим, что мы сидим в офисе в начале ра- бочего дня. В оф|г входит один из сотрудников и говори г: «Доброе у гро». Вероятность этого сообщения очень высока, и оно нс несет прак- тически никакой информации. Представим, что этот же сотру дннк при входе в офис сказал: «По- кар!» Очевидно, что вероятность этого сообще- ния очень мала, следовательно, оно песет намного больше информации, чем предыдущее. Допустим что мы хотим передать одно сооб- щение из списка в деся ь сообщений: А, А. В. С. С. С, С, С, D. Е. Вероятность того» что мы перед 1дц,м сообще- ние А. равна 2/10. Вероятное гь передачи С равна 5/10. Чгобы определить количество информации, содержащейся в .м их сообщениях, достаточно за- менить эти числа обратными Будем говорить, что количество информации, соетвстствующсс сооб- щению А. равно 5, количество информации в со- общении С раьио 2. В журналистском фолькло- ре популярно выражение: «Если собака укусила
Эпоха коммуникаций *1% перемен», состоящая хи 64 гексаграмм» об- разованных знаками двоичного кода: ннг> (—) К SH (). Сообщения передаются cwwufw кодов, например t прмощою двоичного кода, а котором иенользуготпеч все- /ев- 1 У (л,) = log---------. л. ^"Й’йг гУиШШ1ШВД==ШШп£ 3F£*?ic *>^Лх -к Л ~====й=ё ====*" ТЕГйИлЙ iz л Л ЕЕй- Я 3? V человека — ло нс новость, а вот если человек уку- сил собаку!..»' Эта фраза выражает все ту же идею: чем менее вероятно событие, тем большее количе- ство информации ему соответствует. Измерение количества информации Сформ}лируем более строгое математическое определение количеству информации. При пере- даче сообщения мы выбираем один или несколь- KAACiUVC- ска-ч кххтайскля «Книга Единицы измерения Для определения единицы измерения разумно начать с самой простой из возможных ситуаций. В нашем случае будем рассматривать лишь два ис- хода {ль <г2}, имеющих одинаковую вероятность. Таким образом, р [at] = р (д2) = 1 /2. Если мы хо- тим, чтобы эта величина была единицей измере- ния информации, логично выбрать 2 в качестве основания логарифма. Получим 1 У(«J = У (л.) - log,-- log,2 = 1 бит 1/2 По опреде ^ению количестве миф, рмации из- меряется в битах. Существуют и другие единицы измерения, которые используются реже, напри- мер дит или Хартли, в которых используется лога- рифм по основанию 10, и наг, в котором исполь- зуется логарифм по основанию е. Все примеры, которыми мы проиллюстриро- вали основы теории информации, очень просты. И хотя в реальности все намного сложнее, так как объемы информации исчисляются миллионами бит, но основной принцип, позволяющий рассма- тривать передачу информации с алгебраической точки зрения, остается неизменным ко элементов из некоторого множества, причем вероятность выбора всех элементов одинакова. В более общем случае это множество образовано буквами алфавита, из которых состоит конкрет- ное сообщение. Функция, выражающая количе- ство информации, обозначаемое У, определяется как величина, обратная вероя гностн передачи со- общения: У = \/р. Величину У можно назвать «не- вероятностью», что будет более корректно гово- рить о неопределенности. Заметим, что функция У является убывающей. Это означает, что с ростом вероятности неопределенность уменьшается, и наоборот. С другой стороны, из теории вероят- ностей известно, что если два независимых собы- тия А и В происходят одновременно, то вероят- ность такого исхода будет равна сумме отдельных вероятностей: Р (А - В) = Р (А) + Р (В). Суще- ствует математическая функция, которая обла дает этим свойством и является убывающей. Эта функция — логарифм. Если а > Ь, то log л < log b (напомним, что 0 < л < 1,0 < £ < 1). log (л b) — log а + log b. Именно по этой причине логарифмическая функция была выбрана для математического определения количества информации. Коды корр< кции ошибок При передаче сообщений информация кодируется, например, в виде по- следовательности нулей и единиц. При передаче информации по каналу связи эта последовательность может изменяться под воздействием ис- точников шума различной природы. Коды коррекции ошибок помогают определять и устранять нежелательные помехи. Ti ОрНЯ информации ЕЗ
Также стоит отметить, что определения нами с Minima измерения информации нс характеризу- ет качест во или полезность информации. Две книги объемом в 5(1 страниц каждая могут содержать одинаковое количество информации, но в одной из них может содержаться, например, список всех выпускников университета, а в дру- гой — подробная инструкция по изготовлению атомной бомбы. Биты и информация Одна из интересных особенностей теории Шеннона заключается в том, что с ее помощью можно определить минимальное количество бит, необходимое для получения полной информации. Допустим, мы хотим составить список вопросов, на которые можно отвечать только «да» или «нет», чтобы узнать, кто выиг- рал в лотерею: Иван, Петр, Илья, Никита, Анна, Лилия, Наталья или Ольга. Требуемый список вопросов может выглядеть так: 1. Победитель — мужчина? 2. Имя победителя начинается с гласной? 3. Победитель — старший из оставшихся двух претендентов? После ответа на первый вопрос число воз- можных кандидатов сократится до четырех. После ответа на второй число кандидатов сно- ва уменьшится вдвое, а узнав ответ на третий вопрос, мы определим, кто из двух оставшихся претендентов является победителем. Если мы обозначим «нет» за 0, «да» — за 1, то код 110 будет означать, что победитель лотереи — Илья (если он младше Ивана). Общее количе- ство информации в этой задаче равно 3 битам. Л01ШЖ010 • ............. ~ Одно из ключевых понятий теории инфор- мации — избыточность, то есть повторение ненужных данных. Это подтверждается тем, что буквы на письме располагаются не в про- извольном порядке. Если бы это было так, то сжатие текстовой информации было бы невоз можным. Классический пример: если записать фразу, стерегD все mai ные и попросить другого человека восстановить исходное предложение, он почте всегда сможет справиться с задачей. Шеннон уже в раннем возрасте увлекся мате- матикой (это увлечение он разделил с отцом1 и продемонстри- Гровал талант — ": к изготовлению механических игру шек К примеру, он сконструировал ме- ханическую мышь, способную передви- гаться по лабиринту. Этот талант, воз- можно передался ему от деда, кото- рый был одним из изобретателей современной сти- ральной машины.
Генри Э. Дьюдени Задачи на разрезание 1. Великая монада Это дрсвшш и достойный внимания символ. Он и лображем на флаге Южной Корги, а Север- ная гихоок« янская железнодорожная компания использовала его в качестве эмблемы Немно- гие знают, что он носит название великой мона- ды. Этот знак лл. t китайцев означает то же, что крест для христиан. Это символ божественною И вечного, а две его части, инь и ян, символшпрл ют мужею 1С и женское начала Говорят, что более трех тысяч лет па зад один у чемый заметил: «Без- граничное порождает крайность Крайность по- рождает дна начала. Два нача та производят четы- ре четверти, а от четырех четвертей происходи г квалратура восьми анаграмм феу-хи». Наде- юсь, что читатель не потребует объяснений. по- скольку я нс имею ни малейшего представления о том. что тго значит. Однако я л бежден, что на протяжении веков нот символ имел оккультное значение. Я представляю вашему вниманию просгейшую монаду. Ответите на три вопроса об at ом великом символе. 1 Г1 лощддь какой фигуры больше — вил грсн- него круга, содержащего инь н ян, илы внешнего кольца? 11 Разделите инь и ян на четыре- час ш одинако- во й формы и площади одним ра >резом, 111 . Разделите инь и ян на четыре части рав- ной площади, по различной формы одним пря- мым ра |резом. 2. Рождественский пирог — Раз уж мы ыгонорилп о рождественских пи- рогах, — сказал гостеприимный хогяни ног.ля- дывая на внушительную банку паренья на проти- воположном краю нала. — я припоминаю что один мой друг как-то tai ядал мне задачу о пироге. Воз она, — добавил он. по- копавшись в кармане — Цель задачи — о пре делить начинку, я пола гаю, — сказал студент I !тона. — 11ст, начинку вы опре- делите, когда попробуете пирог. Сейчас я прочитаю условие задачи. «Разрезать пирог па две части о сипа новой формы и размера, не трогая чернослив. Пирог следует считать плоским диском, а не шаром»». — Почему рождествен- ский пирог нужно считать диезом? 11 зачем может понадобиться разрезать его столь точно? — спросил озадаченный гость. — Это всего лишь головоломка Гости один за другим пыта лись справиться с задачей, по нико му нс удалось найти решение. Задаче непросто ре- шить. если не знать ctKbet приготовления пире 1 а Е^.ли же он вам известен, задача нс предсг-авиг для впе никаких трудное ten. 3. Две подковы Пи какой-то никому нс швееiнон причине счи- тается, чго подковы приносят удачу. Эго очень старое суеверие. Еще Джон Обри 11626—1"ЧК)) нис. л: «В большинстве домов лондонского Вест-Энда над дверью висит подкова». В домах на улице Монмут в 1813 воду внесло 1*" подков, в 1855-м — на 13 больше Даже лорд Нельсон приказал прибить подкову на мачт у с коего кора- бля « Викт(три ». Сеч один .ЧП1 астся. что подковы приноеягл ддчл. если они крепко прибиты к копы- там лошади везущей наш жипаж. Подкова, подобно свастике и дрлчпм симво- лам. которые я изучал, озиачадт здоровье, бла гополучис, добрую волю и даже была символом человеческого рода, поэтому она представ лист не- малый интерес. Неужели подкова tie обладает за- гадочными .эзотерическим и . ли математически мч свойствами? Я изучил этот вопрос п решил обратить внимание моих читателей на приме ча- тс льны и фак г: две подковы и зображенные на ри су икс. у ивп тельным ббря юм связаны с икру жно- стью. символом вечности. Я Представлю простую задачу, чтобы вы оце- нили сколь трудно обнаружить эту связь, кото- рая оставалась сокрытой па преняженпн веков. Я .паю, чго моим чигаггелям доставляет удоволь- ствие ра 1Г.1дыв.Г1Ь загадки. Нлжнб рагрезаТь две подковы на четыре ча стн разной формы и cociairiiib на них идеальную окружность. Каждую подкову нужно рзгрезаи, на две части, а внутренняя часть подковы должна располагаться внл три получившейся окружности.
Решения 1. Площади кругов относятся друг к другу как квадраты их диаметров. Если один круг имеет диаметр 2 дюйма, второй — 4 дюйма, то площадь одного круга будет в четыре раза больше площади другого, поскольку квадрат числа 4 в четыре раза больше, чем квадрат числа 2. I. Если мы посмотрим на рисунок 1, то увидим, что два равных квадрата можно разделить на четыре части, образующие большой квадрат. Отсюда следует, что площадь квадрата в два раза меньше ква- драта его диагонали. На рисунке 2 изоб- ражен квадрат, так как он часто встреча- ется на древних изображениях монады. Это дало мне основания полагать, что этот символ имеет математическое зна- чение. Оказалось, что площадь внешнего кольца точно равна площади внутренне- го круга. Сравнив рисунок 2 с рисунком 1, мы увидим, что квадрат диаметра CD в два раза больше квадрата диаметра СЕ внутренней окружности. Следовательно, площадь большого круга в два раза боль- ше площади малого, и это означает, что площадь внешнего кольца точно равна площади внутреннего круга. Таков ответ на первый вопрос задачи. II. На рисунке 3 представлено простое решение второй части задачи Очевидно, что оно верно, и его можно доказать, раз- резав фигуру и наложив ее части друг на друга. Увидеть это вам помогут пунктир- ные линии, изображенные на рисунке. Ill, Третья часть задачи решается раз- резом по линии CD, изображенной на рисунке 2, но нужно доказать, что пло- щадь фигуры F на самом деле в два раза меньше площади инь или ян. Доказатель- ство представлено на рисунке 4. Площадь круга К в четыре раза меньше площади круга, содержащего инь и ян, так как диа- метры зтих кругов отличаются в два раза Кроме того, площадь фигуры L, изображенной на рисунке 3, в четыре раза меньше площади круга. Очевидно, что площади G и Н равны, следовательно, площади их половин также рав- ны. F «теряет» часть фигуры К, но «приобретает» часть фигуры L точно такой же площади. Сле- довательно, площадь фигуры F равна половине площади инь или ян. 2. На рисунке показано, как можно разрезать пирог на две части одинаковой формы и площади. Линии обязательно должны проходить через точки А, В, С, D и Е. Существует бесконечное множество вариантов, удовлетворяю- щих этому условию. Например, в точке, расположенной строго между точкой А и краем круга, линию разреза можно провести бесконечным множеством спо- собов (причем эта линия может быть как прямой, так и кривой) при условии, что линия, соединяющая точку Е с противопо- ложным краем круга, будет зеркальным отражением этой линии. Аналогично можно изменять форму линии и в других местах. 3. Суть задачи в том, чтобы разрезать две подковы (включая их внутреннюю часть) на четыре части, то есть каждую подкову — на две части так, чтобы полу- чилась идеальная окружность. Также указано, что четыре части могут быть разного размера. В действительности при решении этой задачи используется принцип, известный нам по китайскому символу монаде (см. задачу 1). На рисунке изображено решение за- дачи. На рисунках 1 и 2 вы видите подко- вы, разрезанные на четыре части разной формы, из которых можно составить идеальную окружность, изображенную на рисунке 3. Заметьте, что Чости А и В одной подковы и части С и Одру гой подковы образуют две равные половины окружно- сти, инь и ян великой монады. Обратите внимание, что составить подкову из ча- стей круга проще, чем составить круг из двух подков. Однако задача не представ- ляет особой трудности, если знать, что длинная сторона подковы должна обра- зовывать часть границы круга. Обратите внимание на разницу между В и D — она поможет вам решить многие подобные задачи. Фигура D получается из фигуры В добавлением симметричной фигуры — криволинейного квадрата. Следователь- но, чтобы составить из этих элементов окружность, нужно повернуть В и D на четверть оборота в разные стороны. 54
Головоломка «Большой взрыв», получившая свое название благодаря тому, что при РАЗБОРКЕ ОНА «РАСШИРЯЕТСЯ» ПОДОБНО ВСЕЛЕННОЙ ПОСЛЕ БОЛЬШОГО ВЗРЫВА, ИМЕЕТ ФОРМУ ШЕСТИКОНЕЧНОЙ ЗВЕЗДЫ, ИЗВЕСТНОЙ КАК ГЕКСАГРАММА, ИЛИ ЗВЕЗДА ДАВИДА. Головоломка для сборки и разборки Большой взрыв 4 lllei тниконечнлх .зДл — один «3 {11МЫХ НЭНе, чтых ги моллов нудлн; «.z. On лбрл июли шргепеншм двухpa в Ht/t тираннах треугольны Kuo, ннт энных « окружит ть. По иудейской традиции парк < /помп, сын l-isuda, спа- иощью этой те1ды и млн и де,чанов и при цмлл ангелов. Сегодц v imam ен ива i можно youdi ть на ф иге государ- ства (1:р,шль. Стороны собранной головоломки состоят из восьми равносторонних треугольников каждая. Головедомка «Большой взрыв» состоит из шести одинаковых частей, каждая из ко- торых образована чет ырьмя ромбоидами, в свою очередь состоящими из равносторонних трепелы in ков. Строение отдельных частей подсказывает, как можно разобрать юловоломку и собрать се сно- ва. Каждый элемент головоломки состоит из двух частей; темной и светлой, которые содержат боль- шой и малый ромбоиды. Разборка «Большого взрыва» * |з- а особых свойств головоломки разобрать ее не легче, чем собрать. Чтобы разе орать юлово- ломку, ич жно слегка надавить наружу, чтобы рз j делить се на три равные части. Светлая часть Четыре ромбоида, из которых состоя г элемен- ты головоломки, попарно равны между собой. В свою очередь, два больших ромбоида состоят и двух малых ромбоидов. А Счшмлгния, гиащн- конечная utetda представ i s- гш собой fduetmeo нротшю- на юл костей. ля. i я/mt я CUMfiO iOM /Ор нолиU U СО- eeputrucmAg. Чрсуго iimhk, ft fput вил KOIHUpOJW обрЛЩСНЛ вив i, CH Wto Ui iftpyem поду n Mrwt Х'й- начала 'fpry/ель- ник, вершшы кошоро/л на- нравлена вверх, си чволниеру^ ет огонь и иужское navttio. Болес того, малые ромоопды являются ромба- ми, та.. как все их стороны равны. Л,а чес нужно слегка надавить на концы каждой части, чтобы разделить головолчмк} на шесть со- ставных частей. К ж видно на рисунке, каждый ромбоид состо- ит из равносторонних треугольников. 85
Сборка «Большого взрыви» Как прекрасно видно на рисунке спра ва, все элементы головоломки «Боль- шой взрыв», состоящие из светлой и темной частей, одинаковы. Благо- даря этому процесс сборки можно разделить на два этапа. Первый этап (действия 1 —3) со- стоит в том, чтобы попарно соединить части головоломки. Второй этап (действия 4—5) заклю- чается в том, что нужно внимательно соединить полученные элементы головоломки так, чтобы получилась шестиконечная звезда. 1. В начале сборки возьмите две части го- ловоломки и наложите их большие части друг на друга так, чтобы они совпадали. 2. Далее нужно сдвинуть элементы головоломки так, чтобы спрятать короткие выступающие части. 3. Повторив эти действия для че- тырех оставшихся частей, получим три равных элемента головоломки, которые изображены на рисунке. 4. Теперь достаточно расположить три части так, как показано на рисунке, и слегка надавить в направлениях, указанных стрелками. 5, Головоломка «Большой взрыв» полностью собрана
х
D3AGOSTINI представляет Пропустили выпуск любимой коллекции? на сайте www.deagostini.ru Для украинских читателей — по телефону горячей линии 0-800-500-8-40 В следующем выпуске через 2 недели Коробка с поперечными брусками Спрашивайте ® в киосках! Теория чисел Числа Фибоначчи Непонятый гений Нильс Хенрик А бель Немного топологии Узлы Кредиты и проценты Математика в ипотеке Льюис Кэрролл Запутанный рассказ