S-алгоритм

26.01.2011

S-алгоритм

Filed under: В.Д. Ильин,ИНФОПЕДИЯ,Информатика,Наука,Система знаний информатики СИНФ — SINF @ 18:21

©В.Д Ильин, 2011

□ S-АЛГОРИТМ (англ. S-algorithm) — система программно-реализуемых правил, позволяющая за конечное число шагов поставить в однозначное соответствие заданному набору данных, принадлежащему входу s-алгоритма, результирующий набор данных, принадлежащий выходу s-алгоритма. Специализация метода решения задачи (по типу решателя), представленная в форме, рассчитанной на программную реализацию в s-среде.

Выполнение s-алгоритма включает:

распознавание набора входных данных (определение его принадлежности множеству допустимых наборов данных, описанных как вход s-алгоритма): если набор принадлежит входу, то – переход к п.2; в противном случае – СТОП;
получение набора выходных данных (принадлежащего множеству наборов данных, определенных как выход s-алгоритма);
запись набора выходных данных в заданную область памяти.
СТОП.□

Типы решателей: автономная s-машина; сетевая кооперация s-машин; сетевая кооперация s-машин и взаимодействующих с ними людей.

(См. определение алгоритма с точки зрения математика).

Метод (в отличие от алгоритма) не ориентирован на определенный тип решателя задач.

Машина Тьюринга – это s-модель алгоритмического решателя-автомата.

ДРУГИЕ ОПРЕДЕЛЕНИЯ

ALGORITHM

Definition

Given both the problem and the device, an algorithm is the precise characterization of a method of solving the problem, presented in a notation interpretable by

the device.

In particular, an algorithm is characterized by these properties:

Application of the algorithm to a particular input set or problem description results in a finite sequence of actions.
The sequence of actions has a unique initial action.
Each action in the sequence has a unique successor.
The sequence terminates with either a solution to the problem, or a statement that the problem is unsolvable for that set of data.

См. TSM – комплекс средств формализации гипермедийных описаний s-моделей.

Лит.: Ильин А.В., Ильин В.Д. Основы теории s-моделирования, М.: ИПИ РАН, 2009.

…