Все выпуски

Работа посвящена связи параллельных и последовательных вычислений. С одной стороны, рассматривается класс словарных предикатов, основанных на последовательных вычислениях, ограниченных по памяти константами и имеющих полиномиальную временную сложность. С другой стороны, рассматривается класс словарных предикатов, вычислимых на параллельных альтернирующих машинах за логарифмическое время. Доказано совпадение соответствующих классов. Предложено направление использования полученных результатов для взаимного преобразования и сочетания вычислений на молекулярных биоподобных последовательных машинах и параллельных вычислениях на векторно-матричных компьютерах. Предполагаемые области применения: обработка изображений в реальном масштабе времени для задач управления, анализ больших текстов и других больших данных.

The work is devoted to the connection between parallel and sequential computing. On the one hand, we consider a class of word predicates based on sequential calculations, limited in memory by constants and having polynomial time complexity. On the other hand, we consider a class of word predicates that are computable on parallel alternating machines in logarithmic time. The coincidence of the corresponding classes is proven. The direction of using the obtained results for mutual transformation and combination of calculations on molecular biosimilar sequential machines and parallel calculations on vector-matrix computers is proposed. Intended applications: real-time image processing for control tasks, analysis of large texts and other big data.