Русский
Русский
English
Статистика
Реклама

Что такое алгоритм! (часть 2)

Продолжаем искать рецепт блюда "Алгоритм". В меню обусловленная и связная последовательность исполнения.


Title


Задача


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


В качестве основы для решения мы используем разбор существующего определения алгоритма, согласно которому алгоритм является "набором инструкций, описывающих порядок действий исполнителя для решения некоторой задачи". Целью нашего разбора является попытка избавиться от необходимости участия человека в процессе формирования и применения алгоритма. Один из наиболее известных шагов в этом направлении уже выполнен Аланом Тьюрингом, и в его результате мы избавились от необходимости участия человека для исполнения алгоритмов математических расчётов. И наш мир не стоит на месте: на текущий момент программисты способны "научить" компьютер исполнять много других полезных (и не очень полезных) алгоритмов.


Но мы не будем останавливаться на этом значительном успехе. Для дальнейшего движения необходимо рассматривать все понятия и процессы в определении алгоритма, которые неявно предполагают деятельность человека. В предыдущей статье серии (Часть 1) уже разобрано первое такое понятие "действие". Это необходимо, потому что человек при создании алгоритма волен сам находить и формировать набор "действий", с использованием которого он собирается решить задачу. В процессе анализа того, на какие признаки "действия" опирается человек в этом поиске и выборе, мы отметили, что важным, но не единственным таким признаком является Повторимость "действия". На основе этого признака появляется возможность как минимум процесс поиска "действий" передать нашему компьютеру. И в первом приближении это позволит отказаться от услуг человека в этой части работы с алгоритмом.


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


Группировка действий в алгоритм


Как можно объединить "действия" в алгоритм? Ведь не всякое объединение "действий" имеет тождественный результат? Это объединение должно как-то "описывать порядок". Для разбора основ такого объединения следует поискать разные примеры синтеза алгоритма, и для начала желательно, чтобы эти примеры были максимально просты по структуре. И только разобравшись с "тривиальными" ситуациями, следует пробовать перейти к более сложным.


В первой статье мы упоминали, что химические реакции являются "действиями". Давайте попробуем понаблюдать за работой химика. В его арсенале большое количество "действий" (химических реакций). Эти "действия" основываются на разных "объектах" химических веществах, а, вернее, на молекулах этих веществ. Рассмотрим ситуацию, когда учёный-химик пытается найти решение следующей задачи: $S \rightarrow SO_3$. У химика уже есть в арсенале "действия", выделенные на основе признака повторимости:


$ 2H_2S + 3O_2 \rightarrow 2SO_2 + 2H_2O \\ 2SO_2 + O_2 \rightarrow 2SO_3 \\ NaOH + HCl NaCl + H_2O \\ S + H_2 \rightarrow H_2S \\ $


Для решения поставленной задачи химик выбирает, упорядочивает и объединяет некоторые действия, и тем самым находит алгоритм: $S \rightarrow H_2S \rightarrow SO_2 \rightarrow SO_3$. Это решение полностью согласуется с выше приведенным определением алгоритма, в котором под словом исполнитель химик подразумевает себя и других химиков. При этом исполнение в химической лаборатории можно трактовать как управление последовательностью процессов описанных алгоритмом.


Обратим внимание, что алгоритм формирования химиком своего "алгоритма" достаточно прост и не требует большого труда написать автоматическую систему помогающую химику в его творческом поиске. На какие признаки будет опираться эта система? Конечно, главным признаком будет совпадение типов молекул в финальной стадии предшествующей реакции и в начальной стадии следующей реакции.


Типы химических реакций


Построение дерева решений на этом признаке можно строить с двух сторон:


  • от $S$ стартового вещества, указанного задачей, в прямой последовательности исполнения реакций;
  • и от вещества $SO_3$, являющегося результатом поставленной задачи, с использованием обратной последовательности.

В точках пересечения этих деревьев появляется искомый путь решение задачи. И, конечно, таких решений может быть несколько. Некоторые из них будут предпочтительней с точки зрения минимизации количества этапов в последовательности "действий". Некоторые из стоимости требуемых для реакций промежуточных веществ. При большом количестве начальных правил-реакций для повышения скорости поиска решения задачи становится актуальных построения индекса реакций по участвующим в них веществам. Но все эти вопросы уже оптимизация алгоритма. Отложим пока это увлекательное, но отвлекающее нас занятие оптимизацией. Сосредоточимся на главном.


Алгоритм построения алгоритма для химика Прост!


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


В живой клетке также протекают цепочки химических реакций, но совершенно определенно можно утверждать, что никакой химик не контролирует там пробирками смешивание веществ. Это очень важное наблюдение, что сложная цепочка процессов (например, цикл Кальвина) может выполняться без "исполнителя" в том смысле, какой предлагается определением алгоритма. Это странно, и можно сказать, что это вовсе не имеет никакого отношения к алгоритму.


Цепочка органических реакции (Цикл Кальвина)


Но вспомним задачу, которую мы себе поставили убрать участие человека из процессов связанных с алгоритмом. Тьюринг заменил управление исполнителя-человека на управление исполнителя-компьютера. Если рассматривать химические процессы, то управление порядком смешивания пробирок, которое осуществлялось химиком, можно заменить управлением, выполняемым компьютером. Удивительно, но в живой клетке управлением очень сложными цепочками процессов как будто вообще никто не занимается. То есть этим цепочкам процессов не нужен исполнитель?


Если судить по процессам эволюции не нужен не только исполнитель. Ведь как подметил Дарвин, и подтвердили фактами многие его последователи: преобразование и развитие этих сложных цепочек процессов в клетке могут происходить самостоятельно, то есть без участия обозначенного выше химика. Это для нашего исследования алгоритма очень важно. А вот отсутствие привычного исполнителя не должно нас огорчать. Тем более что в живой клеточке он есть, только имеет структуру, отличающуюся от исполнителя-человека и исполнителя-компьютера. Нам даже полезно в текущем анализе, что структура исполнителя в клетке так сильно отличается. Полезно и то, что она очень проста. Попробуем обнаружить, где спрятался этот 'Демон Максвелла', и для этого рассмотрим, что в клетке контролирует последовательность исполнения химических реакций.


Исполнитель


Очевидно, что взаимодействие химических веществ в клетке происходит при контакте их молекул в процессе теплового движения. Эти процесс равномерно перемешивает свободные молекулы клетки и обеспечивает встречу тех, которые могут при контакте осуществить химическую трансформацию (реакцию). Что контролирует последовательность таких трансформации? Ответ прост это изменения концентрации молекул соответствующих веществ. Если концентрация C мала (или этот элемент отсутствует в клетке), то реакция производства A-C останавливается. Это не очень похоже на контроль исполнения алгоритма привычный программисту, но этот контроль работает, и циклические последовательности исполнения реакций в живой клетке происходят снова и снова и без нашего участия. В клетке можно найти более эффективную реализацию контроля исполнения, для этого нам нужно вспомнить об еще одном типе химических реакций.


Рассмотрим этот подарок природы программисту реакции, которые характеризуются использованием особенного участника. Этот участник не изменяется, но контролирует реакцию, присутствуя в ней от начала до конца взаимодействия.


Химическая реакция с катализатором


Такой компонент, который остается неизменным в процессе исполнения, но при этом ускоряет протекание реакции, химики называют катализатором. Можно долго ходить вокруг и около, но лучше сформулируем сразу.


Катализатор (необходимый компонент процесса, не изменяющийся в ходе выполнения и задающий способ преобразования других компонентов) это ещё химический, но уже более привычный нам "исполнитель алгоритма". Интересно, что если этот катализатор в дополнение имеет сложную структуру, объединяющую несколько более простых катализаторов, то он частично реализует смысл фразы "описание порядка" из терзаемого нами определения алгоритма.


Для нашего разбора одними из самых наглядных исполнителей-катализаторов в клетке являются цепочки ДНК и РНК. Если немного ориентироваться в клеточных процессах с участием ДНК(РНК), то можно, наблюдая за их исполнением, найти много интересных структурных алгоритмов. В следующем видео целая библиотека приемов программирования: параллельных процессов, работы с линейными списками, трансформациями структур, маркерами исполнения...


DNA animations for Science-Art exhibition


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


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

Отметим, что порядок исполнения в среде мы уже рассматривали ранее. Этот порядок повторяющиеся процессы среды, то есть "действия", которым была посвящена предыдущая статья.


Можно рассматривать процессы в живой клетке и далее. Тогда в дополнение к подсмотренному процессу контроля исполнения алгоритма мы найдем массу важных для программиста уже готовых алгоритмов и алгоритмов работы с алгоритмами:


  • параллелизм на основе большого количества точек контакта,
  • транскрипцию, трансляцию (контактный изоморфный перенос структуры одного объекта в другой объект с отличающимся набором составляющих элементов),
  • репликацию (контактное копирование объекта),
  • обособление функции (инкапсуляция),
  • наследование,
  • и многие другие.

Но отложим пока эти "вкусные" алгоритмы, и обязательно вернёмся к ним, когда расправимся с рецептом главного "блюда" программиста Алгоритма.


Выводы


Попробуем собрать всё, что мы отметили рассматривая пример химического "алгоритма".


  • задаваемый определением алгоритма исполнитель не всегда является объектом;
  • контроль исполнения, то есть "порядка действий", могут выполнять закономерности существующих процессов среды (таких как изменение концентрации молекул);
  • контроль исполнения ("порядка действий") может основываться на структуре объекта (например, линейной структуре ДНК);
  • если структура объекта контролирует исполнение алгоритма, и этот объект не изменяется в процессе исполнения то такой объект наиболее точно соответствует привычному смыслу слова "исполнитель" из определения алгоритма.

Чтобы разделять алгоритмы по способу контроля исполнения введём два термина, которые нам понадобятся в следующих статьях:


  • контроль исполнения, основанный на существующих в среде закономерностях процессов будем называть обусловленным исполнением.
  • контроль исполнения, основанный на структуре связей объекта-исполнителя, назовём связным исполнением, подчёркивая тот факт, что порядок контролируется именно внутренними связями объекта.

На основе текущей статьи уже можно уже начинать выписывать требования к системе "Алгоритмов над алгоритмами", поставленной в качестве главной цели работы. Похоже, что систему работающую с алгоритмами, не получится реализовать из набора компонентов меньшего состава чем обнаружено в живой клетке:


  • взаимодействие со средой;
  • начальный набор "действий";
  • система учёта "полезности" изменения в среде в результате исполнения "действия".

Да, этот набор близок к системам автоматического управления. И это хорошо, ведь эта область научно проработана, а значит её методы будут помогать нам в работе.


Другим положительным моментом в контексте текущей статьи является то, что модели процессов синтеза алгоритма на уровне изменения цепочки ДНК уже успешно используются в науке причем с двух сторон:



Здесь следует отметить, что "генетически-эволюционный" синтез алгоритмов (как тип алгоритма работы с алгоритмами) это не самый эффективный метод, который природа нам может продемонстрировать. У этого метода есть ограничения. Прежде всего они связаны с необходимостью перебора большого количества маленьких шагов изменений на большой выборке родственных исполнителей алгоритма. При этом полезность результата таких изменений никак не направляется согласно решаемой задаче и оценивается уже после совершения этих изменений, что приводит к "гибели" большей части проделанной работы (созданных, но нежизнеспособных алгоритмов). Это является недостатком только с одной стороны много "холостой" работы. Но это и достоинство: с точки зрения элементной базы, требуемой для построения такой системы работы с алгоритмами. Ведь каждый элемент и каждая операция в такой модели могут быть достаточно просты, и это не мешает системе работать изготавливать полезные алгоритмы.


Где же искать более эффективные методы работы с алгоритмом? Смотреть нужно в сторону более развитых живых организмов! В этом пути подсматривания у природы нас ждет две ключевые остановки: Память и Язык. Следующая статья серии будет посвящена синтезу алгоритма на основе процедур запоминания. Этот синтез насыщен приемами, более эффективен и, что очень странно, наименее научно проработан. Дополнительной пользой от рассмотрения синтеза алгоритма на основе памяти является возможность построить мостик между методами генетического синтеза алгоритмов и методами синтеза алгоритмов с использованием языка. Но не будем сильно забегать вперёд, ибо Память сама по себе очень полезна, и похоже описание её возможностей в алгоритмическом мире не помещается в формат одной следующей статьи.


Спасибо Вам за внимание.


Отзывы


Буду очень благодарен за отзывы, пожелания и предложения, так как они помогают мне скорректировать направление развития работы в этой области.


Отдельное волнение у меня есть по стилю повествования и форматированию, используемым в статье (кавычки, абзацы, курсив). Напишите, пожалуйста, если у Вас есть замечания к ним. Можно личным сообщением.


Ссылки


Источник: habr.com
К списку статей
Опубликовано: 14.06.2020 10:15:40
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Алгоритмы

Анализ и проектирование систем

Программирование

Алгоритм

Химические реакции

Теория

Категории

Последние комментарии

© 2006-2020, personeltest.ru