Зубенко, Омельчук - Програмування. Поглиблений курс

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

I = (Π,δ), де δ – функція розташування, яка кожному базовому еле-

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

Блок-схема A разом зі своєю інтерпретацією I і виділеною підмно- жиною початкових станів (входів) S0 називається структурним алго-

ритмом, який будемо позначати AI (S0 ). Кожний такий А-алгоритм за-

дає формальне правило для обчислення значень певної регулярної фун- кції (див. підрозд. 1.3.3). Ми не будемо строго задавати функцію керу- вання такого А-алгоритму – це можна зробити індукцією за часом (див. вправу 34). Просто пояснимо, як гіпотетичний Виконавець виконує

структурний алгоритм AI (S0 ). Позначимо через AI (s) значення алгори-

тму AI на вході s S0 . Правило обчислення значення AI (s) визначаєть-

ся структурою СБС. Складений структурний алгоритм трактується за правилом множення функцій, розгалуження – за правилом розгалужен- ня функцій, обхід – за правилом обходу тощо. Усі ці правила можна знайти в підрозд. 1.3.3. Інтуїтивно це означає, що необхідно, розпочи- наючи зі входу СБС, рухатись за стрілками й виконувати відповідні дії на поточному стані. Це можуть бути або елементарні перетворення, або обчислення значень предикатів. Даний рух або закінчиться за скінченну кількість кроків у вихідній вершині СБС, або безрезультатно зациклить- ся. Розглянемо кілька прикладів структурних алгоритмів.

Приклад 2.4. Алгоритм вибору для обчислення відображення sign(x) має вигляд:

Наступний структурний алгоритм обчислює квадратний корінь x :

131

ПРОГРАМУВАННЯ

x<0 x≥0

Цей алгоритм також є вибором, але, на відміну від попереднього вибору, він недетермінований. Алгоритм GCD для обчислення найбі- льшого спільного дільника двох чисел має вигляд (див. приклад 1.8):

■

2.1.6. КОНСТРУКТИВНІ ІНФОРМАЦІЙНІ СИСТЕМИ

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

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

132

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

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

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

Які ж існують шляхи для подолання неузгодженості загальних ін- формаційних систем? Їх може бути кілька. Стандартний шлях полягає в обмеженні умов задач (сукупностей запитів, інтерпретацій і озна- чень змінних вхідних систем). Глобальний же шлях може передбачати заміну Виконавця вихідної системи або перехід узагалі до іншої па- радигми конструктивності інформаційної системи [106, 109, 142].

2.1.7. CКЛАДНІСТЬ ІНФОРМАЦІЙНИХ СИСТЕМ

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

133

ПРОГРАМУВАННЯ

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

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

ється функція FA (n ), що визначає найбільшу кількість елементарних

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

складність алгоритму PA (n ) визначається розміром пам'яті, необ-

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

Складність алгоритмів практично всіх реальних задач є неспадною функцією. Аналітичне подання функцій FA (n ) та PA (n ) для реальних

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

індексів, то FA (n ) = 4 ×n ×(n −1)/2 , тобто ми маємо функціональну

залежність між розмірами n і максимальними кількостями елемента- рних дій, виконуваних за алгоритмом A .

Функція f (n ) має порядок, або верхню оцінку O(g (n )), якщо іс-

134

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

Наприклад, функція f (n ) = 25n має порядок O(n ), оскільки для C = 25 та n0 =1 вірно, що f (n ) = Cn , n > n0 . Наведена вище часова складність бульбашкового сортування має порядок O(n2 ).

Якщо кількість виконаних операцій алгоритму описує функція f (n )= Ω(n2 ), то це означає, що навіть у найкращому випадку буде

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

Якщо обидві (верхня й нижня) оцінки складності функції збігають- ся, то кажуть, що вона має оцінку f (n ) = Θ(n ). Наприклад, це вико-

нується для наведеної вище функції f (n ) = 25n .

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

0.5 * n2 < n * (n −1)< n2 .

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

Увага! Найкращими з практичного погляду вважаються алгоритми з логарифмічною й лінійною часовою складністю FA (n ). На жаль, у біль-

шості випадків така складність недосяжна. Проте достатньо широкі класи алгоритмів мають прийнятну поліноміальну часову складність ► Окрім часової та просторової складностей, розглядають також складності розуміння та структури алгоритму. Останню умовно мож-

на назвати інтелектуальною складністю алгоритму.

Усі форми складності взаємопов'язані. Зазвичай при поліпшенні часової складності алгоритму погіршуються його просторова та інте- лектуальна складності, і навпаки.

*Література для CР: вихідні системи – [93, 108]; алгоритми –

[50, 56, 74, 80, 84, 94, 129]; А-алгоритми – [44, 45]; табличні алгоритми – [44, 45]; еквівалентність універсальних класичних систем алгоритмів, теза Чорча – [52, 80, 94]; NP-повні й алгоритмі- чно нерозв'язні проблеми – [29, 94, 97]; інтелектуальна складність інформаційних систем – [49, 90, 91]; шахові програми – [13, 83].

135

ПРОГРАМУВАННЯ

Контрольні запитання та вправи

1.Що таке вхідна система?

2.Дати визначення вихідної системи.

3.Яка роль вхідної й вихідної систем у інформаційній системі?

4.Що таке інформаційний об'єкт та інформаційне поле?

5.Що таке X -фрейм поля?

10. У чому полягає різниця між операцією й оператором при- своювання?

11. Що таке векторний аналог і параметризований векторний аналог X −Y -оператора?

12 ** . Сформулювати для узагальнених алгебричних систем з ек- вітонними X -арними операціями та предикатами поняття: а) замкненої підмножини й підсистеми; б) гомоморфізму та ізоморфізму; в) конгруенції. Довести аналоги лем 1.3 і 1.4 [94, 105].

13.Що таке функції кодування й декодування в інформаційній системі?

14.У чому полягає смисл узгодженості інформаційної системи? Навести приклади узгоджених і неузгоджених інформацій- них систем.

15.Які інформаційні системи називаються конструктивними?

16.Що таке алгоритмічна мова?

17.Що таке конструктивний об'єкт?

18.Що таке абстрактний алгоритм?

19.Сформулюйте основні властивості А-алгоритмів.

20.У чому полягає релятивність і темпоральність А-алгоритмів?

21.Що таке алгоритми з оракулами?

22.Що таке графік А-алгоритму й алгоритмічно обчислювальна відповідність?

23.Що таке розв'язна множина?

24.Що таке частково розв'язна множина?

25.Сформулювати теорему про замкненість А-алгоритмів.

26.Що таке табличний алгоритм?

27.Написати послідовність ходів для обходу шахової дошки n ×n конем і турою, які спочатку розташовані в лівому ни- жньому куті. Кожне поле відвідується лише один раз. Чи завжди можливий розв'язок?

136

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

28. Розв'язати шахові задачі. Розв'язок полягає в побудові від- повідних шахових обчислень. Перший хід у задачах завжди в білих. Оголосити мат за три ходи:

а) білі: Кр g8, Te1, Tg1, Kg3, пішак f4; чорні: Кр f6, Td7, Th6,

пішак f5;

б) білі: Кр f4, Tc4, Cd4, Ce4, Kf5, Kf3, пішаки: a2, b3, g4, h4;

чорні: Кр b8;

в) білі: Кр e4, пішаки: c7, d6, e7, f6, g7; чорні: Кр e6; г) білі: Кр e7, Ca1, Kh6; чорні: Кр h8, пішаки: g7, h7;

д) те саме, що й у г), тільки дошка перевернута – чорні пі- шаки прямують на восьму горизонталь.

29.Розробити нотацію для запису партій гри в; а) шашки; б) доміно. Навести приклади партій у цих іграх. Правила ігор можна знайти в [108].

30.Що таке табличний алгоритм?

31.Побудувати табличні алгоритми для функцій із вправ 12, 13, 27 із підрозд. 1.3.

32 ** . Довести теорему 2.2.

33. Дати визначення структурної блок-схеми та структурного алгоритму.

34 * . Описати строго функцію керування структурного алгоритму. 35. Які функції обчислюють такі структурні алгоритми:

а)

S := sin(X); I :=1; B :=X;

I<N

B := B*X;

S := S + sin(B);

I:=I+1;

137

ПРОГРАМУВАННЯ

36.Що таке алгоритмічно нерозв'язна проблема?

37.Що таке просторова й часова складності алгоритму?

38.Оцінити просторову й часову складності структурних алго- ритмів із вправи 28.

138

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

2.2. Життєвий цикл інформаційних систем

¾Основні етапи життєвого циклу інформаційних систем

¾Деякі методологічні принципи програмування

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

Надалі під інформаційними системами (або просто системами) бу- демо розуміти інформаційні системи на базі ОбС. Життєвий цикл си- стем уже згадувався у вступі. У цьому підрозділі ми детальніше обго- воримо його з урахуванням специфіки ОбС.

2.2.1. ОСНОВНІ ЕТАПИ ЖИТТЄВОГО ЦИКЛУ ІНФОРМАЦІЙНИХ СИСТЕМ

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

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

Бачимо, що ЖЦ охоплює не тільки процес створення інформацій- них систем, а й питання, пов'язані з реалізацією відповідних комуні- кативних процесів.

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

Основою технологiй програмування (ТхП) є різноманітні засоби (у тому числі й автоматизовані), що реалiзують ЖЦ. Будь-яка ТхП спирається на

139

ПРОГРАМУВАННЯ

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

Охарактеризуємо коротко кожний з етапів ЖЦ.

На етапі аналiзу вивчається актуальність задачі з побудови даної інформаційної системи й описуються (специфікуються) вимоги до неї. Цей етап містить:

•з'ясування актуальності задачі;

•специфікацію вхідної системи (на теоретико-множинному рівні);

•вимоги до апаратури й системної частини ОбС;

•прагматичні вимоги до прикладної частини ПЗ;

•оцінку й планування ризиків.

Перед початком розробки вивчають актуальність системи й комер- ційну доцільність її створення (який на неї може бути попит, скільки вона коштуватиме, які матиме переваги над існуючими аналогами тощо). Потім аналізують безпосередньо складові інформаційної сис- теми. Як зазначалось у підрозд. 2.1, вхідні системи є наближеними моделями реальних об'єктів зовнішнього світу та взаємозв'язків між ними. Тому спочатку вивчають первинні об'єкти, операції та преди- кати на них. Такі первинні системи можуть бути як неперервними, так і дискретними (зліченними), але їхні вхідні моделі – обов'язково дискретними, оскільки такими є вихідні системи, а функції кодуван- ня в інформаційних системах вважаються однозначними. Фактично вхідні системи є фактор-алгебрами первинних систем. Звідси й ви- пливає методика побудови вхідних Ω -систем. Шляхом аналізу пер- винні об'єкти за певними ознаками об'єднують у класи еквівалентно- сті й отримують зліченну фактор-множину первинних об'єктів – уні- версум майбутньої вхідної системи. При цьому необхідно слідкувати, щоб усі операції та предикати були стабільними відносно вибраної еквівалентності. Тоді (див. підрозд. 1.4.2) на фактор-множинах мож- на визначити операції та предикати так, щоб отримати модель пер- винної системи, тобто вхідну Ω -систему. Після цього уточнюється су- купність запитів системи, а точніше, відповідність між їхніми вхід- ними параметрами й результатами.

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

Важливою складовою аналізу системи є специфікація й тестування властивостей апаратури та операційної системи ОбС, а також оцінка й планування ризиків проекту.

140