Від наукового результату до комп’ютерної технології

Computer technologies for solution of complex problems in calculus and applied mathematics with given characteristics of the accuracy and operation speed have been developed. They are based on the computation error theory, the common optimal algorithm theory, and application of computation optimizat...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2017
Автори:	Zadiraka, V. K., Sergienko, I. V.
Формат:	Стаття
Мова:	Українська
Опубліковано:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2017
Онлайн доступ:	https://journal.iasa.kpi.ua/article/view/109716
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	System research and information technologies
Завантажити файл:

Репозитарії

System research and information technologies

_version_	1867334318791065600
author	Zadiraka, V. K. Sergienko, I. V.
author_facet	Zadiraka, V. K. Sergienko, I. V.
author_institution_txt_mv	[ { "author": "V. K. Zadiraka", "institution": null }, { "author": "I. V. Sergienko", "institution": null } ]
author_sort	Zadiraka, V. K.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2018-04-11T11:06:21Z
description	Computer technologies for solution of complex problems in calculus and applied mathematics with given characteristics of the accuracy and operation speed have been developed. They are based on the computation error theory, the common optimal algorithm theory, and application of computation optimization reserves. Some examples of high-quality solution of complex problems are considered.
first_indexed	2025-07-17T10:23:02Z
format	Article
fulltext	© В.К. Задірака, І.В. Сергієнко, 2008 Системні дослідження та інформаційні технології, 2008, № 2 7 TIДC ТЕОРЕТИЧНІ ТА ПРИКЛАДНІ ПРОБЛЕМИ ІНФОРМАТИКИ УДК 519.6 ВІД НАУКОВОГО РЕЗУЛЬТАТУ ДО КОМП’ЮТЕРНОЇ ТЕХНОЛОГІЇ В.К. ЗАДІРАКА, І.В. СЕРГІЄНКО Побудовано комп’ютерні технології розв’язування складних задач обчислю- вальної та прикладної математики із заданими характеристиками якості за точністю та швидкодією. Технології засновано на теорії похибок обчислень, загальній теорії оптимальних алгоритмів та використанні резервів оптимізації обчислень. Розглянуто приклади розв’язування складних задач із високою якістю. Вычислительная математика — часть ин- форматики, относящаяся к методологии примене- ния ЭВМ для решения задач науки, техники, произ- водства и практически всех областей человеческой деятельности А.Н. Тихонов, Энциклопедия математики На сьогодні «легкі» задачі обчислювальної на прикладної математики вже перерішані. Лишилися «складні», тобто такі, які неможливо розв’язати із заданою якістю за допомогою штатного математичного забезпечення ЕОМ. Саме ці задачі стимулюють створення нових поколінь ЕОМ, сучасних чи- сельних методів їх розв’язування та методів діагностики якості наближеного розв’язку задачі за точністю та швидкодією. Прикладами таких задач є ви- сокоточні задачі, задачі математичного моделювання, нелінійні, великої розмірності, задачі, близькі до NP-повних, інформаційної безпеки тощо. Все це спонукає, не зважаючи на нові перспективи в розв’язанні склад- них задач шляхом використання Grid-систем, методів системного аналізу [1, 2] тощо, активізувати роботи в галузі теорії похибок, загальної теорії оп- тимальних алгоритмів, виявлення та уточнення апріорної інформації про задачу, виявлення та використання резервів оптимізації обчислень і на базі відповідних фундаментальних досліджень запропонувати комп’ютерні тех- нології розв’язання задач обчислювальної та прикладної математики із зада- ними характеристиками якості за точністю та швидкодією. Використання таких технологій дасть змогу або розв’язати задачу із за- даною якістю, або дати поради замовнику (що треба додатково зробити для розв’язання задачі), або довести: при даній інформації про задачу її немож- ливо розв’язати із заданою якістю. В.К. Задірака, І.В. Сергієнко ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 8 Оскільки аналіз Фур’є широко використовується в обчислювальній практиці при розв’язанні багатьох класів задач (наприклад, краєві задачі для рівнянь в частинних похідних, спектральний та кореляційний аналіз випад- кових процесів, розпізнавання образів, цифрова голографія та томографія, медична електроніка, інформаційна безпека), то будемо ілюструвати загаль- нотеоретичні положення цієї роботи на прикладі задачі наближеного обчис- лення перетворення Фур’є. 1. АНАЛІЗ ЯКОСТІ НАБЛИЖЕНОГО РОЗВ’ЯЗКУ ЗАДАЧ Головне, на що треба звернути увагу — це гарантовані оцінки якості харак- теристик обчислювального алгоритму. Спершу розглянемо таку його характеристику, як точність. Гарантією якості похибки є комплексний підхід до оцінки точності, який враховує різні джерела її накопичення (реальний обчислювальний процес супроводжують такі види похибок: неусувна за рахунок неточності вхідної інформації про задачу, а також методу та заокруглення). І тільки врахування всіх трьох видів похибки (так званої повної похибки) дасть змогу гарантувати оцінку якості наближеного розв’язку задачі. На жаль, у більшості результатів з обґрунтування тих чи інших методів наближеного розв’язання задач, як правило, проведено аналіз лише одного виду похибки і не врахована реальна обчислювальна ситуація. Через це їх можна використовувати для з’ясування якості наближеного розв’язку задачі з відповідними застереженнями. Обчислювальна складність часто визначається вимогами до точності наближеного розв’язку, співвідношеннями складових повної похибки, за- лежністю похибки від типу, структури, об’єму вхідних даних та їх точності, розрядної сітки комп’ютера, правила заокруглення, типу оцінки похибок. Розглянемо вплив величини частки окремих складових повної похибки на можливість отримання ε-розв’язку задачі за заданий час. Інформація 0I , що визначає клас задач, і )( fI n , що стосується конкретної задачі, як прави- ло, задані наближено. Нехай TI0 , )( fI T n — точні значення цієї інформації, а інформація 0I , )( fI n — точна для деякої задачі φ; fR і ϕR — точні розв’язки задач відповідно до TI0 , )( fI T n і 0I , )( fI n ; α fR , α ϕR — набли- ження відповідно до fR , ϕR , які отримані деяким алгоритмом в припу- щенні, що обчислення виконуються точно (без заокруглень); τ fR , τ ϕR — розв’язки, отримані тим же алгоритмом з заокругленнями. Тоді для повної похибки наближеного розв’язку ),,( YXIE ( YX , — вектори параметрів, що характеризують відповідно алгоритм і ЕОМ) можна записати =−+−+−=−= )()()(),,( τα ϕ α ϕϕϕ τ ffff RRRRRRRRYXIE )()()( •+•+•= τµ EEEH , )()()()( τµ ρρρρ EEEE H ++≤ , Від наукового результату до комп’ютерної технології Системні дослідження та інформаційні технології, 2008, № 2 9 де )(•ρ — деяка міра похибки наближеного обчислення розв’язку задачі; )(•HE — неусувна похибка за рахунок неточності вихідної інформації про задачу; µE — похибка методу; τE — похибка заокруглень. Розглянемо можливий розподіл доданків в умові ++ )()( µρρ EEH ερ τ ≤+ )(E з урахуванням обмежень на час розв’язку задачі. Замінемо цю умову на такі: ττµµ δρδρδρ ≤≤≤ )(,)(,)( EEE HH , де τµααεαδ ,,,0,1, Hii i iii =≥=≤ ∑ . Згаданий розподіл визначається вибором чисел }{ iα . Невдалий роз- поділ може значно ускладнити нашу задачу. Наприклад, при −≤ ε0 ερ <<− )( HE необхідно накласти жорсткі обмеження на обидві інші скла- дові повної похибки ερερρ τµ <<−<<+ )()()( HEEE . Як відомо, оцінки можуть бути апріорні та апостеріорні, мажорантні та асимптотичні, детерміновані та стохастичні. Кожний з цих типів оцінок має свої «плюси» і «мінуси». Так, апріорні мажорантні детерміновані оцінки, з одного боку, гарантовані, достатньо легко обчислюються, а з другого — оці- нка може бути дуже завищеною і малозастосовною для подальшого аналізу. Ситуація не змінюється в класі задач, якщо навіть оцінка не покращується. Задача, на якій досягається ця оцінка, може бути нетиповою для класу, тому можливості обчислювального алгоритму на інших задачах класу залиша- ються не використаними. Асимптотичні апостеріорні оцінки можуть бути достатньо близькими до похибки, але така близькість досягається при значеннях параметру з пев- ної області асимптотики, що не завжди зручно для практичних обчислень. Крім того, у обчисленні таких оцінок використовується розв’язок задачі, а для його побудови потрібен значний об’єм обчислень. Доцільність використання оцінок певного типу визначається обчислю- вальною ситуацією. Особливою цінністю користуються непокращувальні оцінки. З теоре- тичної точки зору вони є оцінками найвищої якості, наприклад, оцінка кон- станти Лебега [3]. Розглянемо ітераційний поліном вигляду )(),(,,)( 1 1,),( 1 2 00 jjn j n i j n j k jjk n k k kn ue n u τϕτϕτττϕατατϕ π === + == ++ = − = + ∑∑ . Теорема 1. Має місце оцінка ( ) ( ) ( ) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ⎥⎦ ⎤ ⎢⎣ ⎡ − + + ++ ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ++ ≤+ ,непарногодля)(max 2 1ln 1 12 ,парногодляmax12ln24 , nun n С nun u j j j j n ϕ ϕ πππτϕ (1) В.К. Задірака, І.В. Сергієнко ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 10 ( 577215,0=С — стала Ейлера), причому її не можна покращити в тому сенсі, що існує функція )(tψ , для якої ( ) ( ) ( )j j n u u n Onuu ψ πππ ψ max112ln24,max ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛+⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ++=+ . Тобто оцінка (1) є асимптотично досяжною. Константа Лебега відіграє важливу роль у теорії наближень. Знаю- чи її оцінку, можна легко отримати оцінку похибки наближення функції ( ),)( γτϕ C∈ де γ — границя одиничного кола, інтерполяційним по- ліномом ( )τϕ,+ nu (наприклад, для парного n ) — ≤− + ),()( τϕτϕ nu ( ) ( )γϕ πππ ,12ln241 nEn ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ +++≤ , де ( )γϕ,nE — елемент найкращого на- ближення )(τϕ в )(γC ( ) ( ) ( )r n n n cuu E 12 , + ≤ + πγϕ , …,2,1,0=r , …,2,1,0=n Треба зауважити, що з практичної точки зору непокращувальні оцінки не завжди нас задовольняють, бо є досяжними на екзотичних задачах, які на практиці майже не зустрічаються. Через це для практичних задач вони за- вищені. Має сенс використовувати поряд з детермінованими і ймовірнісні оцінки похибки. Наведемо детерміновано-ймовірнісні оцінки точності обчислення оцінок математичного сподівання, перетворення Фур’є, згортки, коре- ляційної функції, які часто використовуються при розв’язанні задач цифро- вої обробки сигналів, алгоритмізації неперервних виробничих процесів, тео- рії оптимізації тощо. Оскільки ці ймовірнісні характеристики зустрічаються досить часто, є сенс дослідити оцінки повної похибки і окремих її видів відповідних алго- ритмів їх наближеного обчислення, які в подальшому будуть використані в згаданих вище комп’ютерних технологіях. Почнемо з оцінки математичного сподівання випадкової величини x . ∑ = = N x N xM 1 * 1)( υ υ . Припустимо, що замість υx ми маємо справу з ευx , причому дисперсії ( ) 2εευυ ≤− xxD . Тоді замість ( )xM * отримаємо ∑ = = N x N xM 1 * 1)( υ ευε . Крім того, припускаючи ευυ xx − попарно незалежними, будемо мати [ ] ( ) N xxD N xMxMD N 2 1 2 1)()( ε υ ευυε ≤−=− ∑ = . Від наукового результату до комп’ютерної технології Системні дослідження та інформаційні технології, 2008, № 2 11 Звідси, в силу відомої нерівності Чебишева ( )( ) 2 11 K xDKxMxP −>≤− , знаходимо, що N xMxM ε ε 5,4)()( ≤− з ймовірністю 0,95. Для оцінки похибки заокруглення зауважимо, що при додаванні двох нормалізованих чисел х та у на ЕОМ (з плаваючою комою), що мають τ двійкових розрядів для представлення мантиси числа, отримуємо число τττ yxz ⊕= , де ⊕ означає додавання на ЕОМ з заокругленням, причому з точністю до перших степенів τ−2 [ ]( ) τ τττ ηξξηξξ −≤++++=⊕= 2,,,1)1()1( yxyx yxyxz . Аналогічно ( ) ( )( ) τ τττ ηξξηξξ −≤+++=⊗= 2,,,111 yxyx yxyxz . Застосовуючи ці формули до рекурентного співвідношення Nrxx N x N r r r ,2,11 1 1 1 = ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⊕⊕⊗=⊕⊗∑ ∑ = − =υ ε υ ευευ τττ , отримаємо ( ) ( )( )( ) ( )( )∑ = − ++××+++= N Nxx N xM 1 21 * 11...1111 υ υευτε ηηηηξ ευ , .2,, τηηξ ευ −≤ix Звідси ( ) ( ) ( )∑ = +−− ⎥⎦ ⎤ ⎢⎣ ⎡ −+≤− N N x N xMxM 1 2 1211 υ υτ ευτεε . Якщо 1,02 <−τr , то .206,11)21( ττ −− <−+ rr Тому при умові ( ) 1,021 <+ −τN ( ) ( ) ( ) ( ) τ ευ υυ τ ευτεε υ − = − + ≤+−≤− ∑ 2 2 3max06,12206,1 1 NNxNx N xMxM N . При великому N похибка заокруглення може бути значною. Для того щоб уникнути цього недоліку, необхідно здійснювати додавання на ЕОМ по можливості без заокруглення. Один із таких способів діє, якщо нор- малізовані числа ( ) ( ) ( ) ,0...0...,02 1 21 − = τ υυυ ευ υ s P aaax N,1=υ мають не більше s значущих цифр, причому В.К. Задірака, І.В. Сергієнко ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 12 rxrs 2, <−< ευτ . Тоді очевидно ∑∑ −−−− == =⊕ rsrs xx ττ υ ευ υ ευ 2 1 2 1 . Якщо rsN −−>> τ2 , то слід використати формулу ( ) ( ) ∑∑ ∑∑ −− −− −− ⋅+== + ⋅== += N m m K k k N rs rs rs x N x N x N τ τ τ υ ευ υ ευ υ ευ 210 21 21 111 , ( ) ( ) rsrs mNm −−−− +≤≤+ ττ 2221 . Другий спосіб полягає у використанні комп’ютерної арифметики бага- торозрядних чисел [4]. Розглянемо оцінку повної похибки ∆ оцінки автокореляційної функції ( ) ( )( ) ( )( )( )∑ − = −∆+−∆ − =+ jL LLxx MtjxMtx jL ttR 1 * ,,, * ,,, * 1, υ τετετετε υυθ , Mjttj ,1, 2 = ∆ ≤∆−θ ; ( ) ...,1,0,* +==+ MjttRxx θ для випадкової функції вигляду )()()( tntytx += , Ctxtx tt ≤− )()(max 21 , 21 , де )(ty — стаціонарна нормально розподілена функція, для якої 0)( =θyyR , θθθθψθθθ ≤≤≥ ),()()(, yyyy RR ; )(tn — довільна функція, що не зале- жить від )(ty і 0,)( >≤ δδtn з ймовірністю 0,99; )(tx у вузлах t∆υ задана з похибкою ε . Тоді з ймовірністю 0,95, з точністю до малих першого поряд- ку відносно ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ∆ 2 ,1, t L yωδ маємо ( )( )1=θψ [5] ( ) τδω −++ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ++⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ∆≤∆ 2806,1104 2 2 Lc L Mtc y , де ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ∆ 2 t yω — модуль неперервності функції )(ty . На практиці зазвичай відома додаткова інформація про мажорантну функцію ( )θψ , що дозволяє отримати більш точні оцінки. Якщо ( ) θ θθψ −=1 , то ( ) τδω −++ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ + ++⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ∆≤∆ 2806,1 2 3 4 54 2 2 Lc L Mtc y . Від наукового результату до комп’ютерної технології Системні дослідження та інформаційні технології, 2008, № 2 13 Якщо ( ) θ θ θψ a e − = , то ( ) τδω − − − − ++ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎟⎟ ⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎜ ⎝ ⎛ − ++++⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ∆≤∆ 2806,1 1 4154 2 2 2 1 2 2 2 Lc e ee L tc L a L a L aj y . Дві останні оцінки мають місце з ймовірністю 0,95 та з точністю до ма- лих першого порядку відносно ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ∆ 2 ,1, t L yωδ . При великих L оцінка похибки в наведених оцінках ∆ може бути ве- ликою за рахунок похибки заокруглення, яку можна значно зменшити, ви- користовуючи непрямий метод обчислення ),(* θ+ttRxx з використанням теореми про дискретну згортку функцій та алгоритму швидкого перетво- рення Фур’є (ШПФ) [3]. ( ) 2 1 ** 206,18 EExxxx xNRRf τγ −⋅<− , де LMN +=1 , γ21 =N . Для квадратурної формули типу Файлона наближеного обчислення пе- ретворення Фур’є фінітної функції з носієм ],0[ T ∫ −= T ti dtetfI 0 )()( ωω наведемо спочатку для порівняння детерміновану та ймовірнісну оцінки не- усувної похибки H∆ (щоб продемонструвати, наскільки ймовірнісна оцінка точніша за детерміновану). Нехай δ — максимальна похибка, з якою задана )(tf на [ ]T,0 (для де- термінованої оцінки), або, припускаючи, що можливі похибки iξ задання )(tf у вузлах ,)()(~ iii tftf ξ+= 1,0 −= ni є взаємнонезалежними випадковими величинами, розподіленими рівномірно на [ ]δ,0 . Оцінки мають вигляд: T•≤∆ δH — детермінована; n T 3 5 H δ ≤∆ — з ймовірністю 0,96 ( n — кількість вузлів). (2) Для отримання гарантованої оцінки якості наближеного розв’язку за- дачі треба враховувати всі види похибок (неусувну H∆ , методу M∆ , заок- руглення C∆ ), які реально супроводжують обчислювальний процес. У зв’язку з цим наведемо оцінку повної похибки квадратурної формули типу Файлона В.К. Задірака, І.В. Сергієнко ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 14 ( ) ( )∑ − = − ∆−− = 1 0 1 n j ti j ti n jetf i eI ω ω ω ω для класу [ ]TC ,0 . Має місце така теорема. Теорема 2 [3]. Нехай ( ) [ ]TCtf ,0∈ , виконується оцінка (2). Тоді з ймо- вірністю 0,96 маємо таку оцінку повної абсолютної похибки ∆ квадратурної формули ( )ωnI : ≤∆+∆+∆≤∆ ЗMH ( ) [ ] ( ) ( ) r rnrn r f II T n t ω ωω εδω ττ ImRe 231max2 3 5 ШПФ + ++⎥ ⎦ ⎤ ⎢ ⎣ ⎡ +∆≤ −− , де ШПФ ε — похибка заокруглення алгоритму ШПФ. Ми приділили достатньо уваги якісним конструктивним оцінкам (дете- рмінованим, ймовірнісним, асимптотичним) повної похибки алгоритмів розв’язування деяких часто використовуваних задач. На використанні тако- го типу оцінок ґрунтується комп’ютерна технологія розв’язування задач із заданими характеристиками якості (див. розд. 6). 2. ВИЯВЛЕННЯ ТА УТОЧНЕННЯ АПРІОРНОЇ ІНФОРМАЦІЇ Відомості про вихідну інформацію задачі та її якість дуже важливі з бага- тьох причин. Відмітимо деякі з них. • Чим якісніша інформація про задачу, тим якісніший наближений розв’язок, на який ми можемо розраховувати. • Максимальне використання усієї наявної інформації про задачу дає змогу звузити клас задач, що розв’язуються, і тим самим підвищує по- тенційну спроможність чисельного методу. • Чим точніша вихідна інформація, тим точніші оцінки похибки і менша область невизначеності наближеного розв’язку задачі. • На аналізі оцінок похибки ґрунтується комп’ютерна технологія розв’язування задач із заданими характеристиками якості за точністю і швидкодією. Зупинимося на деяких аспектах виявлення та уточнення апріорної інформації про задачу. Для отримання якісних розв’язків задач необхідна відповідна апріорна інформація. Наприклад: порядок похідної, константи, які її обмежують, кон- станта Гельдера і відповідний показник (для задач відновлення функцій і функціоналів). Корисною може бути також інформація про геометричні вла- стивості (опуклість, монотонність, кількість екстремумів та інші властивос- ті). Така інформація необхідна, щоб отримати оцінку похибки наближеного розв’язку. Якщо ця інформація з достатньо великою похибкою, то неточни- ми будуть і висновки про якість розв’язку. Від наукового результату до комп’ютерної технології Системні дослідження та інформаційні технології, 2008, № 2 15 Отже, отримання якісної апріорної інформації має важливе значення при розв’язанні прикладних задач. Таку інформацію отримують у фахівців, які добре знають фізичне явище, що ми вивчаємо. Ця інформація може бути отримана і за допомогою алгоритмів виявлення та уточнення апріорної інформації. Наприклад, якщо апроксимується функція з інтерполяційного класу Ліпшица ε,,NLCF ≡ [3], а відомі не самі L і ε , а лише наближення до них, то у таких випадках доцільно використовувати для апроксимації функції методи нев’язки та квазірозв’язків [6]. Для класу ε,,NLCF ≡ апроксимуюча функція є розв’язком задачі i iFf εmaxmin ∈ . (3) Іншими словами, метод квазірозв’язків полягає в знаходженні функції, що найменше відхиляється від заданого набору точок ( )ii fx ~, , 1,0 −= Ni , iii ff ε+= ~ . Розв’язок задачі (3) є лінійним сплайном ( )LxS , , у якого максимальне відхилення від заданих точок ( )ii fx ~, , 1,0 −= Ni , мінімальне [6]. ( ) ( )ii ii i i ff xx xx fLxS ˆˆˆ, 1 1 − − − += + + , [ ]1, +∈ ii xxx , 1,0 −= Ni , 2 ~~ ˆ −+ − = ii i ff f , ( )[ ]ijj Nj i xxLff −±= ≤≤ ± ∓~max~ 1 , 1,0 −= Ni . (4) Часто кількісна апріорна інформація, задіяна у визначенні класу F , за- дається у вигляді обмежень на деякий функціонал. Для класів NLC , і ε,,NLC в якості такого функціоналу ( )fΦ є рівномірна норма похідної. Будемо ап- роксимувати функцію )(xf функцією, яка є розв’язком задачі ( )f Ff Φ ∈ min . (5) Розв’язком задачі (5) є лінійний сплайн ( )MxS , , що визначається співвідношеннями (4) із заміною константи Ліпшица на константу M , де ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − −−− = >≤≤ ij ijij ijNj xx ff M εε max;0max 1 . Розглянуті алгоритми апроксимації є оптимальними за порядком точ- ності з константою, яка не перевищує 2 (навіть якщо порівнювати з випад- ком точного задання L і ε ) [3]. Однак наближення, які отримані за методом нев’язки або квазірозв’язків, можуть виявитися набагато точнішими за оптимальний за точністю алгоритм апроксимації, тому що пошук цих розв’язків направлений на уточнення апріорної інформації. Застосування методів нев’язки та квазірозв’язків є одним із способів використання ре- зервів оптимізації за точністю. В.К. Задірака, І.В. Сергієнко ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 16 3. РЕЗЕРВИ ОПТИМІЗАЦІЇ ОБЧИСЛЕНЬ ТА ЇХ ВИКОРИСТАННЯ Складні задачі (які не розв’язуються «штатним» математичним забезпечен- ням і для розв’язання яких використовуються певні резерви оптимізації об- числень) завжди були каталізатором створення нових поколінь ЕОМ та роз- витку чисельних методів. Розвиток теорії обчислень показує, що використання оптимальних за точністю та швидкодією обчислювальних алгоритмів при розв’язуванні дея- ких важливих класів задач (оптимізації, цифрової обробки сигналів тощо) дає ефект, порівняний з використанням нової елементної бази та архітек- тури ЕОМ [3, 7]. Використання резервів оптимізації обчислень дозволяє підвищити по- тенційну спроможність чисельних методів і розв’язати задачу із заданою якістю та надати користувачеві певні рекомендації, щоб перевести задачу з розряду нерозв’язних у розв’язні, або довести, що при даній інформації про задачу її розв’язання із заданою якістю неможливе. Наведемо резерви оптимізації обчислень. • Виявлення та уточнення апріорної інформації про задачу (див. розд. 2). • Звуження класу задач за рахунок максимального використання інформації про задачу. • Використання оптимальних та близьких до них інформаційних опе- раторів [8,9]. • Використання якісних оцінок обчислювальних алгоритмів (див. розд. 1). • Використання оптимальних та оптимальних за порядком (точністю та швидкодією) алгоритмів в умовах найбільш повного використання апріорної інформації про задачу [3]. • Використання алгоритмів для високоточних обчислень [5]. • Використання схем обчислень, які мінімізують швидкість накопи- чення похибки заокруглень. • Підвищення точності обчислень параметрів обчислювального процесу. • Узгодження обчислювального алгоритму з архітектурою комп’ю- тера. • Розпаралелювання обчислень. • Використання результатів тестування алгоритмів-програм [10]. • Розробка спеціалізованих обчислювачів (вибір архітектури, який найкращим чином узгоджується з обчислювальним алгоритмом розв’язу- вання задач даного класу). Перераховані резерви оптимізації обчислень використовуються в комп’ютерних технологіях розв’язування задач прикладної та обчислюваль- ної математики із заданими характеристиками якості [11]. 4. ОПТИМАЛЬНІ ЗА ТОЧНІСТЮ ТА ШВИДКОДІЄЮ АЛГОРИТМИ Не завжди можна отримати ε-розв’язки деяких задач (хоча, в принципі, вхідної інформації може бути для цього достатньо) або не можна перекона- Від наукового результату до комп’ютерної технології Системні дослідження та інформаційні технології, 2008, № 2 17 тися, що ε-розв’язки досягнуті. В таких випадках важливо мати оптимальні за точністю алгоритми (які з метою покращення точності максимально пов- но використовують всю наявну інформацію про задачу), а також апо- стеріорні оцінки похибки (у порівнянні з апріорними вони більш точні). Для побудови оптимальних за точністю алгоритмів можна використати метод «капелюхів» М.С. Бахвалова або «метод граничних функцій» (МГФ), роз- роблений в Інституті кібернетики ім. В.М. Глушкова НАН України [12, 13]. МГФ, як правило, застосовується в умовах найбільш повного використання апріорної інформації про задачу і дає можливість, на відміну від методу «капелюхів», будувати оптимальні за точністю алгоритми. При цьому треба зважати на те, що максимальне врахування апріорної інформації про задачу покращує точність, але збільшує складність алгоритму. Як приклад розглянемо задачу побудови оптимальних за точністю та близьких до них квадратурних формул наближеного обчислення інтегралу від швидкоосцилюючої функції вигляду ( ) ( )∫= 1 0 1 sin dtttfI ωω , де ( ) Ftf ∈ , πω 2≥ та інформація про ( )tf задана не більше ніж в N точ- ках ( ){ } 1 0 −N jtf . Наведемо результати для таких класів підінтегральних функцій: Ліпшиця ( LC ) та інтерполяційного класу Ліпшиця ( NLC , ) [13]. Інтерполяційні класи максимально використовують всю інформацію про підінтегральну функцію і за рахунок цього звужують клас LC до NLC , , функції якого не розрізняються квадратурною формулою. Теорема 3. Нехай ( ) LCtf ∈ , виконується умова A: нулі tωsin співпадають з [ ] 1+πω вузлами jt квадратурної формули; сітка є рівномірною. Тоді квадратурна формула типу середньої точки для інтегралу ( )ω1I ∑ ∫ − = + − = 1 0 1 2/1 2/1 sin N j t t j j j dttfR ω оптимальна за точністю при ω≥N та [ ] 1+= πωN , причому для опти- мальної оцінки похибки на класі LC має місце оцінка знизу ( ) [ ] ⎪ ⎪ ⎩ ⎪⎪ ⎨ ⎧ += ≥ ≥ .1,2 ,, 2, πω ωπ ω πω NL N N L CV LN Теорема 4. Нехай ( ) NLCtf ,∈ , виконується умова А. Тоді квадратурна формула ( )∑ ∫ − = ∗ + = 1 0 2 1 sin N j t t j j dtttfR ω , В.К. Задірака, І.В. Сергієнко ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 18 де ( ) ( ) ⎪ ⎪ ⎩ ⎪⎪ ⎨ ⎧ ≤≤ ≤≤∆−+ ≤≤ = ++ ,, ,,sin , 11 , * jjj jjjjj jjj tttf tttfttLf tttf tf L ftt t jjj j 22 1 ∆ − + = + , L ftt t jjj j 22 1 ∆ + + = + , jjj fff −=∆ +1 , є оптимальною за точністю при ω≥N та [ ] 1+= πωN , причому має місце оцінка знизу ( ) ( ) [ ] [ ] ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ += ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ∆ − + + ≥⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ∆ − ∆ + ≥ ∑ ∑ = − = + .1, 4 sin42 ,, 4 sin 2 sin 2 sin4 , 0 2 2 0 22 12 , πω ω ωπω π πω ω ωωω ω ω πω N L fL N L ft ttL CV j j N j jj jj NLN У роботах [3, 13] наведено отримані квадратурні та кубатурні формули ще для 20 класів підінтегральних функцій. Скориставшись оптимальним за точністю алгоритмом розв’язування даної задачі і апостеріорною оцінкою похибки, нерідко можна отримати розв’язок, який задовольняє користувача, або зробити висновок, що такий розв’язок отримати неможливо. 5. ВИКОРИСТАННЯ РІЗНИХ МОДЕЛЕЙ ОБЧИСЛЕНЬ Як було зазначено вище, вибір моделі обчислень для розв’язання задачі є одним із резервів оптимізації обчислень. Конкретизуємо модель обчислень і розглянемо різні поняття склад- ності. Вагомим є поняття складності задачі — це мінімальна вартість побу- дови ε-наближення. Однією із частин моделі складності обчислень є набір найпростіших операцій. Алгоритми із скінченного числа найпростіших операцій назива- ють доступними. Звичайна модель для однопроцесорної ЕОМ. Нехай ρ — найпростіша операція. Найпростішими можна назвати, наприклад, арифметичні операції, операції порівняння, обчислення максимуму з n чисел, арифметичного ко- реня, інтегралу, лінійного або нелінійного функціоналу. Позначимо складність операції ρ через )(comp ρ і будемо вважати цю величину скінченною. Вибір множини P найпростіших операцій та визначення їх складності — це важлива проблема і її вирішення пов’язано з класом задач, що розв’язується. Питання в тому, яка повинна бути множина P , щоб зада- чу з певного класу можна було розв’язати з меншою складністю. Від наукового результату до комп’ютерної технології Системні дослідження та інформаційні технології, 2008, № 2 19 Нехай PN — інформаційний оператор. Назвемо його допустимим від- носно P, якщо існує програма обчислення ( )fN P Ff ∈∀ , яка складається із скінченного числа найпростіших операцій. Якщо це операції ,,...,1 Nρρ то ( )( ) ( )∑ = = N i iP fN 1 compcomp ρ . Назвемо число ( )( )fN Pcomp інформаційною складністю оператора ( )fN P . Нехай алгоритм φ використовує допустиму інформацію ( )fN P . Для того щоб знайти ( )( )fN Pϕ , треба обчислити ( )fNy P= та ( )yϕ . Назвемо алгоритм φ допустимим відносно P , якщо існує програма обчислення ( )yϕ для ( )fNy P= Ff ∈∀ , яка складається із скінченного числа найпростіших операцій. Якщо це, скажімо, операції ,,...,1 jqq то ( )( ) ( )∑ = = j i iqy 1 compcomp ϕ . Назвемо число ( )( )yϕcomp номінальною складністю алгоритму ( )yϕ . Як приклад розглянемо оцінку інформаційної та комбінаторної склад- ності деяких алгоритмів відновлення функцій. Нас цікавить відповідь на питання: яка мінімальна кількість інфо- рмаційних операторів про функцію, що відновлюється, і який мінімальний об’єм пам’яті ЕОМ потрібно використати для побудови ε-розв’язку задачі, тобто відновлення функції з деякого класу з точністю ε , 0>ε . Це, по суті, задача стиснення інформації про функцію, поставлена мовою теорії апрок- симації. В якості класу функцій розглянемо клас Ліпшиця. Нехай ρ CC ,1 — клас функцій, що задовольняє на відрізку [ ]ρ,0r умову Ліпши- ця з константою L і таких, що ( ) Cf ≤0 ; Φ — метричне розширення класу ρ CC ,1 , яке зберігає матрицю; )( fT Φ ε — таблиця ρ CCf ,1∈ , яка є впорядкованим набором ( )pttt ,...,1= елементів деякої множини ω та розшифровуючого алгоритму (р.а.) ( )tA , який набору t ставить у відповідність деякий елемент Φ∈ϕ такий, що εϕρ ≤Φ ),( f ; ( )( )fTP Φ ε — об’єм таблиці (мінімальна кількість двійкових розрядів, необхідна для запису параметрів таблиці); ( ) ( )ρ ε ρ ε CC CNCH ,12,1 log= — абсолютна ε -ентропія простору ρ CC ,1 , де ( )ρ ε CCN ,1 — число елементів найбільш економного ε2 покриття множини ρ CC ,1 ; В.К. Задірака, І.В. Сергієнко ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 20 ρ ε,1Φ — сукупність функцій ( )xϕ , які можна представити на відрізку r у вигляді ( ) ( )∫ ∗= x dttLx 0 ϕϕ , де ( )t∗ϕ — функція, яка приймає значення 1± і є постійною на кожному з інтервалів виду ( ) L kt L k k εεδ << −1: , ⎥⎦ ⎤ ⎢⎣ ⎡= ε ρLk ,1 ; ( )ρε CN C ,1 — найкраща гарантована точність на класі ρ CC ,1 та множині пасивних алгоритмів. Таблицею ( )fT Φ ε може слугувати послідовність з 2log2 +⎥⎦ ⎤ ⎢⎣ ⎡+ ε α C двійкових розрядів 21 ,,...,,,,..., 2121 KK βββααα , де ⎥⎦ ⎤ ⎢⎣ ⎡= ε ρ α L , 11 +=αK , 1log22 +⎥⎦ ⎤ ⎢⎣ ⎡= ε CK , які в залежності від )(* tϕ обираються таким чином: 0=Pα , якщо на елементарному відрізку kδ , α,1=k 0)(* <tϕ і 1=Pα в іншому випадку, 1,1 Kp = ; 2 ,...,1 Kββ — коефіцієнти двійкового розкладу числа )0(f . Вираз ∫+≈ x dttfxf 0 * )()0()( ϕ є р.а., що по t обчислює )(xf в будь-якій точці rx∈ з точністю ε . При цьому [14] ( )( ) 2log2 +⎥⎦ ⎤ ⎢⎣ ⎡+=Φ ε αε CfTP , ( ) 2log2log 2,12 ++≤≤−+ εε ρ εε ρ ρ ε CLCHCL C , ( )C≤ε . Із наведеного співвідношення видно, що для класу ρ LC ,1 не існує способів побудови таблиць з суттєво меншим об’ємом, ніж наведений. Оцінки комбінаторної складності (затрати ресурсів ЕОМ на «внутрішні потреби» алгоритмів) та порівняльний аналіз різних алгоритмів побудови ε- розв’язків задачі наведено в роботі [15]. Постійно зростає кількість задач, для розв’язування яких недостатня продуктивність сучасних однопроцесорних комп’ютерів. Джерелами таких задач є дослідження з ядерної фізики, екології, інформаційної безпеки, кос- мосу, моделювання клімату, довгострокового прогнозу погоди тощо. У зв’язку з цим розглянемо можливості використання принципів пара- лельної обробки даних, квантової механіки та оптичних перетворювачів для організації високопродуктивних обчислень. Від наукового результату до комп’ютерної технології Системні дослідження та інформаційні технології, 2008, № 2 21 Модель паралельних обчислень. Важливими задачами організації швид- ких паралельних обчислень є розробка паралельних алгоритмів, які відоб- ражають паралелізм задачі, узгодження таких алгоритмів з можливостями паралельних комп’ютерів та організація обчислювальної системи таким чи- ном, щоб на ній найкраще реалізовувалися алгоритми даного класу. Для аналізу обчислювальної складності паралельних алгоритмів може бути використана ідеалізована модель паралельних обчислень, в якій k іден- тичних процесорів мають необмежену пам’ять, що доступна кожному з них без конфліктів. Один процесор за одиничний інтервал часу (крок обчислень) може точно виконати одну з бінарних арифметичних операцій. Часом реалі- зації інших операцій можна знехтувати. k операцій, виконаних паралельно, здійснюються за один крок обчислень. Час розв’язання задачі дорівнює чис- лу паралельних кроків обчислень. Паралельний алгоритм, реалізований на k процесорах, будемо називати k-алгоритмом. Як міра паралелізму k-алгоритму використовується ко- ефіцієнт прискорення паралельного алгоритму kk TTS /1= , де kT — час об- числень при розв’язанні задачі k-алгоритмом, 1T — мінімальний час розв’язання задачі на одному процесорі. У більшості випадків відомі лише оцінки 1T . Ця величина може відноситись до послідовного алгоритму, що розпаралелюється. Враховуючи те, що в паралельних алгоритмах обсяг обчислень може бути більший, ніж у кращого (послідовного), тобто не усі k процесорів ви- користовуються в k-алгоритмі на кожному кроці обчислень, використаємо співвідношення )(1 kTVT kk ϕ= , де 1≥kV — величина, яка характеризує збільшення обсягу обчислень при переході від послідовного до паралельно- го алгоритму, ∑ = = k i i i a k 1 )(ϕ , 1 1 =∑ = k i ia , 0≥ia , ia — частина обсягу обчис- лень, яка виконується синхронно i процесорами при реалізації k-алгоритму. Нехай k T T kk 1 1 υ= — час обчислень при рівномірному розподілі обсягу обчислень між процесорами. Тоді 21 kkk TTT += , де ( ) ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ −= k kTT kk 1 12 ϕυ — витрати часу за рахунок простоїв деяких процесорів. Формула для приско- рення може бути записана у вигляді ( )kk k kS δυ + = 1 , 1 2 k k k T T =δ . Тобто максимальне прискорення ( )kSk = досягається тоді, коли перехід від послідовного до паралельного алгоритму відбувається без збільшення обся- гу обчислень ( )1=kυ при рівномірному розподілі обчислень між процесо- рами ( )1=kα . Чи завжди паралельні алгоритми можна застосовувати до реальних об- числень? Не завжди. Паралельні алгоритми можуть бути чисельно не- В.К. Задірака, І.В. Сергієнко ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 22 стійкими. Це, наприклад, алгоритми обчислення арифметичних виразів, подвоєння. При розв’язанні задач лінійної алгебри з розпаралелюванням обчислень чисельна стійкість може істотно погіршитися при значному збі- льшенні числа процесорів [25]. Разом з тим, паралельний алгоритм методу «пристрілки» розв’язання крайових задач для звичайних диференційних рі- внянь має кращу чисельну стійкість, ніж послідовний. Витрати на обмін даними можуть бути обмежуючим фактором в ефек- тивному використанні паралельного алгоритму. У конкретних паралельних комп’ютерах реалізовані певні форми паралельної обробки даних, тому для ефективних паралельних обчислень функціональні зв’язки алгоритму по- винні бути узгоджені з комутаційними схемами комп’ютера. Для отримання прискорення, близького до максимального, повинен бу- ти достатньо великий обсяг обчислень на одиницю витрат при підготовці даних, достатньо малі простої та надлишок обчислень. Модель обчислень для квантової ЕОМ. Як відомо, при будь-яких здо- бутках у розвитку ЕОМ завжди існують задачі, що їм «не під силу». Скоріш за все суперкомп’ютери майбутнього не зможуть розв’язувати задачі, які мають експоненціальну і більші складності (PSPACE, EXPTIME тощо). Однією з таких задач є задача практичної криптостійкості алгоритму RSA двоключової криптографії. Криптостійкість алгоритму RSA залежить від обчислювальної складності розв’язання задачі факторизації — розкла- дання двоскладового модуля (добутку двох простих чисел) на множники. Факторизація модуля дає змогу розкрити секретний ключ і, як наслідок, де- шифрувати будь-яке повідомлення, підробити цифровий підпис. Чим більше число, тим більша обчислювальна трудомісткість факторизації. Основне завдання при виборі модуля RSA — одночасне забезпечення крип- тостійкості та обчислювальної ефективності процедури шифруван- ня /дешифрування. Таким чином, при виборі модуля необхідно виходити з реальних оцінок зростання потужності комп’ютерів та досягнень в галузі теорії чисел. Час роботи найкращих (на сьогодні) алгоритмів факторизації числа x, яке записується за допомогою n двійкових розрядів, оцінюється виразом ( )( )3231 log08,2 nnO , тому рекомендована мінімальна довжина RSA — 768 бітів (або ≈ 230 десяткових знаків). Продуктивність комп’ютера для ефек- тивної факторизації такого числа повинна бути не меншою, ніж 810 МУ (1 МУ — рік роботи комп’ютера з продуктивністю 1 мільйон цілочисельних інструкцій в секунду). Нещодавно розроблено алгоритм факторизації числа на квантовому комп’ютері, час роботи якого оцінюється виразом ( )ε+2nO , де ε — деяке мале число [16]. Це означає, що криптосистеми з відкритими ключами, кри- птостійкість яких ґрунтується на складності задачі факторизації та дискрет- ного логарифму, можуть бути зламані. Таким чином, існують моделі обчислень, які дозволяють прискорити процес обчислень для деяких спеціальних класів задач. Наведемо прикладні задачі, на яких використання квантових моделей обчислення [17] дає виграш (за часом розв’язання) порівняно з класичними. Від наукового результату до комп’ютерної технології Системні дослідження та інформаційні технології, 2008, № 2 23 По-перше, на квантовому комп’ютері можна моделювати довільну квантову систему за поліноміальне число кроків. Це дає змогу (за наявності квантово- го комп’ютера) передбачити властивості молекул і кристалів, проектувати мікроскопічні електронні пристрої. Інший приклад ґрунтується на роботі П. Шора [16], який показав розв’язність на квантових машинах задачі зна- ходження дискретного логарифму числа в мультиплікативних цілочисель- них групах і задачі розкладання цілого числа на множники за поліноміальний (відносно довжини числа) час. Прослуховування інформації, що передається квантовим каналом зв’язку, неможливе без внесення в повідомлення спотворень, які можуть бути виявлені користувачами каналу. Цей ефект дає можливість двом або- нентам таємно обмінюватися інформацією «під носом» у противника, який хоче її перехопити. Наскільки складно буде побудувати квантовий комп’ютер? Квантові обчислення ґрунтуються на побудові траєкторії від стандартного початково- го стану до складного кінцевого. Найбільша проблема — це надчутливість до збурень, які порушують траєкторію випадковим чином. Такі збурення відбуваються завдяки неконтрольованим зв’язкам із зовнішніми шумами. Здається, що немає фундаментальних обмежень на те, як добре ми можемо ізолювати систему. На сьогоднішній день теоретики і експериментатори різних країн досліджують деякі реалізації квантових комп’ютерів. З’явилось повідомлення [26], що 13 лютого 2007 р. відбулася демонст- рація квантового комп’ютера Orion. Його створила компанія D-Wave. Модель обчислень для оптичних ЕОМ. Динамічна голографія [18] є пер- спективним засобом реалізації різних оптичних перетворювачів. Зокрема, ефект перекачки енергії пучка світла в когерентний йому пучок, що скеро- ваний в іншому напрямку (завдяки їх перетину в динамічному середовищі), фактично є оптичним аналогом транзистора. Змінюючи інтенсивність підсилюючого пучка, можна керувати часовими змінами його інтенсивності. Існує варіант оптичного аналогу електронного транзистора, коли таке керу- вання досягається шляхом зміни не інтенсивності, а фази підсилюючого пучка. Ще одним прикладом може бути оптичний перемикаючий пристрій, який діє аналогічно швидкодіючому електронному перемикачу, що є не- від’ємною частиною найважливіших приладів обчислювальної техніки. Пе- ревагою голографії є також можливість перетворення найбільш складних зображень, а не тільки найпростіших плоских або сферичних хвиль. На сьогодні вже виконані експерименти зі створення оптичних бі- стабільних пристроїв, що перемикаються за 1210− с, та елементів волоконно- оптчиних ліній зв’язку, інформація з яких переноситься за допомогою оп- тичних солітонів з довготривалістю, що досягає 1310− с. З перемиканням за такий час продуктивність оптичного процесора, який має 65 1010 − пара- лельних каналів, склала б до 1810 операцій за секунду, тобто на 6 порядків вища за потенційну продуктивність електронних схем. Прикладами елемен- тарних операцій для оптичного комп’ютера є додавання і віднімання зобра- жень, обчислення перетворення Фур’є, розпізнавання образів тощо. В.К. Задірака, І.В. Сергієнко ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 24 6. НАУКОЄМНІ КОМП’ЮТЕРНІ ТЕХНОЛОГІЇ РОЗВ’ЯЗАННЯ ЗАДАЧ ОБЧИСЛЮВАЛЬНОЇ ТА ПРИКЛАДНОЇ МАТЕМАТИКИ Під комп’ютерною технологією (КТ) розв’язання задач прикладної та обчи- слювальної математики із заданими значеннями характеристик якості буде- мо розуміти вибір і побудову обчислювальних ресурсів і способів ефектив- ного їх використання при обчисленні наближеного розв’язку задачі із заданою точністю за обмежений процесорний час. Загальна схема розв’язування задач прикладної та обчислювальної ма- тематики з використанням КТ складається з таких етапів: 1. Постановка прикладної задачі в термінах предметної області. 2. Вибір математичної моделі прикладної задачі (ММ). 3. Вибір комп’ютерної моделі обчислень (КМО), яка має складові: • вхідні дані про задачу; • клас задач обчислювальної математики на основі вхідних даних; • клас обчислювальних алгоритмів (о.а.) обчислення розв’язку, побу- дова оцінок характеристик якості та параметрів обчислювального процесу (ОП); • архітектура комп’ютера; • програмне забезпечення ОП; • обмеження на значення характеристик якості. 4. Можливі корегування ММ, складових комп’ютерної моделі обчис- лень та повторний розгляд етапів цієї схеми. 5. Побудова ОП і здійснення обчислень. 6. Інтерпретація результатів обчислень. Загальною схемою побудови розв’язків породжується множина КТ у залежності від глибини розробки і конкретного використання наведених етапів. До факторів, які породжують множину КТ, належать: тип задачі і ММ, доступні вхідні дані про задачу (вид, об’єм, точність), вимоги до на- ближеного розв’язку задачі та обмеження на обчислювальні ресурси (проце- сорний час, пам’ять комп’ютера), можливості обчислювальної техніки, ал- горитмічне та доступне програмне забезпечення, кваліфікація розробників та користувачів. Постановка задачі: обчислити наближений розв’язок задачі за умов ( ) ερ ≤),,( YXIE , (6) ( ) )(),,, 0 εε TYXIT ≤ , (7) ( ) )(),,, 0 εε MYXIM ≤ , (8) де ( )•ρ — деяка міра похибки наближеного розв’язку задачі; ( )YXIE ,, , як правило, — повна похибка наближеного розв’язку, яка є сумою трьох скла- дових: ( )•HE — неусувної похибки, ( )•µE — похибки методу, ( )•τE — похибки заокруглення; YX , — вектори параметрів, які характеризують відповідно алгоритми і комп’ютери; ),,( YXIT , ),,( YXIM — процесорний Від наукового результату до комп’ютерної технології Системні дослідження та інформаційні технології, 2008, № 2 25 час та пам’ять комп’ютера, необхідні для обчислення наближеного розв’язку; )(),(, 00 εµεε T — обмеження, задані на основі вимог до математичного мо- делювання і властивостей вхідної інформації (об’єму, точності, структури). Наближений розв’язок, для якого виконана умова (6), називається ε -розв’язком, ),,( YXA ε — множина о.а. побудови ε -розв’язку в даній КМО. Обчислювальний алгоритм, який задовольняє умовам (6), (7), назива- ється Т-ефективним, ),,,( 0 YXTA ε — множина Т-ефективних о.а. в даній КМО. Опишемо коротко послідовності кроків КТ. Крок 1. ММ задачі, яку ми розв’язуємо на основі її вхідних даних, відноситься до відповідного класу обчислювальної математики. Вивчається вхідна інформація. Крок 2. Встановлюються вимоги (6)–(8) до значень характеристик якості розв’язку задачі до точності ( 0>ς ), до комп’ютерного часу )(0 εT побудови ε-розв’язку, до пам’яті комп’ютера 0M , які повинні бути забезпе- чені відповідною о.а.-програмою. Крок 3. Із використанням вхідної інформації про задачу і оцінок точ- ності їх задання (обчислення) знаходиться оцінка HE неусувної похибки розв’язку задачі. Крок 4. Для знайденої оцінки HE перевіряється виконання умови ( ) εαρ 1H ≤E , 10 1 << α , наприклад 3 1 1 =α . (9) Якщо умова (9) виконується, то перейти на крок 6, інакше — на крок 5. Крок 5. Для забезпечення розв’язку задачі з точністю (6) треба змінити (якщо це можливо) вимогу до точності (збільшити ε ) або зменшити (по- кращити) оцінку неусувної похибки HE , використовуючи резерви її покра- щення. Перейти відповідно на крок 2 або 3. Якщо Hε значно перевищує за- дане ε і не може бути зменшена, треба змінити саму постановку задачі і перейти на крок 1. Крок 6. На основі апріорної інформації про задачу та вимог до значень характеристик якості розв’язку (6)–(8) звужується клас задач, що розв’язується. Це дає змогу розраховувати на більші можливості по забезпе- ченню точності та швидкодії побудови розв’язку задачі. Крок 7. Наслідком кроку 6 є такі ситуації: а) для розв’язання підкласу задач метод не відомий; перейти на крок 8; б) відомі методи розв’язання підкласу задач, але не розроблені на їх ос- нові о.а. і програми та теоретично не вивчені оцінки їх характеристик ),,( TME ; перейти на крок 9; в) маємо програму підкласу задач, але вона не має оцінок характери- стик ),,( TME , за допомогою яких можна було б говорити про забезпечення розв’язку задачі з заданими характеристиками якості; перейти на крок 15; В.К. Задірака, І.В. Сергієнко ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 26 г) для підкласу задач є програма, яка має оцінки характеристик ),,( TME і забезпечує побудову ε-розв’язку задачі з підкласу із заданою точністю; перейти на крок 16. Крок 8. Для підкласу, якому належить задача, не відомий метод. Здійснюється розробка методу. Крок 9. Із множини методів розв’язання задачі обирається кращий за точністю та швидкодією. Крок 10. Обираються параметри Y комп’ютера, на якому задача буде розв’язуватися. Крок 11. На основі обраного або розробленого методу будується T-ефективний о.а. обчислення ε-розв’язку і знаходяться його характеристики ),,( TME , згідно з описаною в роботі [19] технологією. Крок 12. Розроблений T-ефективний о.а. реалізується в програмі на відповідній алгоритмічній мові. Крок 13. На визначеному наборі тестових задач здійснюється тесту- вання програми у відповідності до технології тестування характеристик якості програм [10]. Якщо результати тестування підтверджують виконання умов (6)–(8), то перейти на крок 17, інакше — на крок 14. Крок 14. Проводиться аналіз програми для виявлення резервів її по- кращення за тими характеристиками, які не задовольняють вимогам (6)–(8). Здійснюється оптимізація програми, і для отриманої її модифікації вико- нується робота, згідно з технологією [19]. Якщо вичерпані всі резерви оп- тимізації для вибраного о.а. і відповідної програми, але їх характеристики не задовольняють обмеженням (6)–(8), то необхідно продовжити пошук о.а., згідно з попередніми кроками (тобто перейти на крок 10 та 11). Крок 15. Здійснюється тестування програми розв’язання підкласу задач і отримання її оцінок характеристик ),,( TME у відповідності до технології [10]. Якщо результати тестування підтверджують, що обрана програма може забезпечити наближений розв’язок з потрібними значеннями характеристик якості за точністю та швидкодією, то перейти на крок 17, інакше — на крок 7. Крок 16. Використовуючи оцінки характеристик ),,( TME програми побудови розв’язків підкласу задач, перевіряється, чи може вона забезпечи- ти ε-розв’язок задачі з заданою точністю ε (6) і при обмеженні (7) на комп’ютерний час. Якщо ця програма здійснює побудову ε-розв’язку задачі з заданими характеристиками якості (6)–(8), то перейти на крок 17, інакше — 7. Крок 17. Будується розв’язок підзадачі з заданими характеристиками якості (6)–(8). 7. ПРИКЛАДИ РОЗВ’ЯЗУВАННЯ ЗАДАЧ З ВИСОКОЮ ТОЧНІСТЮ Перелічимо задачі, при розв’язанні яких було важливим використання оп- тимальних і близьких до них алгоритмів та розробка відповідних програм- них засобів для отримання наближеного розв’язку з високою якістю. 1. Для побудови математичної моделі технологічної установки АВТ (атмосферно-вакуумної трубчатки) нафтопереробного заводу використано Від наукового результату до комп’ютерної технології Системні дослідження та інформаційні технології, 2008, № 2 27 ефективні за точністю та швидкодією алгоритми визначення оцінок ди- намічних та ймовірнісних характеристик об’єктів керування [5]. 2. Для експрес-обробки даних льотного експерименту розроблено системи «Випробувач», «Темп», «Темп-ЕК», в яких були використані оригінальні модифікації алгоритму швидкого перетворення Фур’є і на їх основі створено ефективні за швидкодією алгоритми розв’язання задач спектрального та кореляційного аналізу випадкових процесів [3, 20, 21]. Ці системи впроваджено в Льотно-дослідному інституті (м. Жуковський, Мос- ковської обл.). 3. Розроблено комплекс пакетів програм «ПОМ-1» наближеного розв’язання типових задач обчислювальної математики з діагностикою якості [22]. «ПОМ-1» випробувано у Фізико-енергетичному інституті (м. Обнінськ), Обчислювальному центрі (м. Єреван), Обчислювальному центрі Київського національного університету ім. Тараса Шевченка та інших установах. 4. Розроблено комп’ютерну технологію тестування якості прикладного програмного забезпечення за точністю та швидкодією [10]. 5. Розроблено апаратно-програмний комплекс арифметики багатороз- рядних чисел для систем захисту інформації [23]. Ця робота була виконана в рамках Державного замовлення 8/35 у 2004 р., і результати її впровадження дозволяють підняти продуктивність систем двоключової криптографії. 6. На базі спектрального аналізу випадкових процесів та теорії похибки заокруглення розроблено нові комп’ютерні технології проектування стійких стеганоконтейнерів для розв’язання задач приховування інформації [24]. 7. Розроблено комп’ютерну технологію розв’язування задач приклад- ної та обчислювальної математики із заданими характеристиками якості (див. розд. 6 та роботу [11]). ЛІТЕРАТУРА 1. Згуровський М.З., Панкратова Н.Д. Системний аналіз: проблеми, методологія, застосування. — Київ: Наук. думка, 2005. — 744 с. 2. Сергієнко І.В. Інформатика та комп’ютерні технології. — Київ: Наук. думка, 2004. — 432 с. 3. Задирака В.К., Мельникова С.С. Цифровая обработка сигналов. — Киев: Наук. думка, 1993. — 294 с. 4. Задірака В.К., Олексюк О.С. Комп’ютерна арифметика багаторозрядних чисел: Наук. видання. — Київ, 2003. — 264 с. 5. Методы алгоритмизации непрерывных производственных процессов / В.В. Ива- нов, А.И. Березовский, В.К. Задирака и др. — М.: Наука, 1975. — 400 с. 6. Морозов В.А. Регулярные методы решения некорректно поставленных за- дач. — М.: Изд-во Моск. ун-та, 1974. — 359 с. 7. Сергієнко І.В. Інформатика в Україні: становлення, розвиток, проблеми / Відп. ред. Ю.В. Капітонова, Т.Т. Лебедєва. — Київ: Наук. думка, 1999. — 354 с. 8. Переверзев С.В. Оптимизация методов приближенного решения операторных уравнений. — Киев: Ин-т математики НАН Украины. — 1966. — 251 с. 9. Литвин О.М. Методи обчислень. Додаткові розділи: Навч. посіб. — Київ: Наук. думка, 2005. — 344 с. В.К. Задірака, І.В. Сергієнко ISSN 1681–6048 System Research & Information Technologies, 2008, № 2 28 10. Бабич М.Д., Задирака В.К., Сергиенко И.В. Вычислительный эксперимент в проблеме оптимизации вычислений // Кибернетика и системный анализ. — Ч.1. — 1999. — № 1. — С. 51–63; Ч.2. — 1999. — № 2. — С. 59–79. 11. Компьютерные технологии решения задач прикладной и вычислительной математики с заданными значениями характеристик качества / И.В. Сергиенко, В.К. Задирака, М.Д. Бабич и др. // Кибернетика и систем- ный анализ. — 2006. — №5. — С. 33–41. 12. Иванов В.В. Об оптимальных алгоритмах минимизации функций некоторых классов // Кибернетика. — 1972. — № 4. — С. 81–94. 13. Задирака В.К. Теория вычисления преобразования Фурье. — Киев: Наук. дум- ка, 1983. — 216 с. 14. Витушкин А.Г. Оценка сложности задач табулирования. — М.: Физматгиз, 1953. — 250 с. 15. Задирака В.К. Об оценках информационной и комбинаторной сложности неко- торых алгоритмов восстановления функций // Информатика, вычислитель- ная и прикладная математика. Теория, приложения, перспективы: Тр. меж- дунар. конф. INAMATAP’96. — Киев: Наук.думка, 1998. — С. 94–98. 16. Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Founda- tions of Computer Science // IEEE Computer Society Press. — 1999. — 26. — P. 124–134. 17. Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. — М.: МЦНМО ЧеРо, 1999. — 192 с. 18. Гиббс Х. Оптическая бистабильность. Управление светом с помощью света. — М.: Мир, 1988. — 518 с. 19. Т-ефективні алгоритми наближеного розв’язання задач обчислювальної та прикладної математики: Наук. видання // Задірака В.К., Бабич М.Д., Бере- зовський А.І. та ін. — Київ: Ін-т кібернетики ім. В.М. Глушкова НАН Ук- раїни, 2003. — 216 с. 20. Дехтярюк Е.С., Задирака В.К., Ярошенко Э.В. Пакет программ статистической обработки данных // Опыт создания и внедрения автоматизированных систем обработки данных комплексных испытаний сложных объектов: Тез. докл. научн.-техн. конф. — Киев, апрель 1978. — Киев: ИК АН УССР, 1978. — С. 73–75. 21. Задирака В.К., Абдикаликов К.А. Быстрые ортогональные преобразования: Тео- рия и приложения. — Алматы: Научн.-изд. центр «Fылым», 2003. — 220 с. 22. Комплекс программ по расчету и оценке основных вероятностных характери- стик, аппроксимации функций, решению ряда классов особых уравнений, минимизации функций и математическому программированию / В.В. Иванов, В.К. Задирака и др. — Ин-т кибернетики им. В.М. Глушкова АН УССР. — Киев, 1985. — 1235 с. — Деп. в Гос ФАП 14.02.1986. — №50860000156. 23. Задирака В.К., Кудин А.М. Построение программно-аппаратных комплексов арифметики сверхбольших чисел // Компьютерная математика. — Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины. — 2001. — № 1. — С. 158–165. 24. Задірака В.К. Теорія обчислень та сучасні комп’ютерні технології розв’язання задач інформаційної безпеки // Искусственный интеллект. — 2006. — № 3. — С. 727–736. 25. Воеводин В.В. Математические модели и методы в параллельных процессах. — М.: Мир, 1991. — 365 с. 26. Шевченко В. Квантовый компьютер // Компьютерное обозрение. — 29.03.2007. — URL: http://itc.ua/27644. Надійшла 27.06.2007
id	journaliasakpiua-article-109716
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:23:02Z
publishDate	2017
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/36/c3b3cc9c5fc339976e53483b7e27ca36.pdf
spelling	journaliasakpiua-article-1097162018-04-11T11:06:21Z From scientific results to computer technology От научного результата к компьютерной технологии Від наукового результату до комп’ютерної технології Zadiraka, V. K. Sergienko, I. V. Computer technologies for solution of complex problems in calculus and applied mathematics with given characteristics of the accuracy and operation speed have been developed. They are based on the computation error theory, the common optimal algorithm theory, and application of computation optimization reserves. Some examples of high-quality solution of complex problems are considered. Построены компьютерные технологии решения сложных задач вычислительной и прикладной математики с заданными характеристиками по точности и быстродействию. Технологии основаны на теории погрешности вычислений, общей теории оптимальных алгоритмов и использовании резервов оптимизации вычислений. Рассмотрены примеры решения сложных задач с высоким качеством. Побудовано комп’ютерні технології розв’язування складних задач обчислювальної та прикладної математики із заданими характеристиками якості за точністю та швидкодією. Технології засновано на теорії похибок обчислень, загальній теорії оптимальних алгоритмів та використанні резервів оптимізації обчислень. Розглянуто приклади розв’язування складних задач із високою якістю. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2017-09-08 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/109716 System research and information technologies; No. 2 (2008); 7-28 Системные исследования и информационные технологии; № 2 (2008); 7-28 Системні дослідження та інформаційні технології; № 2 (2008); 7-28 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/109716/104769 Copyright (c) 2021 System research and information technologies
spellingShingle	Zadiraka, V. K. Sergienko, I. V. Від наукового результату до комп’ютерної технології
title	Від наукового результату до комп’ютерної технології
title_alt	From scientific results to computer technology От научного результата к компьютерной технологии
title_full	Від наукового результату до комп’ютерної технології
title_fullStr	Від наукового результату до комп’ютерної технології
title_full_unstemmed	Від наукового результату до комп’ютерної технології
title_short	Від наукового результату до комп’ютерної технології
title_sort	від наукового результату до комп’ютерної технології
url	https://journal.iasa.kpi.ua/article/view/109716
work_keys_str_mv	AT zadirakavk fromscientificresultstocomputertechnology AT sergienkoiv fromscientificresultstocomputertechnology AT zadirakavk otnaučnogorezulʹtatakkompʹûternojtehnologii AT sergienkoiv otnaučnogorezulʹtatakkompʹûternojtehnologii AT zadirakavk vídnaukovogorezulʹtatudokompûternoítehnologíí AT sergienkoiv vídnaukovogorezulʹtatudokompûternoítehnologíí

Від наукового результату до комп’ютерної технології

Репозитарії

Схожі ресурси