Полиномиальные алгоритмы решения переборных задач тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Стрыгин, Владимир Захарович
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2000
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.З.Ломоносова (МГУ) ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНО" МАТЕМАТИКИ И КИБЕРНЕТИКИ (ВМиК)
Ка правах рукописи УДК 319.6; 512.8
Стрыгин Владимир Захарович ПОЛИНОМИАЛЬНЫЕ АЛГОРИТМЫ РЕШЕНИЯ ПЕРЕБОРНЫХ ЗАДАЧ
(oi.oi.o9 - математическая кибернетика, 01.01.06 - математическая логика, алгебра я теория чисел)
Автореферат диссертации на соискание ученой степени доктора физико-математических наук
Москва 2000 г-
Работа выполнена в Центральном аэрогидродинамическом инститз те имени профессора Н.Е.Жуковского ШАГИ).
Официальные оппоненты:
1. доктор физико-математических наук, Алексеев В.Б.,
2. доктор Физико-математических наук Марченков С.С.,
3. доктор Физико-математических наук Бухараев Р.Г.
Ведущее предприятие: Вычислительный центр РАН.
Защита состоится 21 апреля гооо г. в и часов на заседай диссертационного совета Д о 5з. оз. за при Московском государстве; нон университете по присуждению ученой степени доктора Физик< математических наук по адресу-, поезд, Москва, Воробьевы гор) МГУ, Факультет вычислительной математики и кибернетики, ауд. 68.
тел. 3 39-17-90.
С диссертацией можно ознакомиться в библиотеке Факультета В1 числительной математики к кибернетики МГУ.
Автореферат разослан 21 марта 2 о по г. Ученый секретарь совета
профессор Трифонов К.:
I . ОБЩАЯ ХАРАКТЕРИСТИК«! РАБОТЫ
Актуальность темы. Кибернетику (инфсрмгтику. сотриtрг не tone«) можко определить как науку о Формах и алгоритмах представления, преобразования, сбора, хранения, поиска и передачи информации в естёсТвенных и искусственных, биологических, технических и социальных системах, в частности информационных измерительных, поисковых, вычислительных, управляющих, экспертных интеллектуальных сие тема'Х И системах искусственного (и естественного) интеллекта. Формы йрёдставления и алгоритмы преобразована информации непосредственно определяют сложность создаваемых систем и эффективность иХ функционирования. Это особенно относится к переборным (или комбинаторным) задачам (для которых пока не найдены алгоритмы реше ния. не содержащие в той или иной мере полгый перебор всех возмож ных вариантов), число которых последние тридцать лет непрерывно растет во всех областях человеческой деятельности и отсутствие эф Фертивных (полиномиальных) алгоритмов решения которых стало суще стеенным тормозом в развитии научно технич?ского прогресса.
Еще в 1Я5 4 году Яблонским C.B. была выдвинута гипотеза о неу странимости полного перебора в таких задачс.х. как минимизация бу леьых функций, синтез минимальных контактных схем и схем из Функ цокальных элементов. Этими задачами занимались, в частности, Яблонский C.B., Журавлев Ю.И. и Лупгнов С.Б. В Ю71 году канадский математик Кук С.А. выдвинул гипотезу, а в 1072 году американский математик Карп Р-М. доказал теорему о сводимости (эквивалентности) всех np полных (т.е. универсальных) переборных (или комбинатор ных) задач друг к другу. Гипотеза предполагает, что или все мг полные задачи имеют полиномиальный от длины входа алгоритм реше ния (f=np), или ни одна из них такого алгоритма не имеет (p^np). Построение полиномиального на детерминированной машине Тьюринга
-Ч —
алгоритма для любой из ыр-полных задач означает автоматическое построение таких алгоритмов для всех остальных яр-полных задач. При этом мр-полными назывались, в частности, задачи, которые можно сформулировать как задачи распознавания языков, или свойств множеств (с ответом "да" или "нет"), решаемые недетерминированной машиной Тьюринга за полиномиальное время. Первой нр-полной задачей была задача выполнимости, или обратная ей задача определения общезначимости (тавтологичности) булевой формулы (Кук С.А). В 19 79 году в книге "Вычислительные машины и труднорешаемые задачи Г:вве дение в теорию кр-полноты]" (М.: Мир. 1982, 4юс) американские математики Гэри М.Р. и Джонсон Д.С. развили теорию иг-полноты и да ли формулировки трехсот яр-полных задач.
Приведем набор коротких цитат иг этой книги:
"Вопрос о том, действительно ли ыр-полные задачи труднорешае мы, в настоящее время считается одним из основных открытых вопро сов современной математики и теоретической кибернетики" С с г п). "нр-полнота задачи означает, что для ее решения полиномиальным ал горитмом требуется по крайней мере крупное открытие" (сгя). "Сов ременные методы доказательства не достаточны ни для доказательст ва того, что р#кр. ни того, что р-.чг. эти методы бесполезны и для решения других открытых вопросов" (сгз1). "Для решения вопросов о взаимоотношениях между классами р и яр, а также других классов языков, вероятно, требуются совершенно иные методы доказательства. В том случае, конечно, если вообще подобные вопросы можно решить" (с2з1). "По крайней мере в принципе, вопросы такого типа могут быть независимыми от теории множеств и. следовательно, неразрешимыми при использовании стандартных логических средств. Хотя авторы не так пессимистически смотрят на разрешимость вопроса о взаи моотношении классов р и пр. никто не надеется, что этот вопрос бу дет решен в скором времени" (с2з1) .
Фактически выше описаны ступени Формирования и осознания кри зиса математики, т.е. математической логики (исчисления высказыва ний и предикатов) и оснований математики (теории множеств, теории доказательств, теории алгоритмов), вызванного массовым появлением переборных задач.
Недостаточность (или непригодность) средств классической мате матлческой логики (исчисления высказываний и предикатов) и основа ний математики (теории множеств, теории доказательств, теории ал горэтмов) для решения переборных задач сделала возможными и нас тоятельно необходимыми поиски нетрадиционннх подходов, логических средств, форм представлений информации и алгоритмов ее обработки, не укладывающихся ь прокрустово ло:ке классической математической логики и оснований математики.
Целью диссертационной работы является получение ответ.-» на одич из основных открытых вопросов современной математики и теоре тичэской кибернетики (информатики) о существовании (возможности построения) полиномиальных алгоритмов решения переборных задач, или об устранимости перебора в дискретных экстремальных задачах.
Пути достижения цели: разработка новой математической модели:
построение полиномиальных алгоритмов решения нескольких перебор пых задач в этой модели;
- построение абстрактной ЭВМ нового типа для решения переборных задач;
опровержение гипотезы сводимости ир полных переборных задач друг к другу и гипотезы принципиальной неустранимости перебора в них.
Научная новизна диссертации. Получен положительный ответ на один из основных открытых вопросов современной математики и теоре тической кибернетики (информатики) о существовании (возможности
построения) полиномиальных алгоритмов решения переборных задач, или об устранимости перебора в дискретных экстремальных задачах.
Разработана новая модель дискретной математики матричная лб гика, открывающая новое направление в философии математики, обеспечивающая решение ряда переборных задач полиномиальными алгорит мами и включающая в себя: новь» аксиомы теории минимизации булевых Функций, исчисления высказываний, баз данных, знаний и конечного исчисления предикатов, в том числе закон третьего "г и не Р" как основной закон мышления, сжатия информации и образова ния понятий: новые нетрадиционные подходы, логические' средства. Формы представления и методы обработки информации, новое содержа ние основных понятий математической логики (исчисление высказыва ний и предикатов) и оснований математики (теории множеств, теории доказательств, теории алгоритмов).
Построены полиномиальные от и2п (N«1...3) и от длины входа («04...7) по времени и памяти алгоритмы решения ряда кр-полных пе реборных задач: 11 минимизации полностью определенных булевых Фун кций п переменных в дизъюнктивных нормальных Формах (о покрытии): 2) синтеза минимальных схем из Функциональных элементов И НЕ (Фун кций Шеффера): з) синтеза минимальных контактных схем: 1) выявле ния общезначимости (выполнимости) булевых Формул: г>) о разложении булевой Функции на изолированные подфункции: «) о независимом мно жестве (рабочих наборов, не имеющих рабочих соседей); т) [[острое ния и функционирования базы данных и знаний.
Построены классы булевых Функций и их суперпозиций, имеющих полиномиальные степени 2 . . . 4 от тп (сложность с ( л ) <2'¥л ) алгорит мы минимизации: типа шахматная доска, разомкнутая и замкнутая тон кая и толстая цепь, метацепь (с(»(иг" )г ), плотных б.ф.(с(п)<гн" )
зп-£
и случайных ("почти всех") Функций (с(и)<г ). Установлено, что не существует Функций сложнее плотных, а случайные б.Ф. являются
суперпозицией Функций типа шахматная доска л плотных б.ф. Постро ен универсальный алгоритм, который обеспечивает точное решение за дач:* минимизации практически любой б.ф. ¡для неизвестных о ф по грешность не превышает нескольких процентов) и определяет слож ность и точность универсальных алгоритмов синтеза минимальных кон тактных схем и схем из функциональных элементов И НЕ (Функций Шеф Фер.а). описываемых булевыми Функциями.
Предложены архитектура, алгоритмы Фэтпсшгонировалигг и схемные решения ЭВМ принципиально нового тина комбинаторной машины (КМ! которая открывает новое направление в развитии вычиолитлыюй т*х никл и обеспечивает решение полиномиальными и линейными от длины входа алгоритмами двойных переборных задач, слишком сложных для их решения традиционными средствами.
Построена абстрактная машина баз данных и гшаний. в которой аксиомы, правило вывода и клкмны исчисления предикатов клаосичос кой млтомптич-'я'-кой логики являются ненугшымл и заменяются операци ями непосредственно над множествами строк записей таблиц парамет ров бааы данных и знаний о предварительной юдготоркой отгадтов.
Установлено, что в предложенной матчеи.чтлчеекой модели матри •той логике ложными являются гипотеза Кука С.А. (и теорема Кар па p.m.) о сводимости м- полных переборных задач друг к другу и гипотеза Яблонского C.B. о принципиальной неустранимое™ перебора в задачах минимизации булевых Функций, синтэза минимальных контак тных схем и схем из Функциональных »лемтггог. а также широко рас пространенноэ мнение о том. что все иг полные задачи не имеют по линомиальных алгоритмов решения.
Практическая значимость диссертации состоит прежде всего в том. что она знаменует собой начало выхода из кризиса, вызванного массовым появлением нерешенных переборных задач и отсутствием средств для их решения в современной магзмагике и теоретической
-s -
кибернетике (информатике). Диссертация позволяет многим тысячам исследователей в различных областях науки и техники приступить к поиску (построению) полиномиальных алгоритмов решения своих переборных задач, зная, что такое решение принципиально возможно (в частности с использованием новой математической модели - матричной логики). а не ограничиваться признанием нерешабельности этих задач в результате их сведения к известным np-полным (т.е. универсальным) переборным задачам, как это до сих пор было в соответст вии с гипотезой Кука С.А. (и теоремой Карпа P.M.) о сводимости np' полных задач друг к другу, гипотезой Яблонского C.B. о принципи альной неустранимости перебора в некоторых переборных задачах и широко распространенным мнением о том. что все np-полные задачи действительно являются труднорешаемыми, т.е. не имеют полиномиаль ных алгоритмов решения.
Диссертация является теоретическим обоснованием необходимости и- возможности создания ЭБМ принципиально нового типа - комбинатор ной машины для решения полиномиальными и линейными от длины входа по времени алгоритмами двойных переборных задач, - которая явля ется новым направлением в развитии вычислительной техники.
Применение результатов диссертации позволяет повысить эФФек тивность интеллектуальных систем и систем искусственного иителлик та, в частности систем автоматизированного проектирования больших интегральных схем (БИС и СБИС) и машин баз данных и знаний.
Автор защищает:
1. Утверждение о существовании (возможности построения) полиномиальных алгоритмов решения переборных задач, или об устранимо сти перебора в дискретных экстремальных задачах, т.е. утверждение о ложности гипотезы Кука с.а. (теоремы Карпа P.M. и теории np-полноты Гзри м.р. и Джонсона д.с.) о сводимости np-полных (т.е. универсальных) переборных задач друг к другу, утверждение о ложности
гипотезы Яблонского C.B. о принципиальной неустранимости перебора в некоторых дискретных экстремальных задачах (минимизации булевых Функций, синтеза минимальных контактных схем и схем из функциона льнах элементов), а также утверждение о ложности широко раопро стрэненного мнения о том, что все чг-полиые переборные задачи дей ствлтельно являются труднорешаемым.ь т.'З. не имеют полиномиальных алгоритмов решения.
2. Новую модель дискретной мат*?мати:ш - матричную логику, отк рывающую новое направление в философии математики, обеспечивающую решение ряда переборных задач полиномиальными алгоритмами и вклю чающую в себя: новые аксиомы теории минимизации булевых Функций, исчисления высказываний, баз дакныч. знаний и конечного исчвсле ния предикатов, в том числе закон третього "г и не г" как основ ной закон мышления, сжатия информации и образования понятий: но вые нетрадиционные подходы, логические средства. формы представле ния и методы обработки информации, новое содержание основных поня тий математической логики (исчисления высказываний и предикатов) и оснований математики (теории множеств теории доказательств, те орил алгоритмов).
л. Полиномиальные от тп (n<.>i...:m и от длины входа (N04...7) по времени и памяти алгоритмы решения конкретных кг полных пере борных задач-. U минимизации полностью определенных булевых Функ ций il переменных в дизъюнктивных нормальных Формах (о покрытии): 2) синтеза минимальных схем из Функциональных элементов И НЕ (Фун кциа ШеФФера); я) синтеза минимальных контактных схем: 4) выявле ния общезначимости (выполнимости) булевых Формул; г> ) о разложении булэвой Функции на изолированные подфункции; в) о независимом множестве (рабочих наборов, не имеющих рабочих соседей); 7) построе ния и Функционирования базы данных и знаний.
4. Классы булевых функций и их суперпозиций, имеющих полиноми-
альные степени г...4 от п2п (сложность с(п)<2^"^) алгоритмы минимизации: типа шахматная доска, разомкнутая и замкнутая тонкая и толстая цепь, метацепь (с(п^п2-ггп ) . плотных функций Васильева О. Л. (с с п)<21"1) и случайных ("почти всех") Функций (с(п)<г3п 2 ). Утверждение о том. что не существует функций сложнее плотных, а случайные б.ф. являются суперпозицией Функций типа шахматная доска и плотных б.ф. Универсальный алгоритм, который обеспечивает точное решение задачи минимизации практически любой б.ф. (для неизвестных б.ф. погрешность не превышает нескольких процентов) и определяет сложность и точность универсальных алгоритмов синтеза минимальных контактных схем и схем из функциональных элементов (Функций ШеФФера), описываемых булевыми Функциями.
5. Архитектуру, алгоритмы Функционирования и схемные решения ЭВМ принципиально нового типа - комбинаторной машины (КМ) для решения полиномиальными и линейными от длины входа алгоритмами двойных переборных задач, слишком сложных для их решения традиционными средствами, - которая открывает новое направление в развитии вычислительной техники.
6. Абстрактную машину баз данных и знаний, в которой аксиомы, правила вывода и законы исчисления предикатов классической матема тической логики являются ненужными и заменяются операциями непосредственно над множествами строк записей таблиц параметров базы данных и знаний с предварительной подготовкой ответов.
7. Теоремы и их доказательства, являющиеся теоретическим обоснованием существования полиномиальных алгоритмов решения ряда переборных задач.
8. примеры применения разработанных полиномиальных алгоритмов для решения конкретных переборных задач.
Апробация работы. Основные научные результаты диссертационной работы обсуждены на 9-й Всесоюзной конференции по проблемам теоре-
тической кибернетики в г-Волгограде а сентябре эээог,- на и-й меж республиканской конференции по математической логике в г.Казани б -8 октября 1ээ2г: на з-й конференции по искусственному интеллекту КИИ-9 2 в г.Твери 20-23 октября 3992г: на синпозиуме "Методы искус ственного интеллекта в компьютерах новых поколений" в г.Рязани в сентябре гээзг; на международной конференции, посвященной 7 5-ле тию ЦАГИ "Методы и средства экспериментальных исследований в аэро навтике" в г.Жуковском в ноябре 1ээзг; на конференции "Искусствен ный интеллект в 2 1-м веке" в г.Калининграде Московской обл. в ок тябре-ноябре 1Э95г: на 5-й конференции с международным участием "Искусственный интеллект КИИ-эт." в г.Казани в юяг.г.: с ними озна комились ведущие специалисты академии наук к высшей школы. Диссер тация рассмотрена руководством и специалистами ЦАГИ и научно тех ническим советом кафедры математической кибернетики МГУ.
Публикации. Основные результаты диссертации опубликованы и 17 статьях, докладах и тезисах конференций по теоретической кибернетике. математической логике, информатике, искусственному интеллек ту и его приложениям (1. . . 17 ].
Объем работы. Диссертация содержит 2?5 страниц, состоит из введения, четырех глав, заключения и приложений, в том числе г> та блии. 17 рисунков. 7(; наименований цитируемой литературы.
II. СОДЕРЖАНИЕ РАБОТЫ
Классы булевых Функций, имеющих полиномиальные алгоритмы минимизации
Предложен новый подход к минимизации булевых Функций, при ко торс-м не строится сокращенная ДНФ; не применяются операции склей ванк'я и поглощения в явном виде, т.к. не используются булевы Фор-
- /г-
мулы непосредственно-, не рассматривается произвольная ДНФ булевой Функции, а только совершенная ДНФ, а точнее - соответствующая ей таблица истинности, в частном случае в виде циклической карты (Карно) для 1) переменных плакат 1а (либо в виде мозаики пла кат 1в). Построение минимального г" и кратчайшего I1' покрытия, всегда совпадающих для полностью определенной булевой функции р. начинается не о произвольной конъюнкции и не с соответствующего ей произвольного рабочего (г и набора, а с рабочего набора, име ющего наибольшее число гу соседних запрещенных наборов. Поэтому первым этапом процесса минимизации булевой функции, заданной таблицей истинности, является группировка и нумерация рабочих и за
прещенных наборов и установление для каждого у-го (" 1.2.....¡о
рабочего набора числа гу соседних ему запрещенных (к -,2,...ь: и■ +Ъ'2Й). а иногда и рабочих >/у наборов, т.е. отличающихся от него значением одной из п переменных. Трудоемкость этого этапа не пре вышает полинома второй степени от и г." . Дальнейшие этапы процесса минимизации свои для каждого класса булевых функций. Клас. ' б.ф. выделяются по внешнему виду Функций на циклической карте и оггасы ваются с помощью указания числовых значений характеризующих Функ цию количественных параметров ее рабочих наборов и переменных; чи ела соседних запрещенных <\, и рабочих наборов, кратности^ по крытия рабочих наборов максимальными нодкубами размерности ко эффициентов относительной контрасноети переменных и др. При ми нимизации могут использоваться процедуры сжатия Функции, выделе ния изолированных подфункций и др.
В рамках нового подхода были выделены классы булевых Функций и их суперпозиций, имеющих полиномиальные от объема таблицы истин ности п2л алгоритмы минимизации (плакаты 1...7), типа: п шахматная доска; г) (тонкая) замкнутая и разомкнутая цепь; з) толстая замкнутая и разомкнутая цепь: 4) замкнутая и разомкнутая метацепь
и их суперпозиций между собой и с другими Функциями; г>) плотных Функций Васильева Ю-Л.. имеющих сложность алгоритма минимизации с(п), т.е. не выше полинома четвертой степени от иг", в то время как остальные классы имели сложность алгоритма не выше второй степени от тп . Показано, что нельзя построить Ф'ункцию (поско льку она не существует). которая имела б-( сложность алгоритма ми нимизашш выше полинома четвертой степени от иг". т.е. была бы сложнее плотной функции при том же п. Показано, что случайные бу левы функции, образующие класс "почти всех булевых Функций", таблица истинности для которых получается, например, путем подбрасы вания монеты, представляют собой суперпозицию булевых функций ти па шахматная доска и плотных Функций и имеют сложность алгоритма минимизации с(п)<г3п~г. т.е. не превышающую полином третьей сте пени от пгп. Универсальный (составной) алгоритм, включающий в се бя все частные точные алгоритмы для всех вцгеленных классов булевых Функций, обеспечивает за один проход алгоритма построение кра тчайшей V и минимальной I7" (т< г") ДКФ практически для всех пол ностыо определенных булевых Функций.
Полиномиальные алгоритмы решения переборных задач
Универсальный алгоритм минимизации полностью определенных бу левьх функций является необходимой составной и наиболее трудоем кой частью алгоритмов синтеза минимальньх схем из Функциональных элементов И-НЕ (функций ШеФФера) и контактных схем (плакаты п.о). ПерЕЫй из них содержит дополнительные алгоритмы уменьшения схемы за счет перехода к частично скобочным Форма«/' и к обратным (инвер сньа) функциям, т.е. за счет выход? из ДНФ. но при сохранении в базисе {И,ИЛИ.НЕ}. Второй содержит дополнительные алгоритмы умень
-Га-
шения числа контактов за счет перехода к скобочным формам (левая скобизация) и за счет непосредственной минимизации схемы без уме ньшения числа букв в скобочной Форме Функции (правая скобизация). Сложность алгоритма синтеза схемы определяется сложностью алгори тма минимизации описывающей схему булевой Функции и н*з превышает полином четвертой степени от пгп.
В рамках нового подхода построен полиномиальный алгоритм выя вления общезначимости (выполнимости) произвольной ДНФ булевой Фо рмулы (плакат ю). сложность которого линейно зависит от количе ства информации, получаемой в результате преобразования ДНФ в совершенную ДНФ и для "почти всех Формул" не превышает степени i.c от п2п. Это лучше известного алгоритма, использующего подстановку всех гп возможных наборов в Формулу и имеющего сложность не выше полинома второй степени от иг". Построенный алгоритм является не обходимой составной частью алгоритмов решения трех переборных за дач (минимизации б.Ф- и синтеза минимальных схем из ФЭ и контакт ных) и применяется для преобразования произвольной ДНФ булевой функции в таблицу истинности. Однако обеспечиваемая им возможность непосредственной проверки общезначимости (выполнимости) Формул ис числения высказываний и бескванторных Формул исчисления предика тов без использования аксиом, правил вывода и логических законов делает ненужными соответствующие разделы математической логики.
Приведены доводы в обоснование ложности гипотезы Кука с.А., теоремы Карпа P.M. и теории np-полноты Гэри М.Р. и Джонсона Д. Со сводимости всех np-полных задач друг к другу-
Разработана база данных на циклических картах (Карно) для дефектоскопии планера самолета и база данных с предварительной под готовкой ответов (плакаты 11...13). алгоритм описания и Функционирования которых является полиномиальным не выше второй степени от объема входных данных nm, где п - число строк записей, го - число
стслбцов-параметров исходной таблты данных и знаний. На их осно ве сформулированы первые семь (из девяти) аксиом теории баз дан ныу: и знаний и конечного исчисления пргдикатов (плакат мб).
' Метаматематическое, теоретико-множествегное и математико логическое обоснование решения некоторых переборных задач полиномиальными алгоритмами
В обоснование нового подхода к решению переборных задач были сФсрмулированы з з аксиом теории минимизации булевых Функций и ис числения высказываний (плакат 14а), две из них зависимые.
Новый подход сопровождается изменением содержания основных по нятий математической логики и оснований математики (теории множеств, теории доказательств, теории алгоритмов). Например, доказа тельством является доведение до очевидности любыми средствами, а не только указанными в классической математической логике, в част ности путем проверки истинности Формулы на всех наборах значений переменных. Теоремой исчисления высказываний и бескванторных предикатов является любое утверждение (булева Формула), истинность которого может быть непосредственно проверена на циклической кар те. Алгоритмом решения задачи является предписание (перечень дей ствий), обеспечивающее по исходной инФормагии о задаче получение конечной информации, содержащейся в утверждении или теореме, за число шагов (элементарных операций ЭВМ). з?висящее полиномиально от объема информации \0 . необходимого и достаточного для решения задачи. Доказательство работоспособности алгоритма основано на его построении, на свойствах циклической кг рты. на свойствах геометрических образов Функций на карте, на связи свойств (одни порождают другие с необходимостью) и, конечно, на аксиомах, содержащих в себе в какой-то мере все перечисленное.
Развитие содержания понятия переборности переборных задач позволяет ранжировать их по степени сложности и подрывает гипотезу Кука и теорему Карпа о их сводимости друг к другу. Задача с двой ным перебором (минимизация б-Ф. и синтез схем) решается путем замены перебора Функций (число которых равно г" или даже г ) перебором наборов (число которых равно гп ) и перебора свойств функций (число всех свойств неизвестно) перебором свойств наборов и их групп или последовательностей (число свойств мало, но не известно заранее). Поэтому утверждение о том, что универсальный алгоритм минимизирует точно любую булеву функцию, носит лишь вероятностный характер: по мере совершенствования алгоритма уменьшается возможное (ничтожно малое) число минимизируемых неточно Функций и возможная погрешность их минимизации (которая не превышает нескольких процентов) и обе характеристики уменьшаются до нуля с ростом п. в этом особенность содержания понятия универсального и точного алгоритма решения двойных переборных задач. Задача с одинарным перебо ром решается точно в связи с отсутствием перебора неизвестного числа свойств Функций. Например, в задаче выявления общезначимое ти булевой Формулы проверяется лишь одно свойство б-Ф- - равенство единице на всех рабочих наборах (г=1).
Решены полиномиальным степени 2 от п2п по времени и памяти алгоритмом еще две одинарные переборные задачи: разложения буле вой Функции на изолированные подфункции и ее частный случай - по строения максимального независимого множества (рабочих наборов, не имеющих рабочих соседей), являющийся известной ^-полной зада чей.
Сформулированные аксиомы (плакат 14а) могут рассматриваться как аксиомы теории множеств, описывающие по-новому не только ее собственные объекты (натуральные числа, множества, функции и др.) и их отношения, но и в определенной мере алгоритмы обработки (пре-
образования) содержащейся в них исходно!! информации о задаче с це лью получения решения задачи (т.е. требуемой в задаче выходной информации о ней)• Введение в теорию множеств двумерного представле ния n-мерного пространства двоичных (булевых) переменных и принци па множественной симметрии, позволяющего оперировать элементами п-мерного пространства (наборами двоичных переменных) в их двумерном представлении, открывает новую эру » теории множеств, математической логике, теоретической кибернетике л информатике. Циклическая карта позволяет свести алгебраические преобразования к ге омегрическим, более наглядным и потому сопев эффективным. При этом для решения задачи привлекаются образное (пространственное) мышление и интуиция, а не только логика, т.е. подключаются правое полушарие головного мозга (см. книгу: Спингер С, Дейч Г. Левый мозг, правый мозг: асимметрия мозга. Пе.5. с англ. М. . Мир. юпз. 2560) и мозжечок (из выступления экстрасенса Луценко Ю.Н. - 1Э90) дополнительно к левому полушарию, чего раньле не было. Без циклической карты решить задачу минимизации б.ф. было бы невозможно, но даже с ней потребовалось is лет.
Здесь уместно заметить, что новая Форма представления и обра ботки информации в виде карты Карно (Ю53) и визуально матричного метода А.Д.Закревского (toen) встретила резкое противодействие в первую очередь со стороны специалистов по математической логике и теоретической кибернетике. В in в i году советом по комплексной проблеме "Кибернетика" при Президиуме Акадэмии наук СССР было приня то решение о нецелесообразности проведения исследований в области полуинтуитивных методов минимизации булевых Функций как ненаучных, а также защиты их в виде диссертаций и их греподавания в вузах-Можно предположить, что этот административный запрет на пользование правым полушарием головного мозга способствовал оформлению кризиса математики в виде антинаучной гипотезы Кука, теоремы Кар
па и теории ир-полноты Гэри и Джонсона. Нужно ли говорить, что однополушарного знания не существует, это полузнание, или недозна-дие. Мозг един, его два полушария асимметричны и взаимно дополняют друг друга (логическое - мистическое (интуитивное), вычисления - пространственные представления, алгебра - геометрия, абстрактное - конкретное, анализ - синтез, наука - искусство). Для преодоления кризиса математики необходимо признать, что одной из задач теории множеств является ассимиляция новых Форм представления и обработки информации. При этом понятно, что новые Формы рождаются правым полушарием.
Существует жесткая зависимость возможности построения решавших задачу алгоритмов от правильного выбора Форм представления информации о задаче на всех этапах ее решения.
В рамках нового подхода не сводятся друг к другу рассмотренные переборные задачи и не годятся применявшиеся к ним ранее Формы представления информации (языки) и алгоритмы ее обработки (машины Тьюринга).
Закон третьего, комбинаторная машина и полиномиальные от длины входа алгоритмы решения переборных задач
Наряду с законом исключенного третьего ^+х;-= 1 •, Iе {1.....п})
в математическую логику, определяемую новым подходом к решению переборных задач, введен также закон третьего (х^ =1; ;)г{1,...,п}), который распространяется на переменные, отсутствующие в конъюнкциях ДНФ булевой Формулы Это, в частности, позволило решить задачу выявления общезначимости (выполнимости) булевых Формул линейным от длины входа по времени алгоритмом при объеме памяти пг" бит (таблица истинности). Реализация на ЭВМ закона третьего обеспечивает возможность групповой адресации, т.е. записи одинаковой
информации в 2т (те{1.....п}) ячеек памяти, адреса которых описы
ваются (п-ш)-местной конъюнкцией, за один: тгкт вместо гт тактов.
Разработаны архитектура, алгоритмы Функционирования и схем ные решения комбинаторной машины КМ, использующей закон третьего (групповую адресацию) и выполняющей операции в г" раз более зФ Фективные по сравнению с существующими в ЭВК (плакат ш). В качестве абстрактной машины КМ развивает теорию алгоритмов, заменяет машину Тьюринга и может применяться для доказательства решаемости переборных задач полиномиальными и линейными от длины входа по времени алгоритмами. В качестве конкретней машины КМ открывает новое направление в развитии вычислительной техники и обеспечивает практическое решение переборных задач, слишком сложных для их решения традиционными средствами вычислительной техники. Приведены примеры КМ для нескольких переборных задгч: исчисления высказываний (выявления общезначимости и выполнимости булевых Формул), минимизации булевых функций, синтеза минимальных контактных схем и схем из функциональных элементов и НЕ (Функций ШефФера).
Полиномиальными степени 2 от числа г. конъюнкций в ДНФ по вре мени и памяти алгоритмами решены задачи разложения булевой Функ ции на изолированные подфункции и ее частный случай построения максимального независимого множества (рабочих наборов, не имеющих рабочих соседей) (плакат ' г,) •
Построен полиномиальный от длины входа го времени и памяти алгоритм выявления общезначимости (выполнимости) булевых Формул (плакат 17). Для этого использованы закон третьего (для отсутствующих в конъюнкциях переменных). таблицы сравнения конъюнкций для исключения их пересечений и поглощений (построения однократного покрытия всех рабочих наборов Формулы) и проверка, что каждая из 2п букв п переменных покрывает ровно г^'1 рабочих наборов, вмес то проверки равенства на гп наборах. На примере трех задач по
- го -
казано, что задачи с одинарным перебором могут быть однозначно и точно решены на обычной ЭВМ полиномиальными от длины входа по времени и памяти алгоритмами. На примере других трех задач показано, что задачи с двойным перебором могут быть решены на обычной ЭВМ полиномиальными от тп по времени и памяти алгоритмами. С помощью комбинаторной машины они могут быть решены линейными от длины входа (точнее от числа I. конъюнкций в ДНФ булевой Функции) по време ни алгоритмами за счет многократного увеличения аппаратных затрат (в том числе на память) по сравнению с обычной ЭВМ.
Сформулированы аксиомы й.д теории баз данных и знаний и коне чного исчисления предикатов (см. плакат 14б). Построена абстрак тная машина баз данных и знаний и рассмотрены особенности ее реализации на универсальной и специализированной ЭВМ. в частности на комбинаторной машине. Поскольку истинность предикатов и предикат ных Формул проверяется непосредственно по таблицам базы данных или знаний, то исчисление предикатов становится ненужным и заменяется операциями непосредственно над множествами строк записей. на которых определенные столбцы-параметры принимают определенные значения.
Сформулированные 2 3 аксиомы (плакат м и закон третьего) тео рии минимизации булевых Функций, исчисления высказываний, баз дан ных, знаний и конечного исчисления предикатов Фактически образуют новую модель дискретной математики - матричную логику, в которой не используются многие основные понятия, аксиомы, правила вывода и законы классической математической логики (исчисления высказываний и предикатов) и оснований математики (теории множеств, теории доказательств, теории алгоритмов), в которой изменено, в частности, содержание понятий теоремы, доказательства, алгоритма, переборное™ переборных задач, универсальности и точности алгоритмов решения переборных задач и в которой ложными являются понятия
полноты (универсальности) переборных задач и их сводимости друг к другу, т.е. ложными являются гипотеза Кука С.А.. теорема Карпа P.M. и теория np-полноты Гэри М.Р. и Джексона Д.С. Матричная логи ка образует новое направление в философкк математики. Показана не состоятельность формальнологического метода исследования в диекре тноГ; математике ■
JTI. ВЫЕОДЫ
В результате проведенных исследований достигнута цель диссертационной работы, т.е. получен полс-жительны{ ответ на один из основных открытых вопросов современной математики и теоретической кибернетики (информатики) - о существовании (возможности построения) полиномиальных алгоритмов решения пересорных задач, или об устранимости перебора в дискретных экстремальных задачах. Для до стижения этой цели разработана новая модель дискретной математики матричная логика, построены полиномиальные алгоритмы решения нес кольких переборных задач в этой модели, построена абстрактная ЭВМ новсго типа для решения переборных задач и опровергнуты гипотезы об их сводимости друг к другу и о принципиальной неустранимое-и в них перебора. Автором разработаны теоретические положения, совокупность которых можно квалифицировать как ковое крупное достиже ние в развитии математической кибернетики и логики, в частности направления, связанного с решением переборных задач.
1. Сформулированы гз аксиомы теории минимизации булевых функций, исчисления высказываний, баз данных, знаний и конечного исчисления предикатов, которые Фактически образуют новую модель дискретной математики - матричную логику, которая открывает новое направление в философии математики и в которой не используются многие основные понятия, аксиомы, правила вывода и законы класси-
-zz-
ческой математической логики (исчисления высказываний и предикатов) и оснований математики (теории множеств, теории доказательств. теории алгоритмов), в которой изменено, в частности, содержание понятий доказательства, теоремы, алгоритма, переборности переборных задач и в которой ложными являются понятия np-полноты (универсальности) переборных задач и их сводимости друг к другу, т.е. ложными являются гипотеза Кука С.А., теорема Карпа Р'М. и теория np-полноты Гэри m.р. и Джонсона Д.С., гипотеза Яблонского C.B. о принципиальной неустранимости перебора в задачах минимизации булевых Функций, синтеза минимальных контактных схем и схем из Функциональных элементов, а также широко распространенное мнение о том. что все пг-полные задачи действительно являются трудно-решаемыми, т.е. не имеют полиномиальных алгоритмов решения-
2. Предложены новые подходы к решению переборных задач, ис пользующие новые Формы представления информации (циклическая кар-•та, мозаика, таблицы соседства наборов, относительной контрастно сти переменных, сравнения конъюнкций, перекрестных связей параметров и др.). количественные характеристики переменных и их наборов, новые методы обработки информации (минимизации булевых Функций, выделения изолированных подфункций, перехода к обратным функциям, конъюнкциям и их группам, к скобочным и частично-скобочным Формам, минимизации схемы ниже алгебраического минимума и др.), аксиомати ческое обоснование возможности решения некоторых переборных задач полиномиальными алгоритмами, новое содержание некоторых основных понятий математической логики и оснований математики.
3. Построены полиномиальные от »г" (Noi-..з) и от длины входа (no4...7) по времени и памяти алгоритмы решения нескольких переборных задач: 1) минимизации полностью определенных булевых Функций п переменных в дизъюнктивных нормальных Формах (о покрытии): 2) синтеза минимальных схем из Функциональных элементов И-НЕ (Фун-
кци-.й ШеФФера); з) синтеза минимальных контактных схем; D выявле ник общезначимости (выполнимости) булевых формул: 5) о разложении бухевой Функции на изолированные подфункции: к) о независимом множестве (рабочих наборов, не имеющих рабочих соседей); 7) построения и Функционирования базы данных и знаний.
4. Новый подход к минимизации булевых Функций позволил постро ить классы Функций и их суперпозиций, ккеющих полиномиальные сте пени 2...4 от mn алгоритмы минимизации (сложность с (и) -~гЧп ). ти па шахматная доска, разомкнутая и замкнутая тонкая и толстая цепь, метацепь (с(п)«па2гп), плотных Фуккыий 'Васильева Ю.Л.) (ein) < < гчп ) и случайных ("почти всех") Функции (с(п)<23"~г ). Установ лено, что не существует Функций сложнее плотных {с(п)<2Чп), а слу чайные б.ф. являются суперпозицией Фунрций типа шахматная доска и плотных б.ф. (с(п)<г3" z ). Построен универсальный алгоритм, кото рый обеспечивает точное решение задачи минимизации практически лю бой б.ф. (для неизвестных б.ф. погрешнссть не превышает нескольких процентов) и определяет сложность и точность универсальных алгоритмов синтеза минимальных контактных схем и схем из функциональных элементов И-НЕ (функций ШеФФера), описываемых булевыми функциями .
5. Предложены архитектура, алгоритмы Функционирования и схем ные решения комбинаторной машины vКМ), основанной на неклассической математической логике (законе третьего "р и не р") и выполняющей операции в г" раз более эффективные по сравнению с сущест вующими в ЭВМ. В качестве абстрактной маши.чы КМ развивает теорию алгоритмов, заменяет машину Тьюринга и можзт применяться для доказательства решаемости ряда np-полных перебэрных задач полиномиаль ными и линейными от длины входа алгоритмам!. В качестве конкрет ной машины КМ открывает новое направление з развитии вычислитель -ной техники и обеспечивает практическое реиение двойных перебор
ных задач, слишком сложных для их решения традиционными средствами.
6. Построена абстрактная машина баз данных и знаний и рассмотрены особенности ее реализации на универсальной и специализированной ЭВМ, в том числе на комбинаторной машине. При этом аксиомы, логические законы и правила вывода исчисления предикатов классической математической логики становятся ненужными и заменяются операциями непосредственно над множествами строк записей таблиц-параметров базы данных и знаний с предварительной подготовкой ответов.
V. Достоверность полученных результатов подтверждается доказательствами теорем и примерами применения разработанных алгоритмов. Они обсуждены на межреспубликанских конференциях по теоретической кибернетике (1990). математической логике (1902). информатике (1993), искусственному интеллекту (.1002.1995.1900) и его приложениям ( 1993) .
8. Практическая значимость диссертационной работы состоит прежде всего в том, что она позволяет многим тысячам исследователей в различных областях науки и техники приступить к поиску (построению) полиномиальных алгоритмов решения своих переборных задач, зная, что такое решение принципиально возможно (в частности с использованием новой математической модели - матричной логики), а не ограничиваться признанием их нерешабельности в результате их сведения к известным np-полным (т.е. универсальным) переборным задачам, как это до сих пор было в соответствии с гипотезой Кука С.А. (и теоремой Карпа P.M.) о сводимости np-полных задач друг к другу, гипотезой Яблонского C.B. о принципиальной неустранимости перебора в некоторых переборных задачах и широко распространенным мнением о том, что все np-полные задачи действительно являются труднорешаемыми, т.е. не имеют полиномиальных алгоритмов решения•
э. Научные выводы диссертации целесообразно использовать в
учзбных программах вузов для подготовки специалистов в области прикладной математики, теоретической кибернетики, информатики и вычислительной техники. Целесообразно лоручить министерству эконо мики совместно с Академией наук и министегством науки и техничее кой политики рассмотреть практические вопросы разработки. созда ния и внедрения ЭВМ принципиально нового типа комбинаторной машины для решения двойных переборных задач как нового направле ния в развитии вычислительной техники. Применение результатов дис сертации позволяет повысить эффективность интеллектуальных систем и систем искусственного интеллекта, в частности систем автоматизм рованного проектирования больших интегральных схем (БИС и СБИС) и машин баз данных и знаний.
Основное содержание диссертации изложено в следующих публика -
циях:
1. Стрыгин В.З. Классы булевых Фунхций. имеющих полиномиаль нь-е алгоритмы минимизации- Препринт ЦАГИ. М. . юэо. No.т. 7,тс.
2. Стрыгин В.З. Классы булевых Функций, имеющих полиномиаль ные алгоритмы минимизации. Проблемы геогетической кибернетики. Тезисы докладов о-й Всесоюзной конференции, сентябрь н)эог. Волгоградский гос.университет. Волгоград, ч i (л) , с-12.
.ч. Стрыгин В.З. Полиномиальный алгоритм минимизации случайных ("почти всех") булевых Функций. Препринт НАГИ. М.. н><)2. Попг.. юс.
■; . Стрыгиь' В.З. Полиномиальный алгоритм минимизации случайных ("почти всех") булевых функций. Одиннадцатая межреспубликанская конференция по математической логяке. 5-в октября тяг года. Ка занский госуниверситет. Тезисы сообщений. Казань, юэг. cisn.
5. Алехина Н-С., Стрыгин В.З. База данных на циклических кар тах (Карно) для дефектоскопии планера самолета. - Третья конФере нция по искусственному интеллекту КИИ зг. Сборник научных трудов
-Z6-
в двух томах, т.2, Тверь, 1992, сс55-57.
6. Стрыгин В.3■ Полиномиальный алгоритм выявления общезначимости (выполнимости) булевых Формул. - Препринт ЦАГИ, М., ¡ээз.
No96, 20с.
7. стрыгин В■3. Полиномиальный алгоритм синтеза минимальных схем из Функциональных элементов И-НЕ (функций ШеФФера). - Препринт ЦАГИ. М.. 1993. no9 3. 2 7C.
8. Стрыгин В-3. Формы представления и алгоритмы обработки информации (булевы Функции и базы данных в прочностном эксперимен те). - Международная конференция, посвященная 75-летию НАГИ: "Методы и средства экспериментальных исследований в аэронавтике". ноябрь 1993г. г.Жуковский. Тезисы докладов. Секция "Информатика и измерительно-вычислительные системы", е(4-14).
9. Стрыгин В.3. База данных с предварительной подготовкой ответов. - Труды симпозиума "Методы искусственного интеллекта в компьютерах новых поколений" 2й-зо сентября 19эзг. г.Рязань. Извес тия РАН. Техническая кибернетика. 1994, N02. ссгоо-212.
10. Стрыгин В-3 Полиномиальный алгоритм синтеза минимальных контактных схем. - Препринт ЦАГИ. M. , i994. воюг,. гг.с.
11. Стрыгин В-3. Метаматематическое, теоретико-множественное и математико-логическое обоснование решения некоторых np-полных задач полиномиальными алгоритмами. - Препринт ЦАГИ. М.. 199.1, N0IO6, 35C.
12. Стрыгин В.3. Закон третьего и линейный алгоритм выявления общезначимости (выполнимости) булевых Формул. - Препринт ЦАГИ.
М- , 1995, No98, 7 С.
13. Стрыгин В-3. Комбинаторная машина для np-полных задач искусственного интеллекта. - Доклад на конференции "Искусственный интеллект в 21-м веке" (зо октября - з ноября юэбг, г.Калининград Московской обл.). - Препринт ЦАГИ, 1996, M. , n0102, юс.
14. Стрыгин В.З. Машина баз данных л знаний. - г,-я конферен ция с международным участием "Искусственный интеллект КИИ по" 7 II октября 199бг, Казань. Сборник трудов в трех томах. Т.з. с279 гг.г.
15. Стрыгин В..3. Полиномиальный от длины входа по времени и памяти алгоритм выявления общезначимости (выполнимости) булевых формул. - Препринт ЦАГИ, 1996. N0 104. ОС.
16. стрыгин В.З. Матричная логика л комбинаторные машины. Препринт ЦАГИ, м., 1998, N0120, 19017. Стрыгин В.З. Критика Формальнологического метода исследования в дискретной математике. - Препринт ЦАГИ. м.. юоп, N«121. юс.
-Z8-
П/УЛк-схт 1
методы МИНИМИЗАЦИИ ВУЛЕВЫХ ФУНКЦИЙ (ЬМ).
КЛЯССЫ Б<Р. ТИПА ШАХ МЯТНАЯ ДОСКА (ШД)
О5оъна»9ния ■■
□ .И О
®
J 6 7 l
; 9 10 11 11
:! Ъ г' II 1*
.3 IS IS
элементарная ШД
tv=ConS*
циклическая О карта (Карно) — мноместбенна я симметрия
5"
Mosa и KCL Наооры g-lZ
Относ um?льна я контра стность переменных
«о о
0 •о
1
>i
о Ч)
Е
и iO ш «J
с
Суперпозиция ШД
Xi
1? а «2 t б о] а t £ h
- - — 1 гА а fc
- - - 1/г '4 % %
1 % г4 - - - %
'Л 1Л % - - - %
:*з)
(.01 а° ё' рЮ а,
К' * о Т ' *< г о ё '
k- rnax {k,J,
i
Ч 14:1S 16
• • • 0 0 0 0
- % VA
z 2 2 г 1
*S*4 • •
* ■ 4**
• •
TT • IT г
i Щ i .1 Ii
'm- ff
V- U - u¿¿> ч • •
x,
...а *, x, t.
's
смешанная
ШД
1уг- Const г*1,г, ь
.....аг
ж
-2.9-
П л о к л I
КЛДССЫ Б .00. ТИПЛ ЦЕПЬ
Элементарные и.впи-ъамкнутая разомкнутая
х3 ХУ__X,
-ГУЛУ/У/.^ -3
<2
в
*1 ч
I №
I сз э!
1 <а !э
ч <2 3
г^п-1
X, Х1
Суперпозиция■ цепей
Определение набороЬ
с Ч„ФП
-г
ЛЧ: *г
П /I с* к а гп 3
КЛАССЫ БМ ТИПЙ ТОЛСТАЯ ЦЕПЬ ф
разомкнутая т-и тапишны (тш2)
Замкнутая Т-й толщины (Т~2)
П л Ci t
КПЙСС Б.Ф. ШД МОЙ ЦЕПЬ
У
Замкнутая T-ù толщины (Т-2)
Определение набороЬ с xv=2
<г
Пл
5
ШСС ПЛОТНЫХ В.Ф. ВДОШЬЕВД ЮЛ
на рабочих наборах с 3,4 или 5 единицами
т^
х, хг
а
Определение рабочих на^ороб
■'//////////////////л >//////////
ьт 'М// ¿Ш
пф
1 в. я 7. я и л бОф
1 « • ч % Ч и Д » « %
и II ¥ л
I л. в. %
\ И « И.
1 I » • ч и » п. и • !1 « л И
и# и и • и. 11 и » »»
Д* ■*6
X, *г
* —лб...56, »-57...И; гy■^0¡
Ччср'Ы
^у = 2
агусР=9,2
-зз-
Пл
я КЯН1 о
ЧАСТНЫЙ СЛУЧАЙ СУПЕРПОЗИЦИЙ
ЦЕПЕЙ
У5Х6Х7ХЯ
Плак«m 7
кжс случайных споч г и Шх'ГЪ. ф.
n=7,а , 1П=23
Xv*5*6* 7
S
íí
öSi
•з S
/ТГ x,x2xj
в
S
Gs
U
il
и
3
■ »»}>>> i'jíiht' '-''1
m
Ыав
¿a
SI
й
дЗС
3
s
в
Irl
а
Е)
3
9«
«*
d
-*7
а
Определение 7y.qv>Rv,xv рабочих набороб
y4xsx6x1
Wfn Wir, Wiäf я г„< 2 5 & 3 3 2 > 2 3
9*- V Гб -г» V 2 Ч V 2 « Î.J f 2
: 2 2 1 S SA S 2 V з'з V 2 * 5.2 ♦ 2 ? » * 1
5 £ i V if z 2 5 V г « 2 J и К V ач К
Í f Л W V 2» 1-1 iî
i I t 4 V fi и lí V а * г'* и M
t s n't ♦.а з s X 3 3 Í.3 i а V Л « И
I M V л V г * S.» з г M в.1 Я s * Га 5 * V а чг V 1 ÎÎ
Ii 2 <1 г «i <( г J 3 V 14 и ÎÎ к к
Лу
Xj "в •*7
X, х2х3
URvi3; f¿3zys*7
ívcp'3'6' Rvop~2'1> Ävep-2,7
/7 Л ак <?
гтномтьный от п-з" мтпп сингш
НИНИММНЫХ СХЕМ Ш ФУНКЦИОНАЛЬНЫХ.
шпентов и-не (функция шефрер/п^
РОС^.Х,)-плотная Ад ¿.х^х^х? а =х,хг Щ (х5+х6 +х7)
Х^Х^ХуХ^
шахматная доска
у2.Х2Х3Х,,Х5Х6Х7
а = х^-хух^Ыб^ ■>
■V"
О!
-
Хз-
^ ■ а и ю гогтгч;
ШНЕ -1шт. 6И-НЕ - 7шт.
5И'НЕ-7шт.
п
з:
в — _ сн а—
е-
^ / —
а' д-12
*2 *б
Хз-
1
со
_ /8—Н
19 —
27— /2 _22Н
2*Г
з:
I
<г
1И-НЕ- 1Шт.
Шт.
5*.% с.<р.—30 без о.ф- -36
1- И
Г'-355=»5 Р'г21505= 141 букв.
П /1акят 9
полиномиальный от п2п алгоритм синтез/1 минимальных контактных схем _ (§)
/ Минимальная ДНФ Р" ^
г г
*3 XI,
и
х2 Хч
_М_I и
1*-
1-Н-^
и \IZ-J
1 1*4_
в*—]г----^—¿ц
3. 1-1-2 + правая скоВизация- =
3
IН^-Ш
3
Суперпозиция цепей'ОР-^б 5ук6 (контактов); 2)6« конт.,4*^1.85; 3)5&конт., г(=§§НП-, ^№£/7.
Г!/) сл к am 10
гтношльный ялгоритм выявления обще значимости (выполнимости) 5улевых формщ
ПРИМЕР /•" Определить, на каких наборах переменных /¡от срормула F(x,.....xj-xji+xfa+xtxa+ws+bn, -х^+х,^.
**XJ*S
ч&
to
25
49
31
35
26
Si
3<
30
Z2
62
38
5S
20,
■ *» ft, ft,). ***!*>
0v
¿J
-3 (x^i)
/ (X,*i) I (X,X3)
X, хгх3 6 I, *
O.viem: наборы H. 12.20,32.33,3436; ^ОООЮО-Ш^ц^б>
Xi^XjX^XfX^; ytXiXjX^XsXg; X^X^X^X^^Xg; Xt,'2X3 ; A.^^j^XyXg; X,^Xj X^XyXg.
ПРИМЕР 2 - Проверить общезначимость qюрмулы F(xt.xz,x})=
=!х,хг xj —[х,-~(хг—хг)]; а-в-a; а-И~а6
F=(Wz +xi)l = Wi + ^4><zJ*з 'МгЪ+Ъ+Ъ+Хз.
ъь.......................Отбет■ F*1.
T
Сложность слгоритма не пре-Ьышает полиноиа 1-й степени от \ !Л •'■3) 2.П" " " ч<-'С/7°
4 , переменных б.ср , А'^А.А-число коньюныши
(*г М Г г г г - !
к^-число дука о г-г/ конъюнкции. |
Для .почти 5сех' 5.ср. Е(£сдп)+2 (?де ^-размерность
у-го подкуба, Е-целая часть аргумента) и сложность С(п)■.
3 2 < (2п*г0)£
П-,.5
те. не преЬышарт полинома степени 1.5 от числа п-2п Ь'/одных данных, задающих таблицу истинности буледой формулы.
П/\а кат 11
база данных на циклических картах для дефектоскопии планера самолета\
Параметры
3
з «г О
паоаз
киша
ваза
пешп
□акт
ЕЗОПП наша псзав кзсиш пппо санов шсшв газов
ГШ
13
7777ЛУ 3
аЛ,
©г1 ®2=г фз «з@
/г
14
- • • - - 1
+ 1, • • 1 •
- - - - - - т "г -
'1
+
ш1 (¿г
со^сОц
f
) тля,
т Щ
- 1 1 г
1 3 1 3
\ 1 - -
1 1 1 1
®г
Ф
®
- 1 1 1
1 1 г 1
г ~ - -
г г г г
©1 ©2
- 1 3 г
ч 5 1 5
1 - - -
ч 5 Ч 6
©1 ©г Фз
+
аа □□ па □□
®1+6
- 7 • •
т 2 7 7
• • Г
7 • 7
Ф6
ПОСТРОЕНИЕ ОТВЕТА т шт 01'
ПРИ НАРАБОТКЕ ОТ 30500 ДО 31650 ПОЛЕТОВ (ф^ф3) НАЙТИ НАРУШНЫЕ Ш1) УСТАЛОСТНЫЕ ТРЕЩИНЫ ДЛИНОЙ ДО 7 мп
у
®1
(
©1 ®г ©ъ Фч гШ
(®1+ФзЩ Я«
Пл а кат
5азд знаний по конструкции плднерд
V \0\ 1/1 [Г,
Структурная cxe.no. конструкции планера. ®
О
у=о.1,г 1-0.1 у*0
Ч
!/=2,3.4
г-г. г
У* 0.1
/г
2-5 у*0
6
¡1=5,7 г «2.5
7гУ77777777.
1
н-м.г 2-0.1
5 г-г
и
9
у
н<=г,з
3
Ч=г,г.ч г*1.г
7
У-4.5.6 г=г.з
У*1
15
11 »■7
2
У" О./, 2
5
</-.'^,5,6
г«2.з
_
14
19 г»з
v
х3
д.
ТАБЛИЦЫ СЬЯЗИ ПЕРЕПЕННЫХ У,г,у,Х
о
У-0,1
л«а<г
2 VI у4,5
хач.6- 9
7
3
V*!
у.6
®
шя '/¿¿¿///Ж
о Х'0,1,2 2-0 У-0 1 х=о,1.г 3 Х«ЗЛ5 2-1 у=0 2 Х'0.:Ч % %
Ч X* 1,4.6.1 1-г уя* 5 Х*6-9 2-2 У = * см &• Х-11ЫО г«-з
йг Г Уз
О
г-а г
Х = 0...5
Ч77777П77У V)
1
г«г.з
V = «/... 7 х.3,45-«
V - агрегаты
2 - конструктивные группа У -конструктивные подгруппы X - конструктивные мементы
-ко -
БЛЗЙ ДАННЫХ С ПРЕДВАРИТЕЛЬНОЙ ПОДЕ010ВКОЙ ОТВЕТОВ
ПРИМЕР ЗЛПРОСД <3: Определить нопера записей о побреждениях В о5ши6ке (х3) нижних (у,) панелей (20) нособой части фюьеляша (уа) Ил-86 за бремя от 3^1.10.79 до дг =10.10.84. Табл. 1.6
А/2 значения параметра ем Значение параметра бм Номера строк записей Кратность (побторяе-м ость)
1 гч 3 1. </,<^,73... 76. /66.../69. П6. /32 а
(Ю 2.15./9.25...29, к2, 5В... 53, а...6з. &7. 88. иб.-.мг. т. /«а, /70. >77, Ш 32
Та 5л. 1.5
№ значения параметра. 5(4) Значение параметра sfy) Номера строк записей ^A^j Кратность
11 1 S6...5S, 7В...83, m...1kZ, 181 -/Vy 17
Та5л. 2.5
•№$.п. 5 (у) З.п. 6 (X) in. 11 (дата) з.п. 1 (номера строк)
11 г 15.2k. 25. 33. 52 5S...58, 78... S3, 136... 142 =//у
I 1 5 17
Та5л. 2.6
№ ЗЛ 6 (к) зл 6 ty) З.П. 11 1дата) З.П. 1 (номера строк записей)
2 2,7, 11 1.6.8.10,11.13.15.19, г«, 25,27,28.33,3'/, 48,52 2.15.19,2S...29, k2.56...5Q, 7&..83.87,83, 136... т,п М. 170.177. 181
I 3 16 32
Та 5л. 1.11
Nun. 11 (дата) ал. 11 (дата) З.П. 1 (номера строк) Кратность
15 16,12. 85 к к, 55... 59 6
19.9.80 v 78 1
25 „ - 25.6.86 79.33 г
Ф) 1.11.82 v 136... 1к5 ~М(Дзз) 10
52 13. 1.86 181 /
Ombm R:
П /1 сскат 14
¿:
аксиомы теории минимизации булевых функций нй основе циклической кйрты
I О ИНФОРМАЦИОННОЙ ДОСТАТОЧНОСТИ ЗАДАЧИ; ® 2.0 ПРЕДСТАВЛЕНИИ НАТУРАЛЬНЫХ ЧИСЕЛ НА КАРТЕ -.
3.0 СВОЙСТВЕ МНОЖЕСТВЕННОЙ СИММЕТРИИ КАРТЫ-, к О ПРИНАДЛЕЖНОСТИ Б.Ф. КЛАССУ ЛИБО СУПЕРПОЗИЦИИ ИХ: 5.0 НЕПРЕРЫВНОСТИ СВОЙСТВ Б.Ф. ;
б.0 РАВНОПРАВНОСТИ ПЕРЕПЕННЫХ Б.Ф. ;
7. О ЗАВИСИМОСТИ АЛГОРИТМА ОТ СВОЙСТВ Б.Ф.: 8.0 НЕВОЗМОЖНОСТИ ПОСТРОИТЬ ГШ ТАБЛИЦЫ ИСТИННОСТИ-. 9. О НЕПРЕРЫВНОСТИ СВОЙСТВ АЛГОРИТМА МИНИМИЗАЦИИ-. 10.0 ДОСТАТОЧНОСТИ ОДНОЙ Б.Ф. Д/!Я ПОСТРОЕНИЯ АЛГОРИТМА МИНИМИЗАЦИИ КЛАССА Б.Ф.; Ш. ья)
II О НЕВОЗМОЖНОСТИ ПОСТРОИТЬ Р" 6.Ф., СВОЙСТВ КОТОРОЙ НЕ ЗНАЕМ И, СЛЕДОВАТЕЛЬНО, НЕ МОШЕН ПОСТРОИТЬ;
12 О ВОЗМОЖНОСТИ УКАЗАТЬ САМУЮ СПОШНУЮ &Ф ДЛЯ П 13.0 НЕПРИМЕНИМОСТИ ОСНОВАНИЙ МАТЕМАТИКИ В ДАННОЙ ТЕОРИИ.
аксиомы теории баз данных и знаний и конечного исчисления предикатов
1. О СУЩЕСТВОВАНИИ МАТЕМАТИЧЕСКОГО ОБЪЕКТА; 2.0 СВЯЗИ МАТЕМАТИЧЕСКОГО ОБЪЕКТА С ФИЗИЧЕСКИМ; 3.0 ПРЕДСТАВЛЕНИИ ФИЗИЧЕСКОГО И МАТЕМАТИЧЕСКОГО ОБЪЕКТОВ В ВИДЕ БАЗЫ ДАННЫХ ИЛИ ЗНАНИЙ (БДЗ); к ОБ ИЗМЕНЯЮЩЕМСЯ МАТЕМАТИЧЕСКОМ ОБЪЕКТЕ: 5. О ФИЗИЧЕСКОЙ БАЗЕ ДАННЫХ ИЛИ ЗНАНИЙ (ФБДЗ);
в. О МАТЕМАТИЧЕСКОЙ БАЗЕ ДАННЫХ ИЛИ ЗНАНИЙ (МБДЗ):
7. О МАТЕМАТИЧЕСКОЙ БАЗЕ ДАННЫХ ИЛИ ЗНАНИЙ С ПРЕДВАРИТЕЛЬНОЙ ПОДГОТОВКОЙ ОТВЕТОВ (МБДЗ НПО);
8. О НЕПОСРЕДСТВЕННОЙ ПРОВЕРЮ ИОТИфсТИ ПРЕДИКАТНЫХ ФОРМУЛ НА БАЗАХ ДАННЫХ И ЗНАНИЙ-.
9. О НЕПРОТИВОРЕЧИВОСТИ ТЕОРИИ БАЗ ДАННЫХ И ЗНАНИЙ И КОНЕЧНОГО ИСЧИСЛЕНИЯ ПРЕДИКАТОВ.
-чг-
Пла. кат 15
К0М5ИНШРНДЯ МАШИНА ДЛЯ ПОЛНЫХ (к) ЗЩДЧ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА ^
¿.Архитектура КМ /^^ЧЧМ»*^)
Хг1101111
IЩ-ШЩг;
1 ТТ •
6СМ 1 тг -
х+зт
у»
I
Уп-
ш Х.+У,
ш
ад* Л/7
Ш
Ш
0 \—1
2я-/
3. СЗС-схема запроса сбязи
Й/-—ЩХ з^
^ БСМ-8/10К сравнения множеств
\ а а г^ \ о Г «о \ а \ Е ■3 з э: а оО а * о Ч) X 8 о ^ 0) «о £ о а) а 0 1 с £ о £ «о <3 О) сз 3 3 3 •к а; 8- •3 сэ осз <11 Кз 0) 3 а: 41 3* О С'. 8-Й 45 <0 О ч з а 3 I 2 Е I? N 3 3 «* ч * * £ о с о; 3 3 <3 <0 3 3 * 3 £ 8-<о X а: •3 а > 2 § 3 о 3 г: 3: Л 5; г 4) * 0 ч л 1 а « а Е X 3 С «Л Е а: 3 Со
ЦП 4- + + + + 4- +
гл + _ - + + +
2 ПИ + - — — + +
пэ — - — ■Ь + + 4-
СЗС — — — + +
ьт — - — — ■ ч- + 4-
др. - — — — - + - -
СЮ 1 £ £ 1. £ 1. £
Ей
N
ЦК/ М1 СВ1 Ф1 У1
ЦК2 ¡12 СВ2 Ф2 У2
К
а. 2
канала
ШПЬМ
св-Ф-у-тп
6. I кона/7
Пл лкат 16
5".
полиномиальный от длины входа по времени и памяти алгоритм разложения булевой функции на изолированные подфункции
1
УУУУУУУУУУ,
г~\
1 •
¡1 1-3
1 0 3
ч
г г
2 з
х
2
1 М
2 3
полиномиальный от длины входа по времени
и памяти алгоритм построения максимального независимого множества 1 г з ч
+ ^¿х^х^ + x) Х^ Х3 хц+Л; Хз хц;
12 3 ь
х3хн
ь>
6®
С
V
Ъ
ч ®
<0
т-
5_б
X 3 2,4 23 1.2 1.Н 1.3
3 X 2,3.4 2 1.2,3 1.3.4 1
2.4 2.3.4 X 3,4 1.4 1.г 1&З.Ч
13 г 3,4 X 1.3 1.2.3.4 1.2
1,2 1,г,з 1,4 1,3 X 2.4 2,3
1,4 /.ЗЛ 1,2 1.г,г.ч г.ч X 3.4
1,3 1 1.гхч 1,2. 2.3 г.ч X
и «г
7
П /iaK.cj.rri 17
полиномиальный от длины входя по времени и памяти алгоритм выявления общезначимости
е*(*ь ад)х,х2+ х, х2
2 3 1 1
У 7 — 1 }
2 X —
ч/
J
Г 21 3
1 — —
Г X —
Иа] А4/
1 гЧ ¿--г
г' 21-г г%1
3 24
1 2: 3 I
1 Ч 0 0 Ч
2 0 2 2
3 Х2 2 г 0 Ч
Ч х2 2 0 2 Ч
S *э 2 1 1 Ч
6 *3 г 1 1 Ч
р хгх5
1
2
3
