Рубрика «Мак-Класки»

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

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

К рассмотрению предлагается одна из возможных реализаций алгоритма минимизации логических (булевых) функций (ЛФ) заданных в виде совершенной дизъюнктивной нормальной формы (СДНФ) методом КвайнаМак-Класки (далее просто Мак-Класки) и проблемы, выявленные при её тестировании. В исследуемом варианте алгоритм Мак-Класки реализован на языке C# с использованием Generic-коллекций библиотеки .NET.

Хотелось бы отметить, что задача минимизации ЛФ, по моему мнению, незаслуженно обходится стороной в тематике алгоритмов машинного обучения, т. к. по своему смыслу она реализует процедуру обучения с учителем для определённого набора входных терм (простых конъюнкций), на которых оптимизируемая функция принимает истинное (true) значение. Следовательно, этот набор входных терм, из общего их возможного числа $inline$2^N$inline$, где N – количество двух классовых категориальных (двоичных) переменных в термах, является обучающей выборкой для задачи обучения с учителем с известным (данном случае истинным) выходным значением целевой функции. Для всех остальных возможных терм, не входящих в обучающую выборку, минимизированная ЛФ должна принимать ложное (false) значение.

Одним из легко реализуемых для любого количества входных переменных алгоритмов минимизации ЛФ является метод Мак-Класки. Согласно теории метод Мак-Класки состоит из двух основных этапов:
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js