Cтраница 4
В самом деле, эта машина, увидев букву С, будет работать без конца, поочередно то стирая, то вновь записывая букву С в обозреваемой мигающей ячейке. Увидев же букву Н, она сразу останавливается. Таким образом, факт существования алгоритма В не вызывает сомнения, он доказан описанием этой машины Тьюринга. [46]
Даже в тех задачах, где существование алгоритмов и возможные способы их построения очевидны, все же может потребоваться довольно много труда для их воплощения в нечто полезное с точки зрения практического использования. Иной раз небольшая догадка или искусный ход могут в значительной степени упростить алгоритм или же многократно увеличить его быстродействие. [47]
Существование алгоритма слияния, не требующего резервных объемов памяти, очевидно для случая, когда размер меньшего из двух сливаемых массивов равен единице. Из сказанного выше по индукции следует, что алгоритм слияния, не использующий резервных объемов памяти, существует при произвольных размерах сливаемых массивов. Оператор слияния, не использующий резервных объемов памяти, представляет собой рекурсивную процедуру, описание которой непосредственно вытекает из доказательства существования алгоритма. [48]
Рассмотренный выше случай представляет в основном теоретический интерес, так как на практике задачи, сводящиеся к простым гипотезам, встречаются крайне редко. Но даже в том случае, когда параметр, характеризующий семейство распределений наблюдаемых данных, является непрерывным и одномерным ( одномерные параметры будем обозначать греческими буквами 6 с индексами и без индексов), для существования РНМ алгоритмов необходимо, чтобы семейства распределений удовлетворяли некоторым дополнительным требованиям. Рассмотрим этот случай подробнее, для чего нам понадобится понятие монотонного отношения правдоподобия. [49]
Переходим к рассмотрению понятия алгоритма. Пусть задано бесконечное множество задач и каким-нибудь обр-азом указано, что понимается под решением каждой из них. Будем говорить, что существует алгоритм для решения данного бесконечного множества задач, если существует единый способ, позволяющий для каждой задачи этого множества в конечное число шагов найти ее решение. Иными словами, существование алгоритма означает наличие единого способа, который для каждого слова алфавита Л, кодирующего какую-нибудь задачу данного множества, позволяет в конечное число шагов найти слово алфавита Л, кодирующее решение этой задачи. [50]
Не для всякой вычислимой функции можно реально осуществить вычисление ее значения. Существование алгоритма не означает, что нам по силам проделать все предписанные действия. Препятствие может заключаться в том, что требуемые для этого вычисления ресурсы слишком велики. Поэтому нас интересует не столько существование алгоритма для решения задачи, сколько существование эффективного алгоритма. [51]
Существенно, что уже на первом шаге возникает возможность постановки и решения ряда содержательных вопросов. А именно, устанавливаются условия, обеспечивающие разрешимость изучаемых задач. Эти условия определяют по сути дела непротиворечивость прецедентной и дополнительной информации. Они же, естественно, оказываются условиями существования корректного алгоритма - решения. [52]
В класс Е1 входят задачи, имеющие для своего решения экспоненциальные алгоритмы, но относительно которых неизвестно, существуют для них полиномиальные алгоритмы иди нет. К этому классу относится большинство задач дискретно. Дня ряда задач получен отрицательный ответ на возможность построения полиномиального алгоритма, но вопрос существования экспоненциального алгоритма не решен. На рис. 22 изображена схема перехода задач из класса в класс, который постоянно происходит в связи с ведущимися во всем мире исследованиями в области построения алгоритмов. [53]
Основной смысл метода эвристического ветвления [1, 2] состоит в следующем. Тогда задача эксперта, осуществляющего поиск решения, состоит в том, чтобы указать наиболее перспективное, по его мнению, направление или упорядочить все возможные направления по эвристической оценке их перспективности. После этого с помощью ЭВМ порождаются допустимые решения, принадлежащие всем возможным направлениям, однако основное внимание сосредоточивается на тех направлениях, которые эксперт считает наиболее перспективными. Результаты работы машины выдаются эксперту, он их анализирует, уточняет свои предположения и процедура переходит к следующему шагу, аналогичному предыдущему. При этом предполагается существование реализуемых алгоритмов для порождения допустимых решений, принадлежащих заданным направлениям поиска. [54]