Архив за 26 сентября 2018 - 4

Данная статья является, в некоторой степени, продолжением моей статьи по минимизации логических функций методом Квайна-Мак’Класки. В ней рассматривался случай с полностью определёнными логическими функциями (хотя этого в ней прямо не упоминалось, а только подразумевалось). В реальности такой случай встречается достаточно редко, когда количество входных переменных мало. Частично или не полностью определенными называются логические функции, значения которых заданы лишь для части Q из полного множества P= возможных наборов (термов) их аргументов (переменных) количеством N, т. е. Q < P. Такая ситуация встречается на практике в большинстве случаев применений алгоритмов оптимизации логических функций. Действительно, например, если число входных переменных N=30, что является заурядным случаем, например на финансовых рынках, то объём входной обучающей выборки должен составлять порядка > элементарных уникальных термов. Такой массив данных встречается не в каждой даже очень крупной организации, не говоря уже о частных лицах, т. е. это уже сфера BigData, использования ЦОД-ов и т. д.

Поэтому на практике чаще всего минимизируемые логические функции будут определены не полностью просто в силу отсутствия необходимого количества накопленных данных или в силу разных других объективных причин (например, не хватает места для их хранения). Возникает вопрос о возможности «обхода» этой неприятности при использовании алгоритма, работающего с полностью определённым набором терм логической функции, таким как, например, из предыдущей моей статьи.
Читать полностью »