Cтраница 3
Теория алгоритмов возникла и оформилась в самостоятельную дисциплину в 30 - 40 - х гг. нашего века. Примерно в это же время, а также в последующие годы были получены решения ряда классических алгоритмических проблем математической логики, алгебры и топологии. В дальнейшем наметилась связь теории алгоритмов с кибернетикой: проектированием вычислительных устройств, программированием, моделированием биологических объектов ( хотя в довольно скромных пока масштабах), математической лингвистикой. Обнаружилось, что бывают алгоритмические проблемы ( рекурсивно) разрешимые и неразрешимые. Последние даже различают по степеням неразрешимости. [31]
Для этого достаточно представить i; в виде последовательной композиции трех программ: программы перевода из десятичной системы в унарную, программы 31, программы перевода из унарной системы в десятичную, ( Здесь напрашивается сравнение с электронными вычислительными машинами, работающими в двоичной системе счисления; в них имеется устройство, или программа, для пераработки исходных данных из десятичной системы в двоичную, а также устройство, или программа, для перевода окончательной программы опять в десятичную систему. Полезно заметить, что хотя мы намерены уделять главное внимание вычислению числовых функций, тем не менее это не ограничивает по существу природы алгоритмических проблем, решаемых на машинах Тьюринга. Поскольку такое же замечание можно сделать и относительно слова, изображающего результирующие данные, то ясно, что алгоритм поиска решения задачи можно интерпретировать как алгоритм вычисления значения числовой функции по заданному значению ее аргумента. Подобная арифметическая интерпретация ( или короче - арифметизация) часто применяется в математической логике и теории алгоритмов; мы с ней еще встретимся в данном параграфе. [32]
Соответственно двум возможным альтернативам, алгоритмическую проблему называют разрешимой или неразрешимой. Алгоритмические проблемы рассматриваются преимущественно для полугрупп, заданных тем или иным эффективным способом; наиболее типично их рассмотрение для полугрупп, заданных определяющими соотношениями. [33]
Свойство комплекса быть стягиваемым или замкнутого многообразия - гомеоморфным сфере 5 - становится алгоритмически нераспознаваемым для п 3 ( комплексы) и п 5 ( многообразия), как отметил С.П.Новиков в начале 1960 - х гг., используя конструкции гомологической алгебры, хотя для п 4 ответ также вряд ли положителен. Заметим, что проблема гомеоморфизма двумерных комплексов и проблема гомеоморфности трехмерного многообразия с краем стягиваемому, вероятно, разрешимы. Простейшие алгоритмические проблемы теории трехмерных замкнутых многообразий и узлов, по-видимому, также разрешимы, хотя пример задачи о распознавании тривиального узла ( выше) показывает, что, ввиду алгебраических сложностей теоретико-групповыми методами, несмотря на наличие критерия тривиальности узла, этот вопрос не удается завершить. [34]
Рольф [402] доказывает, что структура FM ( 2 2 2) содержит бесконечную цепь. Заметим, что-все основные алгоритмические проблемы для модулярных структур остаются открытыми. Элемент а структуры с отношением А и с I называется нормальным ( субнормальным), если а А 1 ( соотв. Это понятие нормального элемента является обобщением нормального делителя в структуре подгрупп группы, отличное от известного понятия нормальности в смысле Куро-ша. [35]
Конечная цель специальной теории сетей Петри - автоматический анализ свойств сетей, их автоматические синтез и преобразования, на основании чего могут быть построены практические алгоритмы анализа, синтеза и преобразований дискретных систем, моделируемых сетями. В частности, полезно найти алгоритмы, с помощью которых для любой предъявленной сети можно установить, обладает ли она интересующим нас свойством - является ли она ограниченной, живой, устойчивой и т.п. В первую очередь нужно выяснить существование таких алгоритмов. Эти вопросы формулируются как массовые алгоритмические проблемы для сетей: проблема ограниченности ( существует ли алгоритм, который позволяет узнать, является ли данная сеть ограниченной), проблема потенциальной живости переходов, проблема живости сетей, проблема устойчивости, проблема безопасности. Говорят, что проблема разрешима, если соответствующий алгоритм распознавания свойств существует, в противном случае проблема неразрешима. [36]
Доказан следующий результат о равносильности различных концепций понятия алгоритма: классы функций, вычислимых на машинах Тьюринга, частично рекурсивных функций, вычислимых с помощью нормальных алгорифмов Маркова ( аналогичные классы функций при других концепциях понятия алгоритма), совпадают. По мнению большинства современных математиков, этот класс функций адекватен классу интуитивно В. Такое отождествление позволяет придать математичность алгоритмическим проблемам. [37]
Этот факт, установленный в 1936 А. Church), является одним из фундаментальных результатов общей алгоритмов теории. На нем основаны ( или могут быть основаны) все известные отрицательные решения алгоритмических проблем. [38]
Принятые соглашения позволяют проводить анализ многих естественных и компактных программных реализаций алгоритмов сортировки массивов. В разделах 6.7 и 6.8 рассматривается драйвер, который служит иллюстрацией того, как следует использовать реализации сортировок в более общих контекстах, а также различные реализации типов данных. И хотя мы всегда будем уделять должное внимание требованиям к организации программных пакетов, основные усилия будут направляться на решение алгоритмических проблем, к рассмотрению которых мы сейчас и переходим. [39]
Определение понятия алгоритма было использовано, для доказательства несуществования алгоритмов для решения того или иного класса задач. Так, например, Черч показал, что не существует алгоритма, решающего проблему разрешимости исчисления предикатов. Проблемы, заключающиеся в отыскании алгоритма, решаю -, щего ту или иную бесконечную серию однотипных задач, получили название алгоритмических проблем. Неразрешимость алгоритмической проблемы означает, что, искомый алгоритм невозможен. В последнее время no - J лучен ряд результатов, относящихся к неразрешимости алгоритмических проблем в различных разделах математики. Эти результаты являются приложением математической логики к вопросам, лежащим вне ее. [40]
Переходя к многокомпонентной динамике сорбции, следует подчеркнуть, что в практических приложениях значение этого раздела теории возрастает. В то же время количество публикаций по динамике смеси явно недостаточно. Эта ситуация в значительной мере объясняется теми математическими трудностями, которые возникают при попытках распространить локально-детерминированную модель ( 1) - ( 5) для описания динамики смеси. Хотя чисто алгоритмические проблемы и могут быть решены, эксплуатация программ на ЭВМ требует несоразмерно больших затрат машинного времени, причем по мере увеличения числа компонентов эти затраты резко возрастают. [41]
Определение понятия алгоритма было использовано, для доказательства несуществования алгоритмов для решения того или иного класса задач. Так, например, Черч показал, что не существует алгоритма, решающего проблему разрешимости исчисления предикатов. Проблемы, заключающиеся в отыскании алгоритма, решаю -, щего ту или иную бесконечную серию однотипных задач, получили название алгоритмических проблем. Неразрешимость алгоритмической проблемы означает, что, искомый алгоритм невозможен. В последнее время no - J лучен ряд результатов, относящихся к неразрешимости алгоритмических проблем в различных разделах математики. Эти результаты являются приложением математической логики к вопросам, лежащим вне ее. [42]
Теория алгоритмов возникла и оформилась в самостоятельную дисциплину в 30 - 40 - х гг. нашего века. Примерно в это же время, а также в последующие годы были получены решения ряда классических алгоритмических проблем математической логики, алгебры и топологии. В дальнейшем наметилась связь теории алгоритмов с кибернетикой: проектированием вычислительных устройств, программированием, моделированием биологических объектов ( хотя в довольно скромных пока масштабах), математической лингвистикой. Обнаружилось, что бывают алгоритмические проблемы ( рекурсивно) разрешимые и неразрешимые. Последние даже различают по степеням неразрешимости. [43]
В последующие годы в универсальной алгебре выделяется два основных направления. Первое из них связано с изучением свойств алгебраических систем и описанием этих свойств различными логическими средствами. Это приводит к рассмотрению классов алгебраических систем и способов конструирования классов. Второе направление связано с алгоритмическими проблемами алгебры, и оно также инспирировано исследованиями по логике. [44]
Обо всех словах Q, к-рые при этом получаются ( в том числе и о самом исходном слове Р), говорят, что они эквивалентны Р в А. Это позволяет естественным образом сопоставить всякому А. Отсюда становится понятной важность исследования разрешимости алгоритмической проблемы распознавания эквивалентности слов в произвольном А. Эта проблема была впервые сформулирована А. Туз [1]; она заключается в том, что для произвольного А. [45]