Самое интересное и самое сложное, самое скучное и самое полезное об алгоритме. Страна чудес и зазеркалье Алгоритма одновременно. Попробуем подобно известному сказочнику познакомить воображаемую Алису с лабиринтом "мыслей" математика — со способами использования переноса, моделирования и синтеза. И опять под катом много слов и немного картинок...
Задача
Почти все предыдущие статьи этой серии были очень странными. А эта статья будет самой "чудесатой". Поэтому настроенным на взрослый скепсис пожалуй стоит закончить чтение тут, но готовых развлечься с пользой в разговоре с не очень научной строгостью и на очень важные темы — Вам найдется здесь немного "сложноватого" и увлекательного чтения.
В обсуждении предыдущей статьи (как же хорошо что обсуждение наконец состоялось!) стало ясно, что за большим нагромождением слов, каждый раз формирующих статью серии, очень плохо просматривается цель. А цель, с которой все эти слова собираются под заголовком "Что такое алгоритм ?!", очень проста и одновременно амбициозна.
Цель всей работы — это способы создавать алгоритмы без участия человека (формализация и автоматизация этого процесса).
Для достижения обозначенной цели необходимо много составляющих. Прежде всего и самое главное — необходимо найти подсказки, как работать с алгоритмом. Можно попробовать дать определение слова "Алгоритм". Вы скажете определение "Алгоритма" уже существует, и легко найти его, например, на Вики. И да, и нет. На страницах Википедии есть множество определений разных понятий. Давайте рассмотрим простой пример — ну, скажем, возьмем "Молоток". Значение (читай "определение" этого слова) тоже есть на Вики:
Молото́к — небольшой ударный ручной инструмент, применяемый для забивания гвоздей, разбивания предметов и других работ. В основном изготавливается из стали. Молоток — один из древнейших инструментов, используемых разумным человеком.
Тут дан некоторый набор слов. Что из них определение, а что инструкция к применению? Является ли фламинго молотком для крокета. Есть ли в приведенном значении слова "Молоток" сведения, помогающие в изготовлении молотка? Думаю, что подсказок в этом "определении" так же мало, как и в определении слова "Алгоритм", взятом на странице Вики.
А почему этих подсказок нет. Первым делом можно сказать, что это связано с типом приведенного "определения". Это определение неформальное. Оно для человека. А не для математика. И почти потому оно не подходит и для станка, изготавливающего молотки. В чем проблема? Конечно, тут нет проблем. Если этим пользуется человек, то всё нормально. А вот если нам все же нужно сделать станок для производства молотков, то нужно думать. И изобретать формальное определение. Например, это будет "чертеж" или программа для изготовления этого молотка на автоматическом фрезерном станке или какой-то другой вариант описания. И это будет формальное "определение" для изготовления. Формальное "определение" для использования тоже потребуются, если этим молотком будет пользоваться не человек, а машина.
К чему это всё? Возвращаемся к алгоритму. Легкий вывод: чтобы "научить" машину изменять и создавать алгоритм тоже необходимо формальное определение. Если уточнять, то это необходимо пока машина сама не сможет конвертировать наши "определения" на свой язык. Поэтому первая статья серии начинается с разбора существующих определений "алгоритма". И вся работа опирается на констатацию факта, что формального определения алгоритма еще нет. Но для поставленных задач это определение необходимо сформулировать.
… Если быть совсем честными, то формальное определение Алгоритма в работе уже сформировано. Но в этом определении есть недостаток. Это определение — математика. Для того чтобы им начали пользоваться (и может быть добавили в Вики), необходимо предоставить способы применения этой математики к практическим задачам. И таких способов слишком много, и только самые важные появляются в статьях этой серии. И способ, которым является сама Математика, будет рассмотрен в текущей статье. Да, мы будем с помощью Математики описывать как работает Математика. Думаю, Льюис Кэрролл порадовался бы такому приключению для Алисы. С чего же нам начать? Ах, да...
Следуй за белым кроликом. Тук-тук...
Алгоритм сложения
В предыдущей статье этой серии с загадочным номером 101, мы уже на "небольшом" примере изготовления торта познакомились с тремя способами создавать алгоритмы: это случайное обнаружение алгоритма, объединение алгоритмов и эволюционная аккумуляция алгоритма. Эти способы хороши — с их использованием алгоритмы успешно, но очень медленно развивались, и они развивались бы и дальше. Но так случилось, что на их основе были сформированы следующие два. Эти способы: алгоритмический перенос и трансляция алгоритма из модели. И с этой парой, как у Алисы со встречей Траляля и Труляля, всё стало развиваться значительно веселее и, что самое главное, это позволило гораздо быстрее формировать новые и сложные алгоритмы. Что же это за близнецы Перенос и Трансляция? И почему необходимо их все же различать для продолжения разговора об Алгоритме?
Ответам на эти вопросы посвящена текущая статья. И, чтобы начать наше приключение, все же будет необходимо воспользоваться результатом предыдущей статьи. Необходимо попробовать испеченный в ней волшебный тортик с надписью "Съешь меня". Попробовать не на вкус, но использовать как рабочий метод разбора формирования сложного алгоритма.
И в этой статье будет особенный алгоритм. Для наших целей нам очень подойдёт простой и одновременно уже знакомый нам — "Алгоритм сложения". Мы встречались с ним в первой статье этой серии.
Давайте немного с ним развлечёмся, оценивая структуру этого "математического действия", которое для многих наших задач является элементарным. Ведь эта элементарность появилась не сразу. И для Алисы это действие еще сложнó и не всегда дается.
Сложению тебя обучили? – спросила Белая Королева. – Сколько будет один плюс один плюс один плюс один плюс один плюс один плюс один плюс один плюс один плюс один?
– Я не знаю, – ответила Алиса. – Я сбилась со счета.
Поможем Алисе обучиться такому сложению? Давайте рассмотрим ситуацию с участием "древнего математика", которому впервые могла понадобиться эта математическая операция. У этого "математика" тоже было что считать. Это, конечно были не слова "один" во фразе королевы, но тоже очень одинаковые объекты. Ну, например, коровы в большом стаде. И пусть сначала в его стаде было три-семь коров, так что, окинув их взглядом, "математик" всегда мог легко сказать их "количество". Это "количество" изначально даже не было числом. Это был способ оценить количество стогов сена, которое нужно запасти на зиму для стада. Или оценить количество времени, которое нужно потратить на заготовку этого сена.
Попробуем на примере стада коров разобраться в последовательности событий и действий человека, ухаживающего за стадом, приведшей к появлению "Алгоритма сложения". Мы основываемся на некоторых фактах. Например, что человек, ухаживающий за стадом, (далее будем условно называть его "пастухом") знает, что для одной коровы количество времени для заготовки сена на зиму — это полдня. На основе этого знания попробуем запланировать количество труда "пастуха" (читай написать алгоритм вычисления трудозатрат). Для этого не нужно знать слово "количество" и даже знание "чисел" не является необходимым.
Опять, как и предыдущей статье, рассматриваемый алгоритм опирается на базовую стратегию "Поддержание своей жизнеспособности", и в угоду сокращения количества слов в статье текущей, опустим множество этапов эволюционного развития и сразу перейдем к достаточно элементарному алгоритму пастуха. Упростим ситуацию со стадом и оставим в нём только одну корову.
Алгоритм обеспечения одной коровы сеном на зиму прост:
Работай полдня, укладывая сено рядом с этой коровой.Да, количество времени, необходимое для одной коровы, выбрано произвольно и не соответствует нашей реальности, но для сказочной страны — вполне подходит.
Как сформировался этот алгоритм? Те кто запасал корове сена меньше — оставались к весне без коровы, затем без еды — и погибали. Суровая сила эволюционного отбора. Не будем рассказывать это Алисе и оставим такие сведения для взрослых размышлений.
Но ситуация поменялась, и коров стало больше. С несколькими коровами "пастуху" стало сложнее. Сена и работы стало тоже больше. И появилась необходимость это сено распределять между коровами. Стал нужен признак, показывающий, что не нужно укладывать сено рядом с коровами, которым уже нанесли достаточно сена. Таким признаком может быть, например, укрытый стог, в ситуации когда в конце сбора стога для текущей коровы этот стог обвязывается и укрывается. Тогда алгоритм с несколькими коровами следующий:
Для любой коровы, рядом с которой нет укрытого стога,
работай полдня, укладывая сено рядом с ней,
и, заканчивая, укрой стог.Да, этот алгоритм посложнее и еще далек от математики. Все же с некоторым усилием его эволюционное формирование просматривается. Оставим разбор этого развития для индивидуального развлечения заинтересовавшегося читателя. А вместе направимся дальше.
Среда снова предоставляет нашему "пастуху" новые ситуации и проверяет его профпригодность в разработке алгоритмов выживания. Итак, у "пастуха" новое счастье — коров в его стаде ещё больше. И эти коровы очень плотно живут в коровнике и сено рядом с ними укладывать не получается. Коровы размещены также плотно как слово "один" во фразе Королевы. Но сено на зиму нужно запасти, а Алисе необходимо посчитать сумму. Пора изобретать более совершенные алгоритмы. И эти алгоритмы будут основываться на комплементарных действиях и сходстве разных предметов по отношению к некоторым алгоритмам. На сцену выходит первый близнец — синтез алгоритма с именем "Перенос".
Перенос
Для использования чисел еще рановато, но мы уже близко. Возьмем вместо них пока нечто попроще и породнее. Алисе я бы посоветовал посмотреть на пальцы. Ну а для "пастуха" — пальцев будет маловато. Но всегда можно найти объект поменьше коровы, который можно поместить в руках, например, камешки. И что нужно с ними сделать? Правильно сопоставить! Палец сопоставим слову "один". А камешек сопоставим одной корове. Легко сказать "сопоставить". А каким алгоритмом это можно сделать?
У Алисы ситуация проще. На каждое услышанное слово "один" достаточно "комплементарно" загнуть один палец на своих руках. Для "пастуха" это сопоставление чуть сложнее, но принцип схож. Стадо тоже необходимо выстроить в структуру — и лучше всего использовать структуру линейную, совсем как у слов "один" во фразе Королевы. Например, это можно сделать утром, когда коровы выходят из коровника с узкой дверью, пропускающей за раз только одну корову. Необходимо заранее запастись камешками. И для каждой выходящей коровы брать камешек и "загнуть его", ну, нет, конечно, это же не палец Алисы. Нужно положить его в отдельное выбранное место. Так формируется кучка камней. И когда последняя корова выйдет, в кучке будет лежать столько же камней сколько коров в стаде. А зачем нам эти загнутые пальцы и кучка камней? Правильно! С ними проще работать, чем с растворяющейся в памяти длинной фразой или большим стадом. С ними можно выполнить подсчет. С кучкой камней легко придумать алгоритм формирования запаса сена на зиму в отдельном от коровника хранилище. И можно выполнить много еще чего. Мы перенесли опору алгоритма запаса сеном на зиму с использования коров на использование камешков. И упростили жизнь "пастуху", сделав его уже немного "математиком".
До серьезного математика остался один шаг. Этот шаг — появление операции сложения. И шаг прост. Например, нужно, два "пастуха", хранящих в кармане кучки камешков, которые соответствуют каждая своему стаду. При этом достаточно только возникновения ситуации, когда два стада нужно объединить. В этом случае, конечно, можно прогнать полученное объединенное стадо через коровник с узкой дверью. Но ведь гораздо проще просто высыпать две кучки камешков в одно место!
Наверно, как-то так и родился алгоритм сложения! А вместе с ним зародилась и математика. Как способ повышать эффективность алгоритмов переносом в более удобную область. И эта область только поначалу была камешками, а в последствие дополнилась числами, интегралами, исчислением предикатов и много, много, много еще чем...
Но, а как же второй близнец "Трансляция"? Да, да… он тоже нам нужен, и тоже нужен Алисе.
Трансляция
– Сложения не знает, – сказала Черная Королева.
– А Вычитание знаешь? Отними из восьми девять.
– Этого я не знаю, но зато…
Зато? Что так смутило Алису? Ответ прост, и подсказкой будет то, что этот момент смущал те только Алису, он сильно мучил и "древних математиков". А сложность этого момента сводится к простому утверждению: не все математические действия с "камешками" однозначно соответствуют (то есть переносятся) на стадо коров. И отрицательные числа, наверно, стали самой простой и только первой проблемой, с которой столкнулась математика. Ведь очень непонятно какой корове соответствует отрицательное число -1.
И дальше встает вопрос. Отказываться ли от этих "странных" отрицательных чисел? Или можно использовать их, но не переносить в коровы? Со знаниями, которыми обладает современный школьник старших классов, ответ тривиален. Конечно, использовать! И, видимо, Алисе придётся все же изучить и такое "странное" вычитание. Но "древним математикам" было не так легко. И только польза от алгоритмов, использующих отрицательные числа, помогла принять это сложное решение и ответить на заданный вопрос утвердительно. Да, нужно использовать отрицательные числа!
Такие же странные вопросы, подобные вопросу об "отрицательных числах", впоследствии вставали перед математиками не один раз. Вопросы были запутанными совсем как у Гусеницы, и каждый раз новая абстракция становилась всё "страньше" и "страньше". Иррациональные числа вместо рациональных (например, для алгоритма нахождения длины окружности по диаметру). Квадратный корень из отрицательного числа ("мнимая единица"), например, для алгоритма решения кубического уравнения. "Бесконечность", например, для нахождения значения предела сходящейся суммы бесконечного ряда (еще древнегреческий философ Зенона размышлял над этой странной задачей в парадоксе "Ахиллес и черепаха"). Парадоксов перед математиками было много. Некоторые все же исключались, потому что не было возможности использовать их в полезных алгоритмах. Так было, например, с парадоксом "Множество всех множеств". Но основой всех таких размышлений и решений было одно — наличие полезных алгоритмов, в которых использовались эти "странности". И тут "естественный отбор" тоже работал. И эволюционный способ формирования математических алгоритмов, медленным и в дополнение к нему быстрым накоплением привел к тому, что мы сейчас называем слово "Математика".
А где же прячется различие двух близнецов "Переноса" и "Трансляции". Вы, да и Алиса, верно уже догадались. При задании трансляции обязательно вводятся ограничения и указывается подмножество взаимно-однозначно соответствующих объектов и алгоритмов, внутри которого можно корректно произвести перенос между двумя алгоритмическими областями: прикладной областью ("стадом коров") и пространством модели ("горсткой камешков"). Вне этого подмножества перенос невозможен. Как невозможна "минус одна корова". Эти ограничения необходимы в представленной модели с "отрицательными числами". Самой простой модели, которую удалось найти. Но такие же ограничения есть и для моделей с трансляцией куда более сложной. Все же здесь остановимся. Не будем всё сваливать в одну кучу — ведь перед нами нечто посложнее стада коров.
Оставим сложную часть для следующей статьи, в которой продолжим наш разговор об ученых, моделях и разных способах использования Алгоритма для изучения научного познания. На очереди вывод на чистую воду алгоритмичности "Физики". И, думаю, опять в этом нам должна помочь Алиса. Осталось только найти этому занятию время и надеяться, что мы не потратим его впустую.
– хорошо бы получше провести время…
– Все понятно! – с торжеством сказал Шляпа.
– Провести время?! Ишь чего захотела! Время не проведешь! Да и не любит он этого!
Выводы
Вознаградим себя за проделанную в чтении текущей статьи работу. Пусть даже наградой будет лишь похвала и перечисление значимых свершений.
В этой статье мы познакомились еще с двумя способами синтеза алгоритмов ("Перенос" и "Трансляция из модели"). Эти способы еще не до конца описаны, но их основа уже немного просматривается.
На примере "пастуха-математика" смогли понаблюдать за эволюцией и скрытой алгоритмичностью Математики.
Вроде бы разработали помощь Алисе в сложении для правильных ответов Королеве.
Развлеклись?
Спасибо Вам за внимание.
Отзывы
Буду очень благодарен за отзывы, пожелания и предложения, так как они помогают мне скорректировать направление развития работы в этой области.
Отдельное волнение у меня есть по стилю повествования и форматированию, используемым в статье (кавычки, абзацы, курсив). Напишите, пожалуйста, если у Вас есть замечания к ним. Можно личным сообщением.
Ссылки
- Главная страница и теория работы (GitLab GPL): Проект "Общая теория алгоритмов"
- Вводная статья работы "Разрабатываем теорию алгоритмов как проект с открытым исходным кодом". Пожалуйста, не судите строго эту наивную публикацию "сверх-идеи" устаревшей версии 2019 года.
- Статьи серии "Что такое алгоритм?!"
- Статьи в хабе "Программирование":
- Иллюстрации из книг «Приключения Алисы в Стране чудес» и «Алиса в Зазеркалье» выполнены Сэром Джоном Те́нниелом
