На нашем ресурсе вы можете полностью погрузиться в мир книги «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина» — читайте её онлайн бесплатно в полной, несокращённой версии. Если предпочитаете слушать — воспользуйтесь аудиоформатом; хотите сохранить — скачайте через торрент в fb2. Жанр произведения — Знания и навыки, Компьютерная литература, Книги о компьютерах. Также на странице доступно подробное описание, авторская аннотация, краткое содержание и живые отзывы читателей. Мы постоянно пополняем библиотеку и улучшаем сервис, чтобы создавать лучшее пространство для всех ценителей качественной литературы.
Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина
0 баллов
0 мнений
0 чтений
Автор
Дата выхода
09 декабря 2020
🔍 Загляните за кулисы "Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина" — аннотация, авторский взгляд и ключевые моменты
Перед погружением в полный текст предлагаем познакомиться с произведением поближе. Здесь собраны авторские заметки, аннотация и краткое содержание "Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина" — всё, что поможет понять глубину замысла и подготовиться к чтению. Материалы представлены в оригинальной авторской редакции (Геннадий Степанов) и сохраняют аутентичность произведения. Если чего-то не хватает — сообщите нам в комментариях, и мы дополним описание. Читайте мнения других участников сообщества: их отзывы часто раскрывают скрытые смыслы и добавляют новые грани понимания. А после прочтения обязательно вернитесь сюда — ваш отзыв станет ценным вкладом в общее обсуждение книги.
Описание книги
В этой, предлагаемой мной умному, любознательному и доброжелательно настроенному читателю, книге, описываются некоторые примеры решения труднорешаемых задач. В этих примерах показываются возможные, в общем виде, некоторые приёмы применения Русского метода при решении NP-задач. Таких приёмов (вариантов) применения Русского метода может быть неограниченное множество для получения как приближённых, так и оптимальных решений NP-задач без зацикливания.
📚 Читайте "Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина" онлайн — полный текст книги доступен бесплатно
Перед вами — полная электронная версия книги "Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина", адаптированная для комфортного онлайн-чтения. Мы разбили произведение на страницы для удобной навигации, а умная система запоминает, на какой странице вы остановились — можно закрыть браузер и вернуться к чтению позже, не тратя время на поиски. Персонализируйте процесс: меняйте шрифты, размер текста и фон под свои предпочтения. Погружайтесь в мир литературы где угодно и когда угодно — любимые книги теперь всегда под рукой.
Текст книги
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-полноты более сложных задач.
Тут будет реклама 1
Вершинное покрытие для неориентированного графа G = (V,E) – это множество его вершин S, такое, что, у каждого ребра графа хотя бы один из концов входит в вершину из S.
Размером (size) вершинного покрытия называется число входящих в него вершин.
Задача о вершинном покрытии состоит в поиске вершинного покрытия наименьшего размера для заданного графа (этот размер называется числом вершинного покрытия (https://ru.
Тут будет реклама 2
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), то, в настоящее время считается, что неизвестны алгоритмы для её решения за полиномиальное время.
Тут будет реклама 3
Однако существуют алгоритмы, дающие«приближённое» решение этой задачи за полиномиальное время.
С их помощью можно найти, например, вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.
Безпереборный метод (русский метод) решения задачи о вершинном покрытии графа.
Мной предлагается следующий способ решения задачи о вершинном покрытии:
Этап1.
Выберем интервал изменения числа угадывания (N уг) для данной конкретной задачи.
Тут будет реклама 4
Этот интервал зависит от характеристик этой задачи.
Он изменяется от 1 до определённого, предварительно, для этой задачи значения (N макс).
Процесс изменения можно осуществлять, например, путём прибавления 1 к значению N уг.
Это не является принципиально важным.
Этап2.
Осуществим сортировку вершин графа, в соответствии с числом входов в вершину графа рёбер графа.
Этап3.
Мнения
О книге «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина» ещё никто не оставил отзыв — у вас есть шанс стать первым, чьё мнение задаст тон всему обсуждению! Поделитесь впечатлениями, эмоциями, замечаниями или рекомендациями. Ваш отзыв не только добавит живого голоса к произведению, но и поможет будущим читателям понять, стоит ли им открыть эту книгу. Не держите мысли при себе — ваше слово имеет значение!
Другие книги автора
Если «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина» пришлась вам по душе, самое время открыть для себя другие работы Геннадий Степанов! В этой подборке — только произведения того же автора, чтобы вы могли глубже погрузиться в его творческий мир и насладиться схожим стилем, темами и атмосферой. Возможно, следующая книга станет для вас ещё более ярким открытием.
