Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Слабо импликативно и комбинаторно селекторные множества Иванов Дмитрий Иванович

Слабо импликативно и комбинаторно селекторные множества
<
Слабо импликативно и комбинаторно селекторные множества Слабо импликативно и комбинаторно селекторные множества Слабо импликативно и комбинаторно селекторные множества Слабо импликативно и комбинаторно селекторные множества Слабо импликативно и комбинаторно селекторные множества
>

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Иванов Дмитрий Иванович. Слабо импликативно и комбинаторно селекторные множества : диссертация ... кандидата физико-математических наук : 01.01.06 / Иванов Дмитрий Иванович; [Место защиты: Ин-т математики и механики УрО РАН].- Тюмень, 2007.- 73 с.: ил. РГБ ОД, 61 07-1/1578

Введение к работе

Актуальность темы

Диссертация посвящена одному из новых подходов к классификации подмножеств /V = {0>1*2»„.} множества всех целых неотрицательных чисел, который использует булевы функции и эффективную вычислимость. Первым, кто заинтересовался этим направлением, был Э- Пост [16]. Среди рекурсивно перечислимых множеств он определил классы рекурсивных, простых, креативных и мезоичных [11] множеств. Позже [10]» [12] класс мезоичных множеств был разбит на семейства псевдопростых и псевдокреативных множеств. Однако, как пишет в своей монографии X. Роджерс [8], это полезный каталог изученных к настоящему времени типов множеств, но с теоретической точки зрения» несколько произвольный". Другой подход к изучению произвольных подмножеств множества N заключается в их классификации по "сложности". Инструментом для такой классификации служит понятие сводимости, являющееся одним из центральных в теории алгоритмов. На интуитивном уровне множество А сводимо к множеству В, если существует алгоритм, который решал бы проблему вхождения элементов для множества А при условии^ что есть возможность по мере надобности пользоваться информацией о принадлежности тех или иных чисел из N множеству В. Наиболее пристальное внимание было уделено т -, табличной {ft -) и тьюринговой (Г -) сводимостям, введённых также Э. Постом. Среди рекурсивно персчислимых множеств от —полные (креативные [15]) являются наиболее "сложными", а рекурсивные, для которых существует эффективная процедура распознавания принадлежности к ним любого числа из ТУ, наиболее "простыми". Вопрос о существовании относительно Г -сводимости множеств, промежуточных по сложности, получили название проблемы Поста. Она была положительно решена независимо Р. Фрндбергом [13] и А. А, Мучником [7]* Что касается сводимостей, промежуточных между

т- и «-сводимостями, то основными оказались ещё пяты btti -оіраничснная tt -сводимость с нормой 1, с -конъюнктивная, d -дизъюнктивная, р-позитивная и /-линейная [I]* [9]. Важные

результаты о соотношениях между этими сводимостямн были получены А, а Дегтевым [2], [3], [4].

В работе [14] К. Джокуш ввбл понятое полурекурсивного множества, именно, подмножество А множества N называется полурекурсивным, если существует двуместная общерекурсивная функция (ОРФ) / такая, что

(v*X4rft/fc yh k j*} a W*)v xiy))=і ** f{x, yh л),

где #-хараісгеристическая функция множества Л, По аналогии А. Н. Деїтев определил понятие 0-комбинаторных [5] множеств, а именно, множество А называется //-комбинаторным, где р- произвольная «-местная булева функция, при условии /?(*,,.,, д;) = х, если существует «-местная общерекурсивная функция f % такая что

Оказалось, что число различных классов /?-комбинаторных множеств равно семи.

Если потребовать, чтобы ОРФ f была селекторной, т. е.

(Vx|,...,*w)(/(x| х„)є{*і хп})>

то придём к определению понятия р-селекторного [5] {р-комбинаторно-селекторного {р-КС)) множества. Выяснилось, что число различных классов /7-селеіггорііьіх множеств всего три: класс всех рекурсивных, класс всех

полурекурсивных и класс F* '— всех подмножеств /V,

Далее, если в определении /?-ком6инаторно*селекторного множества эквивалентность заменить на импликацию, то получим определение Д-имтикативно-селекторного (р-ИС) множества [6], множество А

называется /?-импликативио-селеісторньім, если существует л-местная селекторная ОРФ f такая, что

(Ухь...,ЖяХ^('І>...^(^))я=1^/(^".»'И)б4

Пусть F^m\ m > 1, семейство всех fim+\ -ИС множеств где

Aif+Ie & (xivxjh

Центральным результатом статьи [6] является следующая теорема: если /?-БФ такая, что /?(х,.„,х) = ха то семейство /7-ИС множеств совпадает с

одним из г ^ % m 2:1 или гч , причем имеют место строгие включения

Обобщением данных понятий послужили работы [17J и [18], rjig в определении в качестве f используется селекторная частично-рекурсивная функция (ЧРФ), т. е. такая, что

где f(x\»„.txff)п) определено.

Именно, множество j4 с # называется слабо Р-хшгыикативно-селекторным (слабо fl-ИС)* где fi - w-местная буяева функция, если существует ^-местная частично-рекурсивная функция f такая, что:

Далее, множество А называется слабо fl-комбинаторно-селекторным множеством (слабо fi-КС)* если существует «-местная ЧРФ / такая, что

^Xv*l хлХ/^х11..-^хя)) = 1«*Дх1 хп)єА\

При этом в обоих определениях функцию / называют соответствующей множеству А.

Обозначим через K(fi) (/?(/?)) класс слабо /?-ИС (соответственно

/?-КС) множеств, считая размерностью K{fi) {R{fi)) число существенных

переменных булевой функции /?. Назовем функцию fi допустимой, если

р ?ь О, I и /?(0,„м0) = 0. Кроме того, будем рассматривать БФ ft с точносгью

до перестановки переменных- Рассмотрению именно этих классов множеств и посвящена настоящая диссертация.

Цель работы

При написании диссертационной работы были поставлены следующие цели: во-первых, описать классы К{0) и R{fi) для произвольных БФ /?; во-вторых, выяснить соотношения между этими классами по включению.

Основные методы исследования

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

Научная новизна

Все основные результаты диссертации, выносимые на защиту, являются новыми. Они состоят в следующем:

полностью описаны все классы слабо -ИС множеств, размерность которых не превосходит трёх, как и монотонных слабо /У-ИС множеств размерности не выше четырёх, и выяснены соотношения межлу ними по включению (теоремы 1.1 J и 1.1.2)- В частности, классов монотонных слабо /?-ИС множеств оказалось бесконечно много (теорема ІЛ.З);

— полностью описаны все классы слабо /?-ИС множеств для линейных и самодвойственных (размерности не выше четырех) ЬФ и выяснены соотношения между ними по включению (теоремы 1.4,1 и 1,4*2);

полностью описаны все классы размерности 3 слабо fi-KC множеств как для монотонных, так и для немонотонных БФ р и выяснены соотношения между ними по включению- Этот результат также обобщен для случая БФ произвольной размерности (теоремы 2,2Л и 2,2.2).

Теоретическая н практическая ценность

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

Апробация результатов

Изложенные в диссертации результаты были представлены на международной конференции, посвященной 200-летию Казанского государственного университета (Казань, 2-9 июня 2004 года), а также на межрегиональных конференциях "Современные математические методы и информационные технологии в образовании" (Тюмень, 14-16 апреля 2005 года, 18 апреля 2007 года). Кроме того, полученные результаты регулярно докладывались на заседаниях кафедры алгебры и математической логики Тюменского государственного университета. По результатам работы автор выступал с докладом в Уральском государственном университете на семинаре "Алгебраические системы" (Екатеринбург, 8 февраля 2007 год).

Публикации

Основные результаты диссергации опубликованы в семи работах, список которых приведён в конце автореферата [17-23], Результаты первых трех из них получены в соавторстве с научным руководителем А. Н. Дйгтевым,

Стругоура диссертации

Текст диссертации состоит из оглавления, введения, двух глав, объединяющих 6 параграфов, заключения и списка литературы. Библиография включает 38 наименований. Общий объСм диссертации составляет 73 страницы.

Похожие диссертации на Слабо импликативно и комбинаторно селекторные множества