Комментарии 24
Я правильно понимаю, что это частное решение общей NP-сложной задачи построения минимальной комбинации булевых функций по таблице состояния?
Да, правильно. Только лучше сказать из таблицы истинности.
Это не совсем частное решение. Скорее, минимизация исходных данных для такой задачи.
Вот когда оказывается, что по такой карте каждая из единиц может быть "покрыта" несколькими способами — и из них всех надо выбрать оптимальное покрытие — тогда-то NP-полная задача и вылезает.
Вот когда оказывается, что по такой карте каждая из единиц может быть "покрыта" несколькими способами — и из них всех надо выбрать оптимальное покрытие — тогда-то NP-полная задача и вылезает.
Картинки в экселе можно сделать и скриншоты в статью добавить. Смотрелось бы симпатичнее.
Ошибаетесь. Симметричные карты были созданы исторически после метода Куайна—Мак-Класки и превосходят его по эффективности. Чтобы в этом убедиться, необходимо просто решить приведенный пример вручную двумя этими методами. Что касается автоматизации, то симметричные карты легко алгоритмизуются в силу формальности правил и могут точно решать задачи на 16 и более переменных.
А можно вас попросить написать прототип для автоматизации предложенного решения и прогнать его через бенчмарк/другой? Было бы любопытно посмотреть, как конкретно влияет такая минимизация на конечный результат. Ну и да, если сегодня говорить о проблемах минимизации функций, то тут интерес представляют функции куда большей размерности, чем 16 (мое сообщение чуть ниже).
PS
Эх, доделать бы свою версию espresso, оптимизированную под совсем большие задачи...
PS
Эх, доделать бы свою версию espresso, оптимизированную под совсем большие задачи...
SCHERZO is 16 times faster than ESPRESSO-SIGNATURE and 19 times faster than ESPRESSO-EXACT (правда не знаю где этот музыкальный пакет взять)
Doing Two-Level Logic Minimization 100 Times Faster
citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.9246&rep=rep1&type=pdf
Doing Two-Level Logic Minimization 100 Times Faster
citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.9246&rep=rep1&type=pdf
Вопрос дилетанта: нужно минимизировать функцию 64 переменных, Espresso с такой задачей справится? Раньше такими задачами не занимался, а сейчас как раз возникла необходимость.
Да, легко. Espresso сносно работает с функциями до 200 переменных, потом как повезет. Есть опыт использования на функциях как раз с 180+ переменными и несколькими десятками тысяч строк. В мои требования по рантайму (20-30 минут — это норма) вполне укладывается.
Спасибо! Есть еще вопрос по Espresso.
Имеется нетлист схемы (реализация функции в виде базисных элементов логики). Из этого нетлиста хотелось бы восстановить функцию. Можно написать скрипт, который выпишет в виде отдельных формул функции всех элементов, составляющих нетлист. В результате, искомая функция окажется суперпозицией функций элементов.
Вопрос: умеет ли Espresso работать с функцией, заданной в виде суперпозиции частичных функций? Т.е. если я загружу список из функций элементов, сможет ли Espresso эти частичные функции склеить в единую функцию, и затем минимизировать? Или же, 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) во втором часу ночи выше моих сил. Статья на редкость интересная, но честно, пока не осиливаю. Завтра попробую на свежую голову еще раз перечитать.
причем строки 0 и 10 — это толстая линия, соответствующая инверсному значению
Это просто такое правило?
ищем оставшиеся единицы, не входящие в уже сформированные группы
Клетка 0-2 не берется потому что это не однозначно единица или потому что она находиться внутри уже обработанной фигуры (не склеенных единицы, а в прямоугольнике)?
Для этого берут восемь значений из таблицы истинности и заносят их в соответствующую строку (индексы столбцов соответстуют номеру в восьмерке входного набора).
Почему именно 8, а не 16? Шестнадцатеричная система наиболее распространённая, кажется в ней удобнее будет работать. Не пробовали адаптировать к шестнадцатеричной системе исчисления?
Из нее можно получить две равновеликие группы, первая из которых содержит клетки в строках 0 и 10, индексы столбцов 5 и 4, а вторая — все клетки в последнем столбце.
Т.е. первая группа: сначала симметрию берём по вертикали, а потом по горизонтали.
Вторая группа: сначала симметрию берём по горизонтали, а потом по вертикали?
Почему нумерация иксов на рисунке 2 (рассматривается в качестве примера) отличается от других таблиц: к2, к3, к4...?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Симметричные карты как средство минимизации булевых функций