Cтраница 1
Теория алгоритмов возникла и оформилась в самостоятельную дисциплину в 30 - 40 - х гг. нашего века. Примерно в это же время, а также в последующие годы были получены решения ряда классических алгоритмических проблем математической логики, алгебры и топологии. В дальнейшем наметилась связь теории алгоритмов с кибернетикой: проектированием вычислительных устройств, программированием, моделированием биологических объектов ( хотя в довольно скромных пока масштабах), математической лингвистикой. Обнаружилось, что бывают алгоритмические проблемы ( рекурсивно) разрешимые и неразрешимые. Последние даже различают по степеням неразрешимости. [1]
Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов. [2]
Теория алгоритмов, используемая в К. [3]
Теория алгоритмов - в форме теории рекурсивных функций, машин Тьюринга и финитных комбинаторных процессов Поста - возникла в 30 - х годах, до кибернетики и ЭЦВМ. [4]
Теория алгоритмов в качестве средства для определения смысла предложений рекомендует алгоритмы. Точность и определенность алгоритмов гарантирует выполнение требований, предъявляемых к формальным языкам, наделенным семантикой. [5]
Теория алгоритмов позволяет, как говорят, конст-руктивизировать различные определения. [6]
Теорию алгоритмов, которой посвящена эта книга, мы называем содержательной в том смысле, что именно алгоритмы как таковые во всем их разнообразии являются ее предметом. В этом отношении она является противоположностью традиционных теорий, которые изучали вопросы существования и несуществования алгоритмов путем сведения вопросов к исследованию какого-либо одного узкого класса алгоритмов и потому очень многие важнейшие проблемы оставляли вне своего поля зрения. В последнее время традиционные теории алгоритмов нередко объединяют названием логические, а вышеупомянутую содержательную теорию стали называть аналитической. [7]
В теории алгоритмов такого рода проблемы, для которых может быть предложен частичный алгоритм их решения, частичный в том смысле, что он возможно, но не обязательно, за конечное количество шагов находит решение проблемы, называются частично разрешимыми проблемами. Например, проблема останова является частично разрешимой проблемой, а проблемы эквивалентности и тотальности не являются таковыми. [8]
В теории алгоритмов очень важным понятием является понятие экв ивалентности. [9]
В теории алгоритмов это составляет содержание теоремы о функции, универсальной; для частично рекурсивных функций. [10]
В теории алгоритмов и автоматов рассматриваются различные абстрактные системы ( машины, автоматы), предназначенные для моделирования функционирования дискретных систем. Их выразительная мощность, т.е. способность адекватно описывать сложное поведение моделируемых систем, часто характеризуется классами порождаемых ими языков, которые, как и в случае языков сетей Петри, определенным образом кодируют разные возможные способы функционирования систем. В теории формальных языков выделены и изучены некоторые классы языков, порождаемых системами разного типа. Эти же классы языков порождаются конечными множествами правил, называемых порождающими грамматиками. [11]
В теории алгоритмов известны некоторые задачи, о которых доказано, что для их решения не существует алгоритма. Такие задачи называются алгоритмически неразрешимыми. Обычно алгоритмическая неразрешимость новых задач доказывается методом сведения к этим задачам известных алгоритмически неразрешимых задач. Тем самым доказывается, что если бы была разрешима новая задача, то можно было бы решить и заведомо неразрешимую задачу. В самом деле, если удается свести к новой задаче неразрешимую задачу, то любой алгоритм решения новой задачи решал бы и ту задачу, что противоречило бы ее неразрешимости. Применяя метод сведения, обычно ссылаются на искусственные задачи, которые не представляют самостоятельного интереса, но для которых легко непосредственно доказать их неразрешимость. К числу таких задач относится проблема распознавания самоприменимости. [12]
В теории алгоритмов - натуральная операция, состоящая в преобразовании однобуквенного слова в пустое слово. [13]
В теории алгоритмов строго доказано, что по своим возможностям преобразования нормальные алгоритмы эквивалентны машине Тьюринга и другим моделям, уточняющим понятия алгоритма. [14]
В теории алгоритмов изучаются алгоритмы, заданные в строгом, формализованном виде. [15]