авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 |
-- [ Страница 1 ] --

Министерство образования и науки Российской Федерации

Восточно-Сибирская государственная академия образования

Институт математики им. С.Л. Соболева СО РАН

СИНТАКСИС И

СЕМАНТИКА

ЛОГИЧЕСКИХ СИСТЕМ

Материалы 3-й Российской школы-семинара,

посвященной 80-летию со дня рождения А.И. Кокорина

(Иркутск, 10–14 августа 2010 г.)

Иркутск 2010

Печатается по решению редакционно-издательского совета

Восточно-Сибирской государственной академии образования УДК 510.6+512+519.7 Издание осуществлено при под ББК 22.12+22.14+22.18 держке Российского фонда фун даментальных исследований по проекту 10-01-06822 Синтаксис и семантика логических систем: Матери алы 3-й Российской школы-семинара. – Иркутск: Изд-во ГОУ ВПО Восточно-Сибирская государственная академия образо вания, 2010.– 124 c.

Сборник содержит материалы 3-й Российской школы-семинара Синтаксис и семантика логических систем, посвященной 80-летию со дня рождения профессора А. И. Кокорина и проходившей в Ир кутске с 10 по 14 августа 2010 г. при поддержке Российского фонда фундаментальных исследований (проект 10-01-06822). Первая школа семинар состоялась в 2006 году в Иркутске, вторая в 2008 году во Владивостоке.

Для студентов, аспирантов и научных работников, специализи рующихся в области математической логики и дискретной матема тики.

Редакционная коллегия:

д-р физ.-мат. наук Е.А. Палютин, д-р физ.-мат. наук Н.А. Перязев, д-р физ.-мат. наук С.Ф. Винокуров, д-р физ.-мат. наук В.И. Пантелеев c ГОУ ВПО Восточно-Сибирская государственная академия образования, Издаются в авторской редакции Подписано в печать 01.08.2010. Бумага Ballet.

Формат 60x84 1/16. Условных печатных листов 7,6.

Тираж 100 экз.

Отпечатано на RISO в ОКИС ф-та МФИ ВСГАО Иркутск, Н. Набережная,6, тел. 24-04- К 80-летию со дня рождения профессора А. И. Кокорина (1929–1987) Перед вами сборник материалов школы-семинара Синтак сис и семантика логических систем, проходившей в Иркутске с 10 по 14 августа 2010 года и посвященной памяти Али Ива новича Кокорина, 80 лет со рождения которого исполнилось в ноябре 2009 года. Тематика сборника отражает широту на учных интересов Али Ивановича и представляет те области исследований, где сегодня работают его ученики.

Ранний уход Али Ивановича не дал ему возможности уви деть, как развивается его школа, как защищают диссертации ученики его учеников. Наверное, научные школы чем-то схо жи с произведениями искусства их настоящая цена прояв ляется спустя десятилетия после смерти своих создателей. То, что школа Кокорина сегодня успешно развивается и не по одному, а сразу по нескольким направлениям говорит само за себя. Обладая мощной внутренней энергетикой, Али Ива нович вдохновлял своих учеников на решение крупных задач, без малейших колебаний внедрялся в новые направления иссле дований. Даже если ученики приходили с дикими идеями, он их поддерживал, вероятно считая, что собственные шишки важнее чужих побед. Поддержка А.И. Кокорина сыграла су щественную роль в получении его учениками многих результа тов, включая построение примера неупорядочиваемой группы со строго изолированной единицей (Блудов, 1972), доказатель ство неразрешимости универсальной теории конечных групп (Слободской, 1980), установление позитивной классификации свободных моноидов (Перязев, 1986), доказательство неразре шимости теории полей рациональных функций над полями ха рактеристики два (Пензин, 1973), исследование на разреши мость расширенных теорий алгебраических систем (Мартья нов, 1979, Фридман, 1979, Дулатова, 1987), нахождения кри терия корректности вывода в инвариантных преобразованиях (Манцивода, 1983). Ключевым качеством профессора Кокори на было то, что он относился к успехам своих учеников как к своим собственным, всегда с энтузиазмом рекламировал и продвигал их.

У А.И. Кокорина была сложная судьба, он поздно пришел в науку, став учеником сначала создателя уральской алгебраи ческой школы П.Г. Конторовича, а затем выдающегося русско го математика академика А.И. Мальцева. До этого он прослу жил несколько лет офицером на военном флоте (где воспринял лучшие качества отца-командира ), работал разметчиком на Уралмаше, и даже тренером по плаванию и шахматам. У него был по-настоящему спортивный характер, который он привнес в организацию научных исследований, поддерживая конкурен цию учеников, их амбициозность и самостоятельность. С одной стороны, это ставило их в весьма непростые условия, а с дру гой, воспитывало необходимую свободу мышления, жесткость и инициативность, которыми и подпитывается сегодня школа Кокорина. Что Али Ивановичу было абсолютно чуждо, так это выбрать узкое направление исследований, а затем по полной программе эксплуатировать его, штампуя близкие по смыслу результаты и выпекая кандидатскую за кандидатской. Страсть к неизведанному постоянно подвигала Али Ивановича к заня тиям в новых областях, куда он бросал очередного своего уче ника. Поэтому наследники школы Кокорина работают сейчас в самом широком спектре математических направлений от глубоких вопросов теории групп до систем обработки знаний в распределенных информационных пространствах.

Школа Кокорина развивается и сегодня, спустя двадцать два года после его ухода. Из четырнадцати учеников, защи тивших под его руководством кандидатские диссертации, пя теро стали докторами наук. И главное у его учеников уже десятки своих учеников научных внуков Али Ивановича, которые стали докторами и кандидатами наук. Более того, уже появились научные правнуки, работающие в самых разных областях исследований. Школа Али Ивановича Кокорина про должается.

В.В. Блудов, А.В. Манцивода, Н.А. Перязев, ученики А.И. Кокорина ОБ АНСАМБЛЕ M –ЗНАЧНЫХ МОДЕЛЕЙ ТЕОРИИ ДЛЯ ОПТИМИЗАЦИИ АДАПТИВНЫХ РАССТОЯНИЙ И КЛАСТЕРИЗАЦИИ ЗНАНИЙ А.А. Викентьев, Р.А. Викентьев В настоящее время появляется большой интерес к построе нию решающих функций на основе анализа экспертной инфор мации, заданной в виде вероятностных логических высказыва ний нескольких экспертов, реализациям адаптивных алгорит мов кластеризации и согласованиям высказываний [1–6]. В дан ной работе предлагается записывать высказывания экспертов в виде формул m–значной (с их значениями истинности, m 2) логики. На значения истинности таких формул можно так же смотреть и как на вероятности (в частности, ошибочности) и в каждом конкретном случае правильном (в смысле предлагае мой семантики) определении истинности формулы на модели.

В произвольном m–значном случае с помощью ансамбля мо делей некоторой теории найдено, на наш взгляд, правильные (с точки зрения теоретических сображений, а так же мнений экспертов) обобщения расстояния между такими формулами и меры опровержимости (недостоверности) таких формул, что позволяет решать более утонченно (по сравнению с 2–значным случаем) прикладные задачи. В частности, значение истинно сти на модели (введенное по аналогии со случаем m = 2) может служить и субъективной вероятностью этой части реализации формулы в алгебраической системы теории 1-го порядка, а сам подход обобщается и на случай многосортных теорий любого порядка. При организации поиска логических закономерностей и построении решающих функций требуются расстояния меж ду высказываниями экспертов и формулами в моделях в про извольный (текущий) момент времени с фиксированными зна ниями, которые вводятся здесь с помощью подходящей теории моделей фиксированной М-теории.

Институт математики СО РАН и Новосибирский госуниверситет, Но восибирск, e-mail:vikent@math.nsc.ru Определение. Расстоянием между формулами и, такими, что S() S() S(), на множестве P (S()) назовем (нор мированную симметрическую разность в многозначном случае, как обобщение расстояния в 2-х и 3-значном случаях) величину S() (, ) = ns ns 0 ModS() ModS() + k k ns ns k=1 k= =.

n|S()| Возможные модификации этого определения касаются в уче те значений, больших 0.5 как истинных в будущем и учетом меньших значений, но больших или равных 0.0 как ложных в различных подклассах моделей теорий.

Теорема [О свойствах расстояния S() (, )] Для любых формул,, таких, что S() S() S() верны следующие утверждения:

1. 0 S() (, ) 1;

2. S() (, ) = S() (, );

3. S() (, ) = 0 ;

n1 n 4. S() (, ) = 1 Mod() Mod() = k l n1 n l=1 k= P (S()).

5. S() (, ) S() (, ) + S() (, );

6. Если 1 2, то S() (1, ) = S() (2, );

различных модельных примерах. Аналогично можно изучить меру недостоверности (обобщение меры "опровержимости"по учету с параметрами степеней недостоверности) в рассматри ваемом здесь М-случае. Параметры расстояний и меры недо стоверности находятся с привлечением оптимизации по крите рию качества, сформулированному по конкретной задаче или методом наименьших квадратов.

Работа выполнена при финансовой поддержке грантов РФ ФИ, проект № 07–01–00331–a, 08-07-00136a.

Список литературы [1] Лбов Г. С., Старцева Н. Г. Логические решающие функции и вопросы статистической устойчивости решений. Новоси бирск: Изд–во Ин–та математики СО РАН, 1999.

[2] Кейслер Г., Чэн Ч. Ч. Теория моделей. М.: Мир, 1977.

[3] Викентьев А.А, Лбов Г.С. О метризации булевой алгеб ры предложений и информативности высказываний экспер тов// Доклады РАН 1998. Т.361, №2 С. 174–176.

[4] Викентьев А.А, Лбов Г.С. Setting the metric and informativeness on statements of experts// Pattern Recognition and Image Analysis, 1997, V.7, №2, P. 175– 183.

[5] Ершов Ю.Л., Палютин Е.А. Математическая логика Санкт–Петербург, 2004.

[6] Викентьев А.А., Коренева Л.Н., К вопросу о расстояни ях между формулами, описывающими структурированные объекты// Математические методы распознавания образов (ММРО–99), РАН ВЦ, Москва, 1999. С.151–154.

АЛГОРИТМ ВЫЧИСЛЕНИЯ СЛОЖНОСТИ ПРОИЗВОЛЬНО ЗАДАННОЙ ОБРАТИМОЙ ФУНКЦИИ † С.Ф. Винокуров, А.С. Францева В работе рассматривается алгоритм вычисления сложности произвольно заданной обратимой функции. Алгоритм исполь зует библиотеку обратимых схем, построенную на основании алгоритма синтеза, приведенного в [2, 3].

Под обратимой функцией будем понимать взаимнооднознач ную функцию, определенную на множестве наборов {0, 1}n.

Любому двоичному набору = (0, 1,..., n1 ) из множества наборов {0, 1}n (i {0, 1}) соответствует двоичный вектор длины 2n с 1 на позиции с номером и 0 на остальных ме стах. Тогда n-местной обратимой функции f, действующей на множестве {0, 1}n соответствует перестановочная матрица Mf размерности 2n 2n, строки которой в лексикографическом по рядке наборов есть f ().

Обратимой функции f соответствует обратимая логическая схема, которая представляет собой систему обратимых венте лей или гейтов, соединенных проводами. Для построения об ратимой логической схемы используется библиотека элемен тарных гейтов, реализующих определенный набор функций. В работе рассматриваются гейты NOT, TOFFOLI. Таблицы функций, реализуемых этими гейтами можно посмотреть в [2].

Естественно предполагать, что вместе с гейтом, реализую щим функцию f (x1,..., xn ) присутствуют гейты, реализую щие функции f (xi1,..., xin ), где (i1,..., in ) некоторая перестановка (1,..., n). C точки зрения построения схемы это означает, что гейт можно присоединить к разным проводам (более подробно см. [2]).

Восточно-сибирская государственная академия образования e-mail: vin@math.isu.ru † Иркутский государственный педагогический колледж № e-mail: fas@igpk.ru Сложностью обратимой схемы называется число гейтов в ней. Обратимая схема S называется эквивалентной данной схеме S, если обе схемы реализуют одну и ту обратимую функ цию. Обратимая схема называется оптимальной, если не су ществует эквивалентной ей схемы меньшей сложности [4]. Под сложностью обратимой функции будем понимать сложность соответствующей оптимальной обратимой схемы.

Задача синтеза обратимых логических схем заключается в представлении перестановочной матрицы каждой такой схемы в виде произведения заданных (библиотечных) матриц. Была сформирована библиотека всех оптимальных схем при n = и библиотека оптимальных схем до сложности 8 при n = 4. В алгоритме синтеза используется факториальная система счис ления, которая однозначно ставит в соответствие каждой пе рестановочной матрице натуральное число [2,3]. Это позволило ввести естественный порядок в библиотеку схем и реализовать удобство задания произвольной обратимой функции.

Пусть P перестановка, соответствующая матрице Mf об ратимой функции f. Перестановка P для функций, зависящих от 4 переменных, представляется в виде 8-байтового числа X, записанного в шестнадцатеричной системе счисления. Если из вестна сложность соответствующей схемы, то значение этой сложности хранится на последнем разряде числа X.

Алгоритм int Cost_circuuit( U_I64 nt[],// библиотека схем U_I64 nt8[],// библиотека схем сложности U_I64 x // натуральное число, соответствующее обратимой функции f ) { U_I C, c;

U_I64 X, j, J, A, *y;

X=natur_16ns(x);

// перевод натурального числа в пере становку через факториальную систему счисления;

// сложность 0,1,..., y=Search(nt[], X);

// найти Х в библиотеке схем if(y!=nt[last]+1) return get_cost(*y);

// если най дено, вычислить сложность // 8 сложность else{ C=9;

for(j=0.. J-1){ // по всем схемам сложности A=product(X, nt8[j]);

// произведение схем y=Search(nt[], A);

if(y!=nt[last]+1) c=get_cost(*y);

if(cC) C=c;

} } if(C9) return 8+C;

else return 0;

} В случае, если сложность функции больше 16, алгоритм возвращает 0.

Алгоритм void Tr_cost( U_I64 T[], U_I c_T[], U_I64 nt[], U_I64 nt8[], U_I64 x ) { U_I c[];

U_I64 X, j, TP[], *m;

X=natur_16ns(x);

get_transpositions(T, c_T, X);

// разложить переста новку X в транспозиции T[] и вычислить их сложности c_T[];

j=0;

while(jlast) { // по всем элементам массива T[], кроме последнего;

TP[j]=product(T[j], T[j+1]);

c[j]=Cost_circuit(nt, nt8, TP[j]);

j++;

} while(TP.size()!=0) { m=min_element(c);

// возвращает указатель на мини мальный элемент в массиве c[];

if(*m17) { // заменить транспозицию на соответству ющую подсхему;

T[m-T.begin()]=TP[m-TP.begin()];

с_T[m-с_T.begin()]=с[m-с.begin()];

delete(T, c_T, m+1);

// удалить лишние;

recount_neighb(TP, c);

// пересчитать соседние эле менты в массивах TP[] и с[];

} else break;

} } В заключении работы алгоритма массив T[] содержит оп тимальные подсхемы схемы функции f. В данном алгоритме при вычислении элементов массивов c[] и c_T[] используется предыдущий алгоритм.

Алгоритмы реализованы на языке программирования C ++ с использованием библиотеки оптимальных схем до сложности 8.

В результате Алгоритм 1 позволяет вычислить сложность обратимой функции, зависящей от 4-х переменных, если эта сложность не превышает 16. Алгоритм 2 вычисляет сложность некоторой обратимой схемы необязательно являющейся опти мальной для данной обратимой функции.

Работа выполнена при поддержке РФФИ, проект 09-01 00476a.

Список литературы [1] Винокуров С. Ф., Францева А. С. Квантовые вычисле ния на языке линейных пространств // Вестник бурятского университета. - 2006, Выпуск 3. - С. 15-22.

[2]Винокуров С. Ф., Францева А. С. Факториальная систе ма счисления в задаче сиснтеза обратимых логических схем // Алгебра и логика: Материалы международного российско китайского семинара. - Иркутск: Издательство Иркут. гос. пед.

ун.-та, 2007. - 150 с.

[3] Винокуров С. Ф., Францева А. С. Синтез обратимых ло гических схем // Синтаксис и семантика логических систем:

Материалы Российской школы-семинара. - Владивосток: Из дательство Дальневост. гос. ун.-та, 2008. - 150 с.

[4] Vivek V. Shende and oth. Synthesis of Reversible Logic Circuits// IEEE Transactions on Computer-Aided design of integ rated circuits and systems, VOL.22, NO.6, June ЯЗЫК ФОРМАЛЬНОЙ МАТЕМАТИКИ mdl ‡ Д.Ю. Власов Примечательным фактом истории развития математики яв ляется то, что по мере развития математики сложность доказа тельств неуклонно возрастает. На текущий момент сложность доказетельств достигла качественной границы, т.к. появились сверхсложные доказательства вообще недоступные для пони мания одиночным специалистам. Ярким примером такого до казательства является классификационная теорема для конеч ных простых групп.

Поэтому есть все основания считать, что необходим очеред ной качественный скачок в сторону строгости математических доказательств, и он связан с полной автоматизацией проверки доказательств на компьютере, что, очевидно напрямую связан но с полной и явной формализацией математического знания.

Подробный обзор и обоснование этого тезиса можно увидеть в статье Х. Барендрегта и Ф. Видайка [1].

Знаковым событием в деятельности по формализации ма тематики стала публикация так называемого QED манифеста [2], в котором тезисно сформулированны основные задачи, тре бующиеся для явной формализации математики в виде язы ка, реализованного на компьютере, и позволяющего проверять правильность доказательств при помощи программы, т.е. фор мально. К настоящему времени существует уже большое ко личество систем формальной математики, обзор 17 наиболее популярных систем формальной математики находится в ста тье [3].

К сожалению, полной реализации реализации QED мани феста ни одна из перечисленных выше систем не достигает. В статье Ф. Видайка [4] делается обзор наиболее продвинутых систем формальной математики, таких как Mizar, Coq, HOL ‡ Институт математики СО РАН Новосибирский государственный университет e-mail: vlasov@academ.org и др., и анализируются причины, почему ни одна из этих си стем не используется в широкой повседневной практике среди математиков.

Если попытаться выделить основные проблемы, которые препятствуют полной реализации QED манифеста, то из вы шеупомянутой статьи Ф. Видайка можно выделить следую щие принципы. Принцип элиминации ограничений: следу ет максимально уменьшать ограничивающие выразительную силу исчисления факторы, а не увеличивать их. Принцип синтаксической ясности: формализованная теория долж на максимально походить по форме на свой неформальный первоисточник в общепринятом синтаксисе. Принцип коге рентной открытости: система должна предоставлять воз можность пополнения большим количеством пользователей, но при этом хорошо организованная (когерентная).

Яызк формальной математики metamath [5], был разрабо тан Н. Мегилом в начале 90-х годов XX века. Этот язык резко выделяется из зоопарка различных систем формальной мате матики по двум ключевым признакам: универсальности и простоте.

Универсальность языка metamath заключается в том, что фактически этот язык не описывает никакое логическое исчис ление. Вместо этого он предоставляет средства для записи ши рокого спектра формальных исчислений и теорем на их базе.

Прямым следствием столь большой универсальности metamath является то, что этот язык очевидно удовлетворяет принци пам элиминации ограничений и синтаксической ясности мате матических выражений. Отдельного внимания достойно и вто рая ключевая особенность языка metamath: несмотря на свою универсальность, это очень простой язык. Прямым следствием этой простоты является тот факт, что можно написать сравни тельно простой, небольшой по объему, верификатор для этого языка, то есть записанные на metamath доказательства могут быть надежно проверены.

Тем не менее, есть и фундаментальный недостаток языка metamath, являющийся прямым следствием его простоты: до казательства в этом языке синтаксически совершенно не ясны, т.е. для доказательств принцип синтаксической ясности не вы полнен. Таким образом, несмотря на то, что metamath очень выгодно выделяется среди остальных претендентов на реализа цию QED манифеста, у него есть очень серьезный недостаток, не позволяющий считать metamath языком, полностью реали зующим QED манифест.

Язык mdl (акроним от “Mathematics Development Language”) был разработан автором для преодоления следующего недо статка языка metamath: невозможностью редактировать и по нимать доказательства на этом языке без специализированных программ. Вместе с тем, требовалось сохранить степень на дежности metamath. Поэтому программной реализацией mdl является транслятор, переводящий исходные файлы на язы ке mdl в язык metamath. Это позволяет использовать удоб ство чтения и редактирования доказательств на языке mdl, и надежность верификации доказательств на языке metamath.

При этом степень универсальности почти не изменилась. Един ственным ограничением, уменьшающим степень универсально сти mdl по сравнению с metamath, является то, что в mdl рас сматриваются только контекстно-свободные грамматики выра жений. Но, если принять во внимание широту класса контекстно свободных языков, это не является принципиальным ограни чением. Следует отметить, что на самом деле транслятор mdl переводит файл с исходной формализацией не в полный язык metamath, а в подмножество языка metamath с идентичной се мантикой, но ещё более простого. Этот язык называется smm (акроним от Simplied MetaMath). Следует отметить, что по сравнению с metamath, принцип синтаксической ясности дока зательств в mdl выполнен. Выполнимость принципа элимина ции ограничений и синтаксической ясности выражений также наследуется. Для обеспечения принципа когерентной открыто сти, в mdl есть языковое средство, позволяющее структуриро вать базу теорем в виде дерева теорий, а также специальная синтаксическая конструкция для определений, гарантирующая консервативность расширений языка определениями.

Реализация системы формальной математики mdl может быть загружена из http://mathdevlanguage.sourceforge.net, и на данный момент включает исходные коды транслятора mdl, исходные коды транслятора mm (это транслятор из metamath в mdl, специально адаптированный для трансляции файла math.mm), исходные коды откорректированного оригинально го верификатора языка metamath, базы теорем math.mm и те стового скрипта. Тестовый скрипт запускает цепочку трансля ций на достаточно большой базе (более 10 000 теорем). Все исходные коды программ, входящих в пакет mdl, распростра няются по лицензии GPLv3.

Работа выполнена в НГУ при финансовой поддержке Сове та по грантам Президента РФ для поддержки ведущих науч ных школ (проект НШ-3669.2010.1), Федерального агентства по образованию, грант ГК-П-1008.

Список литературы [1] H. Barendregt, F. Wiedijk, The Challenge of Computer Ma thematics, Transactions A of the Royal Society 363 no. 1835, 2351 2375, 2005. http://www.cs.ru.nl/~freek/notes/RSpaper.pdf [2] R. Boyer et al. The QED Manifesto. In A. Bundy, editor, Automated Deduction - CADE 12, volume 814 of LNAI, pages 238-251. Springer-Verlag, 1994.

http://www.cs.ru.nl/~freek/qed/qed.ps.gz [3] F. Wiedijk, The Seventeen Provers of the World, foreword by Dana S. Scott, Springer LNAI 3600, 2006.

http://www.cs.ru.nl/~freek/comparison/comparison.pdf [4] F. Wiedijk The QED Manifesto Revisited, Studies in logic, grammar and rhethoric, 10 (23), 2007, pp.121-133.

http://mizar.org/trybulec65/8.pdf [5] N. D. Megill, Metamath: A computer language for pure mathematics, Lulu press, Morrisville, North Carolina, USA, 1997.

http://us.metamath.org/downloads/metamath.pdf О ЗАДАЧАХ ГЛОБАЛЬНОГО ТЕСТИРОВАНИЯ (РАСШИФРОВКИ) БЕСПОВТОРНЫХ БУЛЕВЫХ ФУНКЦИЙ А.А. Вороненко Классическая задача расшифровки функции предполага ет последовательный или одновременный запрос ее значений в точках [15, 2]. При этом последующие аргументы запросов чаще всего зависят от значений, полученных при предыдущих запросах (условный тест). Первой классической задачей такого типа можно считать проблему расшифровки монотонной буле вой функции, решенную Анселем [2].

При рассмотрении задач расшифровки и тестирования бес повторных булевых функций проблемы возникают уже на уров не постановки. Естественно считать вырожденной постановку задачи, для которой ответом служит длина теста 2n – мощ ность множества всех наборов.

При работе с бесповторными функциями базисы зачастую считают наследственными, то есть содержащими вместе с функ цией все получаемые из нее константными подстановками. На зовем сложными базисы, содержащими хотя бы одну нелиней ную и хотя бы одну немонотонную функции. В любом слож ном наследственном базисе бесповторными являются функции 0, 1, x1... xn, x1 &... & xn для любых 1,..., n. Даже n n 1 условный диагностический тест на таком множестве содержит все наборы. Более того, проверяющие тесты для каждой из кон стант также содержат все наборы. В связи с этим при решении задач чаще всего рассматривался базис {&, }. Соответствую щие результаты изложены в работах [1, 12, 13, 3, 4].

В работе [10] автором была поставлена задача тестирования относительно бесповторной альтернативы (далее Alt), состоя щая в следующем. Требуется построить проверяющий тест для Факультет вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова e-mail: dm6@cs.msu.su функции f (x1,..., xn ), бесповторной в базисе B и существен но зависящей от всех n переменных, на множестве всех бес повторных в этом базисе функций, зависящих от переменных x1,..., xn произвольным образом. Было показано [10, 14], что для базиса B2 = {&,,, ¬} соответствующая функция Шен нона равна 1+n+ n. Дальнейшие обобщения этих результатов содержатся в работах [8, 9, 7, 6].

В настоящей работе предлагается рассмотреть принципи ально новые операции тестирования. На одном шаге алгоритма выполняемый запрос может обращаться не к точке, а к неко торой подфункции на подкубе произвольной размерности. При этом, если размерность этого подкуба нулевая, то результат за проса всегда совпадает с результатом запроса значения функ ции в соответствующей точке. Перечислим виды запросов:

сумма по модулю два значений функции на подкубе;

0, если функция равна константе на подкубе, и 1 ина = че.

арифметическая сумма (количество единиц) функции на подкубе.

Первые два запроса, как и стандартный поточечный запрос (его будем обозначать символом f (x)), дают один бит выхода.

В модели же каждый запрос к кубу размерности m дает m + 1 вариант ответа (log(m + 1) бит выхода).

Кроме этого, помимо названных задач тестирования отно сительно бесповторной альтернативы (Alt) и условного диагно стического теста (Diag) мы также рассмотрим задачу Ess по строения условного диагностического теста на множестве всех бесповторных функций, существенно зависящих от n перемен ных. Вырожденность ее в случае немонолинейного базиса так же очевидна.

Через LT [P (B)](n) обозначим максимальную сложность (длину теста, измеряемую количеством запросов в худшем слу чае) задачи P при способе тестирования T на множестве всех бесповторных в базисе B функций n переменных (функцию Шеннона). Символом же LT [P ](M ) обозначим максимальную сложность (в том же смысле) задачи P при способе тестирова ния T на множестве функций M.

Утверждение 1. Для любых запросов T и задач P, если базис B B, справедливо неравенство LT [P (B )](n) LT [P (B )](n).

Утверждение 2. Для любых задач P и множеств функ ций M справедливы неравенства L [P ](M ) L [P ](M ) Lf (x) [P ](M ), L [P ](M ) L= [P ](M ) Lf (x) [P ](M ).

Утверждение 3. Для любых запросов T и любого базиса B справедливы неравенства LT [Alt(B)](n) LT [Diag(B)](n), LT [Ess(B)](n) LT [Diag(B)](n).

Пример 1. Построим множество функций M, для которого L [P ](M ) L= [P ](M ).

Рассмотрим семь функций трех переменных: медиану и шесть получающихся из нее изменением единственного значения на одном из наборов веса один или два. Любой запрос типа = дает одинаковый ответ не менее чем для пяти функций, сле довательно, любой диагностический тест будет иметь длину не менее четырех. Тем не менее, нетрудно показать, что расшиф ровка осуществима за три запроса типа.

Пример 2. Приведем для того же числа переменных при мер противоположного соотношения. Рассмотрим следующие 32 функции трех переменных x1, x2, x3. Восемь из них тожде ственно равны нулю при x3 = 0 и имеют нечетное число единиц при x3 = 1. Восемь из них тождественно равны единице при x3 = 0 и имеют нечетное число единиц при x3 = 1. Четыре из них равны x1 x2 при x3 = 0 и имеют ровно одну единицу при x3 = 1. Четыре из них равны x1 x2 при x3 = 0 и имеют ровно три единицы при x3 = 1. Наконец, восемь из них имеют нечетное число единиц при x3 = 0 и тождественно равны нулю при x3 = 1.

Несложно построить условный тест длины 5 при помощи запросов типа =. Для того чтобы расшифровка тридцати двух функций имела длину 5, необходимо, чтобы каждый запрос делил число функций пополам. При типе запросов такое вы полняется лишь для запросов вида f (1, 2, 0), где 1, 2 – кон станты. Повторный же запрос, обладающий тем же свойством, невозможен, что и доказывает желаемое.

В работе [5] доказано, что для базиса B0 = {&,, ¬} Lf (x) [Alt(B0 )](n) = n + 1.

В работе [11] продемонстрировано, что n2 n + 1, L [Ess(B0 )](n) а для всякого сложного наследственного базиса B, содержаще го хотя бы одну не бесповторную в B0 функцию, L [Ess(B)](n) = 2 (n).

Принципиальная сложность идентификации множества фик тивных переменных с помощью запросов типа определяется следующей теоремой:

Теорема.

L [Diag(B0 )](n) 1,5n.

Доказательство. Рассмотрим функцию x11 &...&xkk. От i i вет 1 на запрос типа может быть получен тогда и только тогда, когда запрашиваемый подкуб имеет с подкубом xi1 = 1,..., xik = k ровно одну общую точку. Каждый подкуб име ет ровно одну общую точку ровно с 2n другими подкубами, а общее число конъюнкций литералов равно 3n. Следователь но, для любой последовательности из менее чем 1.5n запросов существуют по меньшей мере две различные функции, соот ветствующие нулевым последовательностям ответов. Теорема доказана.

Работа выполнена при поддержке ФЦП Научные и научно педагогические кадры инновационной России на 2009–2013 го ды.

Список литературы [1] D. Angluin, L. Hellerstein, M. Karpinski Learning read-once formulas with queries // Journal of ACM. 1993. 40, p. 185–210.

[2] Hansel G. Sur le nombre des fonctions boolennes monotones e de n variables // C. R. Acad Sci. Paris, 1966, 262, p. 1088–1090.

[3] Goldsmith J., Sloan R. H., Szrenyi B., Turan G. Theory o revision with queries: horn, read-once, and parity formulas // Articial Intelligence. 2004. V. 156. N 2. P. 139–176.

[4] Golumbic M. C., Mints A., Rotics U. Read-once functions revisited and the readability number of a Boolean function // Electronic Notes in Discrete Mathematics. 2005. 22. 357–361.

[5] Бубнов С.Е. Функция Шеннона длины проверяющих тестов функций, бесповторных в элементарном базисе // Сборник статей молодых ученых факультета ВМиК МГУ 6. С. 47–57.

[6] Бубнов С.Е., Вороненко А.А., Чистиков Д.В. Некоторые оценки длин тестов для бесповторных функций в базисе {&, } // Прикл. матем. и информатика. 2009. 33. С. 90–100.

[7] Вороненко А.А., Чистиков Д.В. Индивидуальное тести рование бесповторных функций // Ученые записки Ка занского государственного университета. Сер. Физико математические науки. 2009. 151. Кн. 2. C. 36–44.

[8] Вороненко А.А. Об оценке длины проверяющего теста для некоторых бесповторных функций // Прикл. матем. и ин форматика. 2003. 15. C. 85–97.

[9] Вороненко А.А. Распознавание бесповторности в произ вольном базисе // Прикл. матем. и информатика. 2006. 23.

С. 67–84.

[10] Вороненко А.А. О проверяющих тестах для бесповторных функций // Матем. вопр. киберн. Вып. 11. М.: Физматлит, 2002. С. 163–176.

[11] Вороненко А. А., Чистиков Д. В. Расшифровка бесповтор ных функций оракулом счетчиком четности // Прикл. ма тем. и информатика. 2010. 34.

[12] Гурвич В.А. Критерий бесповторности функций алгебры логики // Докл. АН СССР. 1991. 318. No 3. C. 532–537.

[13] Гурвич В.А. О бесповторных булевых функциях // Успехи матем. наук. 1977. 32. No 1. C. 183–184.

[14] Рябец Л.В. Сложность проверяющих тестов для беспо вторных булевых функций // Иркутский гос. пед. ун-т. Сер.

Дискретная математика и информатика. 2007. 18. 32 с.

[15] Чегис И.А., Яблонский С.В. Логические способы контро ля работы электрических схем // Тр. матем. ин-та им.

В.А.Стеклова. Том 51. 1958. C. 270–360.

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ В ЗАДАЧЕ НАХОЖДЕНИЯ СЛОЖНОСТИ ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ В КЛАССЕ ПОЛИНОМИАЛЬНЫХ НОРМАЛЬНЫХ ФОРМ Д.Ю. Галков В работе рассматривается возможность применения генети ческих алгоритмов в задаче нахождения сложности L(n) пред ставления булевых функций в классе полиномиальных нор мальных форм с использованием специальной операторной фор мы. Подробно о специальной операторной форме и ее свойствах можно посмотреть в [1] и [2].

Алгоритм приближенной минимизации функции в классе полиномиальных нормальных форм Алгоритм приближенной минимизации функции в классе полиномиальных нормальных форм заключается в последова тельном построении ПНФ путем добавления операторов, вы бранных на некоторых шагах алгоритма. Пусть требуется най ти минимальное представление в классе ПНФ для функции f (x1,..., xn ). Строится специальная операторная форма функ ции SOF (f ). Далее алгоритм формулируется по шагам.

1. Для данного набора операторов из M (SOF (f )) строится матрица принадлежности операторов специальной опера торной формы пучкам, порожденным всеми операторами размерности n;

2. Находится сложность вложения SOF (f ) в каждый класс сумма всех произведений порождающего класс опера тора на элементы множества M (SOF (f ));

3. Выбирается оператор из M (SOF (f )), имеющий минималь ную сумму сложностей вложений SOF (f ) в пучки, в ко торые входит данный оператор;

Восточно-Сибирская государственная академия образования e-mail: den galk@mail.ru 4. Для найденного оператора выбирается пучок, содержа щий его и имеющий максимальную сложность вложения SOF (f );

5. Оператор, порождающий выбранный пучок, дописывает ся к операторной форме, а его разложение на операторы соответствующего двупорожденного пучка прибавляется к M (SOF (f )). Если полученное множество M (SOF (f )) не будет пустым, то повторяются все шаги, начиная с ша га 2.

По всем пучкам, полученным в результате выполнения ша гов 3 и 4, до достижения определенной глубины проводится перебор, после достижения этой глубины выбирается любой.

Сравнение с жадным алгоритмом Результаты работы описанного алгоритма минимизации детально разобраны в [3].

Основные трудности в работе алгоритма были связаны с вы числением сложностей функций четной размерности. Пробле ма возникает на шагах 3 и 4, то есть при выборе следующего оператора для добавления к SOF (f ). Для попытки ее разреше ния были выполнены различные варианты выбора оператора, а именно:

1. Был построен и реализован жадный алгоритм, работа ющий след. образом: к первоначальной SOF (f ) добав лялись последовательно все 3n оператора, и из получен ных SOF (f ) выбирались наиболее короткие. На каждом уровне фиксировалась наименьшая длина SOF (f ).

2. На основании алгоритма осуществлен поиск в ширину.

На каждом уровне по различным критериям осуществ лялся отбор цепочек операторов для следующего уровня.

При этом фиксировалась минимальный размер получен ных SOF (f ) и производился их анализ.

Результаты работы жадного алгоритма оказались гораздо хуже, как при получении итоговой сложности(она, как пра вило, выше известной), так и в динамике работы(на каждом уровне минимальный размер SOF (f ) был больше аналогично го при более "мягком"поиске в ширину). При анализе полу чаемых наборов весов было сделано предположение о наличии некоторых классов функций, для которых наборы весов иден тичны и, следовательно, можно построить статические табли цы, на основании которых появляется возможнось повысить эффективность вычислений. Открытым остался вопрос отбора на 3 и 4 шагах алгоритма. Учитывая, что качество получае мых решений улучшалось по мере ослабления жесткости усло вий выбора операторов, было принято решение прибегнуть к стохастическим методам вычислений, в частности реализовать алгоритм, использующий на этапе выбора оператора эволюци онные принципы.

Возможные направления работы На данный момент рассматриваются следующие пути продолжения исследований:

1. Рассмотрение вариантов применения эволюционных ал горитмов 2. Применение параллельных технологий вычислений 3. Продолжение поиска закономерностей выбора операто ров и связи особенностей SOF (f ) с оценкой сложности.

Работа выполнена при поддержке гранта РФФИ, проект 09 01-00476-a.

Список литературы [1] Избранные вопросы теории булевых функций: Моногра фия / А. С. Балюк, С. Ф. Винокуров, А. И. Гайдуков и др.;

Под ред. С. Ф. Винокурова, Н. А. Перязева. М.: Физматлит, 2001. 192 с.

[2] Винокуров С.Ф. Специальная операторная форма буле вых функций и некоторые ее приложения / С.Ф. Винокуров // Международная школа-семинар "Синтез и сложность управ ляющих систем". Новосибирск. Изд-во Института матема тики. 2004. С. 26–29.

[3] Рябец Л. В. Алгоритм получения минимальных поли номиальных форм булевых функций / А. С. Казимиров, Л. В.

Рябец // Вестник Иркутского университета. Специальный вы пуск: Материалы научно-теоретической конференции молодых ученых, посвященной 85-летию ИГУ. Иркутск: Иркут. ун-т., 2003. С. 77–80.

ПРИМЕР РАЗРЕШИМОЙ S4-ЛОГИКИ С НЕРАЗРЕШИМОЙ ПРОБЛЕМОЙ ДОПУСТИМОСТИ ПРАВИЛ ВЫВОДА М. И. Голованов Пример разрешимого расширения логики K4, в котором проблема допустимости правил вывода неразрешима, построен А.В. Чагровым в 1992г. (см. например [1] п. 3.8). В своей кни ге [1] В.В. Рыбаков поставил вопрос: существует ли разреши мое расширение S4 с неразрешимой проблемой допустимости правил вывода. В данной работе даётся положительный ответ на этот вопрос.

В работе вначале вводится рекурсивная система аксиом ло гики и описывается класс -фреймов. Так как все фреймы имеют ширину не более 4, то в силу теоремы К. Файна класс -фреймов является характеристическим. Затем доказывает ся, что логика финитно аппроксимируема. В заключение по строено рекурсивное множество правил, в котором подмноже ство допустимых правил не является рекурсивно перечисли мым, откуда и следует неразрешимость проблемы допустимо сти правил вывода.

Логика порождается классом фреймов Fn,k, где n, k 5, множество пар (n, k) рекурсивно, а совокупность вторых ком понент этих пар нерекурсивна. Пример фрейма F8,8 приведён на рисунке.

Сибирский федеральный университет e-mail m.i.golovanov@mail.ru a1 c b a2 c b a3 c b3 d a4 c b4 d a5 c b5 d a6 c b6 d a7 c b7 d b8 d x Фрейм F8, Работа выполнена при финансовой поддержке РФФИ, грант 09-01-00717.

Список литературы [1] Rybakov V.V. Admissible Logical Inference Rules, Elseiver Sci. Publ.. North-Holland. New-York-Amsterdam, 1997.

[2] Chagrov A., Zakharyaschev M. Modal logic, Clarendon press, Oxford, 1997.

[3] Fine K. Logics containing K4, Part I. J. of Simbolic Logic, v.39, 1974, 229- ОЦЕНКИ СТЕПЕНИ КОРРЕКТНЫХ ПОЛИНОМИАЛЬНЫХ ЗАМЫКАНИЙ ПОДМОДЕЛЕЙ МОДЕЛИ АВО А.Г. Дьяконов Введение. В [1] были исследованы полиномиальные замы кания различных семейств алгоритмов распознавания (клас сификации), что положило начало развитию алгебраического подхода к решению задач распознавания. Идея алгебраическо го подхода заключается в ведении операций над алгоритма ми распознавания (классификации) и поиске корректного ал горитма (который не делает ошибок на контрольной выборке) в виде алгебраического выражения. Было доказано (см. [1]), что корректный алгоритм может быть записан в виде полинома над алгоритмами вычисления оценок. Алгоритмы вычисления оценок (АВО) были предложены в [2] как некоторая универ сальная модель алгоритмов, по отношению к которой многие другие модели являются подмоделями при специальных огра ничениях на значения параметров.

Корректные алгоритмы-полиномы в [1] имели степень асимп тотически равную q log q, где q число объектов контрольной выборки задачи классификации. В [3] получена первая нетри вивальная оценка на степень корректного полинома: k q +l 2, где k степень полинома, l число классов в задаче клас сификации, которая была значительно улучшена в [4]: k log2 (ql) (здесь и далее скобками обозначается целая часть снизу ). В [5] получена окончательная (непонижаемая в общем случае) оценка k log2 q + log2 l. В настоящей работе пред ставлены оценки для подмоделей модели АВО.

Модель алгоритмов вычисления оценок. Пусть мно жество допустимых объектов M содержит объединение мно жеств Kj, j = 1,..., l, называемых классами. Каждому объ Факультет вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова e-mail: djakonov@mail.ru екту S M соответствует бинарный вектор классификации (S) = (j (S))l, где j (S) значение предиката S Kj, j= j = 1,..., l. Для каждой пары (S t, Si ) M M можно вы числить значения функций (S t, Si ) EZ, Z, где Z конечное множество параметров, EZ частично упорядочен ное множество. Задача распознавания (классификации) состо ит в том, чтобы построить алгоритм A, который по набору S m = {S t }m эталонных объектов с известными векторами t= { (S t )}m для набора Sq = {St }q контрольных объектов t=1 t= строит их векторы классификаций.

Для решения задач распознавания часто применяется мо дель АВО [1]–[2]. Приведём описание обобщённой модели. Ал горитм в ней является суперпозицией распознающего операто ра B и решающего правила C: A = B · C. Для объектов из Sq оператор B получает матрицу [B] = ij [B] ql, ij-й элемент которой оценка принадлежности объекта Si к классу Kj :

1, wt w()Be,b (S t, Si ), ij [B] = xab Z S t K a a,b=0, j где wt R+ = {x R | x 0} при t {1,..., m} вес t-го объекта, w() R+ при A вес учёта -й близости, e EZ, Be,1 (S t, Si ) функция близости, которая обращается e, в 1 при (S t, Si ) e и в 0 при (S t, Si ) e, B (S t, Si ) = 1 Be,0 (S t, Si ) функция антиблизости, S m Kj, a = 1, a Kj =, m \Kj, S a = 0, xab {0, (1)a+b } для всех j {1,..., l}, (a, b) {0, 1}2. Ре шающее правило C по матрице оценок принимает решение о классификации объектов.

В алгебраическом подходе операции над распознающими операторами индуцируются операциями над их матрицами оце нок: [B1 + B2 ] = [B1 ] + [B2 ], [cB] = c[B], [B1 · B2 ] = [B1 ] [B2 ], умножение поэлементное. При фиксированном решающем правиле получаем алгебру над алгоритмами. Мно жества распознающих операторов (как и множества алгорит мов) принято называть моделями. Алгебраическим замыкани ем k-й степени Uk (R ) модели R называется множество по линомов (с нулевым свободным членом) степени не выше k над операторами модели R.

Через B обозначается множество операторов обобщённой модели АВО, а через B ((a, b)) модель операторов АВО, у которых на множестве нулевых наборов {(a, b)} булевой функ ции (a, b) в формулах вычисления оценок xab = 0 (и, быть может, на каких-то других наборах). Например, B = B (1).

Модель распознающих операторов называется корректной (относительно задачи распознавания) [1] – [2], если для любой матрицы из Rql найдётся оператор модели, который её порож дает. Основной результат алгебраического подхода [1] модель U (B ) корректна тогда и только тогда, когда выполняют 1 ся первые два условия регулярности: 1) {K1,..., Kl1 } = l;

q t, S )) 2) {( (S i A, t{1,...,m} }i=1 = q.

Оценки для подмоделей АВО. Задача об оценке степе ни корректного полинома эквивалентна задаче об оценке сте пени корректного алгебраического замыкания: если замыкание Uk (B ) корректно, то любой корректный полином имеет сте пень не больше k (и наоборот).

Лемма. Для всех натуральных k справедливы равенства Uk (B ) = Uk (B (a b)) = Uk (B ( b)) = Uk (B (b)) a Uk (B (a = Uk (B (a b)), Uk (B (a)) = Uk (B (a&b)).

b)) Из леммы следует, что подмодели разбиваются на три клас са (с точностью до равенства алгебраических замыканий). Для подмоделей первого класса верна оценка общего случая:

Теорема [5]. Модель U(B ) корректна тогда и только то гда, когда корректна модель Uk (B ), где k log2 q + log2 l.

Для любых натуральных q и l, q + l 2, существует (регуляр ная) задача распознавания, в которой модель Uk (B ) некор ректна при k log2 q + log2 l (т.е. оценка непонижаема).

Подмодели второго класса в практически интересных слу чаях (например, когда одна из функций является метрикой) эквивалентны подмоделям первого, что показывает следующая Лемма. Если выполнено третье условие регулярности S m q = и A : (S, S ) M M [ (S, S ) (S, S) S S = S ], тогда Uk (B ) = Uk (B (a b 1)).

Теорема. Пусть в задаче распознавания выполнено первое условие регулярности и |{( (S t, Si ))S t Kj, A }q | = q для i= всех j {1,..., l} (второе условие регулярности для модели Uk (B (a&b))), тогда модель Uk (B (a&b)) корректна при k min{log2 (ql + 1), log2 (q) + log2 (l + 1)}.

Пока открытым остаётся вопрос, является ли последняя оценка точной для подмоделей третьего класса.

Работа выполнена при поддержке ФЦП Научные и научно педагогические кадры инновационной России на 2009 – годы.

Список литературы [1] Журавлёв Ю.И. Корректные алгоритмы над множества ми некорректных (эвристических) алгоритмов. II // Киберне тика. 1977. № 6. С. 21–27.

[2] Журавлёв Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Пробл. кибернети ки. 1978. Вып. 33. С. 5–68.

[3] Матросов В.Л. Корректные алгебры алгоритмов распо знавания ограниченной емкости // Дис.... докт. физ.-матем.

наук. М. Гос. пед. инст-т им. В.И. Ленина. 1985.

[4] Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распо знавание, классификация, прогноз. М.: Наука, 1989. Вып.1.

С.176–201.

[5] Дьяконов А.Г. Алгебра над алгоритмами вычисления оценок: минимальная степень корректного алгоритма // Ж.

вычисл. матем. и матем. физ. 2005. T.45. №6. С.1134– 1145.

THE PERMANENTAL FUNCTION OVER DIFFERENT ALGEBRAIC SYSTEMS G.P. Egorychev Here we give of the known and several new results of the theory of permanents over various algebraic systems.

The permanent of a square n n matrix A = (aij ) over com mutative ring K is dened to be the sum per(A) = a1(1) · · · an(n), (1) Sn where the sum is taken over all permutations = ( (1),..., (n)) of the set Sn = {1,..., n}, or which is the same, over all diagonals of the matrix A.

Many dicult problems of combinatorial analysis, graph theory, other areas of mathematics and statistical physics can be stated and solved in terms of permanents. The basically make use of the major combinatorial properties of permanents of (0, 1)-matrices to count the number of systems of dierent representatives of sets [1–3].

The basic results of thegeneral theory of matrix functions are reduced in review L. Rodman [4]. The permanental function of the matrices over various (partially ordered) algebraic systems arises at study dierent properties of these systems and their applications:

the permanent over max algebras in the classical Travelling Sa lesman Problem (R. Cuninghame - Green, 1975;

V. Gorbunchov, 1980;

R. Bapat, 1995);

the permanent in the theory of distributive Siberian Federal University e-mail: anott@scn.ru lattices (L. Skornjakov and D. Egorova, 1984);

for permanents with logical variables (A. Razborov, 1985);

by reviewing geometrical inequalities for permanents over ps-elds and Boolean algebras (M.

Golovanov, G. Egorychev, and D. Moiseenko, 1987);

the permanents over nite elds emerged investigation of the four-color problem (M. Shor, 1990);

the permanents with nonstandard operations over number elds (G. Egorychev, 1993), and others. In 2004 author has received a set of formulas of new type for permanents over an associative commutative rings, that has allowed me to introduce denitions rstly and to study properties permanents over com mutative rings and a division on integer numbers and permanents over arbitrary (not necessarily associative) rings ([3], § 1.3).

Using the characteristic properties, the known theorem of pola rization, the apparatus of the mixed discriminants and the integral representations by the author are obtained the properties of perma nents over various algebraic systems that has allowed to receive for its a series of new polynomial identities (the calculation formulas) and the geometrical inequalities. Similar results can be received for a wide range of known matrix functions related the permanental function, including matrix functions on subgroups of the symmetric group Sn.

References [1] Hall, JR. Combinatorial theory, Second Edition, John–Wiley &S uns, New–York, 1986.

[2] Minc, H. Permanents, Encyclopedia of Math. and Appl. vol.

6, Addison–Wesley, New–York, [3] Egorychev, G.P. Discrete Mathematics. Permanents, SFU, Krasnoyarsk, 2007, 272 pages (in Russian).

[4] Rodman L. Matrix functions. Handbook of Algedra vol. 1, Ed. M. Hazewinkel, Elsevier Science B.V., 1996, 117 – 154 pp.

METHOD OF COEFFICIENTS AND ITS RECENT APPLICATIONS G.P. Egorychev, M.N. Davletshin, E.V. Zima In the end of the 1970’s author has been developed the method of coecients of the integral representation and the computation of the combinatorial sums [1–3]. Here we have constructed the method of coecients (the set of inference rules and the theorem of on completeness) in following important cases: for Boolean fun ctions, functions of many-valued logic, orthogonal series (Fourier series) and others. It has allowed to consider for the rst time for them the classical method of generating functions as the summation method and to solve several of summation problems of new type.


Among them the proof of the following nontrivial identity of oered V. Stepanenko (2009), laying in the foundation of the algebraic theory of a new extensive class of functions in Cn.

Theorem Let T1 = T1 (k, n;

), T2 = T2 (k, n;

), T3 = T3 p, k, n;

, p and T4 = T4 (q, l;

l ) are sets of vectors = (2,..., n ), m = (m1,..., mn2 ), p = (0,..., p2 ), p = 3,..., n, l = (1,..., l+1 ), l = 0,..., q 2, with natural, or zero values of their coordinates (indexes of summation in (2)–(4)), satisfying to following systems of linear inequalities:

2 +... + n = k, T1 :

2 +... + (n 1) n = n 1.

m1 +... + mn2 = l, T2 :

m1 3, m2 24,..., mn2 (n 2)n.

0 +... + p2 = p, T3 :

0 +... + (p 2) p2 = mp2.

Siberian Federal University Siberian Federal University Physics and Computer Scince Wilfrid Laurier University e-mail: anott@scn.ru, makdav@rambler.ru, ezima@wlu.ca 1 +... + l+1 = q l 1, T4 :

1 +... + (l + 1) l+1 = q 1.

Then the following combinatorial identity for the Stirling num bers of second type is valid :

n1l 2i n n (1)n+k1 (n + k 1)! (i+2) } { mi i !

i=2 i= T1 T k= (2) = S2 (n 1, l + 1), (3) (n) where the numbers in 2 are given by the formula m1,..., mn (p) i ci p ! p (p) := p ! (3), p = 3,..., n, mp 1 !... p2 ! i !

i= T (p) (p) and the numbers c1,..., cp2 in (3) are given by the following formula (i!)i l+ (q) := (1)l (q l 1)! (4) cl, q = 3, 4,...

i !

i= T References [1] Egorychev, G. P.: Integral Representation and the Compu tation of Combinatorial Sums, Nauka, 1977 (in Russian);

Transl.

of Math. Monographs, Vol. 59, Amer.Math. Soc., 1984, 2nd Ed., 1989.

[2] Egorychev G.P. and Zima E.V. (2008). Integral represen taion and algorithms for closed form summation. Handbook of t Algebra, vol.5, Ed. M. Hazewinkel, 85-155 pp.

[3] Egorychev, G.P.: Method of Coecients: an algebraic cha racterization and recent applications. Advances in Combinatorial Mathematics Proceedings of the Waterloo Workshop in Computer Algebra 2008. by Ed. Ilias S. Kotsireas and Eugene V. Zima (Wa terloo, May 5 – 7, 2008), Springer Berlin Heidelberg, 2009, pp 1-30.

О ЧИСЛЕ УНАРНОПОРОЖДЕННЫХ МУЛЬТИОПЕРАЦИЙ В СУПЕРКЛОНАХ О.В. Зубков В данной работе исследуются унарнопорожденные мульти операции, получаемые из унарных мультиопераций путем при менения оператора суперпозиции и µоператора разрешимо сти. В качестве основной задачи рассматриваются подходы к нахождению числа унарнопорожденных мультиопераций от n переменных.

Утверждение 1. Число Un унарнопорожденных мульти операций от 2-х переменных равно 166.

Согласно результату Н.А. Перязева, мультиоперация явля ется унарнопорожденной тогда и только тогда, когда она пред ствима в виде пересечения некоторых из следующего образую щего множества мультиопераций:

B = {(13), (31), (23), (32), (0333), (3033), (3303), (3330)} Указан ные мультиоперации могут иметь фиктивные переменные.

Закодируем 0 в виде 00, 1 в виде 01, 2 в виде 10, 3 в виде 11.

Учитывая, что результат пересечения a b, где a, b {0, 1, 2, 3} при кодировании равен K(a) K(b), где K(x) есть код x, полу чим эквивалентное представление образующего множества в виде набора булевых функций B = {(0111), (1101), (1011), (1110), (00111111), (11001111), (11110011), (11111100)}. Очевид но, что все эти булевы функции, представимы дизъюнкцией двух литералов.

Используя принцип двойственности и вышеупомянутый ре зультат Н.А. Перязева, можно доказать Утверждение 2. Число Un унарнопорожденных мульти операций от n переменных равно числу булевых функций от n + 1 переменной, представимых в виде дизъюнкции элемен тарных конъюнкций, ранг которых равен 2 (дизъюнкции двух литеральных конъюнкций).

Восточно-Сибирская академия образования e-mail: oleg.zubkov@mail.ru Пример. Унарнопорожденная мультиоперация (1002) рав на пересечению (1133) (3322) (1313) (3232). Кодируя, по лучим: (1133) (01011111) = (x1 x3 ), (3322) (11111010) = (x1 x3 ), (1313) (01110111) = (x2 x3 ), (3232) (11101110) = (x2 x3 ), и наконец (1002) (01000010) = (x1 x3 )(x1 x3 )(x x3 )(x2 x3 ). В заключение, переходя к двойственным функци ям, получим: (1002) (01000010) (10111101) = x1 x3 x1 x x2 x3 x2 x3.

Замечание. Очевидно, что для некоторых булевых функ ций может быть несколько представлений в виде дизъюнкции двухлитеральных конъюнкций.

Легко заметить, что если в составе вышеупомянутой дизъ юнкции есть две элементарные конъюнкции вида xi xj j и i xi xj j, эти конъюнкции можно свернуть к виду xi. Число бу i i левых функций от n+1 переменной, представимых в виде дизъ юнкции двухлитеральных и однолитеральных конъюнкций, в которых число однолитеральных конъюнкций не равно нулю, обозначим через Un.

Утверждение 3.

U1 = 2, U1 = 1= U0 = 4, U U1 = 16, U1 = n+ Un = n+1 2i 1 (Uni Uni ).

i=1 i ПАРАЛЛЕЛЬНЫЕ МОДЕЛИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В ЗАДАЧЕ МИНИМИЗАЦИИ ПОЛИНОМИАЛЬНОГО ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ Б.П. Ильин Одной из проблем алгебры логики является задача миними зации полиномиального представления булевых функций. Дан Байкальский Государственный Университет Экономики и Права e-mail: rays.irk@gmail.com ная задача заключается в том, что одна и та же булева функ ция может быть представлена в виде разных полиномиальных представлений. Например, функция f (x1, x2 ) = (1001) может быть представлена в виде различных полиномов:

f (x1, x2 ) = x1 x или f (x1, x2 ) = x1 · x2 x1 x2 1.

Сложность этих булевых функций определяется как число сла гаемых в полиноме. При релизации функции программируемой логической матрицей, эта сложность соответствует количеству горизонтальных шин[1], что имеет практическое применение при разработке электронных устройств.

Известны точные алгоритмы (см. например [2]) получают точное решение задачи минимизации полиномиального пред ставления булевых функций только лишь для функций с чис лом аргументов не более шести. Для функций с большим чис лом переменных недостаточно ресурсов современных компью теров для выполнения на них программ, находящих точный минимум. Практическими методами решения данного типа за дач могут выступать генетические алгоритмы, которые пред ставляют собой эвристические алгоритмы поиска наилучшего решения из набора возможных. Задача кодируется таким обра зом, чтобы её решение могло быть представлено в виде вектора ( хромосома ). Случайным образом создаётся некоторое коли чество начальных векторов ( начальная популяция ). Они оце ниваются с использованием функции приспособленности, в результате чего каждому вектору присваивается определённое значение ( приспособленность ), которое определяет вероят ность выживания организма, представленного данным векто ром. После этого с использованием полученных значений при способленности выбираются вектора (селекция), допущенные к скрещиванию. К этим векторам применяются генетические операторы (в большинстве случаев скрещивание - crossover и мутация - mutation), создавая таким образом следующее поколение. Особи следующего поколения также оценивают ся, затем производится селекция, применяются генетические операторы и т. д. Так моделируется эволюционный процесс, продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий останова алгоритма[3].

Однако, и этот класс методов не лишен недостатков. Т.к.

классический генетический алгоритм относится к классу поис ковых, то есть вероятность, что данный алгоритм свалиться в один из локальных экстремумов.Одним из способов преодо ления данного недостатка является мутация, однако, слишком большое пространство перебора делает маловероятным случай ное нахождение глобального минимума.

Одним из вариантов улучшения этой ситуации – приме нение параллельных моделей генетических алгоритмов с ис пользованием вычислительных кластеров. В этом случае па раллельные генетические алгоритмы позволят осуществлять множественную эволюцию решений на каждом из узлов и обмениваться наилучшими между собой, что позволит суще ственно улучшить качество поиска решений по сравнению с классическим генетическим алгоритмом. Для этого могут быть использованы следующие модели генетических алгоритмов:

Островная модель (Island Model) генетического ал горитма. Популяция разбивается на несколько подпопуляций, каждая их которых будет развиваться отдельно с помощью ге нетического алгоритма. Эти подпопуляции будут развиваться независимо, и только изредка будут происходить миграции, т.е обмен представителями между подпопуляциями. Данная мо дель генетического алгоритма обладает следующими свойства ми:

1. Нескольких популяций, как правило, одинакового фик сированного размера;

любые комбинации стратегий отбора и формирования следующего поколения в каждой популяции.

Можно сделать так, что в разных популяциях будут использо ваться разные комбинации стратегий, хотя даже один вариант дает разнообразные решения на различных островах ;

2. Ограничений на тип мутации нет;

3. Случайный обмен особями между островами. Если ми грация будет слишком активной, то особенности островной мо дели будут сглажены, и она будет не очень сильно отличаться от моделей генетического алгоритма без параллелизма;

если же миграция будет слишком редкой, то она не сможет предот вратить преждевременного схождения подпопуляций.

Клеточная модель (Cellular Model) параллельного генетического алгоритма. Пусть дано 2500 процессов, рас положенных на сетке размером 50x50 ячеек, замкнутой. Каж дый процесс может взаимодействовать только с четырьмя сво ими соседями (сверху, снизу, слева, справа). В каждой ячейке находится ровно одна особь. Каждый процесс будет выбирать лучшую особь среди своих соседей, скрещивать с ней особь из своей ячейки и одного полученного ребенка помещать в свою ячейку вместо родителя. По мере работы такого алгоритма воз никают эффекты, похожие на островную модель. Сначала все особи имеют случайную приспособленность. Спустя несколь ко поколений образуются небольшие области похожих особей с близкой приспособленностью. По мере работы алгоритма эти области растут и конкурируют между собой.


Глобальная модель Хозяин-Работник (Global mo del Worker/Farmer). Алгоритм Хозяин-Работник реали зуется с применением нескольких работающих рабочих стан ций, также есть возможность организовать параллельную ра боту двух процессов на базе двухядерного процессора одной единственной рабочей станции. Среди всех рабочих станций выделяют Хозяина и Работников. Рабочие станции Ра ботники отвечают за процессы воспроизводства, мутации и вычисления функции пригодности особей для их отбора в но вое поколение. Все созданные и оцененные Работниками осо би поступают на рабочую станцию Хозяина, которая затем проводит отбор особей согласно оценке их пригодности в но вую популяцию. Отобранные особи передаются Хозяином к рабочим станциям Работникам.

Перед использованием генетического алгоритма в решении задачи минимизации было необходимо решить задачу нахож дения оптимальных параметров генетического алгоритма. При решении этой задачи, с использованием вычислительного кла стера, построенного на базе учебных классов БГУЭП, были по лучены результаты подбора наиболее оптимальных параметров классического генетического алгоритма.

Были проведены испытания ГА с различными параметрами и были получены следующие выводы:

При небольшом числе итераций наиболее качественные значения алгоритма получены с использованием двухточечно го кроссовера, с использованием первого типа генерации на чальной совокупности, и достаточно большом размере этой по пуляции.

Вне зависимости от выбранного закона распределения с увеличением количества итераций наблюдается следующая особенность независимо от выбранных параметров мутации, генерации первоначальной совокупности представителей, ти па селекции генетический алгоритм возвращает максимально точные решения.

Оптимальным числом мутаций является треть от общего числа итераций, число мутирующих генов - до половины от общей длины функции.

При увеличении числа мутирующих генов, возрастает число итераций вне зависимости от остальных параметров.

Так как в дальнейшем планируется использовать генетиче ский алгоритм 6-ти переменных, как промежуточные вычис ления, то было бы наиболее эффективным получать наиболее точное решение за минимальное время. Такими параметрами могут быть - 100 итераций, 30 мутаций, 4 мутирующих гена, - размер популяции, тип генерации - 1, тип кроссовера - двух точечный, равномерный закон распределения. С данным набо ром параметров задача минимизации полиномиального пред ставления булевой функции 6-ти переменных решается за секунд на одном узле кластера с тактовой частотой 1,7 Ггц и оперативной памятью 1 Гб.

Работа выполнена при поддержке гранта РФФИ, проект 09 01-00476.

Список литературы [1] Ильин, Б.П. Алгоритм минимизации полиномиальных представлений булевых функций с использованием библиотек / Б.П. Ильин // Применение математических методов и инфор мационных технологий в экономике. - Иркутск: Изд-во БГУ ЭП, 2009. С. 67-73.

[2] Балюк А.С. Избранные вопросы теории булевых функ ций / А.С. Балюк, С.Ф. Винокуров, А.И. Гайдуков, О.В. Зуб ков, К.Д. Кириченко, В.И. Пантелеев, Н.А. Перязев, Ю.В. Пе рязева;

Под ред. С.Ф. Винокурова и Н.А. Перязева.- М.: ФИЗ МАТЛИТ, 2001.- 192 с.

[3] Ильин, Б.П. Введение в генетические алгоритмы (ГА) / Б.П. Ильин // Применение математических методов и инфор мационных технологий в экономике. - Иркутск: Изд-во БГУ ЭП, 2008. С. 63-71.

[4] Whitley D. A Genetic Algorithm Tutorial / D. Whitley // Statistics and Computing (4). - 1994, С. 65-85.

[5] Whitley D. An Overview of Evolutionary Algorithms / D.

Whitley // Journal of Information and Software Technology. 2001, С. 43:817-831.

О СЛОЖНОСТИ БУЛЕВЫХ ФУНКЦИЙ 7 ПЕРЕМЕННЫХ В КЛАССЕ ПНФ А.С. Казимиров, С.Ю. Реймеров В работе исследуется сложность представления булевых функций в классе полиномиальных нормальных форм. Поли номиальным представлением булевой функции f (x1,..., xn ) бу дем называть следующее представление:

f (x1,..., xn ) = K1 K2 · · · Ks, Восточно-Сибирская государственная академия образования e-mail: a.kazimirov@gmail.com, sergeyreym@gmail.com где сложение по модулю 2, Ki произведения переменных, возможно с отрицанием, или функция 1. Под сложностью поли нома будем понимать число слагаемых в нем, а под сложностью L(f ) булевой функции f будем понимать сложность наимень шего из представляющих ее полиномов. Через L(n) обозначим максимальную из сложностей функций n переменных.

В [1] были найдены все функции 6 переменных сложности 15 и показано, что L(6) = 15.

0 Разложение Шеннона f (x1,..., xn ) = x1 fx1 x1 fx1 дает сле 0 ) + L(f 1 ), где f 0 и дующую оценку сложности: L(f ) L(fx1 x1 x 1 нулевая и единичная остаточные функции, полученные fx подстановкой констант 0 и 1 вместо первой переменной.

Исходя из данной оценки, все функции 6 переменных слож ности 14 можно найти следующим образом: минимизировать все функции 6 переменных, полученных комбинациями пар функций 5 переменных f1 и f2 таких, что L(f1 ) + L(f2 ) 14.

Полный перебор в данной задаче потребует порядка 260 опе раций. Для сокращения перебора можно использовать отно шение эквивалентности, сохраняющее сложность полиномов.

Наиболее общей из таких эквивалентностей является SP-экви валентность [2]. Если в качестве f1 брать представителя класса SP-эквивалентности, а в качестве f2 любую булеву функ цию, дающую суммарную сложность L(f1 ) + L(f2 ) 14, то общий перебор сокращается до 241 вариантов. Также примене ние SP-эквивалентности дает следующее свойство: сложность 0 f не превышает суммы сложностей производной (fx1 fx1 ) со сложностями каждой из остаточных.

Для поиска функций 6 переменных со сложностью 14 до статочно в качестве остаточных функций в разложении 0 f (x1,..., xn ) = x1 fx1 x1 fx брать пары функций со сложностями (9,9), (9,8), (9,7), (9,6), (9,5), (8,8), (8,7), (8,6), (7,7).

В таблице приведено число SP-классов функций 5 перемен ных со сложностью выше 4.

СложностьЧисло классовЧисло функций 5 971 545 193 6 3572 2 398 267 7 2143 1 299 295 8 86 11 460 9 2 7 Всего 6936 4 294 967 Как видно из таблицы, пар функций, для которых надо по считать сложность, достаточно большое число (241 ), и вычис ление сложности каждой из них алгоритмом точной миними зации займет очень много времени. Поэтому применяется ал горитм минимизации с отсечением при достижении сложности меньше 14 с дополнительными стратегиями.

Алгоритм работает следующим образом: перебираются все функции 5 переменных с заданной сложностью, и для каж дой переберираются все представители классов SP-эквивалент ности. Для каждой такой пары (представитель класса функ ция) по разложению Шеннона и производной вычисляется верх няя оценка сложности для функции, составленной из этих двух.

Если верхняя оценка больше либо равна 14, то эта пара зано сится в список кандидатов. Полученные кандидаты минимизи руются алгоритмом точной минимизации функций 6 перемен ных.

В результате отбора было найдено 62 SP-класса сложности 14, которые в сумме содержат 65 393 568 функций.

В [3] показано, что сложность функций от 7 переменных не превосходит 28. Если существуют функции 7 переменных сложности 27 или 28, то по разложению Шеннона сумма слож ностей нулевой и единичной остаточных этой функции по лю бой переменной должна быть не менее 27.

Таким образом, чтобы проверить, существуют ли такие функции, можно перебрать пары функций 6 переменных (с точностью до SP-эквивалентности), сложности которых в сум ме дают 27 или больше. Такими парами будут пары со слож ностями (12, 15), (13, 14), (13, 15), (14, 14), (14, 15) и (15, 15).

Однако часть групп можно исключить из перебора следующи ми рассуждениями.

Возьмем две функции 6 переменных f1 и f2 такие, что L(f1 ) = 12, L(f2 ) = 15. Из них составляется функция-кандидат 7 переменных f (x1,..., x7 ) = x1 f1 x1 f2. Рассмотрим функцию f3 = f1 f2. Поскольку функции f1 и f2 являются нулевой и единичной остаточной функции f по x1, то функция f3 явля ется производной f по x1.

Если L(f3 ) 14, то функция g(x1,..., x7 ) = x1 f1 x1 f будет иметь сложность L(g) 12 + 14 = 26. Но функция g является SP-эквивалентной f, а значит, L(f ) 26.

Если же L(f3 ) = 15, то функция h(x1,..., x7 ) = x1 f2 x1 f будет рассматриваться в качестве кандидата в группе перебо ра (15, 15). Таким образом, либо f имеет сложность меньше 27, либо эквивалентная ей функция будет в другой группе пе ребора. Значит, группу (12, 15) можно полностью исключить из рассмотрения. Аналогичными рассуждениями исключаются группы (13, 14) и (13, 15).

Из оставшихся групп (14, 14), (14, 15) и (15, 15) были состав лены функции-кандидаты, которые минимизировались гене тическим алгоритмом минимизации с небольшим числом ите раций для более быстрого отсева. Для почти всех функций кандидатов после первого запуска были найдены полиномы сложности меньше 27. Остальные функции проходили более жесктий остев. После нескольких отсевов для всех функций кандидатов были найдены полиномы сложности меньше 27.

Теорема. L(7) 26.

Ранее в [4] было показано, что L(7) 24.

Работа выполнена при финансовой поддержке РФФИ (про ект 09-01-00476-а).

Список литературы [1] Gaidukov A. Algorithm to derive minimum ESOPs for 6 vatiable function. Proceedings of the 5th International Workshop on Boolean Problems 2002, Freiberg, Germany, pp. 141–148, Sept.

19–20, [2] Казимиров А. С. Группы операторных преобразований булевых функций Международная конференция "Алгебра и ее приложения": Тезисы докладов. Красноярск, 2007. С. 64– [3] Винокуров С. Ф., Казимиров А. С. Верхняя оценка слож ности булевых функций в классе ПНФ // Algebra and Model Theory 4. Novosibirsk. Novosibirsk State Technical University, 2003. P. 160–165.

[4] Винокуров С. Ф., Казимиров А. С. О сложности поли номиальных представлений булевых функций 7 переменных // Синтаксис и семантика логических систем. Материалы школы семинара. Владивосток: Дальнаука, 2008. С.34–35.

НЕРЕКУРРЕНТНАЯ ФОРМУЛА ДЛЯ ОДНОГО ЧАСТНОГО СЛУЧАЯ ОЦЕНКИ ШОНХЕМА К.Д. Кириченко Одной из задач экстремального комбинаторного анализа явля ется задача Турана[1], имеющая эквивалентное описание в ви де задачи о покрытии[2], которая формулируется следующим образом. Пусть задано некоторое v-элементное множество A.

Найти набор подмножеств A1,..., As, каждое из которых име ет мощность k, такой что для всякого B A мощности t най дется i, такое что B Ai. За C(v, k, t) обозначим минимально возможное количество таких подмножеств. При этом t k v.

Данная задача возникает в ряде приложений, в том чис ле при изучении сложности представлений булевых функций полиномами [3]. В частности, доказано, что v Lпнф (v) C(v, i, i 1), i= Восточно-Сибирская государственная академия образования e-mail: constkir@gmail.com где Lпнф (v) функция Шеннона сложности булевых функций в классе полиномиальных нормальных форм.

Обзор результатов, по задаче Турана и задаче о покрытии можно найти в справочнике по комбинаторному дизайну[4].

Естественной оценкой снизу числа C(v, k, t) является оцен ка Шонхема[2] L(v, k, t), определяемая следующими рекуррент ными соотношениями (v + 1)L(v, k, t) L(v, k, 0) = 1, L(v + 1, k + 1, t + 1) =.

k+ В интерактивном справочнике числовых последовательностей Н. Слоана[5] данная последовательность имеет идентификатор A036838.

Следующая теорема дает нерекуррентную формулу оценки Шонхема для случая t = k 1, при условии, что v k является простым числом.

Теорема Пусть v k простое число, тогда v v vk vk L(v, k, k 1) = vk Доказательство Обозначим a = v k, тогда требуемое утверждение можно записать в виде a+k k 1a a L(a + k, k, k 1) = a В первую очередь докажем, что для любого k 0 и про стого a имеет место сравнение a+k k + 1 (mod a) a a k. Тогда k = ra + w, где 0 w a. Тогда Обозначим r = a (ra + a + w) · · · (ra + a) · · · (ra + w + 1) a+k = = a(a 1)!

a (ra + a + w) · · · (ra + a + 1)(ra + a 1) · · · (ra + w + 1) = (r + 1) (a 1)!

При переходе в поле Za числитель и знаменатель дроби совпа дут, таким образом a+k k r+1 + 1 (mod a).

a a Теперь докажем основное утверждение теоремы индукцией по k.

При k = 1 имеем a+1 1 a+1a a a L(a + 1, 1, 0) = = = a a Проверим шаг индукции. Пусть для k = n утверждение имеет место. Тогда (a + n + 1)L(a + n, n, n 1) L(a + n + 1, n + 1, n) = = n+ a+n a+n+ a+n+1 n a+n+1 n 1 + n+1 a a a n+1 a = = a a Рассмотрим слагаемое a+n+1 ( n + 1) Представим n в виде n+1 a n = ra + w, где 0 w a. Тогда a+n+1 n ar + a ( + 1) = r + 1 + n+1 a ar + w + При w = a 1 получаем ar + a (ar + a) n+1 n+ r+1+ = r+2 = +1 = +1 = + ar + w + 1 a a a ar+a Рассмотрим w a 1. Введем обозначение = ar+w+1, оче видно 0 1. Тогда получим ar + a ra n+ r+1+ =r+1+= +1+= +1+ ar + w + 1 a a Таким образом, в исходной формуле получаем a+n+1 n+ a a L(a + n + 1, n + 1, n) = a (a+n+1) n+1 Из доказанного ранее утверждения является a a a целым числом, при этом 0 1, следовательно, при округ лении вверх отбрасывается.

a+n+1 n+ a a L(a + n + 1, n + 1, n) =, a что и требовалось доказать.

Работа выполнена при поддержке РФФИ проект 09–01- Список литературы [1] Turan P. Reseach Problems.// Magyar Tud. Acad. Mat.

Kutato Int. Kozl – 1961. – vol 6. – pp 417-423.

[2] Shonheim J. On Covering.// Pacic Journal of Mathematics.

– 1964. – vol 14. – pp 1405-1411.

[3] Кириченко К.Д. Верхняя оценка сложности полиноми альных нормальных форм булевых функций.// Дискретная ма тематика. – 2005. Т. 17, № 3, – С. 81-88.

[4] Gordon D.M., Douglas R.S. Coverings.// Handbook of Com binatorial Designs.– Taylor and Francis Group. – 2007. – pp 365 373.

[5] Sloane N. On-Line Encyclopedia of Integer Sequences [Элек тронный ресурс]// URL: http://www.research.att.com/njas/se quences (дата обращения 10.06.2010).

О СЛОЖНОСТИ ВЕНТИЛЬНЫХ СХЕМ:

БУЛЕВ И ОБЩИЙ СЛУЧАИ В.В. Кочергин В работе исследуется сложность реализации матриц вен тильными схемами для некоторых задач, тесно связанных с проблематикой сложности вычисления одночленов и систем од ночленов. Следуя Н. Пиппенджеру [1], рассмотрим возника ющую естественным образом, например, в задаче о сложно сти вычисления систем одночленов, следующую модификацию классических вентильных схем [2].

целочисленная матрица размера p q с Пусть A = (aij ) неотрицательными элементами. Ориентированный граф S без ориентированных циклов будем называть вентильной схемой с кратными путями (или вентильной схемой с предписанным числом путей), реализующей матрицу A, если: в S выделено p вершин входных полюсов и q вершин выходных полюсов;

в S нет ориентированных путей от одного входа к другому, от одного выхода к другому, от выхода к входу;

для любой пары (i, j), 1 i p, 1 j q, число ориентированных путей от i-го входа к j-му выходу равно в точности aij. Через Lкр (S) обозначим число ребер (вентилей) схемы S и положим ВС Lкр (A) = min Lкр (S), где минимум берется по всем схемам, ВС ВС реализующим матрицу A.

1. Реализация булевых матриц.

булева матрица размера p q. Для j = Пусть A = (aij ) 1,..., q обозначим через pj наибольший номер среди ненулевых элементов j-го столбца матрицы A, т. е. pj = max {i | aij = 0}.

Положим H(A) = q pj. Отметим, что в матрице A ну j= левых элементов не менее pq H(A).

Теорема 1 [3, 4]. Для произвольной последовательности булевых матриц {An } размера pn qn, удовлетворяющей при n условию H(An ), справедливо неравенство Московский государственный университет имени М. В. Ломоносова, Механико-математический факультет;

e-mail: vvkoch@yandex.ru H(An ) LBC (An ) (1 + o (1)) + O(pn + qn ).

log2 H(An ) Замечание 1. Из стандартных мощностных рассуждений легко устанавливается асимптотическая неулучшаемость оцен ки теоремы 1, т. е. справедливость аналогичной асимптотиче ской нижней оценки для "почти всех"матриц из класса буле вых матриц с фиксированной границей между "информацион ной"и "заведомо нулевой"частями матрицы.

Замечание 2. Утверждение теоремы 1 автоматически рас пространяется и на модель классических вентильных схем, от личающуюся тем, что не требуется единственность пути от вхо да к выходу. При этом мощностная нижняя оценка также оста ется справедливой.

Теорема 1 является ключевым моментом при асимптотиче ски точном решении известных задач Д. Кнута о сложности вычисления наборов степеней и Р. Беллмана о сложности вы числения одночлена многих переменных [5].

2. Реализация целочисленных матриц с неотрица тельными элементами.

В работе [6] при слабых ограничениях установлена асимп тотика роста функции Шеннона сложности реализации мат риц заданного размера с элементами, не превосходящими неко торой величины. Про поведение сложности индивидуальных последовательностей матриц известно немного. Помимо доста точно простой нижней оценки [7] Lкр (A) 3 log3 D(A) (через ВС D(A) обозначен максимум абсолютных величин миноров мат рицы A, где максимум берется по всем минорам), в общем слу чае можно отметить следующее.

Теорема 2 [7]. Для произвольного натурального m и произ вольной последовательности матриц {An } с неотрицатель ными элементами, каждая из которых имеет размер либо 2 qn, где qn m, либо pn 2, где pn m, либо 3 3, при условии D(An ) выполняется соотношение Lкр (An ) 3 log3 D(An ).

ВС Отметим, что уже для матриц размера 4 4 аналогичное утверждение неверно [7].

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

Матрица B = (bij ) называется доопределением матрицы A = (aij ) такого же размера, если в матрице B все элемен ты определены (нет символов ), и для любого определенного элемента aij матрицы A справедливо равенство aij = bij.

Пусть A недоопределенная матрица, в которой все опре деленные элементы целочисленны и неотрицательны. Положим Lкр (A) = inf Lкр (B), где инфинум берется по всем доопре ВС ВС делениям B матрицы A до целочисленной матрицы с неотри цательными элементами. Очевидно, что инфинум достигается.

Без ограничения общности можно считать, что в матрицах нет ни строк, ни столбцов, полностью состоящих из нулей и сим волов.

Обозначим через D(A) максимум абсолютных величин ми норов матрицы A, где максимум берется по всем минорам, со стоящим только из определенных элементов.

Далее рассматриваем недоопределенные матрицы только размера p 2 (случай матриц размера 2 q рассматривается аналогично).

Для недоопределенной матрицы A размера p 2 положим max{ai1 } max{ai2 } d1 (a) = max{max{aj1 },1}, d2 (a) = max{max{aj2 },1}, где максимумы в числителях (по i) берутся по всем определенным элементам, стоящим в полностью опредеденных строках, а максимумы в знаменателях (по j) берутся по всем определенным элементам, стоящим в неполностью опредеденных строках (т. е. в стро символ ). Теперь положим ках, в которых второй элемент D (A) = D(A) max{d1, d2, 1}.



Pages:   || 2 | 3 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.