Некоторые вопросы к теории алгоритмов

В теории алгоритмов, составной части естественной науки кибернетики, исследуя удобства решения тех или иных задач, исследователи пришли к мнению, что существует проблема сравнения классов алгоритмов P = или ≠ NP, значение которой подняли до уровня проблем тысячелетия. На общепринятом языке она звучит так:  может ли, реализация алгоритма проверки правильности решения задачи, быть более длительной, нежели реализация алгоритма самого получение решения. Иными словами, действительно ли решение задачи проверить не легче, чем его отыскать? Для решения этой проблемы предлагаются критерии сравнения алгоритмов, которые рассматриваются в ее разделе вычислительной сложности. Анализируя содержание этого раздела, невольно возникает вопрос: «А что в теории алгоритмов понимается под сложностью?» Так, для сравнения алгоритмов весьма часто используют сложность алгоритма  по Колмогорову. Это когда алгоритм оценивается количеством операций, требуемых для его реализации. Такой же количественный подход в оценке вычислительной сложности заложен и в сравнении времени выполнения алгоритма на средствах вычислительной техники. В обоих этих подходах сравнение сложности алгоритма сводится к количественной оценке – числу операций, либо длительности реализации вычислительного процесса. Следует заметить, что в этих подходах используется количественная мера, которая, никоим образом, не проливает свет на сложность алгоритма. Она позволяет судить лишь об объеме обработки информации (количестве операций, или времени их выполнения). По этому использование этой меры в сравнительных оценках для определения сложности алгоритма – не обосновано. Иными словами, исходя из такой количественной меры, неуместными являются выражения – полиномиальная сложность, NP полная сложность.

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

В теории алгоритмов, для их оценки, используются понятие функции характеризующей алгоритм. Тогда возникает вопрос: «Каким образом определяется  эта функция изменения количества операций в зависимости от количества входных данных?» Выше был частично получен ответ на этот вопрос, который сведен к определению измерения затрат на время вычислений в средствах обработки информации. С нашей точки зрения, этот подход нахождения искомой функции не эффективный. Он может частично определить ее вид на основании, той алгоритмической системы, которая положена в основу конкретного, в данном случае, используемого средства обработки. А если изменить эту систему, причем, наделив команды машины кардинально новым видом обработкой информации. Кроме того, если использовать принципиально новое средство обработки, которое позволит использовать  и другой алгоритм решения задачи. Иными словами, применяемый в современной теории алгоритмов способ определения интересующей нас функции, для анализа алгоритма неинформативный. Если воспользоваться табличным методом поиска этой функции, то результат его будет таким же. По этому, не  определив функцию изменения количества операций от изменения количества ее переменных, которая должна характеризовать алгоритм, очень сложно давать ему оценку. Эта функция, согласно современным взглядам, может изменяться согласно полиномиальной зависимости, либо экспоненциальной, а что если она имеет совершенно иной вид.  Конечно, выбрав самый крайний случай решения задачи, методом перебора, можно указывать на экспоненту, но может оказаться, что рассматриваемая задача решается и другим алгоритмом, который  никакого отношения к экспоненте не имеет. В этом месте следует, также, заметить, что для оценки алгоритма использовать операции  машины Тьюринга, либо Поста, команды, или операторы других алгоритмически универсальных систем типа системы Маркова, или Колмогорова-Успенского  в силу мелких в них информационных единиц, которые обрабатываются, не только не информативно, но и абсурдно.

Рассмотренные выше, вопросы к теории алгоритмов невольно приводят и к следующему вопросу. В чем состоит сущность проблемы тысячелетия P = или ≠ NP, и какое отношения она имеет к естествознанию? Напомним, что эта проблема относится к теории алгоритмов, которая является составной частью естественной науки кибернетика. Развитие ее неразрывно связано с применением математического аппарата, причем эта связь настолько «сильна», что признаки естествознания в ней очень часто опускаются в публикациях. В результате, отмеченная выше проблема вошла не в естествознание, а в список «чисто» математических проблем тысячелетия. Читатель может возразить, что, оттого, что она не туда вошла, ее значение не изменилось. Однако она оказалась «перед  глазами» не у тех специалистов, которые ее должны были бы решать, а это, если не замедляет, то в худшем случае исключает ее разрешение. Есть тому аналогичный пример, когда Д.Гильберт в 1900 году поместил в свои 23 математические проблемы шестую проблему «математически обосновать аксиомы физики», то ей пришлось ожидать своего решения более ста лет. И это несмотря на то, что эквивалентная ей  вторая проблема «чисто математическая», из того же перечня, получила свое решение уже через 30 лет.  А так, указанной шестой проблеме пришлось, как уже об этом упоминалось, еще долго ожидать своего разрешения, пока она,  независимо от Д.Гильберта, была востребована и сформулирована исследователями в области естествознания. Известно, что ее пытались разрешить многие математики, включая и самого Гильберта, и, не понимая ее сути, стали приходить к мнению, что она сформулирована расплывчато, а физики, просто «отмахивались», считая, что ее должны решать математики – это их забота.

В перечне задач, касающиеся рассматриваемой проблемы тысячелетия, есть задачи, которые относятся к математическим абстракциям, а есть таковы, что отображают, в какой то мере, природные структуры и явления. Использование математики в познании природы, приводит к образованию множества абстракций, значительно большего, нежели множество всевозможных структур и явлений, которые предлагает природа. Множество математических абстракций, описывающих природу, входит во множество всех абстракций, которые уже изобретены и могут быть дополнены, по мере развития математики и процесса познания. Оказалось, что между этими двумя множествами изоморфизма не существует, т.е. не каждая, искусственно созданная, математическая абстракция имеет во множестве природных структур себе прообраз.  А что касается мономорфизма, т.е. одностороннего отображение природных структур на математические абстракции, то такое отображение имеет место.  Заметим, что задачи, отображающие различные материальные структуры и явления, несмотря на то, что мы их можем не знать, уже давно решены природой, а если не решены в настоящее время человеком, то их не нужно причислять к рассматриваемой проблеме тысячелетия. Иными словами, решение задач, которые отображают природные структуры и явления, по своей сути, не составляют проблемы – их решение может быть осуществлено, по аналогии тому, как оно имеет место в природе. Что же касается той части задач, которая относится к абстракциям и не имеет никакого отношения к описанию  природы, то они носят «чисто» искусственный характер и не все из них имеют решения, поскольку часть из них была заранее, при изобретении, рассчитана на это. Примеров таких задач можно привести довольно много. Таким образом, если исследовательский процесс связывать с познанием природы, то проблема тысячелетия, отображенная в выражении P = или ≠ NP для природы не актуальна,  поскольку она ею уже решена, а для человека (согласно принципу гносеологии) – дело времени.

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

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

Возникает вопрос: «А что эти требования обязательны и к итерационному алгоритму, выполнение которого может быть продлено к бесконечному «количеству элементарно выполнимых предписаний», «конечности действий», когда требуется  во время счета удовлетворять нужной его точности?»

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

И, наконец, последнее требование, согласно которому алгоритм обязательно должен приводить к искомому результату. В этом случае возникает вопрос: «А что алгоритм Гаусса не может быть отнесен к разряду алгоритмов, если с его помощью, решение системы линейных уравнений, описывающей матрицей очень большого порядка, теряет всякий здравый смысл, за счет большого количества округлений. Более того, а если определитель  этой матрицы равен нулю, то алгоритм Гаусса вообще не применим к рассматриваемой системе уравнений. В то же время она решается  с помощью итерационного алгоритма.

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

 

 

Работает на Drupal, система с открытым исходным кодом.