Последний отзыв
От книги невозможно оторваться, супер интересная
По всем вопросам обращайтесь на: info@litportal.ru
(©) 2003-2024.
✖
Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина
Настройки чтения
Размер шрифта
Высота строк
Поля
Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина
Геннадий Степанов
В этой, предлагаемой мной умному, любознательному и доброжелательно настроенному читателю, книге, описываются некоторые примеры решения труднорешаемых задач.В этих примерах показываются возможные, в общем виде, некоторые приёмы применения Русского метода при решении NP-задач.Таких приёмов (вариантов) применения Русского метода может быть неограниченное множество для получения как приближённых, так и оптимальных решений NP-задач без зацикливания.
Вычислительные машины и труднорешаемые задачи
Русский метод. Русская машина
Геннадий Степанов
© Геннадий Степанов, 2020
ISBN 978-5-0051-8960-8
Создано в интеллектуальной издательской системе Ridero
Вычислительные машины и труднорешаемые задачи
Русский метод Русская машина
ВВЕДЕНИЕ
В этой, предлагаемой мной умному, любознательному и доброжелательно настроенному читателю, книге, описываются некоторые примеры решения труднорешаемых задач.
В этих примерах показываются возможные, в общем виде, некоторые приёмы применения Русского метода при решении NP – задач.
Таких приёмов (вариантов) применения Русского метода может быть неограниченное множество для получения, как приближённых, так и оптимальных решений NP – задач без зацикливания.
Русский метод решения NP – задач не отличается особой сложностью. По моему мнению, его легко может понять, на интуитивном уровне, любой школьник.
Существующие методы решения NP – задач являются методами неявного полного перебора. Перебор – это составная часть сортировки.
Русский метод использует сортировку, ограниченную числом угадывания (N уг). Сортировка применяется в Русском методе на каждом промежуточном этапе решения NP – задач.
Отличительной особенностью Русского метода является то, что он основан на найденной мной закономерной зависимости, присущей NP – задачам.
Главным достоинством этой зависимости является возможность создать имитатор человеческого разума и мышления на основе философии Великого философа Иммануила Канта.
В основе данного имитатора лежит разработанный мной механизм машинной интуиции.
По Канту сущность вещей в мире не познаваема человеком. Они ноумены. Человек способен познать только явления в мире.
Невозможно познать человеческий разум и мышления по Канту. Они ноумены.
Хотя создать имитатор человеческого разума и мышления, основанного на выявленных наукой явлениях, вполне возможно, по Канту.
Русский метод, не отличаясь особой теоретической сложностью, требует по своей методологии совершенно другие вычислительные устройства, в отличие от существующих современных вычислительных машин
Русский метод очень сложно приспособить для решения задач на этих вычислительных устройствах, так как они основаны на классической фон-неймановской логике,? так называемое бутылочное горлышко архитектуры фон Неймана (von Neumann bottleneck).
Для решения задач с помощью Русского метода необходимо вычислительное устройство с практически с неограниченным числом параллельных вычислительных путей, что невозможно осуществить на современных вычислительных машинах, основанных на архитектуре фон Неймана, которым требуется для вычислений колоcсальные энергозатраты.
Мной предлагается для решения задач Русским методом совершенно другое вычислительное устройство, а именно Русскую машину.
Архитектура Русской машины обходит серьёзное препятствие в классической фон-неймановской логике, ? так называемое бутылочное горлышко архитектуры фон Неймана (von Neumann bottleneck).
Это ограничение в современных вычислительных устройствах связано с необходимостью извлекать огромные массивы данных из памяти, которые затем пересылаются для обработки в процессор.
Время извлечения данных и их пересылка могут оказаться много больше времени, необходимого на их обработку процессором современных вычислительных устройств.
Это особенно критично для работы ускорителей нейронных сетей, которые опираются на операции с перемножением массивных векторных матриц, а это всё затраты энергии и немалой.
Архитектура Русской машины делает всё иначе.
Русская машина производит вычисления непосредственно в памяти аналогового мультипроцессора и делает это не с цифровыми данными, а с данными, представленными в аналоговом виде.
«Аналоговые» технологии позволяют получить практически тот же результат при перемножении векторных матриц с допущением меньшей точности, чем при использовании данных в виде цифровых.
Экономия происходит сразу по двум пунктам:
– по пересылке данных из памяти в аналоговый мультипроцессор;
– по объёму используемых для расчётов данных, практически неограниченных.
Задача о вершинном покрытии
Задача о вершинном покрытии – NP-полная задача (https://ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0)информатики (https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) в области теории графов (https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2).
Часто используется в теории сложности (https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9) для доказательства NP-полноты более сложных задач.
Вершинное покрытие для неориентированного графа G = (V,E) – это множество его вершин S, такое, что, у каждого ребра графа хотя бы один из концов входит в вершину из S.
Размером (size) вершинного покрытия называется число входящих в него вершин.
Задача о вершинном покрытии состоит в поиске вершинного покрытия наименьшего размера для заданного графа (этот размер называется числом вершинного покрытия (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%BE_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D1%8F) графа).
NP-полнота задачи о вершинном покрытии.
Поскольку задача о вершинном покрытии является NP-полной (https://ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0), то, в настоящее время считается, что неизвестны алгоритмы для её решения за полиномиальное время.
Однако существуют алгоритмы, дающие«приближённое» решение этой задачи за полиномиальное время.
С их помощью можно найти, например, вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.
Безпереборный метод (русский метод) решения задачи о вершинном покрытии графа.
Мной предлагается следующий способ решения задачи о вершинном покрытии:
Этап1.
Геннадий Степанов
В этой, предлагаемой мной умному, любознательному и доброжелательно настроенному читателю, книге, описываются некоторые примеры решения труднорешаемых задач.В этих примерах показываются возможные, в общем виде, некоторые приёмы применения Русского метода при решении NP-задач.Таких приёмов (вариантов) применения Русского метода может быть неограниченное множество для получения как приближённых, так и оптимальных решений NP-задач без зацикливания.
Вычислительные машины и труднорешаемые задачи
Русский метод. Русская машина
Геннадий Степанов
© Геннадий Степанов, 2020
ISBN 978-5-0051-8960-8
Создано в интеллектуальной издательской системе Ridero
Вычислительные машины и труднорешаемые задачи
Русский метод Русская машина
ВВЕДЕНИЕ
В этой, предлагаемой мной умному, любознательному и доброжелательно настроенному читателю, книге, описываются некоторые примеры решения труднорешаемых задач.
В этих примерах показываются возможные, в общем виде, некоторые приёмы применения Русского метода при решении NP – задач.
Таких приёмов (вариантов) применения Русского метода может быть неограниченное множество для получения, как приближённых, так и оптимальных решений NP – задач без зацикливания.
Русский метод решения NP – задач не отличается особой сложностью. По моему мнению, его легко может понять, на интуитивном уровне, любой школьник.
Существующие методы решения NP – задач являются методами неявного полного перебора. Перебор – это составная часть сортировки.
Русский метод использует сортировку, ограниченную числом угадывания (N уг). Сортировка применяется в Русском методе на каждом промежуточном этапе решения NP – задач.
Отличительной особенностью Русского метода является то, что он основан на найденной мной закономерной зависимости, присущей NP – задачам.
Главным достоинством этой зависимости является возможность создать имитатор человеческого разума и мышления на основе философии Великого философа Иммануила Канта.
В основе данного имитатора лежит разработанный мной механизм машинной интуиции.
По Канту сущность вещей в мире не познаваема человеком. Они ноумены. Человек способен познать только явления в мире.
Невозможно познать человеческий разум и мышления по Канту. Они ноумены.
Хотя создать имитатор человеческого разума и мышления, основанного на выявленных наукой явлениях, вполне возможно, по Канту.
Русский метод, не отличаясь особой теоретической сложностью, требует по своей методологии совершенно другие вычислительные устройства, в отличие от существующих современных вычислительных машин
Русский метод очень сложно приспособить для решения задач на этих вычислительных устройствах, так как они основаны на классической фон-неймановской логике,? так называемое бутылочное горлышко архитектуры фон Неймана (von Neumann bottleneck).
Для решения задач с помощью Русского метода необходимо вычислительное устройство с практически с неограниченным числом параллельных вычислительных путей, что невозможно осуществить на современных вычислительных машинах, основанных на архитектуре фон Неймана, которым требуется для вычислений колоcсальные энергозатраты.
Мной предлагается для решения задач Русским методом совершенно другое вычислительное устройство, а именно Русскую машину.
Архитектура Русской машины обходит серьёзное препятствие в классической фон-неймановской логике, ? так называемое бутылочное горлышко архитектуры фон Неймана (von Neumann bottleneck).
Это ограничение в современных вычислительных устройствах связано с необходимостью извлекать огромные массивы данных из памяти, которые затем пересылаются для обработки в процессор.
Время извлечения данных и их пересылка могут оказаться много больше времени, необходимого на их обработку процессором современных вычислительных устройств.
Это особенно критично для работы ускорителей нейронных сетей, которые опираются на операции с перемножением массивных векторных матриц, а это всё затраты энергии и немалой.
Архитектура Русской машины делает всё иначе.
Русская машина производит вычисления непосредственно в памяти аналогового мультипроцессора и делает это не с цифровыми данными, а с данными, представленными в аналоговом виде.
«Аналоговые» технологии позволяют получить практически тот же результат при перемножении векторных матриц с допущением меньшей точности, чем при использовании данных в виде цифровых.
Экономия происходит сразу по двум пунктам:
– по пересылке данных из памяти в аналоговый мультипроцессор;
– по объёму используемых для расчётов данных, практически неограниченных.
Задача о вершинном покрытии
Задача о вершинном покрытии – NP-полная задача (https://ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0)информатики (https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) в области теории графов (https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2).
Часто используется в теории сложности (https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9) для доказательства NP-полноты более сложных задач.
Вершинное покрытие для неориентированного графа G = (V,E) – это множество его вершин S, такое, что, у каждого ребра графа хотя бы один из концов входит в вершину из S.
Размером (size) вершинного покрытия называется число входящих в него вершин.
Задача о вершинном покрытии состоит в поиске вершинного покрытия наименьшего размера для заданного графа (этот размер называется числом вершинного покрытия (https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%BE_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D1%8F) графа).
NP-полнота задачи о вершинном покрытии.
Поскольку задача о вершинном покрытии является NP-полной (https://ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0), то, в настоящее время считается, что неизвестны алгоритмы для её решения за полиномиальное время.
Однако существуют алгоритмы, дающие«приближённое» решение этой задачи за полиномиальное время.
С их помощью можно найти, например, вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.
Безпереборный метод (русский метод) решения задачи о вершинном покрытии графа.
Мной предлагается следующий способ решения задачи о вершинном покрытии:
Этап1.
Другие электронные книги автора Геннадий Степанов
Последний отзыв
От книги невозможно оторваться, супер интересная