Спосіб обробки та захисту інформації в розподілених сховищах даних

Реферат: Спосіб обробки та захисту інформації в розподілених сховищах даних, який вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком. Введено правило відсікання неперспективних варіантів рішень по вибору максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком та сортування даних по зростанню значень коефіцієнтів в обмеженні. UA 92968 U (12) UA 92968 U UA 92968 U 5 Запропонована корисна модель належить до галузі кібернетики і обчислювальної техніки та може бути використана при вирішенні задач комбінаторної оптимізації на графах. Відомий «Спосіб послідовного призначення одиниць для наближеного рішення задачі про одномірний ранець» [1], який вирішує задачу цілочисельного лінійного програмування з булевими змінними:  ѓ x   n  c j x j  max (1) j 1 , при виконанні умов: n  aij x j  b1 j 1 (2) , x j  0,1 a1j  0   , , i  1, j  1 n , (3) , cj  0 10 (4) . В даному способі як початковий розглядається нульовий вектор, в якому змінним присвоюються одиничні значення за умови, що при побудові допустимого цілочисельного 0 рішення z призначаються одиничні значення у відповідності з послідовністю  j1   j 2  ... jn , починаючи з найбільшого значення. Якщо для деякого  jk таке призначення виконати 0 неможливо, тоді z j  0 і переходять до номеру jk 1 . Процес завершується після перегляду усіх k 15 20 змінних або при порушенні умови (2). Призначення одиничних значень виконується у відповідності з послідовністю c j1  c j 2  ...c jn . Недоліком відомого способу є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними складає 20 %. Найбільш близьким до запропонованого технічного рішення, вибраним як прототип, є «Способ решения задачи целочисленного линейного программирования с булевыми переменными на основе рангового похода» [2], який вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу, та полягає у тому, що з   r 1 вершини s графа ΔD будується множина шляхів msj , j  1 n першого рангу r, що задовольняє , 25  r    r 1 властивості, і в множинах msj визначаються шляхи максимальної довжини  sj  за вагою     функціонала c j . Для кожної вершини j визначається вага  j за правилом:  j  c j 1  c j  2  ...  c n   , n  0 ; j  1 n  1 . ,   (5)     r r r Виключаються шляхи sp , p  r, n у множині msj поточного рангу r, довжини якої dc sp задовольняють нерівності:     r    dc r   p  max dc   sp  sp       cj ,  (6) де  p  c p 1  c p  2  ...  c n та для вершини j  n вага  j - дорівнює нулю;   dc r - довжина шляху від вершини s до вершини р рангу r по вагах функціоналу. sp 30   r r 1 Формується множина шляхів msp , p  1, n наступного рангу, що задовольняє властивості r (5), на базі множини шляхів msj попереднього рангу на основі рекурентного співвідношення: 1 UA 92968 U    r  r 1  max  r   j, p  sp sj c j  p  r  1, n (7) j  r, n j  p , r де  sj  j, p - шлях з вершини s графа ΔD у вершину р, що проходить через проміжну вершину j і який одержується за рахунок приєднання до шляху r ребра sj з'єднання не суперечить правилу відсікання неперспективних варіантів рішень. 5 10 15 20 25 30 35 j, p  , якщо таке r  r 1   r  r 1 У визначених множинах m sp виділяються щонайдовші шляхи   sp  .     Якщо визначиться декілька шляхів максимальної довжини, то серед них вибирається шлях з меншим значенням довжини за вагою обмежень a1j . Перевіряється, чи вся множина шляхів наступного (r+1)-го рангу порожня. Якщо умова виконується, то в множинах виділяється шлях максимальної довжини і алгоритм закінчує роботу. Якщо умова не виконується, то перевіряється r = (n-1). У разі виконання рівності в множині виділяється шлях максимальної довжини і алгоритм закінчує роботу, інакше збільшується r на 1 і виконується обчислення у відповідності до формул (5-7). Недоліком способу-прототипу є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу складає 12 %. В основу корисної моделі поставлена задача створити «Спосіб обробки та захисту інформації в розподілених сховищах даних», який дозволить зменшити відносну похибку алгоритму до 6 %. Поставлена задача вирішується за рахунок того, що у спосіб-прототип додатково введено правило відсікання неперспективних варіантів рішень на основі вибору максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком та сортування даних по зростанню значень коефіцієнтів в обмеженні. Технічний результат, який може бути отриманий при здійсненні корисної моделі полягає у зменшенні відносної похибки алгоритму рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком до 6 %. На фіг. 1 представлено граф ΔD. На фіг. 2 наведено приклад рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком. Запропонований «Спосіб обробки та захисту інформації в розподілених сховищах даних» ґрунтується на правилі відсікання неперспективних варіантів рішень по вибору максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком та сортування даних по зростанню значень коефіцієнтів в обмеженні. Суть способу полягає у наступному. Виконується сортування даних по зростанню значень коефіцієнтів в обмеженні: 1   2  3  ...  n . (8)   r 1 З вершини s графа ΔD будується множина шляхів msj , j  1 n першого рангу r, що ,    r  r 1 задовольняє властивості, і в множинах msj визначаються шляхи максимальної довжини  sj      c j . Для кожної вершини j визначається вага  j за правилом (5). за вагою функціонала   40     r r r Виключаються шляхи sp , p  r, n у множині msj поточного рангу r, довжини якої dc sp задовольняють нерівності (6).   r r 1 Формується множина шляхів msp , p  1, n наступного рангу, що задовольняє властивості mr sj 45 (5), на базі множини шляхів попереднього рангу на основі правила відсікання неперспективних варіантів рішень по вибору максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком: 2 UA 92968 U     r  r 1  max r   j, p  ; sj cj  sp  L3 :  r  r 1  min r  j, p  .  sp sj j  p  r  1, n  (9) j  r, n j  p . r  r 1   У визначених множинах mr r 1 виділяються щонайдовші шляхи   sp  . sp     Якщо визначиться декілька шляхів максимальної довжини, то серед них вибирається шлях з найбільшим значенням довжини за вагою функціонала c 1j , та шлях з меншим значенням 5 10 15 довжини за вагою обмежень a1j . Перевіряється, чи вся множина шляхів наступного (r+1)-го рангу порожня. Якщо умова виконується, то в множинах виділяється шлях максимальної довжини за вагою функціонала і алгоритм закінчує роботу. Якщо умова не виконується, то перевіряється r = (n-1). У разі виконання рівності в множині виділяється шлях максимальної довжини за вагою функціонала і алгоритм закінчує роботу, інакше збільшується r на 1 і виконується обчислення у відповідності до формул (5-8). Джерела інформації 1. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. - Изд. 2-е, испр. - М: ФИЗМАТЛИТ, 2003. - 240 с. 2. Третьяк В.Ф., Голубничий Д.Ю., Огурцов В.В. Метод решения задачи целочисленного линейного программирования с булевыми переменными на основе рангового похода // Системи обробки інформації. Збірник наукових праць, 2009. - випуск 4 (78). - С. 152-155. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 20 25 Спосіб обробки та захисту інформації в розподілених сховищах даних, який вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком, який відрізняється тим, що введено правило відсікання неперспективних варіантів рішень по вибору максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком та сортування даних по зростанню значень коефіцієнтів в обмеженні. 3 UA 92968 U 4 UA 92968 U Комп’ютерна верстка С. Чулій Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5