WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     | 1 |   ...   | 5 | 6 || 8 |

«Излагаются некоторые результаты по теории сложности схемных и тьюринговых алгоритмов, полученные А. Е. Андреевым, Нгуен Ким Ань и Т. М. Игамбердыевым. Введение Алгоритмы ...»

-- [ Страница 7 ] --

Символом E2 обозначим множество {0, 1}, а E2 множество всех Значит, E2 это множество всех вершин единичного n-мерного куба B Через P2 обозначим множество всех булевых функций, то есть таких функций, у которых переменные и сами функции принимают значения из E2.

Пусть Элементарной конъюнкцией ранга r называется логическое произведение x11 &x22 &... &xrr, где все xij различны.

Дизъюнктивная нормальная форма (д. н. ф.) есть логическая сумма D(x1,..., xn ) = K1...Kt различных элементарных конъюнкций Kj. Число элементарных конъюнкций в д. н. ф. называется ее длиной и обозначается d.

Если булева функция представима в виде д. н. ф., то говорят, что последняя реализует данную функцию.

Каждой булевой функции f (x1,..., xn ) поставим в соответствие подмножество Nf множества E2 всех a таких, что f () = 1.

юнкции K ранга r, называется интервалом размерности n r.

Пусть f (x1,..., xn ) и f (x1,..., xn ) булевы функции, причем Nf Nf. Говорят, что функция f(x1,..., xn ) аппроксимирует сверху функцию f (x1,..., xn ).

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

Пусть A конечное множество, а функция, ставящая в соответствие каждому a A неотрицательное число (a).

Обозначим через среднее значение (или математическое ожидание) функции на множестве A, а через дисперсию, или среднеквадратичное отклонение функции.

Пусть As = {a1,..., as } последовательность конечных множеств, а Ps (Q) число множеств a As, обладающих свойством Q.

Говорят, что почти все элементы множества A s при s обладают свойством Q, если lim P|As | = 1.

система булевых уравнений.

Рассматривается класс (n, m, t, r) систем булевых уравнений, заданных в виде д. н. ф., со следующими параметрами: число переменных равно n, число уравнений в каждой систем m, число элементарных конъюнкций во всех д. н. ф., соответствующих уравнениям, одинаково и равно t, и число букв во всех элементарных конъюнкциях одинаково и равно r. Изучен вопрос о типичном значении числа решений систем из класса (n, m, t, r).

среднее значение числа решений для систем из (n, m, t, r).

Справедливо следующее утверждение:

Среднее значение числа решений системы булевых уравнений (n, m, t, r) равно M G = 2n (1 (1 2r )t )m.

Теорема 5.1. При выполнении условий r, M G, t2 r для почти всех систем булевых уравнений (n, m, t, r) число решений асимптотически равно Рассматривается класс П(n, m, t, r) систем булевых уравнений, заданных в виде суммы по модулю 2 элементарных конъюнкций, со следующими параметрами: число переменных равно n, число уравнений в каждой системе равно m, число слагаемых во всех суммах, соответствующих уравнениям, одинаково и равно t, и число букв в каждом слагаемом равно r. Изучен вопрос о типичном значении числа решений систем T из класса П(n, m, t, r).

среднее значение числа решений для системы из П(n, m, t, r).

Теорема 5.2. Среднее значение числа решений системы булевых уравнений T П(n, m, t, r) равно M Q = 2 nm (1 (1 21r )t )m.

Пусть n, и все параметры являются функциями от n.

Теорема 5.3. Для любого (0, 1) найдется такое () (0, 1), что для почти всех систем булевых уравнений T П(n, m, t, r) число решений асимптотически равно Следствие 5.1. Если выполняются условия теоремы 5.2, то при m(121r )t = o(1) для почти всех булевых уравнений T П(n, m, t, r) число решений асимптотически равно 2 nm.

Известно, что одной из наиболее удобных и часто применяемых форм задания булевых функций является д. н. ф. В частности, булевы уравнения, возникающие на практике, как правило задаются в виде элементарные конъюнкции, t называем длиной D.

Нетрудно видеть, что сложность решения системы таких уравнений с помощью алгоритмов, предлагаемых, например, в [71], зависит от длин уравнений ti (1 i m), уменьшая которые, можно существенно упростить решение. В связи с эти возникает задача аппроксимации булевых функций.

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

Сопоставим д. н. ф. D(x1,..., xn ) граф G(D), вершинами которого являются элементарные конъюнкции из д. н. ф. D(x 1,..., xn ), причем две вершины графа соединены только тогда, когда они имеют общие переменные.

Назовем д. н. ф. D(x1,..., xn ) ациклической, если граф G(D) является лесом.

есть это доля нулей функции f.

Пусть D(R,, t) это множество всех ациклических д. н. ф. длины t таких, что число букв в каждой элементарной конъюнкции не более R и число букв, общих у двух элементарных конъюнкций, не более.

Пусть (R,, t) это максимальная доля нулей для д. н. ф. из класса D(R,, t) Теорема 5.4. Имеет место соотношение Следствие 5.2. Пусть R и Пусть D(R, t) множество всех д. н. ф. длины t, у которых число букв в элементарных конъюнкциях не превышает R.

Теорема 5.5. Для любой д. н. ф. D D(R, t) найдется д. н. ф. D длины не более t0 такая, что ND ND, причем Предлагаются конкретные алгоритмы аппроксимации булевых функций и алгоритм решения систем булевых уравнений.

Пусть дана булева функция f (x1,..., xn ), заданная с помощью д. н. ф. D(x1,..., xn ) = K1 K2... Kt, где Ki (1 i t) элементарная конъюнкция ранга R.

Предлагаются алгоритмы U1 и U2, строящие аппроксимирующую функцию f(x1,..., xn ), заданную с помощью д. н. ф. D(x1,..., xn ) = K1 K2... Kt0, такую, что Nf Nf, причем t0 t, где t фиксированный наперед заданный параметр, и по ходу работы алгоритма производится подсчет оценки величины возможной погрешности П(D, D) (|Nf | |Nf |).

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

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

Пусть дана система булевых уравнений, заданных в виде д. н. ф.

m), можно получить систему Число решений системы, которые могут не являться решениями оценивается с помощью теоремы 5.5.

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

1) по строится ;

2) решается ;

3) из решений отбираются решения путем проверки.

Список литературы [1] Shannon C. Е. The synthesis of two-terminal swithing circuits // Bell Syst. Techn. J. 1949. V. 28. N 1. P. 59–98.

[2] Лупанов О. Б. О вентильных и контактно-вентильных схемах // Доклады АН СССР. 1956. Т. 111. № 6. С. 1171–1174.

[3] Лупанов О. Б. О синтезе контактных схем // Доклады АН СССР. 1958. Т. 119. № 1. С. 23–26.

[4] Лупанов О. Б. Об одном методе синтеза схем // Известия вузов.

Радиофизика. 1958. Т. 1. № 1. С. 120–140.

[5] Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. 1960. Вып. 3.

[6] Лупанов О. Б. Об одном классе схем из функциональных элементов (формулы с конечной памятью) // Проблемы кибернетики. 1962. Вып. 7. С. 61–114.

[7] Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. 1963. Вып. 10. С. 63–97.

[8] Лупанов О. Б. О сложности реализации функций алгебры логики релейно-контактными схемами // Проблемы кибернетики.

1964. Вып. 11. С. 25–47.

[9] Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики. 1970. Вып. 23. С. 43–81.

[10] Яблонский С. В. О классах функций алгебры логики, допускающих простую схемную реализацию // Успехи математических наук. 1957. Т. 12. Вып. 6. С. 189–196.

[11] Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. 1959.

[12] Лупанов О. Б. О принципе локального кодирования и реализации функций из некоторых классов схемами из функциональных элементов // Доклады АН СССР. 1961. Т. 140. № 2.

[13] Лупанов О. Б. Об одном подходе к синтезу управляющих систем принципе локального кодирования // Проблемы кибернетики. 1965. Вып. 14. С. 31–110.

[14] Потапов Ю. Г., Яблонский С. В. О синтезе самокорректирующихся контактных схем // Доклады АН СССР. 1960. Т. 134.

[15] Мадатян Х. А. О синтезе схем корректирующих размыканий контактов // Доклады АН СССР. 1964. Т. 159. № 2. С. 290–293.

[16] Нечипорук Э. И. О топологических принципах самокорректирования // Доклады АН СССР. 1968. Т. 179. № 4. С. 786–789.

[17] Нечипорук Э. И. О корректировании обрывов в вентильных и контактных схемах // Кибернетика. 1968. № 5. С. 40–48.

[18] Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики. 1969. Вып. 21. С. 5–102.

[19] Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики. 1973. Вып. 26. С. 19–26.

[20] Редькин Н. П. О самокорректировании контактных схем // Проблемы кибернетики. 1978. Вып. 33. С. 119–138.

[21] Редькин Н. П. О самокорректировании контактных схем, II // Проблемы кибернетики. 1979. Вып. 36. С. 195–208.

[22] Улиг Д. Самокорректирующиеся контактные схемы исправляющие большое число ошибок // Доклады АН СССР. 1978. Т. 241.

№ 6. С. 1273–1276.

[23] Кириенко Г. И. О самокорректирующихся схемах из функциональных элементов // Проблемы кибернетики. 1964. Вып. 12.

[24] Кириенко Г. И. Синтез самокорректирующихся схем из функциональных элементов для случая растущего числа ошибок в схеме // Дискретный анализ. 1970. Вып. 16. С. 38–43.

[25] Улиг Д. О синтезе самокорректирующихся схем из функциональных элементов с малым числом ненадежных элементов // Математические заметки. 1974. Т. 15. № 6. С. 937–944.

[26] Ортюков С. И. Об оценках функции Шеннона для схем из ненадежных функциональных элементов // Проблемы кибернетики.

1983. Вып. 40. С. 269.

[27] Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М.: Наука, 1966.

[28] Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. 1960. Вып. 3.

[29] Андреев А. Е. О синтезе самокорректирующихся управляющих систем // Доклады АН СССР. 1984. Т. 277. № 3. С. 521–525.

[30] Андреев А. Е. Универсальный принцип самокорректирования // Математический сборник. 1985. Т. 127 (169). № 6. С. 147–172.

[31] Андреев А. Е. О сложности монотонных функций // Вестник Московского университета. Серия 1: Математика, механика.

1985. № 4. С. 83–87.

[32] Андреев А. Е. Метод бесповторной редукции синтеза самокорректирующихся схем // Доклады АН СССР. 1985. Т. 283. № 2.

С. 265–269.

[33] Андреев А. Е. О синтезе топологических функциональных сетей / Препринт № 259 ИПМех АН СССР и МГУ им. М. В. Ломоносова. 1985. С. 1–67.

[34] Андреев А. Е. О синтезе контактных многополюсников // 7-я Всесоюзная конференция Проблемы теоретической кибернетики, тезисы докладов. Иркутск, 1985. С. 9–10.

[35] Андреев А. Е. О синтезе функциональных сетей / Докторская диссертация. МГУ. 1985.

[36] Андреев А. Е. Об одном методе получения нижних оценок сложности индивидуальных монотонных функций // ДАН СССР.

1985. Т. 281. № 2. С. 1033–1037.

[37] Васильев Ю. Л. О сравнении сложности тупиковых и минимальных дизъюнктивных нормальных форм // Проблемы кибернетики. Вып. 10. М.: Физматгиз, 1963. С. 5–61.

[38] Васильев Ю. Л. К вопросу о числе тупиковых и минимальных дизъюнктивных нормальных форм // Дискретный анализ.

Вып. 2. Новосибирск: ИМ СО АН СССР, 1964. С. 3–9.

[39] Викулин А. П. Оценка числа конъюнкций в сокращенной д. н. ф.

// Проблемы кибернетики. Вып. 19. М.: Наука, 1974. С. 151–166.



Pages:     | 1 |   ...   | 5 | 6 || 8 |
 


Похожие работы:

«Диссертация на соискание звания Мастер ТРИЗ Тема: Технология выбора инструментов инновационного проектирования на основе ТРИЗ - ФСА Научный руководитель Мастер ТРИЗ М.С.Рубин Санкт-Петербург 2010 Оглавление Page 1 ОГЛАВЛЕНИЕ ВВЕДЕНИЕ АКТУАЛЬНОСТЬ ТЕМЫ ИССЛЕДОВАНИЯ ЦЕЛЬ И ЗАДАЧИ РАБОТЫ Цель работы: Задачи работы: Научная новизна исследования Практическая значимость исследования Основные положения, выносимые на защиту Личный вклад соискателя Апробация работы 1. ОБОСНОВАНИЕ ПОСТАНОВКИ ЦЕЛИ И ЗАДАЧ...»

«338 Апушкин Я., Градов Г., Данцигер Ю. Октябрь в деревне. Сборник стихов, песен, пьес. М.- Л., государственное издательство, 1929. Формат издания: 17 х 13 см. 55 с. Экземпляр в издательской бумажной обложке. Хорошая сохранность. 2 500 –4 000 руб. 339 Вольтман В. Первая книга стихов. М., Издательство Всероссийского Союза Поэтов, 1929. Формат издания: 12,5х17 см. 119, [3] с., 1 л. портрет. Тираж 1000...»

«Мониторинг, моделирование и прогнозирование опасных природных явлений и чрезвычайных ситуаций Программа всероссийской научно-практической конференции 14 июня 2013 года г. Железногорск 2013 Мониторинг, моделирование и прогнозирование опасных природных явлений и чрезвычайных ситуаций: Программа Всероссийской научно-практической конференции. г. Железногорск, 14 июня 2013 года / Составители: Мельник А. А., Батуро А. Н., Калюжина Ж. С. – Железногорск, 2013. – 24 с. Программа проведения конференции...»

«Архангельский собор в Московском Кремле Москва Книга по Требованию Эта книга является репринтом оригинала, который мы создали специально для Вас, используя запатентованные технологии производства репринтных книг и печати по требованию. Сначала мы отсканировали каждую страницу оригинала этой редкой книги на профессиональном оборудовании. Затем с помощью специально разработанных программ мы произвели очистку изображения от пятен, клякс, перегибов и попытались отбелить и выровнять каждую страницу...»

«Самооценка: Как обрести уверенность и стать автором собственной жизни. www.etvita.ru 2011 Электронная книга Самооценка: как обрести уверенность и стать автором собственной жизни 2 Содержание: Вступление Глава 1. Как мы теряем веру в себя Глава 2. Что такое самооценка и зачем она? Глава 3. Неуверенность в себе - это проблема? Глава 4. Как справляются с неуверенностью обычные люди.15 - 19 Глава 5. Вы можете и должны жить счастливо! Глава 6. Готовое решение: как эффективно избавиться от проблемы...»

«ПРИКАЗ 28 декабря 201 1 г. N 2895 Москва Об утверждении Порядка приема граждан в образовательные учреждения высшего профессионального образования В соответствии со статьей 1 6 Закона Российской Федерации от 1 О июля 1992 г. 3266-1 Об образовании (Ведомости Съезда народных депутатов N Российской Федерации и Верховного Совета Российской Федерации, 1 992, 30, N ст. 1 797; Собрание законодательства Российской Федерации, 1996, 3, ст. 1 50; N 2000, N 30, ст. 3 120; 2002, N 26, ст. 25 1 7; 2004, N 1...»

«СОДЕРЖАНИЕ Глава 1 Движение – основное свойство денег Глава 2 Неидентифицированные пользователи Глава 3 Идентифицированные пользователи системы Глава 4 Почему все кинулись в Webmoney Глава 5 Как работать в платежных системах Интернета, приравненных к классическим Глава 6 Рекомендую альтернативу использования корпоративных кошельков и корпоративных средств Глава 7 О платежных системах, которые закону не подчиняются Глава 8 Ответы на 12 самых жгучих вопросов Заключение Платежные системы интернета...»

«Сергей Павлович Знай и умей. Самодельные коллекции по ботанике и зоологии ЧЕМУ УЧИТ ЭТА КНИГА? На прогулке, на экскурсиях, работая на школьном участке, на совхозных и колхозных огородах и полях, в саду и в лесу – интересно, да и полезно собирать для коллекций растения, насекомых и других животных, горные породы, минералы, почвы. Во время таких сборов, выбирая наилучшие образцы, невольно становишься более внимательным и познание природы делается более глубоким и основательным. Еще точнее и...»

«Комитет по ликвидации расовой дискриминации Доклады, представляемые государствамиучастниками в соответствии со статьей 9 Конвенции Тринадцатый и четырнадцатый периодические доклады, подлежавшие представлению в 2010 году Доминиканская Республика* ** * В настоящем документе содержатся тринадцатый и четырнадцатый периодические доклады Доминиканской Республики, подлежавшие представлению 24 июня 2010 года. Девятый–двенадцатый периодические доклады и краткие отчеты о заседаниях, на которых Комитет...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

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