Standard

Алгоритмы Маркова-Турчина и доказательства полиномиальной эффективности программ на языке рефал-5. / Косовский, Н.К.

в: КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ, № 4, 2012, стр. 41-49.

Результаты исследований: Научные публикации в периодических изданиях › статья

Harvard

Косовский, НК 2012, 'Алгоритмы Маркова-Турчина и доказательства полиномиальной эффективности программ на языке рефал-5', КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ, № 4, стр. 41-49. <http://elibrary.ru/item.asp?id=18886726>

APA

Косовский, Н. К. (2012). Алгоритмы Маркова-Турчина и доказательства полиномиальной эффективности программ на языке рефал-5. КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ, (4), 41-49. http://elibrary.ru/item.asp?id=18886726

Vancouver

Косовский НК. Алгоритмы Маркова-Турчина и доказательства полиномиальной эффективности программ на языке рефал-5. КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ. 2012;(4):41-49.

Author

Косовский, Н.К. / Алгоритмы Маркова-Турчина и доказательства полиномиальной эффективности программ на языке рефал-5. в: КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ. 2012 ; № 4. стр. 41-49.

BibTeX

@article{4c6edc0ed3844dffa62089d12e48074c,
title = "Алгоритмы Маркова-Турчина и доказательства полиномиальной эффективности программ на языке рефал-5",
abstract = "Вводятся алгоритмы Маркова-Турчина как обобщение алгоритмов, введённых автором в [5], и являющиеся существенной модификацией программ, написанных на языке рефал-5. Предлагается критерий их эффективности для реализации на машине Тьюринга за полиномиальное число шагов. Этот критерий не использует ограничения памяти, в отличие от того, как это было установлено в [3] для дважды полиномиальных программ на языке рефал-5. Критерий основан на специального вида рекурсии в программах, являющейся существенным обобщением хвостовой рекурсии, предложенной Т. Борландом для программ на турбо прологе. Это обобщение связано с основным типом данных в языке рефал-5, представляющем собой древовидно структурированные тексты посредством круглых скобок. Для алгоритмов Маркова-Турчина (со встроенным динамическим интерпретатором) просто доказываются некоторые модификации теорем теории сложности алгоритмов, полезные для математиков-программистов. Иначе говоря, вводится математическое понятие алгоритма, модифицирующее (в основном, упрощ",
keywords = "машина Тьюринга, полиномиальное число шагов, рефал-5, нормальный алгоритм Маркова, класс сложности FP, проблема применимости алгоритмов к данным.",
author = "Н.К. Косовский",
year = "2012",
language = "русский",
pages = "41--49",
journal = "КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ",
issn = "2071-2340",
publisher = "Издательство СПбГЭТУ {"}ЛЭТИ{"}",
number = "4",

}

RIS

TY - JOUR

T1 - Алгоритмы Маркова-Турчина и доказательства полиномиальной эффективности программ на языке рефал-5

AU - Косовский, Н.К.

PY - 2012

Y1 - 2012

N2 - Вводятся алгоритмы Маркова-Турчина как обобщение алгоритмов, введённых автором в [5], и являющиеся существенной модификацией программ, написанных на языке рефал-5. Предлагается критерий их эффективности для реализации на машине Тьюринга за полиномиальное число шагов. Этот критерий не использует ограничения памяти, в отличие от того, как это было установлено в [3] для дважды полиномиальных программ на языке рефал-5. Критерий основан на специального вида рекурсии в программах, являющейся существенным обобщением хвостовой рекурсии, предложенной Т. Борландом для программ на турбо прологе. Это обобщение связано с основным типом данных в языке рефал-5, представляющем собой древовидно структурированные тексты посредством круглых скобок. Для алгоритмов Маркова-Турчина (со встроенным динамическим интерпретатором) просто доказываются некоторые модификации теорем теории сложности алгоритмов, полезные для математиков-программистов. Иначе говоря, вводится математическое понятие алгоритма, модифицирующее (в основном, упрощ

AB - Вводятся алгоритмы Маркова-Турчина как обобщение алгоритмов, введённых автором в [5], и являющиеся существенной модификацией программ, написанных на языке рефал-5. Предлагается критерий их эффективности для реализации на машине Тьюринга за полиномиальное число шагов. Этот критерий не использует ограничения памяти, в отличие от того, как это было установлено в [3] для дважды полиномиальных программ на языке рефал-5. Критерий основан на специального вида рекурсии в программах, являющейся существенным обобщением хвостовой рекурсии, предложенной Т. Борландом для программ на турбо прологе. Это обобщение связано с основным типом данных в языке рефал-5, представляющем собой древовидно структурированные тексты посредством круглых скобок. Для алгоритмов Маркова-Турчина (со встроенным динамическим интерпретатором) просто доказываются некоторые модификации теорем теории сложности алгоритмов, полезные для математиков-программистов. Иначе говоря, вводится математическое понятие алгоритма, модифицирующее (в основном, упрощ

KW - машина Тьюринга

KW - полиномиальное число шагов

KW - рефал-5

KW - нормальный алгоритм Маркова

KW - класс сложности FP

KW - проблема применимости алгоритмов к данным.

M3 - статья

SP - 41

EP - 49

JO - КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ

JF - КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ

SN - 2071-2340

IS - 4

ER -

ID: 5478731