Программа минимизации логической ф-ии до 29 переменных методом Закревского.
Автор : Райцин Михаил (Falcone).
История
Системные требования
Время работы
Спецификация
03.09.2004 kernel v2.03 (dll version)
Изменена структура процедур.
30.08.2004 kernel v2.02 (dll version)
Ядро скомпилировано в в иде DLL - библиотеки. Отлажено и проверено.30.08.2004 kernel v2.02 (delphi version)
Внесены некоторые доработки и изменения. Программа готова к использованию.27.08.2004 kernel v2.0 (delphi version)
Программа переписана полностью.
Заменена основная концепция поиска интервала, что дало очеть ощутимые результаты: (на 16 переменных < 50 с. !!!). "Сырая", недоработання, но, тем не менее, работоспособная и очень производительная.25.08.2004 kernel v1.39 (delphi version)
Небольшая оптимизация, ускорившая работу программы на 15 - 30 %.22.08.2004 kernel v1.38 (delphi version)
Исправлена ошибка при формировании карты карно с ДНФ функции.
Исправлена ошибка, возникающая при нечетном кол-ве переменных.07.08.2004 kernel v1.37 (delphi version)
Внесены изменения в структуру программы, повлекшие за собой увеличение скорости программы. (примерно на 110 - 120 %)07.08.2004 kernel v1.33+ (delphi version)
Решена проблема с созданием и удалением директории временных файлов. Внесены незначительные изменения в структуру программы.06.08.2004 kernel v1.33 (delphi version)
Проведен ряд оптимизаций:
- переписана ф-ия подсчета степени двойки на языке ассемблерС учетом изменений программа улучшила скорость по сравнению с версией v1.27(dos version) приблизительно в 2 раза.
- переписаны процедуры нахождения покрывающего интервала
01.08.2004 kernel v1.30 (delphi version)
Полностью переписан алгоритм подсчета соседей в карте Карно. Опимизация сократила время подсчета примерно в 250 - 300 раз! Изменен срособ хранения файла комбинаторных переборов (вместо одного файла - N+1 файлов, где N - количество переменных). Ядро отлажено и проверено на работоспособность. Возник вопрос о детализации ядра.28.07.2004 v1.20 (delphi version)
Программа скомпилирована под Delphi5.0. Проверена на работоспособность. Возникла ошибка при работе с функцией от 1 переменной.
28.07.2004 v1.20 (consol version)
Заменен алгоритм оптимизации в процедуре поиска покрывающего интервала.
Данная оптимизация, в среднем, повысила производительность программы в 2 раза. Полностью переписана структура программы. Написаны комментарии. Выделены основные функции :- формирование карты Карно с разных источниковПолностью консольная версия без всякого интерфейса. Увеличено максимальное количество переменных до 12. Убрана "защита от дурака". Программа подготовлена к реализации в виде tpu - модуля.
- просчет соседей
- расчет максимального интервала для одной выбранной точки
- реализация алгоритма Закревского28.07.2004 v1.15
Проведена оптимизация в процедуре поиска максимального покрывающего интервала (еще более ограничен перебор). Идет подготовка к глобализации ф-ий и процедур.
25.07.2004 v1.14
Исправлена фатальная ошибка, приводившая к сбою в программе при тождественной или ложной функции.БикЮ Исправлена ошибка в процедуре записи карты в файл.
25.07.2004 v1.13
Исправлена ошибка в работе процедуры формул троичной логики в привычную ТДНФ (процедура пропускала первую коньюнкцию). Написана процедура записи карты карно в файл в привычном для человека виде.
Проблемы : при записи в файл возникает дополнительные временные затраты; с ошибкой работает запись интервалов длиной 0; не удается отобразить линии переменных по строкам.
Внесены небольшие коррективы и исправления.
25.07.2004 v1.11
Внесены небольшие изменения в структуру программы. Написан модуль преобразований формул троичной логики в привычную ТДНФ.
24.07.2004 v1.1
Полностью переписан и оптимизирован алгоритм просчета всех импликант.
Использование нового алгоритма позволило сократить временные затраты на расчет файла более, чем в 500 раз!
24.07.2004 v1.01
Программа оптимизирована благодаря введению отдельной процедуры покрытия точек степени 0.
Рассмотрен случай тождественной и ложной ф-ии (true и false соотв.).
23.07.2004 v1.0
Создана первая рабочая версия версия Karno v1.0.
Минимизирует ф-ии от 1 до 10 переменных. Выдает резудьтат в формулах троичной логики. Не решен вопрос о хранении и использовании файла возможных импликант.май - июнь 2004 v0.01 - v0.37
- Формирование карты Карно с таблицы истинности
- Формирование карты Карно непосредственно
- просчет "соседей" - точек, симметричных данной (глючит)
- написаны основы интерфейса
ОС : Windows 98/Me/2000/Xp
Использование Windows 98/Me нежелательно! (см. раздел Инсталляция).
Требования к аппаратуре:
- 16 Мб оперативной памяти (128 Мб рекомендуется)
- процессор с тактовой частотой 200 Мгц (1.3 ГГц рекомендуется)
- 400 Мб свободного места на жестком диске
- файл подкачки 100 Мб (1 Гб рекомендуется)
- средства ввода - вывода (клавиатура, дисплей)
Количество переменных Время 1 <= n <= 10 системными функциями изменение времени замерить не удаётся 11 не более 0.5 с. 12 не более 1 с. 13 не более 2 с. 14 не более 5 с. 15 не более 15 с. 16 не более 45 c. 20 не более 2 ч. (7200 с.) 29 не известно
Входные данные:
tfile1.txt :
количество переменных (одно натуральное число без пробела в одну строку)tfile2.txt :
способ ввода карты Карно
- (в файле указать 1) - ввод непосредственно карты
- (в файле указать 2) - ввод таблицы истинности ф-ии
- (в файле указать 3) - ввод карты через ДНФ ф-ии
tfile3.txt :
(tfile2.txt : 1) : карта Карно в виде матрицы размером 2^((n div 2) + (n mod 2)) на 2^(n div 2)
- числа(0 или 1) записаны через пробел.
- в конце строки пробела нет!
- в конце файла нет пустых строк!
(tfile2.txt : 2) : в файле записаны числа(0 или 1) по одному числу в каждой строке без пробелов
- в конце файла нет пустых строк!
(tfile2.txt : 3) : в файле построчно записаны коньюнкции ДНФ в формулах 3-ой логики :
1 переменная присутствует в коньюнкции 0 переменная отсутствует в коньюнкции -1 переменная присутствует в коньюнкции с отрицанием
- числа(0 или 1 или -1) записаны через пробел.
- в конце файла нет пустых строк!
Выходные данные:
TEMP директория с файлами комбинаторных переборов в определенном порядке
(в более поздних версиях будет удаляться автоматически)outfile3.txt файл с последней коньюнкцией
(в него будет заноситься максимальный интервал(коньюнкция),
покрывающий выбранную точку)outfile4.txt файл с ТДНФ (в формулах 3-ой логики)