Thursday, November 11, 2010

О практическом применении булевой алгебры в повседневной работе программиста

   Вчера на работе понадобилось написать сложное условие, зависящее от семи переменных. Вроде ничего такого, но больно уж сложными были внутренние зависимости между переменными, т.е. если x1 ИСТИНА И x2 ИСТИНА, но при этом x3 ИЛИ x6 ЛОЖЬ, то результат будет ИСТИНА. Т.е. очень все мозгодробно. Сел, было, я писать это в лоб, ветвистыми if-ами, и тут меня торкнуло - в мозгу всплыло: «Совершенная дизъюнктивная нормальная форма». Точно!
   Построил таблицу истинности, вывел из нее длиннющую СКНФ, затем, пользуясь правилом Де Моргана и другими логическими операциями, упростил ее и получил вменяемую булеву функцию. Быстренько нарисовал на бумажке логическую схему полученной функции и вручную прогнал через нее основные строки таблицы истинности. Потратив на все про все около 15 минут, и получив вместо простыни неудобоваримого кода, одну красивую строку, я понял, что не зря Аюб Акбашевич влепил мне трояк по дискретной математике, и не зря я её (дискретку) потом ботал для пересдачи. Совсем не зря, хотя в то время так не казалось.

2 comments:

Ilya Troitskiy said...

Да. Ностальгия. Жаль только, что такие моменты не часты, и иногда всё же читабельность кода становится более важной. Случай с семью логическими переменными, конечно, жёсток, но иногда бывает полезнее разбить всё сложное лог. выражение на вменяемые подвыражения, оформив их в виде функций с человеческим именем, и тогда читабельность выигрывает, а это поважнее оптимизации, ИМХО, ибо понять, что реально вычисляет твоя преобразованная СКНФ потом уже будет нельзя.
А, вообще, согласен, испытываешь радость, когда удается применить на деле что-то из институтского "багажа". Отличный пост!

Bashir Magomedov said...

Спасибо. Да, не часто понимаешь, что та фигня которой тебя пичкали в универе, вовсе не такая уж и фигня :). Насчет вменяемых выражений, то можно было бы сделать и так, тогда получалось четыре переменных - т.е. более четырех вызовов функций с длинными именами (длинными т.к., это нужно для вменяемости). Т.е. не стоило оно того, хотя да, практика конечно правильная. Я ограничился комментарием, где-то не 10 строк, поясняя, что именно эта формула делает. Да и в javascript-e это было, думаю Фаулер не особо расстроится, если узнает :)