Статья

Название статьи РЕШЕНИЕ ЗАДАЧ ОБРАЩЕНИЯ И УДВОЕНИЯ С ПОМОЩЬЮ ЛИНЕЙНЫХ НОРМАЛЬНЫХ АЛГОРИТМОВ
Автор А.В. Пруцков
Рубрика РАЗДЕЛ 5. МОДЕЛИРОВАНИЕ, АЛГОРИТМЫ
Месяц, год 01, 2012
Индекс УДК 510.5
DOI
Аннотация Линейные нормальные алгоритмы являются модификацией нормальных алгоритмов Маркова и отличаются от них возможностью реализации линейного вычислительного процесса. Цель данной статьи состоит в решении классических задач теории нормальных алгоритмов Маркова – задач обращения и удвоения с линейной трудоемкостью. Для достижения данной цели необходимо разработать линейные нормальные алгоритмы решения этих задач. В статье показано, что даже при наложении ограничений предложенные алгоритмы остаются линейными по трудоемкости. Также разработаны линейные нормальные алгоритмы сравнения слов и сведения нормальных алгоритмов Маркова к линейным нормальным алгоритмам на основе алгоритмов обращения и удвоения.

Скачать в PDF

Ключевые слова Нормальные алгоритмы Маркова; линейные нормальные алгоритмы; обращающий и удваивающий алгоритмы.
Библиографический список 1. Марков А.А., Нагорный Н.М. Теория алгорифмов. – М.: Наука, 1984. – 432 с.
2. Нагорный H.M. Некоторые обобщения понятия нормального алгорифма // Тр. матем. ин-
та АН СССР им. В.А. Стеклова, 52. – М.-Л.: Изд-во АН СССР, 1958. – С. 66-74.
3. Цветков И.А. Обращающий самопополняемый слева алгорифм в алфавите с одной до-
полнительной буквой // Математическое и программное обеспечение вычислительных
систем: Межвуз. сб. науч. тр. / Под ред. А.Н. Пылькина. – М.: Горячая линия-Телеком,
2008. – С. 4-9.
4. Пруцков А.В. Линейная модификация нормальных алгоритмов Маркова // Информаци-
онные технологии в процессе подготовки современного специалиста: Межвуз. сб. ста-
тей. – Липецк, 2010. – Вып. 13. – С. 166-174.
5. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.:
Энергоатомиздат, 1988. – 480 с.
6. Пруцков А.В. Обработка числительных естественных языков с помощью формальных
грамматик и нормальных алгоритмов Маркова // Вестник Рязанского государственного
радиотехнического университета. – Рязань, 2009. – Вып. 28. – С. 49-55.

Comments are closed.