Код креативности. Как искусственный интеллект учится писать, рисовать и думать

Возможно, эту задачу легче понять, если использовать наглядную иллюстрацию. Представьте себе помещение длиной 36 м и шириной 15 м. Вы хотите узнать максимальный размер квадратных плит, которыми можно покрыть весь пол этого помещения, не разрезая этих плит. Как тут поступить? Вот изобретенный более 2000 лет назад алгоритм решения этой задачи:

Предположим, что у нас есть два числа, M и N (предположим также, что N меньше M). Прежде всего разделим M на N и обозначим остаток от деления N₁. Если число N₁ равно нулю, то N – наибольшее число, на которое делятся оба исходных числа. Если же число N₁ не равно нулю, то разделим N на N₁ и обозначим остаток от деления N₂. Если число N₂ равно нулю, то N₁ – наибольшее число, на которое делятся и M, и N. Если же число N₂ не равно нулю, то повторим ту же операцию. Разделим N₁ на N₂ и обозначим остаток от деления N₃. Остатки от деления будут становиться все меньше и меньше, оставаясь при этом целыми числами, так что рано или поздно мы должны дойти до нуля. Алгоритм гарантирует, что, когда это произойдет, остаток от предыдущего деления будет наибольшим числом, на которое делятся и M, и N. Это число называется их наибольшим общим делителем.

Вернемся теперь к задаче о мощении пола. Сначала найдем самую большую квадратную плиту, которая входит в помещение заданной формы. Затем найдем самую большую квадратную плиту, которая помещается на оставшийся участок, – и так далее, пока не дойдем до последней квадратной плиты, которая целиком заполнит все оставшееся место. Это и есть самая большая квадратная плита, которая позволит покрыть весь пол, не разрезая плит.

Если M = 36, а N = 15, то при делении M на N получится остаток N₁ = 6. При делении N на N₁ получится остаток N₂ = 3. Но при делении N₁ на N₂ никакого остатка не получится, и таким образом мы выясняем, что наибольшее число, на которое делятся и 36, и 15, равно 3.

Как вы видите, в этой процедуре много выражений типа «если…, то…». Это характерно для алгоритмов, и именно это обеспечивает столь превосходную пригодность алгоритмов для программирования и компьютеров. Древняя инструкция Евклида затрагивает самую суть четырех ключевых свойств, которыми в идеале должен обладать любой алгоритм:

1. Он должен состоять из точно сформулированных и однозначных инструкций.

2. Процедура всегда должна заканчиваться (а не уходить в бесконечный цикл!), какие бы числа в нее ни ввели.

3. Она должна выдавать ответ для любых значений, введенных в алгоритм.

4. В оптимальном варианте алгоритм должен быть быстрым.

Ни в каком из шагов алгоритма Евклида нет никакой неоднозначности. Поскольку остаток от деления уменьшается на каждом шаге, он неизбежно доходит до нуля за конечное число шагов, после чего алгоритм останавливается и выдает ответ. Чем больше числа, тем больше время работы алгоритма, но работает он все же относительно быстро. (Если вас интересует точное значение, число шагов в пять раз больше числа знаков в меньшем из двух чисел.)

Если самые старые алгоритмы появились более 2000 лет назад, почему же само это название происходит от имени персидского математика IX века? Мухаммад Аль-Хорезми был одним из первых руководителей великого «Дома мудрости» в Багдаде и отвечал за перевод многочисленных древнегреческих текстов по математике на арабский язык.

Слово «алгоритм» происходит от латинской транскрипции его имени. Хотя все инструкции к алгоритму Евклида приведены в его «Началах», язык Евклида чрезвычайно невразумителен. Мышление древних греков было очень геометрическим; вместо чисел они говорили о длинах отрезков, а их доказательства состояли из изображений – приблизительно как в нашем примере с мощением пола. Но изображений недостаточно для строгих математических утверждений. Для них требуется язык алгебры, в котором буква может обозначать любое число. Именно в этом и состояло изобретение Аль-Хорезми.

Чтобы суметь ясно изложить, как работает алгоритм, нужен язык, позволяющий говорить о любом числе, не указывая, какое именно это число. Мы уже видели, как работает этот принцип, в объяснении действия алгоритма Евклида. Мы присвоили числам, которые пытались анализировать, имена – N и M. Эти переменные могут представлять любые числа. Могущество этого нового лингвистического подхода к математике состояло в том, что он позволял математикам понять грамматику, лежащую в основе операций с числами. Можно было не говорить о конкретных примерах работы того или иного метода. Новый язык алгебры дал возможность объяснять закономерности, определяющие поведение чисел. Подобно коду компьютерной программы он показывает, почему метод работает независимо от того, какие числа мы выберем, – в соответствии с третьим критерием нашего определения хорошего алгоритма.