Вводятся алгоритмы Маркова-Турчина как обобщение алгоритмов, введённых автором в [5], и являющиеся существенной модификацией программ, написанных на языке рефал-5. Предлагается критерий их эффективности для реализации на машине Тьюринга за полиномиальное число шагов. Этот критерий не использует ограничения памяти, в отличие от того, как это было установлено в [3] для дважды полиномиальных программ на языке рефал-5. Критерий основан на специального вида рекурсии в программах, являющейся существенным обобщением хвостовой рекурсии, предложенной Т. Борландом для программ на турбо прологе. Это обобщение связано с основным типом данных в языке рефал-5, представляющем собой древовидно структурированные тексты посредством круглых скобок. Для алгоритмов Маркова-Турчина (со встроенным динамическим интерпретатором) просто доказываются некоторые модификации теорем теории сложности алгоритмов, полезные для математиков-программистов. Иначе говоря, вводится математическое понятие алгоритма, модифицирующее (в основном, упрощ
Язык оригиналарусский
Страницы (с-по)41-49
ЖурналКОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ
Номер выпуска4
СостояниеОпубликовано - 2012

    Области исследований

  • машина Тьюринга, полиномиальное число шагов, рефал-5, нормальный алгоритм Маркова, класс сложности FP, проблема применимости алгоритмов к данным.

ID: 5478731