Вычислительные Машины И Труднорешаемые Задачи
На этот вопрос я и не пытался давать ответ в статье. Данная задача берёт свое начало в физике полимеров.
Примерно 50 лет назад физика полимеров стала отдельным направлением науки, поскольку изучение свойств этих самых полимеров оказалось очень важным. Полимер – это большая молекула, которая моделируется в виде простой цепочки (без самопересечений), проходящей по узлам воображаемой решётки. Цепочка может замкнуться сама на себя только в конечных точках, так образуется цикл. Почему циклы гамильтоновы?
Это связано с изучением свойств плотноупакованных полимеров. Плотноупакованный полимер (глобула) будет проходить по всем узлам воображаемой решётки. Зачем считать все возможные циклы? В физике существует понятие энтропия системы. В данной задаче (не буду доказывать строго) энтропия равна логарифму всех возможных конфигураций полимера. Чтобы посчитать этот логарифм, нужно посчитать и само это количество. Разумеется, точное решение физиков не интересует, их интересует скорость, с которой число конфигураций будет расти с увеличением числа узлов.
Эта скорость может быть найдена тем точнее, чем больше точных решений удастся посчитать. Чем больше решёток посчитано, тем точнее будет экстраполяция на большие решетки. В общем, здесь ещё долго можно рассказывать и про константу связности и про другие вещи из физики, но факт в том, что задача имеет практическую ценность. Теоретическая ценность задачи в том, что она позволяет разрабатывать численные методы перечислительной комбинаторики, которая уже имеет огромное количество приложений. Переходы организуются перебором всех 2 m-1 способов поставить горизонтальные рёбра для каждого из разрезов. Вам не нужно выделять невозможные переходы. Нужно переходить от одного разреза в те, в которые возможно.
Вычислительные Машины И Труднорешаемые Задачи Купить
Top Books - книга Вычислительные машины и труднорешаемые задачи - М. Гэри детали по тел.: ☎(044) 383. На тему «Труднорешаемые задачи. Вычислительных задач. Машины и труднорешаемые. Псевдополиномиальное сведение задач и np. Машины и труднорешаемые. И вычислительные.
А невозможные переходы — это когда некоторая комбинация горизонтальных рёбер приводит к одному из трёх случаев, описанных в статье. Начиная с разреза 00.0 нужно построить все допустимые разрезы. Недопустимые вы автоматически даже не увидите. Если это первая задача, которую вы решаете на динамику по профилю, я рекомендовал бы начать с задачи. Моя задача — одна из самых сложных в этой теме. Конечно, если ограничения большие, а не детские.
Вычислительные Машины И Труднорешаемые Задачи
Про паркет читал у Василевского, спасибо. «Переходы организуются перебором всех 2m-1 способов поставить горизонтальные рёбра для каждого из разрезов.» да, разумеется, это ясно «Вам не нужно выделять невозможные переходы. Нужно переходить от одного разреза в те, в которые возможно. А невозможные переходы — это когда некоторая комбинация горизонтальных рёбер приводит к одному из трёх случаев, описанных в статье.» для построения следующего профиля мне необходимо из всех 2^m-1 состояний исключить те 3 варианта, которые вы описали, верно? Не ясно было только как эти 3 случая будут себя «проявлять» для больших N. «Итак, предположим, что мы располагаем информацией обо всех возможных разрезах нашей решётки „ как именно получить информацию обо всех возможных разрезах для N на этапе выполнения программы?