Здравствуйте, Stanky, Вы писали:
>> Сначала находим все подходящие прямоугольники для каждой ячейки. Затем >> сортируем их по убыванию размера. А потом выкидываем ненужные. Алгоритм >> не самый быстрый, но: во-первых на мой взгляд это не тот случай, когда >> надо оптимизировать (карта Карно обычно небольшая, в моем случае - >> вообще 4х4, да и на более больших работает в момент), а во-вторых это >> просто реализовать. Получается 100% результат для минимальной ДНФ. В >> принципе, я думаю, можно найти еще минимальную RYA и определить, что >> лучше. Вот такой вот алгоритм. >> S>А недетерминированные функции учитываешь?
В моем случае функция задается ее таблицей истинности, т.е. для каждого булевого вектора указывается 0 — или 1. Затем я все эти нули и единицы переношу на карту Карно. Так что...
Здравствуйте, Dr.Gigabit, Вы писали:
DG>Здравствуйте, Stanky, Вы писали:
>>> К моему великому щастью я узнал, что мне нужна именно минимальная ДНФ >>> Ее я уже почти получил — осталось выкинуть лишние слагаемые, >>> которые возникают при определенном раскладе. Хотя, просто так, ради >>> интереса можно посидеть дальше, что-то мне эта задача (полной >>> минимизации) понравилась >>> S>>Я сейчас уже конечно не очень хорошо эту тему помню, но для машинной минимизации есть метод Квайна-Максласски (вроде так) и вроде ещё какой-то!!! Так же есть ещё поиск тупиковых форм — всё это мы использовали в своей проге, так что советую найти описание сего детища!!!
DG>Есть еще Алгоритм Рота...По сути полностью формализованный алгоритм Квайна.
Ага, есть такой, его вроде даже программно реализовали студенты в качестве курсача по АиЛОВТ в БГУИР (его там такой пренеприятнейший препод Луцик ведет). Сложный этот алгоритм, а ручками по нем вообще посчитать практически невозможно.
Здравствуйте, Trean, Вы писали:
DG>>Есть еще Алгоритм Рота...По сути полностью формализованный алгоритм Квайна.
T>Ага, есть такой, его вроде даже программно реализовали студенты в качестве курсача по АиЛОВТ в БГУИР (его там такой пренеприятнейший препод Луцик ведет). Сложный этот алгоритм, а ручками по нем вообще посчитать практически невозможно.
Офигеть! А у нас в СПбГААП этот предмет вела (ведёт?) преподша Лупал. Странное совпаденьице, не находите?
Здравствуйте, Stanky, Вы писали:
S>Когда-то ооочень давно с товарищем писали прогу минимизации булевых функций (как детерминированных, так и нет), причём писали это дело ещё на VisualBasic'е (как вспомню аж в дрожь бросает)!!! S>Если интересно, то саму прогу можешь здесь глянуть, а если хочешь на наши исходники взглянуть, то могу тебе их кинуть!!!
> Срочно абоут добавь и копирайты туда!!!!! >
А смысл?
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[2]: Прямоугольники, карта Карно
От:
Аноним
Дата:
22.05.05 08:52
Оценка:
Здравствуйте, Stanky, Вы писали:
>> Подкинули мне тут задачку, да вот не знаю, как решить. >> S>Когда-то ооочень давно с товарищем писали прогу минимизации булевых функций (как детерминированных, так и нет), причём писали это дело ещё на VisualBasic'е (как вспомню аж в дрожь бросает)!!! S>Если интересно, то саму прогу можешь здесь глянуть, а если хочешь на наши исходники взглянуть, то могу тебе их кинуть!!!
S>P. S. Для меньшего гемороя с выводом минимизированной функции в виде текста я не стал сильно париться и сделал весь вывод в Unicod'е с использованием Arial Unicode MS (идёт вместе с офисом)!!!
скинь плиз исходники на gonobobel@ukrpost.com.ua
заранее спасибо )
DG>>Есть еще Алгоритм Рота...По сути полностью формализованный алгоритм Квайна.
T>Ага, есть такой, его вроде даже программно реализовали студенты в качестве курсача по АиЛОВТ в БГУИР (его там такой пренеприятнейший препод Луцик ведет). Сложный этот алгоритм, а ручками по нем вообще посчитать практически невозможно.
Dr.Gigabit, Trean
Можно узнать подробнее об этом алгоритме Рота? Описание, исподники,... все что угодно.
Поиском ничего толкового найти не удалось
Спасибо
Здравствуйте, slay93, Вы писали:
S>Здравствуйте, Dr.Gigabit, Trean, Вы писали:
S>
DG>>>Есть еще Алгоритм Рота...По сути полностью формализованный алгоритм Квайна.
T>>Ага, есть такой, его вроде даже программно реализовали студенты в качестве курсача по АиЛОВТ в БГУИР (его там такой пренеприятнейший препод Луцик ведет). Сложный этот алгоритм, а ручками по нем вообще посчитать практически невозможно.
S>Dr.Gigabit, Trean S>Можно узнать подробнее об этом алгоритме Рота? Описание, исподники,... все что угодно. S>Поиском ничего толкового найти не удалось S>Спасибо
Ее я уже почти получил — осталось выкинуть лишние слагаемые,
Перекуём баги на фичи!
