Issn 2072-0297 Молодой учёный Международный научный журнал Выходит еженедельно №3 (137) / 2017 р е д а к ц и о н н а я к о л л е г и я : Главный редактор
жүктеу/скачать 9,13 Mb. Pdf көрінісі
|
moluch 137 ch1
| .
#3 (137) . January 2017 3 Mathematics множества образуют наименьшую e-степень, вопрос о полных множествах не стоит, зато с элементарными теориями удалось разобраться — они все попарно различаются [6–10]. Как уже отмечено, если e A B ≤ и имеется способ перечислять B, то по нему можно получить и эффективное перечисление А. Это позволяет, например, по множеству свойств В моделирующей системы перечислять свойства из А моделируемой системы, если для множеств этих свойств установлено е-сведение. Но если на самом деле a A ∉ , то перечисляя А, мы просто не получим элемент a , и вообще ни в какой момент времени нет оснований полагать, что a A ∉ . Этим отличаются сводимости по перечислимости. Приведем пример. Рассмотрим модель рюкзак . У нее входом X является пятерка , , , , R s v B K . Здесь R — некоторое конечное множество, , s v — функции, отображающие R в положительные целые числа Z + , выход { } 0,1 Y = . Система функционирует посредством функции ( ) ( ) ( ) ' 1, ' & & , , , , 0, x R x R K если R R R s x B v x K f R s v B K иначе ∈ ∈ ′ ∃ ⊆ ≤ ≥ = ′ ∑ ∑ Система разбиение характеризуется входами , X D d = , где D — конечное множество, функция : d D Z + → , выход { } 0,1 Y = . Система функционирует посредством функции ( ) ( ) ( ) ' 1, ' & , 0, x D x D d если R D D d x d x f D d иначе ∉ ′ ∈ ∃ ⊆ = = ′ ∑ ∑ Основаниями для моделирования является алгоритмически построенное сведение множество истинных предложений одной системы к другой. В основном изучают входы и выходы одной системы, соответствующие входам и выходам другой. Рассмотрим процесс моделирования системы разбиение системой рюкзак . Определим ( ) , , / 2 x R R D v s d B K M s x ∈ = = = = = = ∑ . Тогда можно заметить, что , ,1 , , , , ,1 d R D d f D d d M M f ∈ ⇔ ∈ Ясно, что данное соотношение выражает m-сводимость системы разбиение к системе рюкзак . [12] Построим обратное свед е ние, т. е. промоделируем систему рюкзак системой разбиение . Введем еще одну функцию ( ) ( ) 1, ' & , , 0, x R M если R R R s x K f R s K иначе ′ ∈ ∃ ⊆ = = ′ ∑ Тогда ( ) ( ) ( ) ( ) , , , , 1 ' ' & & & , , 1& , , ' 1 K M M x R f R s v B K B K B B K K K s x f R s B f R v K ∈ = ⇔ ∃ ≤ ≥ ≤ ′ = = ′ ′ ′ ∑ Далее, ( ) ( ) , , 1 , 1 M d f R s C f D d = ⇔ = , где { } 1 2 1 2 , , , , , n n n D d d d d d + + = … , { } 1 2 , , , n R d d d = … , ( ) ( ) ( ) 1 i i i i n d d s d ∀ ≤ ≤ → = , ( ) ( ) ( ) 1 2 1, 1 . n n x R d d C d d s x C + + ∈ = + = + − ∑ Таким образом, система рюкзак d -сводится к системе разбиение и в целом эти две системы таблично или даже более точно, дизъюнктивно эквивалентны. Рассмотрим пример из области принятия решений о законах распределения. Пусть f — закон распределения вещественной случайной величины, {1} X = , Y — семейство всех конечных наборов ( ) 1 ,..., n y y вещественных чисел, 0 1 < α < — заданный уровень вероятности, и ( ) 1 1, ,..., n f y y F ∈ тогда и только тогда, когда ( ) 1 ,..., n y y — с вероятностью, большей α является набором значений случайной величины, распределенной по закону f. Пусть ( , ) g m σ -нормальный закон распределения случайной величины с математическим ожиданием m и среднеквадратическим отклонением σ , ( ) h n - распределение Стьюдента с 1 n − степенями свободы. Тогда ( ) 1 n 1 ( , ) ( ) 1 x x 1, ,..., 1, ,..., n g m h n n m m y y F n n F s s σ − − ∈ ⇒ ∈ , где ( ) ( ) ( ) 2 2 1 1 1 1 1 1 , 1 n n i i j i n j i n j i i x y s y x n n − + − + = = = = − − ∑ ∑ Здесь уже используется сводимость по перечислимости. Таким образом, хотя понятия теории алгоритмов кажутся далекими от теории систем, они могут эффективно приме- няться при моделировании систем, в частности, при уточнении сложности систем, одной относительно другой, что по- зволит успешно ранжировать системы от простых к сложным или доказывать их эквивалентность. Литература: 1. Дёгтев А. Н.. Рекурсивно перечислимые множества и сводимости табличного типа. — М.: Наука. Физматлит, 1998. —176с. 2. Дёгтев А. Н.. Избранные результаты по теории алгоритмов. Монография. Часть I. — Тюмень. Издательство ТюмГУ. 2008. 184с. 3. Соар.Р. И. Вычислимо перечислимые множества и степени: Пер. с англ. — Казань: Казанское математическое общество, 2000. — 576с. 4. Булитко В. К. Сводимости линейными по Жегалкину таблицами // Сиб.мат. журнал. 1980, Т. 21, № 3. С. 23–31. 5. Захаров С. Д. Об алгебре операторов перечисления // Вестник МГУ, сер. мат., мех., 1982, No 5, C. 79–83. 6. Захаров с. Д. О е- и s-степенях // Алгебра и логика, 1984. Т. 23, No 4. С. 395–406. 7. Захаров с. Д. О степенях сводимостей по перечислимости // Алгебра и логика. 1986. Т. 25, № 2. С. 121–135. 8. Захаров С. Д. Степени сводимостей по перечислимости (автореф. канд. дисс.)// Новосибирск, НГУ, 1986. — 14с. 9. Захаров С. Д. Степени сводимостей по перечислимости (диссертация) // Новосибирск, НГУ, 1986. — 75с. 10. Захаров С. Д. Об s-степенях внутри произвольной e-степени // Депон. В ВИНИТИ 20.01.90 № 740-С. — 18с. 11. Селиванов В. Л. Об одном классе сводимостей в теории рекурсивных функций // Вероятностные методы и ки- бернетика. Казань: Изд-во КГУ. 1982. Т. 18 С. 83–100. 12. Карп Р. М.. Сводимость комбинаторных задач. — Киб.сб. Н.С., 1975, вып. 12, С. 16–38. 13. Казиев В. М. Введение в анализ, синтез и моделирование систем. Серия основы информационных технологий. Изд-во Интернет-Университет Информационных технологий, 2006. |