Спосіб динамічного кодування та захисту інформаційного ресурсу в інфокомунікаційних системах

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