Вхід в УЧАН Анонімний форум з обміну зображеннями і жартами.



Додати книгу на сайт:

Скачати одним файлом. Книга: Моделювання та інформаційні системи в економіці: Міжвід. М.Г. Твердохліб

ПРОБЛЕМИ ОЦІНКИ СКЛАДНОСТІ ПРОГРАМ ДЛЯ ЕОМ

Велика кількість актуальних задач досліджень та проектування вимагають для свого рішення можливості попереднього оцінювання складності алгоритмів і обчислень, а також реалізації програм [1].
Апеляцію щодо поняття складності викликано її безпосереднім зв’язком із вартістю розробки та реалізації конкретних алгоритмів і програм. Труднощі вирішення проблем складності визначаються неоднозначністю методів розробки конкретних програм і різноманітністю алгоритмічних мов, технології програмування, а також значним впливом суб’єктивних факторів.
Досягнення в галузі кібернетики, зокрема в теорії алгоритмів і автоматів [2, 3], зумовлюють можливість вирішення практично будь-яких складних прикладних задач. Раніше розв’язання цих задач виявлялося або неможливим без залучення сучасних засобів обчислювальної техніки, або було цілковитим привілеєм інтелекту людини. Нові можливості породжують нові проблеми. Покладання розв’язання нових задач на автомати пов’язано з великими витратами засобів і часу. Перш, ніж зважитися на ці витрати, їх необхідно оцінити. Прогрес неможливий без розрахунку економічної ефективності. У цих умовах виникає важлива проблема визначення доцільності постановки й вирішення складних прикладних задач, оцінки складності й вартості їх обчислень. Постановка і розв’язання нової задачі доцільні, якщо за їхньою допомогою них покращуються результати деякого процесу чи процес реалізується за незначних витрат ресурсів. Очікуваний у цьому випадку виграш вдається звичайно оцінити за наявністю прогнозу змінюваних параметрів процесу, що розглядається.
Інтерес до проблеми оцінки складності алгоритмів виник після появи перших ЕОМ у середині минулого століття. Тому осно вні публікації з цієї проблеми з’явилися в 60-х, 70-х роках. ЕОМ були реальним конструктивним способом реалізації алгоритмів, що потребував складних обчислень, але параметри перших ЕОМ виявилися досить скромними, тому проблема складності реалізації алгоритмів вирішувалася з позиції оцінки можливостей використання алгоритмів і визначення відповідних вимог до ЕОМ, у пер­шу чергу за обсягом оперативної пам’яті та швидкодії. Швидкий прогрес у сфері вдосконалення параметрів ЕОМ вже у 80-ті роки минулого століття зняв обмеження з продуктивності ЕОМ, тому інтерес до оцінки складності втратив актуальність. Проте на початку ХХІ століття досягнення в галузі розвитку сучасних інфор­маційних технологій настільки розширили масштаби застосування ЕОМ, що число машинних алгоритмів, упроваджуваних на практиці, почало невпинно зростати. У зв’язку з цим проблему оцінки складності алгоритмів пов’язують із пошуком найбільш ефективної їх реалізації, що впливає на ціноутворення програмних продуктів. Вирішення цих задач також потребує оцінки складності алгоритмів, що знов зумовлює актуальність проблеми.
Приклади конкретних задач, де використано оцінку складності алгоритмів і обчислень, розглянуто в [1].
У цілому ряді праць, наприклад у [4, 5, 6], вказано, що існують прості (типу простого перебору) алгоритми, які ґрунтуються на переборі астрономічного числа варіантів із дуже довгими обчислюваннями, та, навпаки, складні алгоритми, які швидко приводять до мети. Будь-яке зменшення складності обчислювань пов’язане з ускладненням алгоритмів. Вибір найкращого чи при йнятного співвідношення ґрунтується цілком на обраній відповід­ним чином порівняльній оцінці функцій складності.
Завдання оцінки складності являють собою достатньо широкий і важливий у практичному плані клас задач, який дозволяє зробити висновок щодо актуальності даної проблеми. Ці задачі було поставлено практикою вже давно, проте стають дедалі актуальнішими із впровадженням у життя штучних перетворювачів інформації, чиї можливості зростають і здатні конкурувати з мож­ливостями людського інтелекту.
Перші результати в цій галузі було отримано для конкретних алгоритмів. Так, наприклад, у [7] отримано важливі для використання оцінки складності обчислювання алгоритмів інформаційного пошуку, внутрішнього та зовнішнього сортування. Оцінки виконано за продуктивністю та необхідним робочим обсягом пам’яті (за винятком обсягів, які займає вхідна та вихідна інформація). У [8] синтезуються мінімальні структурні схеми автоматних алгоритмів функціонування елементів ЕОМ. Як критерій складності там, зокрема, використовується кількість типів елемен­тів функціонально повного набору.
Більш узагальнені, але менш точні результати в цьому ж напрямі можна отримати в такій постановці.
Задано: n ( m ) — число літер вхідного (вихідного) алфавіту, r — число внутрішніх станів автомата Мура. Знайти верхню оцінку складності автомата за довільно обраною функцією переходів. Як оцінка вартості будь-якого автомата, котрий задовольняє заданим n , m і r , може виступати вартість найскладнішого автомата. Під вартістю S ( n , r ) розуміється вартість елементів функціонально повного набору [9].
За такої оцінки не враховують вартість поєднання елементів, їх налагодження і т. п., однак це не є принциповим, оскільки вказано витрати пропорційні кількості використаних елементів, необхідних для побудови автомата. Визначимо кількість елементів, необхідних для побудови автомата.
Нехай n = 2 ^{n 1}; m = 2 ^{m 1}; r = 2 ^{r 1}.
Тоді [10] S ( n , r ) = ( m ₁ + r ₁) Lf_{n 1 + r 1} + r ₁ L ₃,
де L ( f_{n 1 + r 1}) — вартість реалізації функцій алгебри логіки від n 1 + r 1 змінних у базисі Ù , Ú , ù ;
L ₃ — вартість елементу затримки.
У [9, 11] показано, що
  за  l = 1—2;
  за  l = 3—5;
  за  l = 6—30;
  за  l > 30,
де l = n ₁ + r _1.
Усі наведені оцінки вартості значно завищено, тому що, по-перше, оцінюють найскладніший автомат, по-друге, методи син тезу, які покладено в основу наведених оцінок, розроблено віднос­но комбініційних схем, що реалізують функції алгебри логіки без пам’яті.
Перелік подібних результатів можна продовжувати досить дов­го, але розроблені методи придатні для конкретних алгоритмів чи для вузьких класів, і їм не притаманна спільність. Для того, щоб подолати ці недоліки, необхідно отримати оцінки складності алгоритмів і обчислень у рамках якої-небудь універсальної алгоритмічної системи. При цьому має бути чітко обґрунтовано критерії оцінки та розвинені методи їх обчислень.
Існують три напрями дослідження проблеми складності.  Перший напрям пов’язано з алгоритмічною вирішуваністю й  доведенням алгоритмічно вирішуваних і невирішуваних проблем. За ним останні класифікуються за ступенем невирішуваності.
Другий напрям пов’язано з класифікацією за складністю  обчислюваних функцій. Тут можна виділити аксіоматичний підхід до вивчення алгоритмів.
Третій напрям передбачає визначення оцінок складності в різ­номанітних алгоритмічних системах із порівняною складністю іншим чином заданих алгоритмів. Цей напрям має найважливіше прикладне значення.
Під час вибору критерію перш за все необхідно розмежувати поняття “складність алгоритму” і “складність обчислень”.
Складність алгоритму — це величина, що характеризує складність (довжину) запису самого алгоритму.
Складність обчислення — це величина, що характеризує процес обчислення та відтворює довготривалість і нагромадженість процесу обчислення.
Складність обчислення задається у вигляді функціонала, який залежить від алгоритму та конкретної вирішуваної задачі (вхідних данних).
У літературі існує опис різних критеріїв, які часто, якщо мож ливо, задаються у вигляді верхніх і нижніх оцінок. Найбільш зміс­товним є опис критеріїв для машин Тьюринга [12]. Як кри терії використовуються:
t_m ( a ) — часова сигналізувальна (час обчислення);
S_m ( a ) — сигналізувальна обсягу (обсяг активної зони);
W_m ( a ) — сигналізувальна коливань (число змін напрямку руху головки за t_m ( a ));
r_m ( a ) — сигналізувальна режиму (максимальне число проходження головки через край комірки за t_m ( a )).
Тут ( a ) — характеристика вхідного слова, а m — характеристика машини.
Звичайно припускається, що вхідні слова задаються в одному й тому ж алфавіті, при цьому a = n , де n — число літер вхідного слова.
Оскільки під час обчислення в реальному часі t_m ( a ) = n , то для автомата S_m ( a ) = n ; W_m ( a ) = 0; r_m ( a ) = n .
У наш час для перетворення інформації універсальною алгоритмічною системою на практиці використовується цифрова обчислювана машина (ЕОМ). Доказ алгоритмічної універсальності ЕОМ із урахуванням можливості нарощування обсягу її пам’яті наведено в [2].
Проте спроби розрахунку складності обчислювання на ЕОМ обмежуються результатами, отриманими для конкретних алгорит­мів і конкретних ЕОМ. Деякі найзагальніші результати, також і для конкретних алгоритмів, отримано в [13, 14, 15]. Така обмеженість результатів пояснюється складністю опису алгоритмів в алгоритмічній системі, яку представляє ЕОМ. Спираючись на тезу Черча, можна спробувати використати для практичних розрахунків складності обчислювання на ЕОМ результати оцінки складності обчислювання, отримані в більш простих за структурою, але універсальних алгоритмічних системах. З цією метою розглянемо отримані в даній галузі результати.
Запропоновану Тьюрингом машину було ускладнено багатьма авторами. Особливо багато змін стосувалося внесення до зовнішньої пам’яті машини єдиної стрічки, нескінченної, за Тьюрингом. Подано на розгляд двострічкові та багатострічкові машини [16, 17]; іноді стрічки обмежуються з однієї чи з двох сторін, упроваджуються багатовимірні стрічки. Робочий алфавіт машини Тьюринга може бути унарним, двійковим чи довільним [12, 18]. Машини Тьюринга розрізняють також за способом подання вхідних (початкових) даних: із записом на стрічці [19] та із входом [20], проте ця різниця не є принциповою.
Поняття t -обчислюваності є головним для визначення складності обчислень на машині Тьюринга. Вхідне слово a (послідовність) t -обчислювано лише тоді, коли часова сигналізувальна машини для слова a не перевищує t ( a ). Більшість праць у галузі дослідження складності обчислень на машинах Тьюринга присвячено вирішенню проблеми t- обчислюваності. Так, у [6] для стрічкових машин наведено конкретні результати для таких задач:
1. Перехід у десятковій системі від числа n до числа n + 1:
t ( n ) = n + 1.
2. Переведення унарного запису числа до десяткового вигляду:
t ( n ) ~ (1 + n ) n ~ n ².
У [17] для того ж класу машин наведено більш розгорнуті результати, до складу яких входить задача розпізнавання симетрії слів у двійковому алфавіті:
а) порівняння за однією літерою у правій та лівій частинах вхідного слова:
t ( n ) ~ n ²/4; S ( n ) ~ n ; w ( n ) ~ n ; r ( n ) ~ n ; r = 8;
б) порівняння блоків довжиною m літер з лівою та правою частинами вхідного слова:
t ( n ) ~ n ²/4 m ; r > 8.
У [21] наводяться верхня та нижня оцінки часової сигналізувальної для розпізнавання множини слів спеціальної конструкції:
C ₁ ( p ₁ r ) n ^p £ t ( n ) £ C ₂( p ₁ r ) n ^p ,
де C ₁ і C ₂ — параметри, які залежать від p і r ; 1 < p £ 2.
Подібні оцінки для конкретних задач наводяться також у [19, 20].
Більш загальні результати належать до будь-яких алгоритмів, на вхід яких надходять слова з довжиною, що не перевищує n .
У [21] показано можливість моделювання автоматом роботи машини Тьюринга, якщо t ( n ) = Cn , де С — константа, а також доведено необхідність “закону квадрату” під час моделювання двострічкової машини Тьюринга однострічковою. Цей результат підсилено положенням для випадку двох стрічок, яке доведено в праці [22]. Воно демонструє таке: якщо функція t- обчислювана на багатострічковій машині Тьюринга, то вона t ²-обчислювана й на однострічковій машині. Крім того, наведено такі теореми:
1. Якщо функція t- обчислювана, то вона і [ Ct ] обчислювана ([ x ] — результат округлення числа x до найближчого цілого).
2. Найбільше покращання, якого можна досягти під час переходу від n- стрічкових машин Тьюринга до ( n + l ) стрічкових, пропорційне корню квадратному з часу обчислення.
3. Якщо функція t- обчислювана на машині з n- вимірними стрічками, то вона t ²-обчислювана на машині з лінійними стрічками. У наступних працях отримано деякі підтвердження.
У [20] показано, що існують функції, які можна обчислити в реальний час на машині Тьюринга з двома стрічками і неможливо обчислити в реальний час на машині з однією стрічкою.
У [16] доведено, що під час моделювання двострічковою  машиною Тьюринга k- стрічкової машини час обчислення підвищується в C log₂ n рази, де n — число операцій, виконаних  k- стрічковю машиною. Слід підкреслити, що в цій праці поняття t- обчислюваності не використовується.
У [23] на базі критерію t ( n ) наводиться результат моделювання m- мірних k- головочних машин Тьюринга (часова сигналізу- вальна t ^{( mk )}( n )) однострічковою машиною з двома головками (часова сигналізувальна t ⁽²⁾( n )):
t ⁽²⁾ ( n ) = C ₁[ t ^{( mk )}( n )]^{2–1/ m} log₂ t ^{( mk )}( n ) + C ₂.
У [19] показано, що час обчислення за умовою зменшення розмірності машини Тьюринга від m до p збільшується за законом t_p ( n ) ≥ C [ t_m ( n )]^{2– p / m} .
І, зрештою, в [24] показано, що швидкість обчислювань (часова сигналізуюча) машин Тьюринга з лінійними стрічками залежить від кількості головок (але не від їх розподілу по стрічках) із точністю до постійного коефіцієнта.
Результати, які встановлюють співвідношення машин, містяться у теоремах Шеннона [12].
Аналіз наведених результатів засвідчує, що вони дозволять класифікувати та порівнювати алгоритми за наведеними критеріями складності. Крім того, існує можливість використання розроблених методів із метою отримання порівняльної оцінки деяких абстрактних алгоритмічних систем. У той же час усі методи доведення теорем зводяться до побудови реального алгоритму та розрахунку для нього спеціальних параметрів або до моделювання одного алгоритму іншим. При цьому питання про кількість станів і потужності зовнішнього алфавіту не розглядається.
Найбільш точною моделлю функціонування ЕОМ є багатомір­на машина Тьюринга, якщо її розмірність дорівнює кількості слів в оперативній пам’яті, а зовнішній алфавіт збігається з алфавітом ЕОМ.
Але і в цьому випадку можливості ЕОМ набагато ширші, ніж у машини Тьюринга; у зв’язку з цим така модель не буде адекват­ ною ЕОМ за своїми можливостями. Тому для отримання практич них результатів в області оцінки обчислень на ЕОМ недоцільно моделювати їх у наведених вище алгоритмічних системах, тим біль­ше, що майже всі оцінки складності є верхніми. Проте існує можливість зворотнього шляху: знайти верхні оцінки складності обчислень, наприклад, на машині Тьюринга чи абстрактному автоматі, а потім моделювати їх роботу на ЕОМ.
ЕОМ витрачає деяку кількість команд на моделювання одного такту роботи машини Тьюринга. При цьому час роботи ЕОМ пропорційний часовій сигналізувальній тільки в тому разі, якщо опис машини та її стрічки розташовано в оперативній пам’яті. Важливо з практичної точки зору знати обсяг опису машини.
За своєю сутністю алгоритм роботи машини Тьюринга організовано таким чином: виконується (якщо можливо) декомпозиція алгоритму розв’язання задачі на розрізнені алгоритми, які реалізуються автоматом. Оцінки Тьюрингових алгоритмів декомпозиції і кодування наведено в [10]. Тому достатньо визначити оцінки параметрів автомата.
Автоматний алгоритм характеризується вхідним алфавітом і величиною N — кількістю літер, від яких залежить вихідне слово — результат розв’язання задачі. Якщо побудувати граф автомата у вигляді дерева, то очевидними стають властивості:
— висота дерева складає N + 1 рівень;
— загальна кількість можливих вхідних слів B ₁, при цьому B ₁ = 2 ^N – 1; (1)
— число станів автомата, що відповідає повному графові висотою N + 1, складає r_g , за формулою прогресії: r_g = 2 ^{N + 1} – 1. (2)
Але ця оцінка є надто завищеною, існує можливість добитися її зниження.
Завдання автомата рівнозначне завданню розбивання [44] В ₁ вхідних слів рівно на В ₂ частин, де В ₂ — число вихідних слів тієї ж самої довжини, що й вхідні. Вид розбивання визначається алгоритмом, який реалізує автомат.
Для точного визначення вважатимемо, що ми використовуємо автомат Мура [10]; тому формування вихідних слів може здійснюватися кодуванням станів автомата літерами вихідного алфавіту. У загальному випадку потужність вхідного ( n ) і вихідного ( m ) алфавітів може бути різною, але ця різниця не принципова, і ми маємо можливість легко перейти від вхідного до вихідного алфавіту, зробивши тотожними підмножини літер вхідного алфавіту та позначивши їх буквами вихідного алфавіту.
Повний граф автомата має висоту N + 1 рівень і відображає всі можливі вхідні слова. Для задання алгоритму граф автомата кодується літерами вихідного алфавіту. Вхідні слова позначимо числами натурального ряду i = 1, 2, …, B ₁.
Цю нумерацію може бути відображено на верхньому рівні графа. Вихідні слова позначимо номерами j = 1, 2, …, B ₂.
Для будь-якого алгоритму B ₂ £ B ₁.
На графі автомата вхідні слова зіставимо гілкам графа. Вихідні слова на графі автомата позначено кодами вихідних літер. Оскільки B ₂ < B ₁, то коди деяких гілок будуть однаковими. Назвемо ланцюжками попарно різні коди вихідних слів та відповідні їм гілки; число ланцюжків дорівнює B ₂.
Виключимо з розгляду всі гілки графа, на яких відсутні коди вихідних слів, а однаково закодовані гілки об’єднаємо в один лан­цюжок.
Утворений таким чином граф і буде відтворювати конкретний автоматний алгоритм. Різницю числа повного графа (опис гілок) та числа станів, які належать ланцюжкам, назвемо пониженням оцінки числа станів графа автомата U ( l _j ), де l — позначення ланцюжка, j — номер ланцюжка; j = 1, 2, …, B _2. Цілком природньо, що U ( l _j ) — це пониження, отримане за умови врахування j -го ланцюжка.
Будемо добиватися пониження оцінки за рахунок кожного лан­ цюжка. Спочатку розглянемо оцінки пониження для випадку n = 2.
Нижня оцінка одержується за припущення, що всі ланцюжки мають висоту на графі N + 1. Величина U ( l ), в залежності від l , може бути визначена безпосередньо на графі на основі розхо дження вхідних та вихідних слів. Результати розрахунку U ( l ) за l = = 1 — 20 наведені в таблиці.

СТУПЕНІ ПОНИЖЕННЯ ОЦІНКИ r ЗАЛЕЖНО ВІД l

l	1	2	3	4	5	6	7	8	9	10
U ( l )	0	1	2	4	5	7	8	11	12	14
l	11	12	13	14	15	16	17	18	19	20
U ( l )	15	18	19	21	22	26	27	29	30	33

Аналізуючи наведені в таблиці значення U ( l ), звернімо увагу на закономірності функції U ( l ), які може бути виражено таким чином:
, (3)
де  — число можливих розложень числа “ i ” вигляду
i = a 2^k; a = 2, 3, … , i ;
k = 0, 1, … ,[log₂ i ],
де [в] — ціла частина числа “в”. (4)
Так, наприклад, число 1 не має жодного розкладення, число 2 має єдине розкладення:
2 = 2 · 2⁰ ( a = 2; k = 0);
число 3 має також єдине розкладення: 3 = 3 ∙ 2⁰;
число 4 має два розкладення: 4 = 2 ∙ 2¹; 4 = 4 ∙ 2⁰ і т. д.
Вираз (4) може бути розписано докладніше. Будь-яке число i ≥ 2 маємо можливість подати у вигляді i = i ∙ 2⁰, при цьому завжди i = a . Враховуючи це, слід записати:
,
де  та  — числа можливих розкладень вигляду i = a ∙ 2 ^k ; a = 2, 3, …, i ; k = 1, 2,…, [log₂ i ] та k = 2, 3,…, [log₂ i ] відповідно.
Наступні додаткові розкладення можливі для числа 8 і для чисел, кратних 4, потім для 16 і всіх чисел, кратних 8 тощо. Наведений приклад засвідчує: усі числа натурального ряду більше одиниці мають розкладення вигляду i = i ∙ 2⁰, і загальне число таких розкладень дорівнює ( i – 1), всі числа i > 2, які кратні 2¹, мають додаткове розкладення вигляду i /2 ∙ 2¹ і їх число дорівнює ( i /2 – 1), всі числа i > 2² мають додаткове розкладення вигляду  i /4 ∙ 2² і їх число дорівнює ( i /4 – 1). Таким чином додаткові розкладення виникають у точках i /2 ^k , k = 0, 1,…, [log₂ i ], отже:
, (5)
де ω _m = {2⁰, 2¹,…, 2 ^m };
— число можливих розкладень вигляду i = a ∙ 2 ^k ; a = 2, 3, …, i ; k = m , m + 1, …, [log₂ i ].
Із формули (5) випливає властивість функції U ( l ):
— функція цілочислена і позитивна;
— функція монотонно зростає;
— швидкість зростання функції не зменшується, через те що зі зростанням l (це випливає з формули (5)) нові позитивні доданки можуть тільки додаватися.
Ураховуючи ці властивості, визначимо загальне пониження оцінки числа станів U для всіх B ₂ ланцюжків:
за , (6)
де  — підмножина номерів гілок, “згорнутих” у “ j ”-ланцю- жок.
Оскільки конкретне розбиття B ₁ на B ₂ частин визначено тільки для конкретного алгоритму, то в загальному випадку слід розраховувати на мінімальне пониженні оцінки. Із формули (5), властивостей функції U випливає, що U min, відповідаючи нерівності Коші, досягається за l _j = B ₁/ B ₂. Але в загальному випадку B ₁/ B ₂ – – [ B ₁/ B ₂] ≠ 0, тому замість B ₁/ B ₂ випливає необхідність шукати рішення у вигляді l _j = l ₀ = [ B ₁/ B ₂] для деяких номерів j та у вигляді l _j = l ₀ + 1 для інших j . Властивості функції U ( l ) (та наведеної таблиці) також є прикладом того, що в деяких випадках рішення, що мінімізують U , будуть дорівнювати l ₀ + Д l .
За достатньо великих B ₁ можна прийняти l _j = l ₀ , m = [log₂ l ₀ ], тоді формула (5) набуде вигляду
;  (7)

За визначенням, якщо m = [log₂[ B ₁/ B ₂]], то останній член у виразі (7) дорівнює нулю, тоді за формулою прогресії
. (8)
Ураховуючи те, що [ b ] + 1 > b і [ b ] ≤ b , одержуємо
;
.
За l = l ₀ загальне пониження оцінки U визначається формулою:
U = B ₂ U ( l ₀ ). (9)
З урахуванням пониження оцінки верхня та нижня оцінки чис­ла станів ( r _в та r _н) автомата, що реалізує алгоритм із характеристиками В ₁, В ₂, N , визначаться співвідношеннями:
(10)
Підставляючи значення, які входять до (10) з (1), (2), (9), отримаємо
r _в < B ₂( N + 2 log₂ B ₂);
r _н > B ₂( N – log₂ B ₂).
Нижню оцінку r _н маємо за умови, якщо хоч один ланцюжок закінчується на ( N + 1) рівні, решта ланцюжків мають висоту мен­ше, ніж N +1. Тоді
r _н ≥ N – 1 + ( B ₂ – 1) 1/2 ^{N + 1} – log₂ B ₂.
Розглянемо тепер загальний випадок n ≥ 2. Аналогічно міркуючи, отримаємо формулу пониження оцінки для кожного ланцюжка:
,
де t_i — число можливих розложень “ i ” вигляду: i = an^k ; (11)
a = 2, 3, …, i ; k = 0, 1, …, [log _n i].
У розгорнутому вигляді формулу (11) подають таким чином:

де ω _m = { n ⁰, n ¹,…, n^m };
— число можливих розкладень “ i ” вигляду i = an^k ; a = 2, 3, …, i ; k = m , m + 1, …, [log _n i].
Отже,

Використовуючи формулу прогресії, одержуємо


Використовуючи отримані вирази у формулах (1), (2), (9), (10), маємо
r _в ≥ – 1/( n – 1) + B ₂/( n – 1) + B ₂( N – log _n B₂),
r _в ≤ – 1/( n – 1) + B ₂ n /( n – 1) + B ₂( N – log _n B₂).
Аналогічно отримуємо
r _н ≥ N + ( B ₂ – 1)/( n – 1)(1 – 1/( n^{N + 1})) — log _n ( B ₂ – 1) – B ₂.
Отримані оцінки дозволяють використовувати їх для аналізу реальних алгоритмів на стадії оцінки можливих варіантів алгоритмів, оцінки складності вирішуваних задач на ранніх етапах проектування.
Виникає питання щодо можливості використання отриманих результатів для програмних продуктів. Сучасні ЕОМ можна розглядати як універсальні алгоритмічні системи, але за умови нескінченного обсягу оперативної пам’яті. За реальних умов цей обсяг обмежений, але сучасні технології і технічні можливості дозволяють нарощувати обсяг оперативної пам’яті значною мі рою. Тому, для вирішення реальних задач цей допуск цілком мож­на вважати практично виконуваним; при цьому ЕОМ і програ ми, які на ній реалізуються, віднесемо до класу алгоритмічно універ сальних. Це дає можливість у повному обсязі використовувати отримані результати для практичного використання оцінок склад­ності програм для ЕОМ.


СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Лавинский Г. В., Петренко П. А., Семенов Н. П. Проблемы оценки сложности алгоритмов и вычислений при проектировании управляющих систем // УСиМ. — 1977. — № 2. — С. 6—13.
2. Глушков В. М . Введение в кибернетику. — К.: Изд-во АН УССР, 1964. — 324 с.
3. Глушков В. М . Основы безбумажной информатики. — К.: Наука, 1982. — 552 с.
4. Лавинский Г. В . Построение и функционирование сложных систем управления. — К.: Вища шк., 1989. — 336 с.
5. Козмидиади В. А., Мучник А. А . Предисловие // Проблемы математической логики. — М.: Мир, 1970. — С. 3—11.
6. Трахтенброт Б. А. Алгоритмы и вычислительные автоматы. — М.: Сов. Радио, 1974. — 282 с.
7. Алферова З. В., Волович М. А. Сортировка информации с помощью электронных вычислительных машин. — М.: Статистика, 1965.
8. Вавилов Е. Н., Портной Г. П. Синтез схем электронных цифровых машин. — М.: Сов. Радио, 1963 — 394 с.
9. Трахтенброт Б. А. О сложности схем, реализующих многопарамет­рическое семейство операторов // Проблемы кибернетики. — 1964. —   № 12.
10. Глушков В. М. Синтез цифровых автоматов. — М.: Физматгиз, 1962. — 476 с.
11. Лавинский Г. В., Сарычев В. А. Некоторые вопросы оценки стоимости устройств переработки информации // Вопросы построе ния электронных систем передачи, обработки и хранения информации. — К.: Республик. дом НТП, 1968.
12. Трахтенброт Б. А. Сложность алгоритмов и вычислений. — Новосибирск: НГУ, 1967. — 211 с.
13. Бриллюэн Л. Наука и теория информации. — М.: Физматгиз, 1960. — 392 с.
14. Солодов А. В. Теория информации и ее применение к задачам автоматического управления и контроля. — М.: Наука, 1967. — 237 с.
15. Иванов В. В . и др. Методы алгоритмизации непрерывных производственных процессов. — М.: Наука, 1976.
16. Хенни Ф. К., Стирнз Р. Е. Моделирование многоленточной машины Тьюринга на двухленточной // Проблемы математической логики. — М.: Мир, 1970.
17. Хартманис Дж., Хопкрофт Дж. Э. Обзор теории сложности вычислений // Кибернетический сборник — 1974. — № 11.
18. Патерсон М. С. Ограничения на ленту для ограниченных во вре мени машин Тьюринга // Сложности вычислений и алгоритмов. — М.: Мир, 1974.
19. Хенни Ф. К. Вычисления на машине Тьюринга со входом // Проблемы математической логики. — М.: Мир, 1970.
20. Рабин М. Вычисления в реальное время. — Там же.
21. Хенни Ф. К. Вычисления на одноленточной машине Тьюринга с записью на ленте. // Проблемы математической логики. — М.: Мир, 1970.
22. Стрнад П. Распознавание на машине со входом. Там же.
23. Штосс Г. Й. Двухленточное моделирование машины Тьюринга // Сложность вычислений и алгоритмов. — М.: Мир, 1974.
24. Штосс Г. Й. К-ленточное моделирование К-головочных машин Тьюринга // Сложность вычислений и алгоритмов. — М.: Мир, 1974.


Л. Ф. ЄЖОВА , канд. екон. наук, доц.,
С. Ф. ЛАЗАРЄВА , канд. екон. наук, доц.,
С. Д. ПОТАПЕНКО , асп.,
Київський національний економічний університет

Книга: Моделювання та інформаційні системи в економіці: Міжвід. М.Г. Твердохліб

ЗМІСТ

1.	Моделювання та інформаційні системи в економіці: Міжвід. М.Г. Твердохліб
2.	ПРОГНОЗУВАННЯ ФІНАНСОВИХ РИНКІВ ЗА ДОПОМОГОЮ СИСТЕМИ ПІДТРИМКИ ПРИЙНЯТТЯ РІШЕНЬ НА БАЗІ НЕЙРОМЕРЕЖ
3.	ДЕРЖАВНЕ РЕГУЛЮВАННЯ ТА УПРАВЛІННЯ РИЗИКАМИ
4.	ВИЗНАЧЕННЯ ЗАКОНІВ РОЗПОДІЛУ ПОКАЗНИКІВ РИЗИКУ НА ТРАНСПОРТІ
5.	ТЕХНОЛОГІЯ РОЗРОБКИ ЕКСПЕРТНИХ СИСТЕМ У ТАБЛИЧНОМУ СЕРЕДОВИЩІ
6.	ВИКОРИСТАННЯ СУЧАСНИХ ІНСТРУМЕНТАЛЬНИХ ЗАСОБІВ ОБРОБКИ РЕЗУЛЬТАТІВ АНКЕТУВАННЯ У МАРКЕТИНГОВИХ ДОСЛІДЖЕННЯХ
7.	ФІНАНСОВІ ІНДИКАТОРИ ЕФЕКТИВНОСТІ БІЗНЕС-ПРОЦЕСІВ
8.	ПРОБЛЕМИ ОЦІНКИ СКЛАДНОСТІ ПРОГРАМ ДЛЯ ЕОМ
9.	МОДЕЛЮВАННЯ ЕФЕКТИВНОСТІ  РЕКЛАМИ ІТ-КОМПАНІЙ
10.	ОСОБЛИВОСТІ МОДЕЛЮВАННЯ ІНВЕСТИЦІЙНИХ ПРОЦЕСІВ У ЕЛЕКТРОЕНЕРГЕТИЧНІЙ ГАЛУЗІ ПРОМИСЛОВОСТІ
11.	МОДЕЛЬ БАГАТОЦIЛЬОВИХ РIШЕНЬ В УМОВАХ РИЗИКУ З УРАХУВАННЯМ ДИНАМIКИ
12.	СУМІСНЕ ВИКОРИСТАННЯ КОНЦЕПЦІЙ СТРУКТУРНОГО МОДЕЛЮВАННЯ ТА БАГАТОВИМІРНИХ БАЗ ДАНИХ ЯК ІНСТРУМЕНТ СТВОРЕННЯ ЕФЕКТИВНОЇ СППР
13.	ЕМПІРИЧНІ ТА ЕКОНОМЕТРИЧНІ МОДЕЛІ ОЦІНКИ РОЗВИТКУ ІНФОРМАЦІЙНОЇ СФЕРИ
14.	АНАЛІЗ ІНВЕСТИЦІЙНИХ ПРОЕКТІВ ПІДПРИЄМСТВА НА БАЗІ МЕТОДІВ НЕЧІТКОЇ МАТЕМАТИКИ
15.	МОДЕЛЮВАННЯ ТА ОПТИМІЗАЦІЯ ДИСКРЕТНИХ ЕВОЛЮЦІЙНИХ СИСТЕМ У ВИПАДКОВОМУ СЕРЕДОВИЩІ
16.	ЕКОНОМІКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ФУНКЦІОНУВАННЯ НАФТОГАЗОВОЇ КОМПАНІЇ ЯК ЦІЛІСНОЇ СКЛАДНОЇ СПЕЦИФІЧНОЇ СИСТЕМИ
17.	СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
18.	ЕКОНОМІКО-МАТЕМАТИЧНА МОДЕЛЬ ГРОШОВОГО ПОТОКУ НА БАНКІВСЬКИХ РАХУНКАХ
19.	ОЦІНЮВАННЯ ТОЧОК ЛАФФЕРА НА ОСНОВІ ДВОПАРАМЕТРИЧНОГО МЕТОДУ
20.	МЕТОДИЧНЕ, МАТЕМАТИЧНЕ ТА ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ВИРІШЕННЯ ЗАДАЧ ЛОГІСТИКИ

На попередню



Додати в закладки

  
Переклад Translate