8399

Автор(ы): 

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Доклад

Название: 

Фундаментальные проблемы управления и гипервычисления

Электронная публикация: 

Да

ISBN/ISSN: 

ISBN 978-5-91450-064-8.

Наименование конференции: 

  • 5-я международная конференция «Параллельные вычисления и задачи управления» (PACO'2010, Москва)

Наименование источника: 

  • Труды 5-й Международной конференции «Параллельные вычисления и задачи управления» (PACO'2010, Москва)

Город: 

  • Москва

Издательство: 

  • ИПУ РАН

Год издания: 

2010

Страницы: 

709-757
Аннотация
Рассматриваются фундаментальные проблемы управления, под которыми понимаются проблемы, сводимые к NP-полным (NP-трудным)задачам. Показано, что такие проблемы могут быть решены с полиномиальной временной сложностью с помощью новых математических моделей вычислений, называемых гипермашинами (вычисления с помощью гипермашин называют гипервычислениями). Приведено описание двух таких моделей вычислений: классический идеальный генератор тестов (ИГТ) и квантовый идеальный генератор тестов. Излагаются параллельно-последовательные D-алгоритмы, решающие одну из NP-полных задач (SAT-проблему) и "заточенные" под архитектуру ИГТ, а также квантовые D-алгоритмы, решающие ту же проблему и "заточенные" под архитектуру квантового идеального генератора тестов. Проведено сравнение возможностей классического и квантового идеального генератора тестов, а также сравнение параллельно-последовательных и квантовых D-алгоритмов.

Библиографическая ссылка: 

Правильщиков П.А. Фундаментальные проблемы управления и гипервычисления / Труды 5-й Международной конференции «Параллельные вычисления и задачи управления» (PACO'2010, Москва). М.: ИПУ РАН, 2010. С. 709-757.