Pull to refresh

Comments 18

Я правильно понимаю, что это частное решение общей NP-сложной задачи построения минимальной комбинации булевых функций по таблице состояния?
Да, правильно. Только лучше сказать из таблицы истинности.
Это не совсем частное решение. Скорее, минимизация исходных данных для такой задачи.

Вот когда оказывается, что по такой карте каждая из единиц может быть "покрыта" несколькими способами — и из них всех надо выбрать оптимальное покрытие — тогда-то NP-полная задача и вылезает.
Картинки в экселе можно сделать и скриншоты в статью добавить. Смотрелось бы симпатичнее.

Описанный метод интересен только с исторической точки зрения. Сначала использовали метод Куайна и его модификации, сейчас производные от опенсорсного Espresso. Позволяет искать как точное решение так и близкое к точному. Запросто работает с количеством входов от 16 и выше.
Ошибаетесь. Симметричные карты были созданы исторически после метода Куайна—Мак-Класки и превосходят его по эффективности. Чтобы в этом убедиться, необходимо просто решить приведенный пример вручную двумя этими методами. Что касается автоматизации, то симметричные карты легко алгоритмизуются в силу формальности правил и могут точно решать задачи на 16 и более переменных.
А можно вас попросить написать прототип для автоматизации предложенного решения и прогнать его через бенчмарк/другой? Было бы любопытно посмотреть, как конкретно влияет такая минимизация на конечный результат. Ну и да, если сегодня говорить о проблемах минимизации функций, то тут интерес представляют функции куда большей размерности, чем 16 (мое сообщение чуть ниже).

PS
Эх, доделать бы свою версию espresso, оптимизированную под совсем большие задачи...
Вопрос дилетанта: нужно минимизировать функцию 64 переменных, Espresso с такой задачей справится? Раньше такими задачами не занимался, а сейчас как раз возникла необходимость.
Да, легко. Espresso сносно работает с функциями до 200 переменных, потом как повезет. Есть опыт использования на функциях как раз с 180+ переменными и несколькими десятками тысяч строк. В мои требования по рантайму (20-30 минут — это норма) вполне укладывается.
Спасибо! Есть еще вопрос по Espresso.
Имеется нетлист схемы (реализация функции в виде базисных элементов логики). Из этого нетлиста хотелось бы восстановить функцию. Можно написать скрипт, который выпишет в виде отдельных формул функции всех элементов, составляющих нетлист. В результате, искомая функция окажется суперпозицией функций элементов.
Вопрос: умеет ли Espresso работать с функцией, заданной в виде суперпозиции частичных функций? Т.е. если я загружу список из функций элементов, сможет ли Espresso эти частичные функции склеить в единую функцию, и затем минимизировать? Или же, Espresso работает по принципу — одна формула — одна функция?
Я не использовал espresso очень уж активно, исключительно как минимизатор и cnf-2-dnf, dnf-2-cnf транслятор. Если в нем и есть умный алгоритм работать с частичными функциями под опциями, то я не знаю. С другой стороны, ведь написать скрипт, который бы склеил набор нетлистов в один — это дело пары часов, разве нет? Пусть у нас есть большой нетлист, составленный из частичных функций. Каждому входу/выходу соответствует некая переменная в PLA (или BLIF, что там у вас). Теперь начинаем перечилсять известные нам "решения" для этого большого нетлиста (строки в PLA, они же конъюнкты). Неизвестные или несущественные значения переменных заполняем don't care (например, мы точно знаем, что вход одного нетлиста никак не влияет на вход другого). Все, получившийся большой файл можно запихивать в espresso. Если я что-то не так понял или криво объяснил, предлагаю перехать в личные сообщения. )
Справится в режиме эвристики точно (то есть найдет не 100% оптимальный результат, но крайне близкий к нему). Режим -exact как повезет.
Мы это изучали на первом курсе под видом карт Карно.
Это не карты Карно ни под каким видом.
Мы тоже такое изучали, и я тоже запомнил это как карты Карно. Хотя я не могу гарантировать что нам так и сказали, потому как теоретическую выкладку, из-за манеры преподавателя вводить для упрощения какие-то примеры и анекдоты для разрядки, я плохо помню, запомнил больше по практике. Пожалуй надо почитать о обоих методах, того гляди и вспомню.

Но данный метод мне показался весьма удобным.
Вам надо было эту статью на Хабре разместить. Она идеально для него подходит.
ТМ конечно, изверги. Столько лет не могут прикрутить отображение LaTeXa. Читать формулы булевой алгебры в виде (not X1)*X3*(not X4), X3*(not X4)*(not X5) во втором часу ночи выше моих сил. Статья на редкость интересная, но честно, пока не осиливаю. Завтра попробую на свежую голову еще раз перечитать.
Only those users with full accounts are able to leave comments. Log in, please.