АЛГОРИТМА ИЗОБРАЖЕНИЕ это:

АЛГОРИТМА ИЗОБРАЖЕНИЕ

конструктивный объект определенного вида (как правило, натуральное число или слово), содержащий в себе закодированную по фиксированным для алгоритмов данного типа правилам полную информацию об этом алгоритме. Обычно определение А. и. формулируется таким образом, чтобы процедуры получения А. и. по исходному алгоритму и восстановления исходного алгоритма по А. и. осуществлялись по возможности более просто.

Изображение нормального алгорифма в алфавите А(не содержащем букв ) определяется как слово в алфавите , получаемое следующим образом (см. [1], с. 163). В каждой формуле подстановки схемы стрелка заменяется буквой , точка (если она имеется) - буквой , а в конце так построенного слова приписывается буква . Затем полученные слова выписываются друг за другом в том порядке, в каком соответствующие им формулы подстановки шли в схеме . По существу, представляет собой всего лишь несколько иначе - в виде слова - записанную схему нормального алгорифма . По соображениям, связанным с технич. деталями определения нормального алгорифма, несколько более удобным оказывается другой тип изображения нормального алгорифма - так называемая запись нормального алгорифма (см. [1], с. 187), являющаяся результатом перевода слова в к.-л. двухбуквенный алфавит (обычно 01). Аналогичным образом может быть построено изображение программы Тьюринга машины. Роль изображения рекурсивной функции играет гёделев номер системы определяющих эту функцию равенств (см. [2], с. 221).

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

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

Длина А. и. является одной из естественных мер алгоритма сложности (объем памяти, требующейся для запоминания программы алгоритма).

Лит.:[1] Марков А. А., Теория алгорифмов, М. 1954 ("Тр. матем. ин-та АН СССР", т. 42); [2] Клин и С. К., Введение в метаматематику, пер. с англ., М., 1957.

Н. М. Нагорный.


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

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

  • АЛГОРИТМА СЛОЖНОСТЬ — описания величина, характеризующая длину описания алгоритма. В зависимости от точной концепции алгоритма А. с. описания уточняется по разному. Единого достаточно устоявшегося уточнения к настоящему моменту (1977) не существует. Ниже рассмотрены… …   Математическая энциклопедия

  • УНИВЕРСАЛЬНЫЙ НОРМАЛЬНЫЙ АЛГОРИФМ — нормальный алгорифм (н. а.) к рый в уточненном ниже смысле моделирует работу любого н. а. в алфавите A ={a1, . .., а п}.Н. а. в алфавите (. не содержит букв является универсальным для алфавита А, если для всякого н. а. в алфавите Аи для каждого… …   Математическая энциклопедия

  • Ray casting — Изображение черепа, полученное при помощи объёмного рейкастинга (Volume ray casting) …   Википедия

  • Сравнение алгоритмов выделения лиц — Содержание 1 Аннотация 2 Введение 2.1 Методы, основанные на знаниях …   Википедия

  • Shortest Path First — Алгоритмы поиска на графах A* B* Поиск в ширину Поиск в глубину Алгоритм Дейкстры Двунаправленный поиск Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Дейкстры алгоритм на графах, изобретенный Э. Дейкстрой. Находит… …   Википедия

  • Дейкстры алгоритм — Алгоритмы поиска на графах A* B* Поиск в ширину Поиск в глубину Алгоритм Дейкстры Двунаправленный поиск Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Дейкстры алгоритм на графах, изобретенный Э. Дейкстрой. Находит… …   Википедия

  • Алгоритмы масштабирования пиксельной графики — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей …   Википедия

  • Передискретизация — Иллюстрация эффекта наложения спектров (алиасинга) при уменьшении разрешения (децимации) растрового изображения. Сверху изображение, уменьшенное без фильтрации. Снизу изображение, уменьшенное с применением фильтра нижних частот. Передискретизация …   Википедия

  • Нефотореалистичный рендеринг — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Нефотореалистичный рендеринг  область компьютерной графики, посвящённая созданию методов имитации большого ра …   Википедия

  • Методы NPR — Нефотореалистичный рендеринг область компьютерной графики, посвящённая созданию методов имитации большого разнообразия выразительных стилей в цифровом искусстве. В отличие от традиционной компьютерной графики, сфокусированной на фотореализме, НФР …   Википедия

Книги

Другие книги по запросу «АЛГОРИТМА ИЗОБРАЖЕНИЕ» >>


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

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