Issn 2072-0297 Молодой учёный Международный научный журнал Выходит еженедельно №3 (137) / 2017 р е д а к ц и о н н а я к о л л е г и я : Главный редактор
жүктеу/скачать 9,13 Mb. Pdf көрінісі
|
moluch 137 ch1
| разбиение
характеризуется входами , 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 − + − + = = = = − − ∑ ∑ Здесь уже используется сводимость по перечислимости. множества образуют наименьшую 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 − + − + = = = = − − ∑ ∑ Здесь уже используется сводимость по перечислимости. множества образуют наименьшую 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 − + − + = = = = − − ∑ ∑ Здесь уже используется сводимость по перечислимости. |