Теорія алгоритмів

Размещено на http://www.allbest.ru/

КОНТРОЛЬНА РОБОТА № 1

1. Вказати ознаки алгоритму у вербальному представленні роботи елементарної системи керування

В 20-х роках ХХ-го століття проблема означення алгоритму стала однією з основних, фундаментальних математичних проблем. Її вирішення було одержано у двох формах всередині 30-х років 20-го століття у роботах таких відомих математиків як Гільберт, Гедель, Черч, Кліні, Пост, Т'юрінґ на базі означень понять класів:

арифметичних функцій (які назвали рекурсивними);

процесу.

Пізніше в роботах Маркова і Калужніна з'явилося інше трактування алгоритму -- як особливої відповідності між словами в абстрактному алфавіті (з означенням понять алфавіт, слово, відповідність).

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

Означення 2. Скінченна сукупність операцій, якій притаманні властивості

дискретності -- виконання чергової операції починається у певний момент часу, моменти часу не обов'язково еквідистантні;

детермінованості -- перед виконанням першої операції відомі початкові дані, у будь-який момент часу точно відомі наступні операції (прогнозованість) та результат попередньої операції;

впорядкованості -- встановлена черговість операції (інакше -- відношення порядку на їх множині);

масовості -- алгоритм розв'язує задачу, що належить до класу задач;

елементарності -- завжди можна вказати елементарну (виконувану апаратно, не програмовану) операцію -- називатимемо алгоритмом.

Таким чином, алгоритм виникає при вирішенні проблеми (інформування, управління). Для цього будується математична модель проблеми і на її базі ставиться задача(і) та будуються методи її розв'язування. Вважатимемо, що алгоритм задано, математичні проблеми його існування, коректності постановки задачі, яку за його допомогою розв'язують, вирішено. А під ТА розумітимемо систему фактів про властивості відповідних математичних об'єктів, якими подають алгоритм, у тому числі про взаємозв'язки між ними (їх алгебру, структури; для детальнішого знайомства з цими поняттями потрібно звернутися до відповідних посібників та підручників, зокрема, конспекту лекцій з курсу дискретної математики, основ алгебри тощо). Особливо про такі взаємозв'язки, які підпадають означенню представлення. При цьому не забуватимемо про математичну коректність, зокрема, вербального, графічного, аналітичного та інших способів подання (визначення) алгоритму.

Для розуміння властивостей вербального подання потрібно ознайомитися з основами лінгвістики.

Математична модель. Задача знаходження найбільшого спільного дільника постала при вирішенні проблеми вимірювань -- знаходження масштабу міри. Відомо, що вимірювання є певною процедурою, алгоритмом над вимірюваною величиною та мірою. При порівнянні об'єктів за значеннями їм властивої величини потрібно спочатку вирішити проблему вибору міри та знайти її значення. Для числових величин цю проблему вирішено постановкою та розв'язуванням задачі найбільшого спільного дільника.

Розглянемо цілі числа (натуральний ряд чисел). Всяке ціле, що ділить без остачі a, b,…,l, називається їх спільним дільником. З теорії подільності відома теорема про ділення з остачею:

Теорема 1. Всяке ціле а представляється єдиним чином за допомогою цілого b рівністю

Якщо взяти числа b та r₀, то отримаємо представлення . Далі, розглядаючи послідовно подібним чином числа , легко встановити, що коли r_n+1=0, то r_n буде найбільшим спільним дільником чисел a, b.

Ресурси та система команд процесора. Потрібні ресурси процесора та система команд визначаються моделлю задачі та методом її розв'язання. Це диктує розроблення спеціалізованого процесора, "під задачу". Проте часто вибирається процесор "близький" до потрібного --"під клас задач" у найкращому випадку.

Лінгвістичні засоби подання алгоритму. Розглянемо лінгвістичні засоби на прикладі української мови (алфавіту, скінченної множини спеціально вибраних слів та граматики). Назвемо тому його вербальним (на словах) поданням. Отже, для вербального подання алгоритму використовують звичайну мову, її граматику -- алфавіт, лексику, синтаксис тощо. При цьому використовується й семантика мови, виконуючи функцію коментаріїв. Але поліморфізм мови порушує однозначність слів -- інформативних денотатів понять, якими означують операції та ін. складники алгоритму. Це знижує ефективність використання мови, зокрема, семантики при поданні алгоритму. Тотожні перетвори (алгебра) алгоритму забезпечуються граматикою мови, вибраної для його вербального подання, при врахуванні властивостей моделі задачі, методу її розв'язування, процесора тощо.

Засобами мови (вербальні) подаються усі операції та оператори (арифметичні, логічні) алгоритму.

Алгоритм (Евкліда). Користуючись обмеженою кількістю (множиною) слів (понять), які повно і несуперечливо означують поняття моделі задачі, систему команд процесора та означенням алгоритму будується алгоритм Евкліда.

2. Вказати ознаки алгоритму у граф-схемі знаходження найбільшої спільної міри двох відрізків з довжинами рівними деяким цілим числам

Означення Алгоритми, у відповідності з якими шукаються значення функції називатимемо числовими.

Числові алгоритми будуються за методами розв'язування задач математичної фізики (крайових задач -- математичних моделей явищ). Ці задачі поставляють у вигляді рівнянь у частинних похідних (рівняння хвиль, дифузії, потоків тощо у різних середовищах, різної природи) при відповідних початкових та граничних умовах.

При послідовному обчисленні формули згортки отримаємо значення функції (яка відповідає заданому диференціальному рівнянню). При цьому виникає потреба встановлення відношення порядку на множині номерів тактів обчислень.

Для простого диференціального рівняння числовий алгоритм будують також за рекурсивною формулою

де k відповідає nT_d. Граф-схема алгоритму наведена на рис. 6.

Рис. 6. Граф рекурсивного алгоритму (вузол 3 відповідає y_k-1, а вузол 4 -- y_k-2)

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

001	К=0; Y1=0; Y2=0; В1=1,8; В2=0.9;	% Налаштування процесора. K -- % номер кроку обчислення, Y1, Y2 -- % чарунки пам'яті, нулеві початкові % умови; В1, В2 -- коефіцієнти % різницевого рівняння
002	ХK=xK;	% Введення значення відліку вхідного % збурення (сигналу) з АЦП
003	YK=XK+Y1B1+Y2B2;	% Обчислення відліку шуканої % функції
004	Y2=Y1;	% Затримка на один такт обчислень
005	Y1=YK;
006	yk=YK;	% Вивід відліку шуканої функції на % ЦАП
007	K=K+1	% Лічильник номеру кроку обчислень
008	GO TO 2	% Безумовний перехід на 2-й крок % алгоритму

3. Вказати ознаки алгоритму у блок-схемі рекурсивного розвязку диференціального рівняння з постійними коефіцієнтами

На практиці алгоритми подають за стандартом -- у вигляді блок-схеми, рис. 1:

Стандартна блок-схема алгоритму в умовних позначеннях, виконана за певними правилами відображає порядок обчислень та їх зміст, логічні операції, операції вводу-виводу тощо. За умови збереження порядку обчислень, при фіксованих моделі задачі, методі її розв'язування та процесорі (системі команд) виконувати тотожні перетворення такої блок-схеми неможливо. Знімаючи ці обмеження, наприклад, при надмірних множинах команд процесора, моделей задачі на базі їх алгебра можлива побудова алгебри блок схем алгоритмів. Це уможливлює їх тотожні перетвори.



Рис.1. Блочна впорядкована схема алгоритму

З теорії цифрових кіл відомі функціональні блок-схеми. У їх позначеннях подаються алгоритми обчислень (рис. 2):

Рис. 2. Блочна функціональна схема алгоритму

-  -- вміст регістрів на і-му кроці обчислень;

- позначення всередині блоків:  -- суматор,

-  -- помножувач,

-  -- обмін даними між регістрами на і-му кроці обчислень ("затримка" даних на час обчислень);

- стрілками показано функціональні "входи")

На функціональній блок-схемі алгоритму впорядкування обчислень позначують нумерацією її вузлів, яку виконують спеціально, використовуючи теорему про вигляд матриці впорядкованого цифрового кола. Логічних операцій ("галуження" обчислень) така блок-схема не відображає. Тому рис. 2 відображає лише частину алгоритму з рис. 1. На функціональній блок схемі (цифровому колі) існує алгебра лінійних тотожних перетворень. Крім того, існує ізоморфне його відображення та його алгебра, що надає великі можливості для розробки алгоритмів.

4. Побудувати граф-схему алгоритму елементарної системи керування.

Рис. 3. Подання алгоритму у вигляді графу (цифрового кола).

5. Побудувати блок-схему рекурсивного алгоритму розвязування диференціального рівняння з постійними коефіцієнтами.



6. Побудувати вербальний алгоритм знаходження найбільшої спільної міри двох відрізків з довжинами рівними деяким цілим числам.

До 1950 р. алгорисмус став алгорифмом. Смисл алгорифму найчастіше пов'язувався з алгорифмами Евкліда -- процесами знаходження найменшої спільної міри (двох відрізків, найменшого спільного дільника двох многочленів тощо).

Аж до 30-х років ХХ століття поняття алгоритму мало методологічне значення. Його означували евристично.

Означення 1. Скінченна сукупність коректно сформульованих правил розв'язування задачі з класу (множини) задач називається алгоритмом.

Таке означення алгоритму не є строгим, математичним, оскільки у ньому не означено понять клас задач, правило (їх розв'язування). Протягом тривалого часу математики задовольнялися цим означенням, теорії алгоритмів не існувало. Не було серйозних випадків, коли математики розійшлися б в тлумаченнях стосовно того, чи є алгоритмом певний конкретно заданий процес.

Становище суттєво змінилося, коли технічні засоби математичних обчислень стали настільки потужними та зручними у практичному користуванні, що розв'язок задачі в аналітичному вигляді (у вигляді формули) виявився не потрібним. Уможливилося розв'язування задач, з невідомим розвя'зком, отримання якого в аналітичному вигляді було важко доступним. Почали бурхливо розвиватися обчислювальні (чисельні) методи розв'язування задач, і на перший план висунулася проблема доведення існування відповідних алгоритмів. Виявилося, що довести наявність чи відсутність алгоритму не все одно. Перше можна зробити шляхом фактичного опису хоч одного методу розв'язування. В цьому випадку достатньо Означення 1 поняття алгоритму, щоб переконатися, що описане є алгоритмом. Довести відсутність існування алгоритму таким шляхом неможливо. Для цього потрібно коректніше означити, що таке алгоритм.

В 20-х роках ХХ-го століття проблема означення алгоритму стала однією з основних, фундаментальних математичних проблем. Її вирішення було одержано у двох формах всередині 30-х років 20-го століття у роботах таких відомих математиків як Гільберт, Гедель, Черч, Кліні, Пост, Т'юрінґ на базі означень понять класів:

арифметичних функцій (які назвали рекурсивними);

процесу.

Пізніше в роботах Маркова і Калужніна з'явилося інше трактування алгоритму -- як особливої відповідності між словами в абстрактному алфавіті (з означенням понять алфавіт, слово, відповідність).

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

КОНТРОЛЬНА РОБОТА № 2

Скласти перелік елементарних операторів алгоритму роботи системи керування

Виміряні дані використовують для керування. Поняття керування виникло давно. Наприклад, вже у стародавньому Китаї, Єгипті, древній Греції та старому Римі розуміли роль зворотного зв'язку та поінформованості при забезпеченні стабільності та потрібного розвитку різних процесів. Проте теорія керування розвинулася лише протягом ХІХ та ХХ століття, а практично широке застосування його розвинулося у другій половині ХХ століття.

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

Поняття зворотного зв'язку є одним з фундаментальних у кібернетиці -- науці про ефективне керування (розрізняють технічну кібернетику та інші: медичну, криміналістичну, спортивну й т.п. -- див., наприклад, книгу С. Бир Мозг фирмы.--М.: Радио и свъязь,1993. 416 с.). Іншим фундаментальним поняттям цієї науки є інформація. Воно безпосередньо розвивалося в теорії комунікації (зв'язку). Ці поняття й розглядатимемо у контексті, прийнятому в цих технічних науках.

В широкому розумінні інформація -- це якісь відомості, дані про конкретне явище. У техніці її, як правило, пов'язують зі змінною фызичною величиною, сигналом (та його математичною моделлю -- функцією). Сигнал є фізичним носієм інформації. Таким чином, вимірюючи параметри та характеристики сигналу отримуємо інформацію якщо вони міняються, а їх інтерпретація відома.

Розглянемо елементарну систему керування (спеціальним чином з'єднані пристрої, рис. 8). Феноменологічно такі системи були зауважені у природі ще в древності. Задля забав їх виконували (імітували, повторювали) різними технічними засобами. Пізніше вони використовувалися у годинниках, парових машинах в регуляторах (стабілізаторах) швидкості обертання валу механізму.

Рис. 8. Блок-схема системи керування

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

Для розуміння властивостей вербального подання потрібно ознайомитися з основами лінгвістики.

Математична модель. Задача знаходження найбільшого спільного дільника постала при вирішенні проблеми вимірювань -- знаходження масштабу міри.

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

Розглянемо цілі числа (натуральний ряд чисел). Всяке ціле, що ділить без остачі a, b,…,l, називається їх спільним дільником. З теорії подільності відома теорема про ділення з остачею:

Теорема 1. Всяке ціле а представляється єдиним чином за допомогою цілого b рівністю Якщо взяти числа b та r₀, то отримаємо представлення . Далі, розглядаючи послідовно подібним чином числа , легко встановити, що коли r_n+1=0, то r_n буде найбільшим спільним дільником чисел a, b [див. Виноградов И.М. Основы теории чисел.-- М.: Наука, 1981.-- 176 с.].

Ресурси та система команд процесора. Потрібні ресурси процесора та система команд визначаються моделлю задачі та методом її розв'язання. Це диктує розроблення спеціалізованого процесора, "під задачу". Проте часто вибирається процесор "близький" до потрібного --"під клас задач" у найкращому випадку. Отже, нехай маємо процесор з (а) --ресурсами:

1. арифметичний пристрій з регістрами для результату q₀ та x₀ і регістрами x₁, x₂ для операндів;

2. пристрій вводу;

3. пристрій виводу,

4. та (б) -- системою команд (множиною елементарних операцій арифметичного пристрою процесора):

5. перемножити операнди;

6. ділити з відкиданням дробової частини результату (функція ціла частина від числа) та присвоїти знак мінус;

7. присвоїти регістрові вміст іншого регістру;

8. перейти на (відповідний) крок (конкретний зміст дивись в наведеному алгоритмі);

9. ввести число у регістр з пристрою вводу;

10. вивести число на пристрій виводу;

11. зупинити.

3. Скласти перелік елементарних операторів рекурсивного алгоритму розвязування диференціального рівняння з постійними коефіцієнтами

В інформаційних та керуючих технологіях для інформування та вироблення керівного впливу використовуються вимірювання -- спеціальні процедури з вимірюваним об'єктом та мірою (однорідною з об'єктом зразковою величиною). Здавна відомий алгоритм Евкліда знаходження спільної міри двох взаємно несумірних відрізків (найбільшого спільного дільника двох чисел). Розглянемо технічні та інформаційні ресурси (характеристики процесора та математичну модель розв'язуваної задачі) для алгоритму Евкліда, його алгебричну структуру. Її знання уможливлює тотожні перетвори алгоритму.

Для розуміння властивостей вербального подання потрібно ознайомитися з основами лінгвістики.

Математична модель. Задача знаходження найбільшого спільного дільника постала при вирішенні проблеми вимірювань -- знаходження масштабу міри. Відомо, що вимірювання є певною процедурою, алгоритмом над вимірюваною величиною та мірою. При порівнянні об'єктів за значеннями їм властивої величини потрібно спочатку вирішити проблему вибору міри та знайти її значення. Для числових величин цю проблему вирішено постановкою та розв'язуванням задачі найбільшого спільного дільника.

Розглянемо цілі числа (натуральний ряд чисел). Всяке ціле, що ділить без остачі a, b,…,l, називається їх спільним дільником. З теорії подільності відома теорема про ділення з остачею:

Теорема 1. Всяке ціле а представляється єдиним чином за допомогою цілого b рівністю

Якщо взяти числа b та r₀, то отримаємо представлення . Далі, розглядаючи послідовно подібним чином числа , легко встановити, що коли r_n+1=0, то r_n буде найбільшим спільним дільником чисел a, b [див. Виноградов И.М. Основы теории чисел.-- М.: Наука, 1981.-- 176 с.].

Ресурси та система команд процесора. Потрібні ресурси процесора та система команд визначаються моделлю задачі та методом її розв'язання. Це диктує розроблення спеціалізованого процесора, "під задачу". Проте часто вибирається процесор "близький" до потрібного --"під клас задач" у найкращому випадку. Отже, нехай маємо процесор з (а) --ресурсами:

арифметичний пристрій з регістрами для результату q₀ та x₀ і регістрами x₁, x₂ для операндів;

пристрій вводу;

пристрій виводу,

та (б) -- системою команд (множиною елементарних операцій арифметичного пристрою процесора):

перемножити операнди;

ділити з відкиданням дробової частини результату (функція ціла частина від числа) та присвоїти знак мінус;

присвоїти регістрові вміст іншого регістру;

перейти на (відповідний) крок (конкретний зміст дивись в наведеному алгоритмі);

ввести число у регістр з пристрою вводу;

вивести число на пристрій виводу;

Лінгвістичні засоби подання алгоритму. Розглянемо лінгвістичні засоби на прикладі української мови (алфавіту, скінченної множини спеціально вибраних слів та граматики). Назвемо тому його вербальним (на словах) поданням. Отже, для вербального подання алгоритму використовують звичайну мову, її граматику -- алфавіт, лексику, синтаксис тощо. При цьому використовується й семантика мови, виконуючи функцію коментаріїв. Але поліморфізм мови порушує однозначність слів -- інформативних денотатів понять, якими означують операції та ін. складники алгоритму. Це знижує ефективність використання мови, зокрема, семантики при поданні алгоритму. Тотожні перетвори (алгебра) алгоритму забезпечуються граматикою мови, вибраної для його вербального подання, при врахуванні властивостей моделі задачі, методу її розв'язування, процесора тощо.

Засобами мови (вербальні) подаються усі операції та оператори (арифметичні, логічні) алгоритму.

Алгоритм (Евкліда). Користуючись обмеженою кількістю (множиною) слів (понять), які повно і несуперечливо означують поняття моделі задачі, систему команд процесора та означенням алгоритму побудуємо алгоритм Евкліда:

ВВЕСТИ більше число у регістр х₂;

ВВЕСТИ менше число у регістр х₁ ;

функція -- ціла частина q₀ частки від ділення вмісту регістрів х₂ на х₁ зі знаком мінус;

добуток x₀ вмісту регістрів x₁ та q₀;

сума x₀ вмісту регістру x₀ з вмістом регістру х₂;

переслати вміст регістру x₁ у регістр х₂;

переслати вміст регістру x₀ у регістр х₁;

переслати нуль в регістр x₀ ;

якщо x₁ не рівне нулеві -- перейти на крок ііі;

ВИВЕСТИ вміст регістру х₂. ЗУПИНИТИ.

КОНТРОЛЬНА РОБОТА № 3

Оцінити час виконання алгоритму Евкліда (в умовних одиницях)

Алгоритм (Евкліда). Користуючись обмеженою кількістю (множиною) слів (понять), які повно і несуперечливо означують поняття моделі задачі, систему команд процесора та означенням алгоритму побудуємо алгоритм Евкліда:

· ВВЕСТИ більше число у регістр х₂;

· ВВЕСТИ менше число у регістр х₁ ;

· функція -- ціла частина q₀ частки від ділення вмісту регістрів х₂ на х₁ зі знаком мінус;

· добуток x₀ вмісту регістрів x₁ та q₀;

· сума x₀ вмісту регістру x₀ з вмістом регістру х₂;

· переслати вміст регістру x₁ у регістр х₂;

· переслати вміст регістру x₀ у регістр х₁;

· переслати нуль в регістр x₀ ;

· якщо x₁ не рівне нулеві -- перейти на крок ііі;

· ВИВЕСТИ вміст регістру х₂.

· ЗУПИНИТИ.

Оцінити час виконання керування елементарною системою керування (в умовних одиницях)

Елементарна система керування складається з ланок: пристрою порівняння (5), регулятора (6, 7, 8), зворотного зв'язку (2, 3, 4). Сигнал х(t) від керованого об'єкту (1) та відповідні характеристики ланок системи у лінійній теорії сигналів та систем подають як функції комплексної змінної р=j, де =2f (інакше - як лапласівські образи функцій часу, який є дійсною змінною), f -- частота, гц. Нагадаймо, що для ланок системи цими характеристиками є тоді лапласівські образи їх вагових функцій (відгуків на дельта-збурення) -- функції передачі регулятора K_р(p) = K₆(p) K₇(p) K₈(p) та зворотнього зв'язку K_зв(p) = K₂(p) K₃(p) K₄(p). Це приводить до зручнішого подання залежності між вхідним сигналом Х(р) (на вході блоку 2) та вихідним -- на виході блоку 8, Y(p):

,

або у наочнішому для користування вигляді

.

Вирази K_р,зв(p) є алгебричними поліномами вигляду (вони називаються функціями передачі). Від їх вигляду (порядку N, значень коефіцієнтів k_i) залежить стійкість системи.

Для дискретних систем (і в основному й для цифрових, коли дискретні значення сигналів кодуються двійковим чи іншим кодом) матимемо подібний вираз, але як функцію від , де T_d -- період дискретизації неперервного сигналу (фіксовані інтервали часу для виконання операцій в алгоритмі)

.

Цей вираз є розв'язком системи лінійних рівнянь, складених за рис. 8 з використанням законів дискретних кіл (мереж) чи властивостей відповідного йому графу. Таким чином, чисельник цього виразу є доповненням до елементу з індексами рівними номерам вузлів входу-виходу матриці системи рівнянь, а чисельник -- детермінантом цієї системи.

Функції K_р,зв(z) у загальному випадку дробово-раціональні, їх обчислення виконується за алгоритмами, подібними на алгоритм ланки управління. Вони за структурою подібні до алгоритмів вимірювання, див. рис. 5-7.

На множині номерів вузлів дискретного (цифрового) кола моментом часу обчислення задається відношення порядку. Множина вузлів розбивається на підмножини (за відношенням еквівалентності). В свою чергу, на цих підмножинах також задається часове відношення порядку. Виникають тим самим умови для паралелення та конвеєризації обчислень. В алгоритмах векторно-матричних обчислень спостерігається залежність кількості зайнятих в обчисленнях ресурсів від часу, яку за аналогією з хвилями в кровоносній системі організмів називають систолічністю. Структури, в яких з метою підвищення їх ефективності враховуються ці особливості, називають систолічними. Ці властивості використовують під час побудови оптимальних за швидкодією чи кількістю обладнання алгоритмів.

Оцінити час розвязування звичайного диференціального рівняння першого порядку за рекурсивним алгоритмом (в умовних одиницях)

Раніше було встановлено, що за математичну модель явища вибирають математичний вираз -- формулу, алгебричне рівняння, систему лінійних рівнянь, диференційне рівняння тощо. Для кожного з цих об'єктів можна виконати їх тотожні перетвори чи ізоморфні відображення і їх тотожні перетвори. Алгоритми вимірювань (інформування), керування будуються на базі цих моделей. З математичної точки зору алгоритми побудовані на базі однієї моделі однакові. Проте технічна реалізація цих алгоритмів порушує це. Виникає задача побудови критерію вибору технічно оптимального алгоритму з множини математично однакових.

Означення 19. Критерієм називається функціонал, який ставить у відповідність алгоритму число.

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

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

Критерій оптимальності алгоритму подається лінійною

("цінова" функція) чи квадратичною

("енергетична" функція) формами -- зважені емпіричними чи евристичними коефіцієнтами параметри характеристик алгоритму, ,  -- число всіх параметрів. Кожен параметр обчислюють за моделлю відповідної характеристики (складності, точності, швидкодії тощо). Важливою характеристикою критерію є його опуклість. Тоді існує глобальний його екстремум. Квадратична форма є опуклою. Вибір вигляду форми обгрунтовується евристично.

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

4. Розв'язування задачі оптимізації алгоритму

Для постановки задачі оптимізації алгоритму потрібно обгрунтувати: вибір критерію оптимальності, вигляд технічних та фізичних обмежень засобів реалізації алгоритму, вибір початкової структури алгоритму, стратегію та метод пошуку оптимального алгоритму, спосіб визначення досягнення мети пошуку. Вибір початкового алгоритму, метод пошуку оптимального алгоритму, спосіб визначення зупинки пошуку залежить від вигляду критерію та обмежень. Загалом, це називають розвязуванням задачі оптимізації (алгоритму). Такі задачі розвязують на базі теорії дискретної оптимізації. При цьому необхідно мати множину алгоритмів. Її "генерують" за допомогою тотожних перетворів структури алгоритму методами дискретної математики, алгебри моделі задачі, зважаючи на відношення порядку. Формально оптимізація подається виразом

,

де  -- підмножина параметрів для вибраного алгоритму,  -- множина всіх підмножин параметрів.

КОНТРОЛЬНА РОБОТА № 4

Побудувати паралелізми в рекурсивному алгоритмі розв'язування диференціального рівняння другого порядку

Розглядаючи різноманітні алгоритми рішення одної і тої ж задачі, корисно проаналізувати, скільки обчислювальних ресурсів вони потребують (час виконання, пам'ять), і вибрати найбільш ефективний. Звичайно треба домовитись, яка система обчислень повинна використовуватись.

Час сортування вставками залежить від розміру масиву який сортуємо: чим більший масив ти більше може знадобитися часу. Звичайно вивчають залежність часу роботи від розміру входу.

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

Як обчислюється розмір входу? Все залежить від конкретної задачі. В одних випадках добре рахувати число елементів на вході (сортування, пере ображення фур'є), в других - рахувати число бітів необхідних для представлення всіх вхідних даних. Іноді розмір входу виміряється не одним числом, а декількома.

Час роботи алгоритму ми називаємо число елементарних кроків які він виконує - запитання полягає у тому чи рахувати це елементарним кроком.

Ми будемо вважати, що один рядок псевдо коду потребує не більше чим фіксованого числа операцій (якщо тільки це не словесне описання якоїсь складної операції типу “відсортувати всі точки по х координаті”).

Ми будемо також відрізняти виклик процедури і її виконання, які можуть бути довгими.

Отже повернемося до процедури Insertion-Sort і відмітимо біля кожного рядка кількість її операцій і кількість раз за який це рядок виконується. Для кожного j від 2 до n (тут n length [A]- розмір масиву) підрахуємо скільки раз буде виконано рядок 5 і визначимо це число через t_j.

Insertion-Sort (А) вартість число раз

1 for j 2 to length[A] c 1 n

2 do key A[j] c 2 n-1

3 додати А [j] до сортованої частини

A [1..j-1] 0 n-1

4 ij1 c4 n-1

5 while i0 and A[i] key c5

6 do A[i+1] A[i] c6

7 ii1 c7

8 A [I+1]key c8 n-1

Рядок стану с, повторення m, дає вклад cm в загальне число операцій. Склавши дані всіх рядків отримаємо

Як ми вже казали час роботи процедури залежить тільки від n, але й від того який саме масив розміру n даний на вхід. Для процедури Insertion-Sort тоді пікл в рядку 5 закінчується після першої пробірки (оскільки А[i] <= key при i=j-1) отже всі t_j рівні 1 і загальний час тоді

Е(т)=с1т+с2(т-1)+с4(т-1)+с5(т-1)+с8(т-1)=(с1+с2+с4+с5+с8)n-(с2+с4+с5+с8)

Таким чином, в найбільш сприятливому випадку час Т(n), необхідне для обробки масиву розміром n, є також лінійною функцією від n.

Якщо масив розміщений в зворотному порядку, час роботи процедури буде максимальним: кожний елемент А[j] потрібно буде порівнювати зі всіма елементами A[1]…A[j-1]. При цьому t_j=j. Згадуючи те що

отримаємо що в гіршому випадку час роботи процедури рівний

Тепер функція T(n)- квадратична ,має вигляд T(n)=an²+bn+c.

КОНТРОЛЬНА РОБОТА № 5

Чи можна побудувати алгоритм знаходження найбільшого спільного дільника двох цілих чисел командами машини Поста?

В алгоритмічній системі Поста інформація представляється в війковому коді А=(1,0).

Таким чином в кожній комірці інформаційної стрічки можна розмістити обо 0, або 1. Алгоритм представляється у вигляді кінцевого впорядкованого набору правил, названих наказами. Робота алгоритма починається з деякої початкової комірки, згідно першого наказу алгоритма. Накази алгоритма можуть належати до одного із 6 наказів, виконуваних пристроєм управління машини Поста:

· Записати в комірку 0 і перейти до і-го наказу;

· Записати в комірку 1 і перейти до і-го наказу;

· Посунути стрічку в право на одну комірку і перейти до виконання і-го наказу;

· Посунути стрічку в ліво на одну комірку і перейти до виконання і-го наказу;

· Якщо в комірці записана 1, то перейти до виконання j-го наказу, а якщо 0, то перейти до виконання і-го наказу;

· Закінчення роботи алгоритма, зупинка.

Таким чином, алгоритмічна машина Поста представляє собою машину з ін формаційною стрічкою, яка має в кожній комірці або 0, або 1; з стрічкою, пересуваючись вліво або право вздовж головки; з пристроєм керування, виконучим 6 наказів ( з внутрішніми станами).

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

Чи можна побудувати алгоритм командами машини Тьюрінга?

В кожній комірці машини Тюрінга може знаходитися один з символів деякого кінцевого алфавіту, а пристрій управління може бути в одному із кінцевих станів. Іншими словами, машина Тюрінга, працюючи в довільному кінцевому алфавіті, може виконувати деяке кінцеве число наказів. При цьому машина Тюрінга, як і машина Поста, можуть посувати стрічку на одну комірку вправо або вліво, залишаючи вміст комірки незмінним, або можуть змінювати стан комірки, залишаючи стрічку нерухомою.

Цей список операцій можна розширити. Машина Тюрінга називається стандартною, якщо вона при зсуві стрічки може попередньо змінювати стан комірки.

В подальшому будемо розглядати тільки стандартні машини Тюрінга.

Нехай алфавіт машини Тюрінга заданий не ввиді множини А=(s₀,s₁,……..s_n ), де s₀ відповідає пустій комірці, а число стану приладу управління задано в вигляді множини Q={q₀,q₁……..q_m} де q₀ відповідає останньому стану.

Кінцева сукупність символів алфавіта, з яким працює машина, називається зовнішнім алфавітом, кінцева сукупність станів прилада управління - внутрішнім алфавітом.

При використанні з стрічками використовуються наступні позначення:

Л-рух стрічки в ліво;

П- рух стрічки в право;

С- нема руху стрічки.

Сукупність всіх команд, які може виконувати машина називається її програма.

Довести еквівалентність трансверсального та рекурсивного алгоритмів

Історично першою алгоритмічною системою була система, основана на використанні конструктивно вичислю вальних арифметичних функцій, отримавши спеціальну назву рекурсивні функції.

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

Чисельні функції, значення яких можна встановити безпосередньо деякого алгоритма, називаються вичисильними функціями. Функція називається рекурсивною, якщо існує ефективна процедура для її обчислення..Поняття ефективна процедура це інтуїтивне. Кажуть, що є ефективна процедура для виконання конкретних обчислень, якщо ці обчислення виконуються по механічним правилам, тобто по конкретному алгоритму.

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

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

Використання рекурсивних функцій в теорії алгоритмів основане на ідеї нумерації слів в довільній алфавітній послідовності натуральними числами.Найбільш просто таку нумерацію можна зробити, маючи слова впорядку зростання їх довжини, а слова, з однаковою довжиною в довільному (лексографічному) порядку.

Після нумерації вхідних і вихідних слів в довільному алфавітному операторі цей оператор перетворюється в функцію у=f(x), в якому аргумент х функція у приймають не позитвне цілочисельне значення. Функція f(x) може бути вичислена не для всіх значень х, але лише для тих, які входять в область обчислення цієї функції.

Подібні частково вичислювальні цілочисельне і цілозначенні функції називаються арифметичними функціями, серед них найбільш прості будем називати елементарними арифметичними функціями:

1. функція тотожна 0 Оⁿ(х₁,х_2,.....х_n)=0, обчислення для всіх негативних значень аргумента;

2. тотожність функції,яка повторяє значення своїх аргументів: частий випадок :

3. функція безпосереднього слідкування S¹(x)=x=1

також обчислення для всіх цілих значень свого аргументу.

Використовуючи в якості вихідної функції перераховані елементи арифметичної функції, можна з допомогою невеликого числа загальних конструктивних прийомів будувати все більш і більш складні арифметичні функції. В теорії рекурсивних функцій особливо важливе значення мають три операції: суперпозиції, примітивна рекурсія і найменший корінь. Розглянемо кожну з них.

Операція супер позиції полягає в підстановці одних арифметичних функцій замість аргументів других арифметичних функцій.

Операція суперпозиції позначається символом Sⁿ⁺¹ , де індекс зверху означає число функцій.

Операція примітивної рекурсії дозволяє будувати n+1 місцеву арифметичну функцію по двох заданих функціях, одна з яких є n-місцевою часткова функція f виникає з функції g і h примітивної рекурсії,якщо для всіх натуральних значень х_1,......,х_n, у має:

F(x_{1,……….,}x_n, 0)=g(x_{1,……….,}x_n):

F(x_{1,……….,}x_n, y+1)=h (x_{1,……….,}x_{n ,} y, f(x_{1,……….,}x_n,y)).

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

В зв'язку з цим операцію примітивної рекурсії будемо використовувати і для n=0, кажуть кажуть, що одночасно частична функція f виникає з постоянної одномісної функції, рівна числу а , і двомісцевій частинній функції h, якщо:

F(0)=a$

F(x+1)=h(x, f(x)).

Постає питання, чи для кожного існує функція F і чи буде вона єдиною. Область визначення функції- множина всіх натуральних чисел, тому відповідь на цих два питання позитивний.

Якщо F існує, то з вище описани формул знаходимо:

F(x_{1,……….,}x_n,0)=g (x_{1,……….,}x_n):

f(x_{1,……….,}x_n,m+1)=h(x_{1,……….,}x_n, m, f(x_{1,……….,}x_n,m))

і тому функція визначена однозначно. Таким чином для будь яких часткових n-місць функція g n +2- місць функція h/ n=0,1,2,...... існує тільки одна часткова n +1- місць функція f, яка виникає із g і h примітивної рекурсії. Символічно пишуть f=R(g,h).

Операція найменшого кореня,або операуія мінімізації, дозволяє вичислити нову арифметичну функцію від n змінних з допомогою раніше побудованихарифметичних функцій g(x_1……..,x_n , y) від n+1 змінних.

Для будь-якого набору значень змінних х₁=а₁....., х_n=а_n в якості відповідного значення f(а_1……..,а_n) шуканої функції f(x_1……..,x_n) приймається найменший цілий корінь у=а рівняння g(x_1……..,x_n , y)=0.

У разі неіснуючих цілих коренів у цього рівняння функція f(x_1……..,x_n) рахується не визначеною при відповідних наборі значень змінних.

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

Побудувати алгоритм, еквівалентний до алгоритму знаходження найбільшого спільного дільника двох цілих чисел

Розглядаючи різноманітні алгоритми рішення одної і тої ж задачі, корисно проаналізувати, скільки обчислювальних ресурсів вони потребують (час виконання, пам'ять), і вибрати найбільш ефективний. Звичайно треба домовитись, яка система обчислень повинна використовуватись.

Час сортування вставками залежить від розміру масиву який сортуємо: чим більший масив ти більше може знадобитися часу. Звичайно вивчають залежність часу роботи від розміру входу.

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

Як обчислюється розмір входу? Все залежить від конкретної задачі.В одних випадках добре рахувати число елементів на вході (сортування, пере ображення фурє), в другиї - рахувати число бітів необхідних для представлення всіх вхідних даних. Іноді розмір входу виміряється не одним числом, а декількома.

Час роботи алгоритму ми називаємо число елементарних кроків які він виконує - запитання полягає у тому чи рахувати це елементарним кроком.

Ми будемо вважати, що один рядок псевдо коду потребує не більше чим фіксованого числа операцій (якщо тільки це не словесне описання якоїсь складної операції типу “відсортувати всі точки по х координаті”).

Ми будемо також відрізняти виклик процедури і її виконання, які можуть бути довгими.

Отже повернемося до процедури Insertion-Sort і відмітимо біля кожного рядка кількість її операцій і кількість раз за який це рядок виконується. Для кожного j від 2 до n (тут n length [A]- розмір масиву) підрахуємо скільки раз буде виконано рядок 5 і визначимо це число через t_j.

Побудувати алгоритм, еквівалентний до рекурсивного алгоритму розв'язування диференціального рівняння другого порядку

Розглядаючи різноманітні алгоритми рішення одної і тої ж задачі, корисно проаналізувати, скільки обчислювальних ресурсів вони потребують (час виконання, пам'ять), і вибрати найбільш ефективний. Звичайно треба домовитись, яка система обчислень повинна використовуватись.

Час сортування вставками залежить від розміру масиву який сортуємо: чим більший масив ти більше може знадобитися часу. Звичайно вивчають залежність часу роботи від розміру входу.

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

Як обчислюється розмір входу? Все залежить від конкретної задачі. В одних випадках добре рахувати число елементів на вході (сортування, пере ображення фур'є), в других - рахувати число бітів необхідних для представлення всіх вхідних даних. Іноді розмір входу виміряється не одним числом, а декількома.

Час роботи алгоритму ми називаємо число елементарних кроків які він виконує - запитання полягає у тому чи рахувати це елементарним кроком.

Ми будемо вважати, що один рядок псевдо коду потребує не більше чим фіксованого числа операцій (якщо тільки це не словесне описання якоїсь складної операції типу “відсортувати всі точки по х координаті”).

Ми будемо також відрізняти виклик процедури і її виконання, які можуть бути довгими.

Отже повернемося до процедури Insertion-Sort і відмітимо біля кожного рядка кількість її операцій і кількість раз за який це рядок виконується. Для кожного j від 2 до n (тут n length [A]- розмір масиву) підрахуємо скільки раз буде виконано рядок 5 і визначимо це число через t_j.

Insertion-Sort (А) вартість число раз

1 for j 2 to length[A] c 1 n

2 do key A[j] c 2 n-1

3 додати А [j] до сортованої частини

A [1..j-1] 0 n-1

4 ij1 c4 n-1

5 while i0 and A[i] key c5

6 do A[i+1] A[i] c6

7 ii1 c7

8 A [I+1]key c8 n-1

Рядок стану с, повторення m, дає вклад cm в загальне число операцій. Склавши дані всіх рядків отримаємо

Як ми вже казали час роботи процедури залежить тільки від n, але й від того який саме масив розміру n даний на вхід. Для процедури Insertion-Sort тоді пікл в рядку 5 закінчується після першої пробірки (оскільки А[i] <= key при i=j-1) отже всі t_j рівні 1 і загальний час тоді

T(n)=c1n+c2(n-1)+c4(n-1)+c5(n-1)+c8(n-1)=(c1+c2+c4+c5+c8)n-(c2+c4+c5+c8)

Таким чином, в найбільш сприятливому випадку час Т(n), необхідне для обробки масиву розміром n, є також лінійною функцією від n.

Якщо масив розміщений в зворотному порядку, час роботи процедури буде максимальним: кожний елемент А[j] потрібно буде порівнювати зі всіма елементами A[1]…A[j-1]. При цьому t_j=j. Згадуючи те що

отримаємо що в гіршому випадку час роботи процедури рівний

Тепер функція T(n)- квадратична ,має вигляд T(n)=an²+bn+c.

КОНТРОЛЬНА РОБОТА № 6

Оцінити складність алгоритму Евкліда

Простих чисел є доволі багато. Це давним давно доказав Евклід. Припустимо що є обмежене число простих чисел к 2,3,5,....Р_к.

Тоді потрібно розглядати число так:

М=2*3*5......Р_к+1

Ні одне із простих чисел не може ділитись на М, бо кожне з них ділить М-1. таким чином, має бути інше просте число, яке ділить М, а, саме М просте число. Це заперечує нашому предположенню, бо 2,3,.....,Р_к зміст простих чисел, так що насправді далі їх повинно бути безкінечне багато.

Евклідові докази наводять на думку визначити рекурентно число Евкліда:

їх послідовність починається з чисел

е₁=1+1=2,

е₂=2+1=3,

е₃=2*3+1=7,

е₄=2*3*71=43,

всі з яких прості. Але вже наступне число е₅ є 1807=13*139.Виявляється, що е₆=3263443- просте число, в той час як

е₇=547*607*1033*31051,

е₈=29881*67003*9119521*6212157481.

Відомо що е_9........., е₁₇- зіставні числа,так як і решта е_n. Однак всі числа Евкліда взаємно попарно простими, тобто:

НОД(е_m, e_n)= НОД(1,е_m)=НОД(0,1)=1

Якщо підставити q_j рівне найменшому множнику числа e_j при кожному j1, то всі прості числа q₁, q_2, q_3.......... будуть різними, вони утворять безкінечну послідовність простих чисел.

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

Оцінити складність алгоритму роботи елементарної системи керування

Елементарна система керування складається з ланок: пристрою порівняння (5), регулятора (6, 7, 8), зворотного зв'язку (2, 3, 4). Сигнал х(t) від керованого об'єкту (1) та відповідні характеристики ланок системи у лінійній теорії сигналів та систем подають як функції комплексної змінної р=j, де =2f (інакше - як лапласівські образи функцій часу, який є дійсною змінною), f -- частота, гц. Нагадаймо, що для ланок системи цими характеристиками є тоді лапласівські образи їх вагових функцій (відгуків на дельта-збурення) -- функції передачі регулятора K_р(p) = K₆(p) K₇(p) K₈(p) та зворотнього зв'язку K_зв(p) = K₂(p) K₃(p) K₄(p). Це приводить до зручнішого подання залежності між вхідним сигналом Х(р) (на вході блоку 2) та вихідним -- на виході блоку 8, Y(p):

,

або у наочнішому для користування вигляді

.

Вирази K_р,зв(p) є алгебричними поліномами вигляду (вони називаються функціями передачі). Від їх вигляду (порядку N, значень коефіцієнтів k_i) залежить стійкість системи.

Для дискретних систем (і в основному й для цифрових, коли дискретні значення сигналів кодуються двійковим чи іншим кодом) матимемо подібний вираз, але як функцію від , де T_d -- період дискретизації неперервного сигналу (фіксовані інтервали часу для виконання операцій в алгоритмі)

.

Цей вираз є розв'язком системи лінійних рівнянь, складених за рис. 8 з використанням законів дискретних кіл (мереж) чи властивостей відповідного йому графу. Таким чином, чисельник цього виразу є доповненням до елементу з індексами рівними номерам вузлів входу-виходу матриці системи рівнянь, а чисельник -- детермінантом цієї системи.

Функції K_р,зв(z) у загальному випадку дробово-раціональні, їх обчислення виконується за алгоритмами, подібними на алгоритм ланки управління. Вони за структурою подібні до алгоритмів вимірювання, див. рис. 5-7.

На множині номерів вузлів дискретного (цифрового) кола моментом часу обчислення задається відношення порядку. Множина вузлів розбивається на підмножини (за відношенням еквівалентності). В свою чергу, на цих підмножинах також задається часове відношення порядку. Виникають тим самим умови для паралелення та конвеєризації обчислень. В алгоритмах векторно-матричних обчислень спостерігається залежність кількості зайнятих в обчисленнях ресурсів від часу, яку за аналогією з хвилями в кровоносній системі організмів називають систолічністю. Структури, в яких з метою підвищення їх ефективності враховуються ці особливості, називають систолічними. Ці властивості використовують під час побудови оптимальних за швидкодією чи кількістю обладнання алгоритмів.

Оцінити складність рекурсивного алгоритму розв'язування звичайного диференціального рівняння другого порядку з постійними коефіцієнтами

Процедуру яка прямо або непрямо звертаються до себе, називають рекурсивною. Застосування рекурсії часто дозволяє давати більш прозорі та стислі описи алгоритмів, чим це було лоби можливо без рекурсії.

Розглянемо знаходження проходження війкового дерева в внутрішньому порядку. При створенні алгоритма, який присвоює вузлам номера в відповідності з внутрішнім порядком, добре було б відобразити в ньому знаходження проходження в внутрішньому порядку.

Один з таких алгоритмів приведемо нижче. Замітимо , що він рекрусивно звертається до себе для нумерації піддерева.

Алгоритм. Нумерація вузлів війкового дерева в відповідності з внутрішнім розпорядком.

Вхід. Війкове дерево, представлене масивом ЛІВИЙСИН і ПРАВИЙСИН.

Вихід. Масив, порядковий НОМЕР, такий, що НОМЕР(і)- номер вузла і в внутрішньому розпорядку.