Материал: 252_337

рг[і] := 1; k := і; rz[j] := k; for і := 1 to n do

if (І О k) and (рк[І, j]=1) then

for m := 1 to П do begin

pk[i, m] := pk[i, m] xor pk[k, m ] ; {елементи /-го ПК операцією XOR} S[i, m] := s[i, m] + s[k, m] {та його послідовності застосування ПК.}

rez[j] := rez[j] + s[rz[i], j ] ; {застосувати для отримання кінцевого результату.} for І := 1 to П do {Визначення тих ПК, які використовуються для перетворення} if odd(rez[i]) then write(f_Out, і, ' '); {заданої таблиці непарну кількість разів.}

Логічним є запитання: чи завжди можна звести задану таб­ лицю елементів пристроїв керування до вигляду, в якому у кожному рядку і стовпці є лише по одному елементу зі зна­ ченням 1, а решта елементів мають значення 0, чи завжди сформульована задача має розв'язок? Ні, не завжди. Однознач­ ної відповіді на ці запитання дати не можна.

Розглянемо кілька окремих ситуацій. Якщо систему, яка описує пристрої керування, не можна звести до необхідного спрощеного вигляду, то це означає, що, можливо, відсутня та­ ка послідовність пристроїв керування, яка переводить заданий пристрій із початкового стану у кінцевий. Серед пристроїв ке­ рування після перетворення значень їх елементів можуть бути такі, що мають лише нульові елементи, або ж кілька елементів зі значеннями 1. Однак це може повністю задовольняти умову задачі:

-«нульові» пристрої керування взагалі не впливають на по­ шук розв'язку задачі, їх можна опустити;

-серед пристроїв керування, що мають більше одного еле­ мента зі значенням 1, можуть знайтися такі, у яких ці елемен­ ти розміщені саме у тих позиціях, які необхідно перетворити для отримання кінцевого результату.

327

Для прикладу дещо змінимо умову попередньо розглянутої задачі.

Нехай початковий і кінцевий стани заданого пристрою залишаються без змін (01101 пристрої керування > 0 Q 1 1 0 ) j & от значення останнього елемента 4-го пристрою керування змінимо з 1 на 0 (мал. 181, а). Опускаючи всі етапи перетворен­ ня вхідних даних за описаним алгоритмом, розглянемо отри­ маний результат (мал. 181, б). Спочатку проаналізуємо, чи вплинули зміни у вхідних даних на очікуваний результат вико­ нання алгоритму. Мабуть, ні, оскільки зміни зроблені для того пристрою керування, який не задіяний для перетворення по­ чаткового стану пристрою керування у його кінцевий стан.

А тепер проаналізуємо інформацію, зображену на малюн­ ку 181, б. Як бачимо, значення елементів 4-го пристрою ке­ рування перетворилися на 0, а це означає, що він взагалі зай­ вий. А от у 2-го пристрою керування два елементи мають зна­ чення 1: четвертий і п'ятий. Але самі ці елементи повинні змінити значення у заданому пристрої. Не вистачає лише пристрою керування, який би змінив значення другого еле­ мента заданого пристрою. Але це може зробити 1-й пристрій керування!

Отже, відповідь знайдена: звернемося до 1-го і 2-го при­ строїв керування у перетвореній таблиці. Для зведення цих пристроїв керування до перетвореного вигляду були задіяні такі ПК (табл. послідовності застосування ПК, мал. 181, б): 1-й - два рази, 2-й - один раз, 3-й - один раз, 4-й - жодного ра­ зу, 5-й - один раз. Виберемо ті ПК, які застосовувалися непар­ ну кількість разів, і отримаємо шукану відповідь: для зміни по­ чаткового стану заданого пристрою на кінцевий необхідно задіяти 2, 3 та 5 пристрої керування. Ця відповідь збіглася з по­ передньою і саме такою передбачалася.

Описана задача є дещо формалізованою. На практиці зустрічаються задачі, які можна звести до застосування описа-

328

ного методу, що дає значний виграш у часі виконання. Альтер­ нативою розв'язання таких задач найчастіше є метод повного перебору з можливим застосуванням евристик, однак це приз­ водить до значного програшу в часі.

Оцінка ефективності виконання алгоритму залежить від кількості п елементів заданого пристрою. Оскільки на кожно­ му кроці виконання алгоритму для подальшого перетворення визначається один із ПК, а таких кроків є п, то й ефективність цього алгоритму є квадратичною 0(га2). Якщо для розв'язуван­ ня даної задачі піти шляхом повного перебору всіх можливих варіантів, перевіривши спочатку окремо всі ПК по одному, потім усі можливі комбінації по два ПК, далі по три ПК і т. д., то такий підхід, як і всі комбінаторні методи, має факторіаль­ ну оцінку ефективності їх роботи 0(п\). Отже, запропонований алгоритм має значні переваги щодо ефективності виконання.

При тестуванні алгоритму, що використовує метод виклю­ чення, необхідно передбачити ситуації, коли у перетвореній таблиці елементів пристроїв керування значення 1 знаходять­ ся на головній діагоналі, а решта елементів мають значення 0; коли немає можливості отримати таку перетворену таблицю елементів пристрою керування, однак розв'язок задачі існує; коли розв'язок задачі не існує. Всі ці варіанти можливих вхідних даних слід перевірити для різної кількості елементів пристрою керування: п < 10, п ^ 50, п < 100.

Завдання

1.Розробити і реалізувати у вигляді програми метод виклю­ чення для задачі з пристроями керування.

2.Виконати завдання 1 для пристроїв з кількістю елементів N < 10 за умови, що таблиця елементів пристроїв керування зводиться до вигляду, коли по головній діагоналі знаходять­ ся елементи зі значеннями 1, а решта елементів мають зна­ чення 0. Результат виконання програми вивести у файл.

3.Виконати завдання 1 для пристроїв з кількістю елементів N < 10 за умови, що таблиця елементів пристроїв керування не зводиться до вигляду, коли по головній діагоналі знахо­ дяться елементи зі значеннями 1, а решта елементів мають значення 0, однак розв'язок задачі існує. Результат вико­ нання програми вивести у файл.

4.Виконати завдання 1 для пристроїв з кількістю елементів N ^ 10 за умови, що задача не має розв'язку. Результат ви­ конання програми вивести у файл.

5.Виконати завдання 2-4 для пристроїв з кількістю елементів ЛГ<100.

329

Запитання для самоконтролю

1.У чому полягає суть методу виключення для системи п лінійних рівнянь з п невідомими?

2.Для якого типу задач можна застосувати метод виключення? Сформулюйте загальний вигляд цієї задачі.

3.У чому полягають основні ідеї застосування методу виключення для алгоритмічних задач?

4.У чому полягає оптимізація застосування методу виключення для алгоритмічних задач?

5.Продемонструйте покрокове виконання методу виключення для власного прикладу.

6.Наведіть фрагмент основної програми, що реалізує метод ви­ ключення для задачі з пристроями.

7.Які можливі варіанти отримання розв'язку задачі з використанням методу виключення? Проаналізуйте й обґрунтуйте свою відповідь.

8.Чи можлива відсутність розв'язку задачі при використанні мето­

330