Мной предлагается для решения задач Русским методом совершенно другое вычислительное устройство, а именно Русскую машину.
Архитектура Русской машины обходит серьёзное препятствие в классической фон-неймановской логике, ― так называемое бутылочное горлышко архитектуры фон Неймана (von Neumann bottleneck).
Это ограничение в современных вычислительных устройствах связано с необходимостью извлекать огромные массивы данных из памяти, которые затем пересылаются для обработки в процессор.
Время извлечения данных и их пересылка могут оказаться много больше времени, необходимого на их обработку процессором современных вычислительных устройств.
Это особенно критично для работы ускорителей нейронных сетей, которые опираются на операции с перемножением массивных векторных матриц, а это всё затраты энергии и немалой.
Архитектура Русской машины делает всё иначе.
Русская машина производит вычисления непосредственно в памяти аналогового мультипроцессора и делает это не с цифровыми данными, а с данными, представленными в аналоговом виде.
«Аналоговые» технологии позволяют получить практически тот же результат при перемножении векторных матриц с допущением меньшей точности, чем при использовании данных в виде цифровых.
Экономия происходит сразу по двум пунктам:
– по пересылке данных из памяти в аналоговый мультипроцессор;
– по объёму используемых для расчётов данных, практически неограниченных.
Задача о вершинном покрытии
Задача о вершинном покрытии – NP-полная задачаинформатики в области теории графов.
Часто используется в теории сложности для доказательства NP-полноты более сложных задач.
Вершинное покрытие для неориентированного графа G = (V,E) – это множество его вершин S, такое, что, у каждого ребра графа хотя бы один из концов входит в вершину из S.
Размером (size) вершинного покрытия называется число входящих в него вершин.
Задача о вершинном покрытии состоит в поиске вершинного покрытия наименьшего размера для заданного графа (этот размер называется числом вершинного покрытия графа).
NP-полнота задачи о вершинном покрытии.
Поскольку задача о вершинном покрытии является NP-полной, то, в настоящее время считается, что неизвестны алгоритмы для её решения за полиномиальное время.
Однако существуют алгоритмы, дающие«приближённое» решение этой задачи за полиномиальное время.