На нашем ресурсе вы можете полностью погрузиться в мир книги «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина» — читайте её онлайн бесплатно в полной, несокращённой версии. Если предпочитаете слушать — воспользуйтесь аудиоформатом; хотите сохранить — скачайте через торрент в fb2. Жанр произведения — Знания и навыки, Компьютерная литература, Книги о компьютерах. Также на странице доступно подробное описание, авторская аннотация, краткое содержание и живые отзывы читателей. Мы постоянно пополняем библиотеку и улучшаем сервис, чтобы создавать лучшее пространство для всех ценителей качественной литературы.
Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина
0 баллов
0 мнений
0 чтений
Автор
Дата выхода
09 декабря 2020
🔍 Загляните за кулисы "Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина" — аннотация, авторский взгляд и ключевые моменты
Перед погружением в полный текст предлагаем познакомиться с произведением поближе. Здесь собраны авторские заметки, аннотация и краткое содержание "Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина" — всё, что поможет понять глубину замысла и подготовиться к чтению. Материалы представлены в оригинальной авторской редакции (Геннадий Степанов) и сохраняют аутентичность произведения. Если чего-то не хватает — сообщите нам в комментариях, и мы дополним описание. Читайте мнения других участников сообщества: их отзывы часто раскрывают скрытые смыслы и добавляют новые грани понимания. А после прочтения обязательно вернитесь сюда — ваш отзыв станет ценным вкладом в общее обсуждение книги.
Описание книги
В этой, предлагаемой мной умному, любознательному и доброжелательно настроенному читателю, книге, описываются некоторые примеры решения труднорешаемых задач. В этих примерах показываются возможные, в общем виде, некоторые приёмы применения Русского метода при решении NP-задач. Таких приёмов (вариантов) применения Русского метода может быть неограниченное множество для получения как приближённых, так и оптимальных решений NP-задач без зацикливания.
📚 Читайте "Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина" онлайн — полный текст книги доступен бесплатно
Перед вами — полная электронная версия книги "Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина", адаптированная для комфортного онлайн-чтения. Мы разбили произведение на страницы для удобной навигации, а умная система запоминает, на какой странице вы остановились — можно закрыть браузер и вернуться к чтению позже, не тратя время на поиски. Персонализируйте процесс: меняйте шрифты, размер текста и фон под свои предпочтения. Погружайтесь в мир литературы где угодно и когда угодно — любимые книги теперь всегда под рукой.
Текст книги
Иначе переходим к следующему этапу.
Этап11.
Данную процедуру повторяем, пока число вершин в подмножествах не сравняются с числом вершин графа. Так, как осуществляется эта процедура, примерно, в задаче коммивояжера русским методом.
Определим
N уг = N макс.
Если равен то переходим к этапу 12.
Иначе увеличиваем N уг, допустим, на 1 и переходим к этапу 3.
Этап12.
Анализ полученного результата.
Оценка полученного решения.
Если не удовлетворяет то уточняем N уг и N макс.
Переходим к этапу 2.
Тут будет реклама 1
Иначе заканчиваем работу.
Задача о доминирующем множестве
В теории графов (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%93%D1%80%D0%B0%D1%84_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0))G = (V, E) – это подмножество (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B4%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE) D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D.
Тут будет реклама 2
Число доминирования ? (G) – это число вершин в наименьшем доминирующем множестве G.
Задача о доминирующем множестве заключается в проверке, верно ли неравенство ? (G) ? K для заданного графа G и числа K.
Задача является классической 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.
Тут будет реклама 3
wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8) в теории вычислительной сложности (https://ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C).
Таким образом, в настоящее время полагают, что не существует эффективного алгоритма (https://ru.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0) для нахождения наименьшего доминирующего множества для заданного графа.
Тут будет реклама 4
Точные алгоритмы
Минимальное доминирующее множество графа с nвершинами может быть найдено за время O (2nn) путём просмотра всех подмножеств вершин.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «ЛитРес».
Мнения
О книге «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина» ещё никто не оставил отзыв — у вас есть шанс стать первым, чьё мнение задаст тон всему обсуждению! Поделитесь впечатлениями, эмоциями, замечаниями или рекомендациями. Ваш отзыв не только добавит живого голоса к произведению, но и поможет будущим читателям понять, стоит ли им открыть эту книгу. Не держите мысли при себе — ваше слово имеет значение!
Другие книги автора
Если «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина» пришлась вам по душе, самое время открыть для себя другие работы Геннадий Степанов! В этой подборке — только произведения того же автора, чтобы вы могли глубже погрузиться в его творческий мир и насладиться схожим стилем, темами и атмосферой. Возможно, следующая книга станет для вас ещё более ярким открытием.
