НОРМАЛЬНЫЙ АЛГОРИФМ, одно из совр. уточнений понятия алгоритма, получившее распространение в исследованиях по конструктивной математике. Предложено в 1950 А. А. Марковым, впервые систематически и строго построившим на основе этого уточнения общую алгоритмов теорию. Н. а. эквивалентны частично-рекурсивным функциям (см. Рекурсивные функции), а следовательно, и Тьюринга машинам.
Концепция Н. а. специально приспособлена для реализации алгоритмов, действующих над словами в тех или иных алфавитах. При этом под алфавитом в математике понимается любой конечный набор чётко отличимых друг от друга графических символов (букв), а под словом в данном алфавите - произвольная конечная цепочка букв этого алфавита. Цепочка, вовсе не содержащая букв, также считается словом в данном алфавите (пустое слово). Напр., цепочки "ииаам", "книга", "гамма" являются словами в русском алфавите, а также в шестибук-венном алфавите {к, н, и, г, а, м}. Элементарным актом преобразования слов в алгоритмических процессах, задаваемых Н. а., является т. н. операция "подстановки вместо первого вхождения". Пусть Р, Q, R - слова в нек-ром алфавите. Результатом подстановки Q вместо первого вхождения Р в R наз. слово сумма (R, Р, Q), получаемое след, образом. Если Р входит в R, т. е. R представимо в виде S1PS2, то среди таких представлений отыскивается представление с наиболее коротким словом S1 и полагается сумма (К, Р, Q) = S1QS2. Если же Р не входит в R, то сумма (R, Р, Q) = R. Так, сумма (гамма, а, е) = гемма.
Формулы подстановок принято записывать друг под другом в порядке следования, объединяя их слева фигурной скобкой. Получающаяся фигура наз. схемой Н. а. Исходными данными и результатами работы Н. а. U являются слова в А (сам Н. а. U наз. Н. а. в алфавите Л). Процесс применения к слову R H. а. U со схемой вида
Смотреть больше слов в «Большой советской энциклопедии»
одно из современных уточнений понятия Алгоритма, получившее распространение в исследованиях по конструктивной математике (См. Конструктивная ма... смотреть
- название, закрепившееся за алгоритмами некоторого точно охарактеризованного типа. Наряду с рекурсивными функциями и Тьюринга машинами Н. а. получи... смотреть
НОРМА́ЛЬНЫЙ АЛГОРИФМ алгорифм преобразования слов в нек-ром конкретном алфавите (при этом слово рассматривается как общая форма конструктивного объе... смотреть
алгорифм преобразования слов в нек-ром конкретном алфавите (при этом слово рассматривается как общая форма конструктивного объекта). Всякий Н. а. вполне определяется заданием алфавита, в к-ром он действует, и списка формул подстановок (схем) в этом алфавите; совокупность предписаний, определяющих применения схем к словам, и наз. Н. а. Понятие Н. а. является одним из уточнений общего понятия алгоритма. См. также Конструктивное направление. ... смотреть