Для чего разрабатываются специальные алгоритмы
Большая Энциклопедия Нефти и Газа
Специальный алгоритм
Специальные алгоритмы позволяют достигнуть максимальной эффективности одновариантного анализа, так как дают возможность наиболее полно учитывать специфические особенности конкретных объектов. Однако область применения таких алгоритмов ограничена. [2]
Специальный алгоритм поиска позволяет отказаться от полного последовательного перебора всех открытых маршрутов и осуществить целенаправленное движение по графу к оптимальному проектному решению. [3]
Специальный алгоритм дешифровки при шифровании с открытым ключом не нужен. Для расшифровки нужно выполнить алгоритм шифрования с другим ключом, который называется обратным к исходному. [4]
Много специальных алгоритмов унификации для простых теорий уже было разработано ранее, что вызвано их важными приложениями в теории и практике машинной обработки информации. Сейчас мы дадим краткое изложение формализма, в котором выражаются наши проблемы. [6]
Принятие специальных алгоритмов позволяет использовать простую, постепенную перегонку для светлых нефтепродуктов и для определения фракционного состава тяжелых нефтепродуктов. [10]
Принятие специальных алгоритмов позволяет использовать простую, постепенную перегонку для светлых нефтепродуктов и для определения фракционного состава тяжелых нефтепродуктов. [11]
Затеи используют специальный алгоритм для вычисления производительности. [12]
ЭС использует специальный алгоритм для систематического перечисления всех возможных молекулярных структур, а затем применяет знания по химии для сокращения этого списка до обозримого размера. Знания в DENDRAL представлены в виде процедур для генератора молекулярных структур и в виде ПП для управления данными и вычислительных программ. ЭС реализована на языке Интерлисп и разработана в Станфордском университете. [14]
Двадцать вопросов, которые помогают разработать алгоритм
Как разработать алгоритм, решающий сложную задачу? Многие считают, что для этого нужно «испытать озарение», что процесс этот не вполне рационален и зависит от творческой силы или таланта.
На самом деле решение любой задачи сводится к сбору информации о наблюдаемом объекте. Причем этот принцип применим как для решения самых сложных научно-исследовательских задач, так и для решения прикладных задач. Работа изобретателя напоминает не столько работу волшебника, сколько путешествие первооткрывателя по неизведанной территории. Главное качество хорошего изобретателя – умение собирать информацию.
Если вы хотите решить сложную задачу, собирайте информацию в самых разных направлениях. Ответив на следующие 20 вопросов, вы легко выстроите план работы над задачей.
Вопрос №1. Кто?
Начиная решать определенную задачу, составьте максимально длинный список людей, имеющих непосредственное отношение к ее решению. Выясните:
— кто в первую очередь заинтересован в ее решении?
— кто уже занимался решением этой или смежной задачи?
— кто определяет, хорошо задача решена или плохо?
— с кем можно советоваться по ходу решения задачи?
— кто может проверить решение?
— кто является автором статей в этой области?
Вопрос №2. Для чего?
Спросите себя несколько раз: «Почему я хочу решить эту задачу? Для чего это нужно?» Часто оказывается, что решение задачи A необходимо для того, чтобы решить задачу B, но при этом задачу B можно решить и другим путем. В этом случае, начиная думать над исходной задачей А, мы лишь теряем время.
Вопрос №3. Как?
Какими методами я буду руководствоваться, решая данную задачу? Как будет структурирован процесс ее решения? Есть ли готовые методологии, которые можно использовать?
Вопрос №4. Что?
Какие объекты присутствуют или подразумеваются в данной задаче? Нарисуйте их на бумаге и обозначьте стрелками всевозможные отношения между ними, связанные с данной задачей. Есть ли неучтенные или лишние объекты?
В каждый объект должны приходить и из каждого объекта должны исходить примерно одинаковое количество стрелок. В противном случае, как правило, мы либо упускаем важные связи между объектами, либо придаем неоправданно большое значение некоторым связям.
Вопрос №5. Когда?
Посмотрите на задачу с точки зрения времени. Выясните:
— как быстро должны работать отдельные блоки алгоритма?
— какие внешние факторы, связанные со временем, могут повлиять на их работу?
— сколько времени есть у вас на разработку, программирование и тестирование алгоритма?
Вопрос №6. Где?
Посмотрите на задачу с точки географической точки зрения. Ответьте на вопросы:
— где, в каких странах, городах, районах будет использоваться ваше решение?
— на каких компьютерных платформах оно будет работать?
— какие еще вопросы, связанные с месторасположением и географией, имеют отношение к данной задаче?
Вопрос №7. Что было?
Какие решения данной задачи существовали год, два, десять, сто лет назад? Ни одна задача не возникает на пустом месте – скорее всего, люди уже справлялись с этой проблемой в прошлом. Интересно и полезно бывает узнать, как именно это происходило.
Вопрос №8. Что есть?
Какие решения этой задачи существуют и используются сегодня? Выясните это и добейтесь четкого понимания альтернативных решений, доступных уже сейчас.
Вопрос №9. Что будет?
Как будут решать эту же задачу люди через три, пять, десять, сто лет? Определите этот тренд хотя бы приблизительно, подумайте над этой темой, пофантазируйте.
Прекрасно, если алгоритм, над которым вы сейчас работаете, будет частью долговременного тренда, а не устареет морально через год после реализации.
Вопрос №10. Частью чего является?
Частью какой более масштабной задачи (или системы) является данная задача? А частью чего является эта более масштабная система?
Вопрос №11. Из чего состоит?
Какие более мелкие подзадачи являются частью исходной задачи? На какие части можно разбить исходную задачу? А на какие еще более мелкие части можно разбить подзадачи?
Вопрос №12. На что похоже?
На что похожа данная задача? В данном случае ассоциации могут быть сколь угодно длинными и метафоричными, и это даже хорошо. Прекрасно, если вы найдете сходное явление в совершенно другой области человеческой деятельности.
Это очень мощный вопрос. Именно на аналогиях между совершенно неожиданными областями знания находятся самые красивые и гармоничные решения.
Вопрос №13. Что вижу?
Визуализируйте задачу, ее решение и все его компоненты. Нарисуйте их. Побудьте ребенком (или дизайнером), найдите наиболее подходящие цвета (даже для виртуальных, абстрактных объектов). Прочувствуйте визуальную гармонию этой задачи или найдите «некрасивые», проблематичные места, если такие есть.
Вопрос №14. Что слышу?
Это очень сложный и полезный вопрос, поскольку та мощнейшая часть мозга, которая отвечает за обработку звуковой информации, у большинства современных людей слаборазвита. При этом я знаю гениальных ученых и инженеров, которые именно «слышат» решение той или иной задачи.
Итак, постарайтесь «услышать» взаимодействие всех элементов задачи (для этого удобным бывает закрыть глаза), услышать характерные звучания ее элементов. Услышьте разговоры и тембры голосов людей, применяющих решение вашей задачи на практике.
Вопрос №15. Что чувствую?
Этот вопрос также может показаться необычным, хотя и не в такой степени, как предыдущий. Ощутите тактильные, температурные, вкусовые, дыхательные ассоциации, вызываемые данной задачей. Некоторые решения могут показаться «крепкими», в то же время как другие «холодными» или даже «горькими».
Подключите часть вашего мозга, отвечающую за ощущения, к анализу задачи. Конечно, это нестандартный путь анализа научной информации, но он также бывает полезным.
Вопрос №16. Каким может быть идеальное решение?
Пофантазируйте, как можно решить эту задачу в идеале; придумайте что-то совершенно невероятное — чем невероятнее, тем лучше. На этом принципе построен метод «мозгового штурма», когда предлагаются любые, даже самые неожиданные решения.
Представьте себе, что у вас нет границ, а условия работы самые благоприятные. Что бы вы могли сделать в этой ситуации?
Как можно было бы сделать решение этой задачи совершенно великолепным?
Вопрос №17. Почему все закончится неудачей?
Побудьте брюзгой и пессимистом-критиком. Найдите все причины, из-за которых у вас не получится решить эту задачу; а также все организационные проблемы, которые приведут к провалу этого проекта. Тщательно их запишите — чем больше, тем лучше.
Когда вы выйдете из состояния критики, записанное станет бесценной информацией о тех опасностях, которые поджидают вас на пути решения задачи, и от которых следует уклониться.
Вопрос №18. В чем польза для меня?
Какие выгоды лично вы извлечете из решения данной задачи? Чему научитесь? Сколько заработаете? Какие важные связи и контакты приобретете? Как улучшите свою репутацию?
Вопрос №19. В чем польза для других?
Какую именно пользу от решения этой задачи получит заказчик, клиент, тот человек, который будет пользоваться результатами вашего труда? Имеет ли решение вашей задачи большое значение для него?
Вопрос №20. В чем польза для общества?
Как повлияет решение вашей задачи на все общество, в котором мы живем? Будет ли она общественно-значимой? Чем и как она поможет всему человечеству в целом?
Уверен, что ответив на все эти вопросы, вы узнаете намного больше о той задаче, которая перед вами стоит. Причем, почти наверняка, вы увидите эту задачу с самых неожиданных сторон — и ваша фантазия сама подскажет вам необычные, надежные, красивые и гармоничные способы ее решения.
Конечно, ответы на эти вопросы не всегда приводят к получению окончательного решения. Существует много других способов, методов, которые помогают найти элегантное решение сложной задачи.
И все же я уверен, что вы ощутимо улучшите свою скорость и качество решения алгоритмических задач, если используете эти 20 опорных вопросов в своей научно-исследовательской и инженерной деятельности.
Что такое алгоритм?! Часть первая
Терзаем вместе основной кирпичик программиста — Алгоритм.
Проблема
Текущее состояние в области программирования — это обучение ремеслу по большей части личной практикой или разборами примеров стороннего кода, с которым по каким-то причинам приходится сталкиваться.
В результате программированию учишься по наитию. Лишь немного в этом труде помогают сборники алгоритмов, прикладных техник и шаблонов проектирования. Общая совокупность предлагаемых ими рецептов выстраивается длинным списком, и его длина грозит каждому из прочитанных приемов быть позабытым (как была забыта 53-яя личная группа в «телеге» до введения разбиения по каталогам). Но даже тот прием, который остался в памяти, чаще всего просто является описанием прикладной задачи, в которой было успешно его использование.
Почему конкретный прием был успешен в задаче-образце? Будет ли он успешен в твоём проекте? Какие признаки проекта дают понять, что использование приёма уместно?
В личном опыте существования в профессии не раз отмечено, что каждый Junior борется с одинаковыми ветряными мельницами и постигает методы создания программ основываясь только на своих ошибках. Но ведь такие ошибки совершили уже очень многие. Почему до сих пор не создана система правил программирования, которая поможет обойти новоиспеченному кораблю-программисту подводные прибрежные камни? Ну, например, объяснение вреда использования метода «Copy-Paste» для развития кода. Если такие правила получится объяснить малым набором причин, их сформировавшим, то это объяснение обеспечит их запоминание и последующее использование в практике, тем самым поможет уклониться от бесчисленных грабель, разложенных тут и там.
Для компактного и полезного набора объяснений нужно:
Если обобщить, то нужны алгоритмы для написания и развития алгоритмов.
Задуманная серия статей не претендует на полное решение указанной проблемы. Предпринимается небесспорная попытка сделать первый шаг на пути к этому решению. Этот шаг состоит в выделении структуры и свойств главного кирпичика программиста — Алгоритма.
Задача
Сформулируем основную задачу, которую хочется решить. Для этого сначала запишем операции над алгоритмами, которые программист выполняет в ходе написания своего проекта:
Рассмотрим существующие на текущий момент варианты значения слова «алгоритм» в поисках подсказок, о том как можно работать с алгоритмами.
Так, например, формулировка «конечная совокупность точно заданных правил решения произвольного класса задач» говорит что есть возможность как-то «точно задать правила» из них собрать «совокупность» и этой совокупностью «решить» некоторый «класс задач».
Сразу возникает масса вопросов к этому определению:
Другая формулировка «набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи» говорит что есть «исполнитель», который может выполнять некоторые «действия», и при некотором «порядке» выполнения этих «действий» «решается задача». Вопросов не стало меньше:
Перечислено много вопросов, но они мало помогают в поиске методов работы с алгоритмом. Поэтому поставим себе меньшую задачу, но тоже очень нам важную. Давайте попробуем сформулировать, что делает алгоритм способом решения наших задач, и какие процессы являются для него «действиями». Даже решение этой «маленькой» задачи оказывается очень объемным для одной статьи, поэтому будем его разбивать на части. И поэтому первую статью серии целиком посвятим только «Действию» и его признакам, которые опущены в указанных выше определениях алгоритма, но являются очень важными для ответов на все заданные вопросы.
Определение алгоритма
Рассмотрим определение алгоритма, говорящее, что он — приводящая к решению задачи последовательность действий. Как программисту мне приходится писать много кода. Этот код состоит из частей. Такими частями являются и функции, и классы, и модули. Когда я пишу текст функции — я занимаюсь написанием алгоритма.
Раньше алгоритм создавали в виде блок схем и полуавтоматически компилировали в машинные коды. Сейчас я избавлен от необходимости быть художником и компилятором для написания программы. Текст моей функции — это запись алгоритма в текстовом виде — его текстовая блок-схема. Здесь можно вспомнить Scratch, где используется визуальное создание блок-схемы алгоритма без написания текста. Способ записи алгоритма сейчас не так важен.
Важно, что в написании алгоритма функции я могу использовать вызовы других функции, которые я или другой программист уже написал до этого момента. Вспоминая фразу «последовательность действий, приводящая к решению задачи», можно отметить, что функции, написанные ранее, являются моими «действиями». То есть «действия» могут быть функциями. Если обобщать, то «действия» могут быть алгоритмами.
Если «действие = алгоритм», то определение можно попробовать переписать рекурсивно «алгоритм — это приводящая к решению задачи последовательность использования существующих алгоритмов». Рекурсивные определение не самое простое, что можно записать в словаре обычного человека. Но для программиста и математика эта форма знакома. Мы умеем с ней работать, и это даёт нам преимущество в рассмотрении разных задач, разбиваемых на подобные себе подзадачи. Так давайте воспользуемся этим преимуществом.
Чтобы разрешить рекурсию нам необходимо найти:
Действие
Для начала рассмотрим «действие» и попробуем найти причину, обеспечивающую возможность использования существующего «действия» для создания нового алгоритма.
Этой причиной является возможность повторного использования «действия» с получением тождественного результата. Только тогда разработанный с использованием этого «действия» алгоритм решения некоторой задачи будет одинаково решать эту задачу снова и снова. Мы нащупали важные законы нашего мира, в котором:
Какие признаки «действия» кроме повторимости делают возможным его использование в создании алгоритма? Что является терминальным неделимым «действием»? Чтобы ответить на этот вопрос стоит рассмотреть разные примеры «действий» из нашего опыта. Программисты встречали их много раз. Это и сложение, и умножение, и установка цвета пикселя на экране. Но мы знакомы с ними и вне программирования. Вся наука основывается на повторяемых явлениях.
Закон гравитации, описывающий повторяющееся явление падения яблока, тоже может стать действием. Ведь любое яблоко будет падать на землю? Значит этот процесс можно использовать в качестве «действия»! Например решая задачу прогнать Ньютона от яблони, на которую Вы случайно забрались ранее.
Рассмотрим, что происходит при выполнении «действия». Например, во время падения яблока с ветки яблони на землю. В этом процессе происходит несколько изменений. Если вспомнить школьную физику и рассмотреть ситуацию в системе отсчета, привязанной к Земле, то сила гравитации вызывает изменение скорости яблока, разгоняя его. При этом в процессе отмечается еще одно важное изменение — уменьшается расстояние между яблоком и Землей.
В рамках примера процесса «Земля-Яблоко» можно отметить у «действия» следующие признаки:
Рассмотрим с этими признаками разные области и процессы, выделяя в них примеры «действий» и контролируя особенности указанных признаков в описании структуры «действия».
Физические процессы
Для физических систем, процессы которых мы наблюдаем в нашем мире, характерные объекты и изменения опираются на фундаментальные взаимодействия и потому их достаточно просто выделить по аналогии с гравитационным взаимодействием Земли и яблока. Например, для системы из протона и электрона или системы двух протонов.
Отдельно от этих простых взаимодействий двух объектов стоят многокомпонентные процессы, например, ядерные реакции (по структуре «действия» близки к химическим процессам, рассматриваемым далее). Сложны и процессы описываемые суммарным взаимодействием большого числа элементов, например, «идеальный газ». Пока отложим их рассмотрение и сосредоточимся на самых простых примерах.
Химические процессы
Перейдем к следующей большой области — химическим процессам. Химические реакции (например, 
) по признаку своей повторимости так же являются «действиями». Объектами в них являются атомы и молекулы. Для описания происходящих изменений необходимо немного преобразовать «физические» изменения. Так изменения параметров движения в совокупности дают нам изменение температуры в ходе химической реакции. А среди изменений расстояний между молекулами мы, игнорируя броуновское движение, можем выделить фиксацию расстояния в виде повторимого формирования и разрушения связей между частями взаимодействующих молекул. Локальность для химической реакции тоже существует — это отсутствие реакции при нахождении гидроксида натрия и соляной кислоты в разных пробирках и наличие реакции при соприкосновении веществ. Конечно, в «химической» области «действий» есть особенности не сводящиеся к молекулам, например, фотохимические реакции, где к объектам необходимо добавить фотоны. Самые простые процессы выбраны для рассмотрения намеренно.
Математические процессы
Следующей областью выберем «действия» из известных нам абстрактных алгоритмов. Самые яркие их представители — математические процессы. В этой области есть действительно «сложные случаи», но для этой статьи достаточно хорошо знакомых примеров. Рассмотрим в качестве «действия» достаточно элементарную операцию — сложение. А примером этого «действия» выберем сложение математиком двух целых чисел.
В ситуации с математиком можно выделить много объектов, но с точки зрения «действия» («сложение математиком двух целых чисел»), объекта всего три: это объект «математик», объект «первое число» и объект «второе число». В отличие от всех рассмотренных ранее объектов числа являются обозначениями, то есть виртуальными объектами. И их преобразование в алгоритме более сложно устроено нежели изменение расстояния и параметров движения объектов, как это было для «химических» действий. Подробности такого преобразования — это тема отдельной увлекательной статьи. А в рамках текущей рассмотрим древнего математика, который складывает числа, используя кучки камешков (рим. ‘calculi’), и более «современного» математика, использующего абак. Абстракции таких способов вычисления суммы не так далеко отошли от физических и химических процессов, поэтому структура процессов их «действий» полностью описывается изменениями расстояний и связей.
Интересно, что на примере древнего математика становится понятен смысл слова «сложить», которое отсылает нас к действию «класть» и к фразе «положить вместе».
Сложение и древний математик
Для математика, оперирующего камешками, сумма это «действие» со следующими характеристиками.
Сложение и математик-абакист
У математика с абаком ситуация сложнее. Кучки разделены по значению на разрядные борозды.
Можно рассмотреть самый простой абак с двумя разрядами-бороздами. Пусть он будет десятичный. Тогда один камешек на борозде десятков соответствует десяти камешкам на борозде единиц. И 10 — это максимальное количество камешков на борозде единиц. По сравнению с действием первого математика меняется представление слагаемых. И в арсенале математика уже необходимы нескольких готовых «действий».
Локальность в этих математических «действиях» описывается отсутствием взаимодействия двух слагаемых, находящихся далеко от математика, и запуском процессов сложения когда все три объекта сложения «близко». Повторяемое изменение в математическом «действии» выражается в изменении связей между камнями и удерживающими их локациями (кучками, бороздами).
Сложение и машина Тьюринга
Можно пойти чуть дальше и заменить математика в таких «действиях» на «управляющее устройство» машины Тьюринга. Тогда «ячейки ленты» машины Тьюринга будут содержать слагаемые.
При этом остаётся и признак локальности как возможность взаимодействия управляющего устройства только с текущей ячейкой ленты, и признак изменения параметров объектов, который можно описать как изменение состояния ячеек.
Подробное описание исходных и результирующих состояний объектов, а так же «действий» производящих эти изменения для сложения, исполняемого машиной Тьюринга, оставим за рамками этой статьи. Но упомянем, что перейдя к машине мы снижаем требования к исполнителю «действия», что является главным способом для создания формальных методов работы с алгоритмом. Можно поставить себе целью упрощение каждой составляющей алгоритма до состояния, когда её выполнение можно будет поручить компьютеру. Тогда в определении алгоритма не останется тёмных мест, и многочисленные вопросы, перечисленные в начале, найдут свои ответы. Пока формализован только исполнитель. Скажем спасибо за это Тьюрингу и вспомним про «действие», формализация которого уже на пороге.
Выводы
Соберём всё, что мы отметили рассматривая разные примеры «действия»:
Признак Повторимости помогает нам в создании наших алгоритмов. С его использованием мы из всех процессов выделяем те, что являются «действием» и на их основе создаём новые алгоритмы. Более того этот признак достаточно прост и на основе его формализации можно снизить требования к системе обнаруживающей и создающей «действия» и поручить это нашему компьютеру.
Следующая статья серии (Часть 2) будет посвящена рассмотрению способов, с использованием которых «действия» могут быть сгруппированы в алгоритм. Этих способов достаточно много и есть предпосылки, что их описание не получится уместить в одну статью. Напишем — увидим.
Спасибо Вам за внимание.
Отзывы
Буду очень благодарен за отзывы и предложения, так как они помогают мне скорректировать направление развития работы в области.
Отдельное волнение у меня есть по стилю и форматированию, используемым в статье (кавычки, абзацы, курсив). Напишите, пожалуйста, если у Вас есть замечания к ним. Можно личным сообщением.