АЛГОРИТМОВ СОЧЕТАНИЯ это:

АЛГОРИТМОВ СОЧЕТАНИЯ

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

В применении к нормальным алгорифмам наибольшую известность получили следующие А. с.: нормальная композиция двух нормальных алгорифмов .нормальное объединение двух нормальных алгорифмов нормальное разветвление двух нормальных алгорифмов управляемое нормальным алгорифмом нормальное повторение нормального алгорифма , управляемое нормальным алгорифмом . Если - нормальные алгорифмы в нек-ром алфавите А, то упомянутые их сочетания являются нормальными алгорифмами в нек-ром фиксированном расширении Аи удовлетворяют следующим условиям: а) для любого слова в имеет место (теорема композиции); б) для любого слова Рв Аимеет место (теорема объединения); в) для любого слова Рв А


причем если ( определено, то определено и (теорема разветвления); г) для любых слов и в A графическое равенство имеет место тогда и только тогда, когда может быть указан ряд слов в алфавите таких, что


(теорема повторения). Аналогичные теоремы могут быть получены и для Тьюринга машин. В теории рекурсивных функций наибольшее употребление нашли их сочетания, доставляемые оператором подстановки, оператором примитивной рекурсии и m-оператором.

Теоремы об А. с. вскрывают весьма существенную особенность осуществленных стандартизации общего понятия алгоритма - их "устойчивость" по отношению к естественным способам А. с. Это обстоятельство является одним из наиболее веских доводов в пользу основной гипотезы теории алгоритмов ( Чёрча тезиса). Теоремы об А. с. составляют важный раздел общей теории алгоритмов. Будучи доказаны однажды, они позволяют в дальнейшем убеждаться в осуществимости сложных и громоздких алгоритмов без фактического выписывания определяющих их схем.

Значительный интерес для общей теории алгоритмов представляет вопрос о разыскании базиса, позволяющего при фиксированном наборе способов А.- с. порождать любой алгоритм к.-л. интересующего нас класса.

Лит.:[1] Марков А. А., Теория алгорифмов, "Тр. Матем. ин-та АН СССР", 1954, т. 42, с. 94-145; [2] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; [3] Успенский В. А., Лекции о вычислимых функциях, М., 1960; [4] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965. Н. М. Нагорный.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "АЛГОРИТМОВ СОЧЕТАНИЯ" в других словарях:

  • Информация — (Information) Информация это сведения о чем либо Понятие и виды информации, передача и обработка, поиск и хранение информации Содержание >>>>>>>>>>>> …   Энциклопедия инвестора

  • КИБЕРНЕТИКА — (от греч. kybernetike [techne] – искусство управления) – наука о самоуправляющихся машинах, в частности о машинах с электронным управлением («электронный мозг»). Кибернетика получила самое широкое распространение в последней трети 20 в. и сейчас… …   Философская энциклопедия

  • § 245-250. ТРАНСЛИТЕРАЦИЯ — § 245. Транслитерация это система точной передачи букв алфавита одного языка средствами иной графической системы, зачастую буквами или сочетанием букв алфавита другого языка. Транслитерация в отличие от транскрипции служит передаче не звучания, а …   Правила русского правописания

  • ГОСТ Р 53953-2010: Электросвязь железнодорожная. Термины и определения — Терминология ГОСТ Р 53953 2010: Электросвязь железнодорожная. Термины и определения оригинал документа: 39 (железнодорожная) телеграфная сеть: Сеть железнодорожной электросвязи, представляющая собой совокупность коммутационных станций и узлов,… …   Словарь-справочник терминов нормативно-технической документации

  • Суверенитет — (Sovereignty) Суверенитет это независимость государства от других стран Суверенитет России и его проблемы, суверенитет Украины, суверенитет республики Беларусь, суверенитет Казахстана, суверенитет Чечни, Проблемы суверенитета стран Европы,… …   Энциклопедия инвестора

  • КОМБИНАТОРНЫЙ АНАЛИЗ — комбинаторная математика, комбинаторика, раздел математики, посвященный решению задач выбора и расположения элементов нек рого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения… …   Математическая энциклопедия

  • Роснефть — (Rosneft) Компания Роснефть, история создания компании Роснефть Компания Роснефть, история создания компании Роснефть, перспективы развития Роснефти Содержание Содержание 1. История 1990 е годы 2000 е годы 2. сегодня География деятельности… …   Энциклопедия инвестора

  • Эволюция — Эта статья  о биологической эволюции. Другие значения термина в заглавии статьи см. на Эволюция (значения). Фи …   Википедия

  • Канадское слоговое письмо — Тип: абугида Языки: кри …   Википедия

  • Канадская слоговая азбука — Канадское слоговое письмо Тип: абугида Языки: кри, оджибва, наскапи, инуктитут и другие Место возникновения: Канада Территория: Канада …   Википедия

Книги

  • Структуры данных и проектирование программ, Круз Р. Л.. В качестве фундаментальных средств разработки программ рассматриваются такие вопросы, как структурное решение задач, абстракция данных, принципы программной инженерии и сравнительный анализ… Подробнее  Купить за 440 руб
  • Коморбидный пациент, Вёрткин, Аркадий Львович. Реальный пациент, особенно пациент в возрасте, обычно страдает от сочетания нескольких заболеваний. Такая коморбидность делает неприменимым устоявшийся подход клечению – лечению по отдельным… Подробнее  Купить за 282 руб
  • Коморбидный пациент, Верткин Аркадий Львович. Реальный пациент, особенно пациент в возрасте, обычно страдает от сочетания нескольких заболеваний. Такая коморбидность делает неприменимым устоявшийся подход клечению - лечению по отдельным… Подробнее  Купить за 276 руб
Другие книги по запросу «АЛГОРИТМОВ СОЧЕТАНИЯ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»