Том 18, номер 6, 2011 г., Стр. 71-81

УДК 519.8
Окольнишникова Е. А.
О распределённых схемах

Аннотация:
Вводится класс распределённых схем, которые моделируют вычисления параллельными компьютерами с распределённой памятью. Доказываются оценки сложности вычисления булевых функций и систем булевых функций этими схемами.
Библиогр. 10.

Ключевые слова: сложность вычислений, схемы из функциональных элементов, моделирование вычислений.

Окольнишникова Елизавета Антоновна ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 3 декабря 2010 г.

Литература

[1] Андреев А. Е. Об одном методе получения нижних оценок сложности индивидуальных монотонных функций // Докл. АН СССР. — 1985. — Т. 282, № 5. — С. 1033–1037.

[2] Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. — Вып. 10. — М.: Наука, 1963. — С. 63–97.

[3] Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики. Вып. 14. — М.: Наука, 1965. — С. 31–110.

[4] Окольнишникова E. A. Нижние оценки сложности реализации характеристических функций двоичных кодов бинарными программами // Методы дискретного анализа в синтезе реализаций булевых функций: Сб. науч. тр. Вып. 51. — Новосибирск: Ин-т математики СО АН СССР,
1991. — С. 61–83.

[5] Окольнишникова E. A. Об одном методе получения нижних оценок сложности реализации булевых функций недетерминированными ветвящимися программами // Дискрет. анализ и исслед. операций. Сер. 1. — 2001. — Т. 8, № 4. — С. 76–112.

[6] Окольнишникова E. A. Нижняя оценка сложности вычисления характеристических функций БЧХ-кодов ветвящимися программами // Дискрет. анализ и исслед. операций. — 2009. — Т. 16, № 5. — С. 69–77.

[7] Параллельные машины // Энциклопедия «Дискретная математика». — М.: Большая Российская энциклопедия, 2004. — С. 193–194.

[8] Параллельных вычислений теория // Энциклопедия «Дискретная математика». — М.: Большая Российская энциклопедия, 2004. — С. 194–196.

[9] Разборов А. А. Нижние оценки сложности монотонной сложности некоторых булевых функций // Докл. АН СССР. — 1985. — Т. 281, № 4. — С. 798–801.

[10] Чашкин А. В. О сложности булевых матриц, графов и соответствующих им булевых функций // Дискрет. математика. — 1994. — Т. 6, вып. 2. — С. 43–73.