РЕАЛИЗАЦИЯ МЕМБРАННЫХ АЛГОРИТМОВ С ПОМОЩЬЮ МАРКОВСКИХ СИСТЕМ
(Стр. 36-46)

Подробнее об авторах
Ершов Николай Михайлович кандидат физико-математических наук, старший научный сотрудник, факультет вычислительной математики и кибернетики
Московский государственный университет им. М.В. Ломоносова
Чтобы читать текст статьи, пожалуйста, зарегистрируйтесь или войдите в систему
Аннотация:
Работа посвящена исследованию алгоритмических возможностей марковских систем на примере решения двух NP-полных задач - поиска гамильтонова пути в ориентированном графе и задачи о выполнимости булевой формулы. Рассматриваются вопросы реализации мембранных алгоритмов решения этих задач, имеющих полиномиальную зависимость времени работы от размера задачи. Приводятся результаты численного исследования предложенных алгоритмов.
Образец цитирования:
Ершов Н.М., (2017), РЕАЛИЗАЦИЯ МЕМБРАННЫХ АЛГОРИТМОВ С ПОМОЩЬЮ МАРКОВСКИХ СИСТЕМ. Computational nanotechnology, 2: 36-46.
Список литературы:
Ершов Н. М. Недетерминированный мембранный алгоритм поиска гамильтонова пути // Программные системы и инструменты. Тематический сборник / Под ред. Л. Королев. - Т. 12. - Издательский отдел факультета ВМК МГУ имени М.В. Ломоносова; МАКС Пресс Москва, 2011. - С. 39-45.
Ершов Н. М., Кравчук А. В. Дискретное моделирование с помощью стохастических клеточных автоматов // Вестник Российского университета дружбы народов: Серия Математика, информатика, физика. - 2014. - № 2. - С. 359-362.
Г. Паун, Г. Розенберг, А. Саломаа, ДНК-компьютер. Новая парадигма вычислений, М. : Мир, 2003.
Leonard M. Adleman, Molecular Computation of Solutions to Combinatorial Problems, Science, 266, 11, pp. 1021-1024, 1994.
K.L. Chung and F. AitSahlia. Elementary Probability Theory: With Stochastic Processes and an Introduction to Mathematical Finance. Undergraduate Texts in Mathematics. Springer, 2003.
Peter Dittrich, Jens Ziegler, and Wolfgang Banzhaf. Artificial chemistries - a review. Artif. Life, 7(3):225-275, June 2001.
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006.
Adam Obtulowicz. Deterministic P systems for solving SAT problem. Romanian Journal of Information Science and Technology, 4(1-2):195-202, 2001.
Gheorghe Paun. Computing with membranes. An introduction. Bulletin of the EATCS, (67):139-152, February 1999.
Gheorghe Paun. P systems with active membranes: Attacking NP-Complete problems. Journal of Automata, Languages and Combinatorics, 6(1):75-90, 2001.
Gheorghe Paun and Grzegorz Rozenberg. A guide to membrane computing. Theoretical Computer Science, 287(1):73-100, September 2002.
Przemyslaw Prusinkiewicz and Aristid Lindenmayer. The algorithmic beauty of plants. Springer-Verlag New York, Inc., NY, USA, 1996.
Grzegorz Rozenberg and Arto Salomaa. Mathematical Theory of L Systems. Academic Press, Inc., Orlando, FL, USA, 1980.
Tommaso Toffoli and Norman Margolus. Cellular automata machines: a new environment for modeling. MIT Press, Cambridge, MA, USA, 1987.
Ключевые слова:
мембранные алгоритмы, клеточные автоматы, системы Линденмайера, ДНК-вычисления, гамильтонов путь, выполнимость булевых формул.