ОснАлгор_Посібн_Яровенко

Яровенко А.Г.

ЛАБОРАТОРНИЙПРАКТИКУМ

З ПРОЕКТУВАННЯ

АЛГОРИТМІВТАПРОГРАМ

Навчально-методичний посібник Частина1

Вінниця – 2014

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

УДК 681.3

Рецензент: доктор педагогічних наук, професор Клочко В.І.

Яровенко А. Г.

Лабораторний практикум з проектування алгоритмів і програм. Навчально-методичний посібник. Частина 1. - Вінниця, 2014. – с.

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

Для студентів різних напрямів підготовки. Може використовуватись для вивчення інформатики у школах.

2

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

ЗМІСТ
1. Життєвий цикл програмного забезпечення........................................................	4
1.1. Основні означення і стандарти.......................................................................	4
1.2. Процеси життєвого циклу програмного забезпечення..................................	7
1.3. Моделі життєвого циклу програмного забезпечення....................................	9
1.4.Рекомендована структура моделі процесу розробки програм, створюваних
в рамках практикуму....................................................................................	18
2. Визначення та аналіз вимог до програмного продукту. ..................................	21
2.1. Важливість робіт з визначення вимог до програмного продукту...............	22
2.2. Основні означення і стандарти.....................................................................	25
2.3. Класифікація вимог.......................................................................................	27
2.4. Специфікації вимог.......................................................................................	31
2.5. Методи визначення вимог. ...........................................................................	33
2.6. Властивості вимог.........................................................................................	34
2.7. Рекомендована структура специфікацій вимог до програм, створюваних в
рамках практикуму.......................................................................................	36
2.8. Приклади визначення та специфікації вимог. .............................................	38
3. Інформаційна та математична моделі об’єкту дослідження............................	41
3.1. Предметна область та об’єкт дослідження..................................................	41
3.2. Модель об’єкту..............................................................................................	44
3.3. Інформаційна модель об’єкту.......................................................................	57
3.4. Математична модель об’єкту........................................................................	59
3.5. Побудова інформаційної та математичної моделі об’єкту дослідження. ..	64
3.6. Вибір та обґрунтування методу розв’язання задачі ....................................	72
3.7. Інформаційна модель задачі. ........................................................................	74
3.8. Рекомендована структура та зміст етапів побудови моделей	для
розв’язання навчальних задач в рамках практикуму. ................................	75
4. Проектування алгоритму розв’язання задачі....................................................	77
4.1. Поняття алгоритму........................................................................................	77
4.2. Формальні властивості алгоритмів ..............................................................	78
4.3. Способи запису алгоритму...........................................................................	79
4.4. Інструментальні засоби створення блок-схем.............................................	81
4.5. Базові структури алгоритму .........................................................................	81
Лабораторна робота № 1........................................................................................	89
Лабораторна робота № 2........................................................................................	91
Лабораторна робота № 3........................................................................................	92

3

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

1. ЖИТТЄВИЙ ЦИКЛ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ.

1.1. ОСНОВНІ ОЗНАЧЕННЯ І СТАНДАРТИ.

На початку введемо декілька фундаментальних означень.

Означення. Програмне забезпечення (ПЗ, software) – сукупність програм системи опрацювання даних і програмних документів, необхідних для експлуатації цих програм.

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

Означення. Єдина система програмної документації (ЄСПД) –

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

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

Означення. Програмна система (ПС), Програмний засіб (ПЗс),

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

Означення. Інформаційний продукт – документована інформація,

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

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

життєвим циклом (life cycle).

Означення. Життєвий цикл продукції (виробу) (product lifecycle) –

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

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

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

Проектування програмної системи (ПЗс, ПП, застосунку) для розв’язання задачі в конкретній предметній області також має свою специфіку. Але всі проекти з розробки ПЗ виконуються за єдиною уніфікованою схемою, яка називається життєвим циклом ПЗ (software life cycle). Поняття життєвого

4

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

циклу ПЗ є фундаментальним поняттям нової галузі науки та індустрії в сфері інформаційних технологій (ІТ) – програмної інженерії (software engineering).

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

Одразу звернемо увагу на некоректність терміну «життєвий цикл розробки ПЗ», який досить часто зустрічається як у вітчизняних, так і в зарубіжних публікаціях. Детальний аналіз некоректності та протиріч цього терміну приведений в роботі А.Баренцева від 2008 року. Ми ж тут тільки констатуємо, що коректним є використання терміну «життєвий цикл ПЗ» (тобто, цикл життя чи існування ПЗ, як продукту) або «цикл розробки ПЗ» (тобто процес розробки ПЗ).

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

Вперше формалізований стандарт ЖЦПЗ був затверджений в 1985 р. (уточнений в 1988 р.) для проектування ПЗ систем військового призначення за замовленням Міністерства оборони США – стандарт DOD STD 2167 А. Для заміни стандартів DOD STD 2167 A, 7935 A, 1703 Міністерством оборони США в грудні 1994 г. затверджений Військовий стандарт MIL STD 498 – Розробка і документування програмного забезпечення.

В 1987 році Міжнародна Організація із Стандартизації (International Organization for Standardization – ISO) та Міжнародна Електротехнічна Комісія

(International Electrotechnical Commission – IEC) створили Спільний Технічний Комітет з Інформаційних Технологій – Joint Technical Committee (JTC1) on Information Technology.

Зміст робіт JTC1 визначається як «Стандартизація у сфері систем і обладнання інформаційних технологій (в тому числі мікропроцесорних систем)». В 1989 році цей комітет ініціював розробку стандарту ISO/IEC 12207, створивши для цього підкомітет SC7 (SuСommittee 7) з програмної інженерії.

Стандарт ISO/IEC 12207 «Information Technology – Software Life Cycle Processes» («Процеси ЖЦ ПЗ») був опублікований 1 серпня 1995.

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

Стандарт був схвалений і прийнятий до використання як основа процесів ЖЦ в складі IEEE Software Engineering Collection (IEEE Institute of Electrical and Electronics Engineers Інститут інженерів електротехніки та електроніки).

Адаптацією IEEE стандарту ISO/IEC 12207 є стандарт IEEE/EIA 12207.0-1996,

який містить ISO/IEC 12207 з наступними доповненнями: покращений підхід до

5

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

сумісності, призначення процесів ЖЦ, призначення даних ЖЦ, список виправлень.

В Україні розроблені національні стандарти щодо ЖЦПЗ, ідентичні (IDT) зарубіжним стандартам:

1.ДСТУ 3918-99. Інформаційні технології. Процеси життєвого циклу програмного забезпечення (ISO/IEC 12207-95).

2.ДСТУ ISO/IEC TR 15271:2010 Інформаційні технології. Настанови щодо застосування ISO/IEC 12207 (Процеси життєвого циклу програмного забезпечення) (ISO/IEC TR 15271:1998, IDT).

3.ДСТУ ISO/IEC 15288:2005 Інформаційні технології. Процеси життєвого циклу систем. (ISO/IEC 15288:2002, IDT).

4.ДСТУ ISO/IEC TR 15504-1-9:2002 Інформаційні технології. Оцінювання процесів життєвого циклу програмних засобів. Частини 1-9. (ISO/IEC TR 15504-1-9:1998, IDT).

Таким чином, стандарт ISO/IEC 12207-95 (ДСТУ 3918-99) є основним нормативним документом, який регламентує ЖЦПЗ.

Тут варто зробити невеликий відступ.

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

Програмна інженерія (software engineering) є галуззю Computer science,

тобто, наукою, яка вивчає питання побудови комп’ютерних програмних систем на інженерній основі за методами, засобами і інструментами програмування, сучасними стандартами процесів ЖЦ, менеджменту та керування якістю.

Визначення предмету програмної інженерії та концептуальний зміст її десятьох базових областей (knowledge areas) наведено в базовому ядрі знань

SWEBOK (Software Engineering body of Knowledge), яке було сформовано і опубліковано (1999 р.– перший варіант, 2001 р. – другий) спеціально створеним комітетом фахівців з інформатики при ACM (Association for Computer Machinery) і IEEE Computer Society. Програмна інженерія інтегрує в собі принципи математики та головні положення фундаментальних наук, а саме, теорії алгоритмів, математичної логіки, теорії керування, теорії множин, доведення тощо (рис.1).

Рис. 1. Теоретичний фундамент програмної інженерії

То ж хіба можна стверджувати, що без вивчення фундаментальних математичних дисциплін можна стати кваліфікованим програмістом?

6

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

1.2. ПРОЦЕСИ ЖИТТЄВОГО ЦИКЛУ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ.

Стандарт ISO/IEC 12207-95 (ДСТУ 3918-99) визначає багаторівневу архітектуру ЖЦПЗ, яка містить процеси, дії та задачі, що мають бути виконані під час створення ПЗ.

Архітектура ЖЦПЗ будується як набір 17-ти розділених на 3 групи та взаємозв’язаних процесів. Так, наприклад, основні процеси звертаються до допоміжних, в той час, як організаційні процеси діють протягом всього ЖЦ і зв’язані з основними процесами.

Два принципи визначають правила декомпозиції ЖЦ на групи процесів:

Модульність:

задачі в процесі є функціонально зв’язаними;

зв'язок між процесами – мінімальний;

якщо функція використовується більш, ніж одним процесом, то вона сама є процесом;

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

Відповідальність:

за кожний процес відповідає (керує і/або контролює) конкретна особа, визначена для заданого ЖЦ, наприклад, у вигляді ролі в проектній команді;

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

Процеси ЖЦПЗ:

Основні процеси (primary processes):

Придбання (Acquisition) – дії та задачі замовника, який купує ПЗ ;

Постачання (Supply) – дії та задачі постачальника, який постачає замовнику програмний продукт чи послугу;

Розробка (Development) – дії та задачі, які виконуються розробником: створення ПЗ, оформлення проектної та експлуатаційної документації, підготовка тестових і навчальних матеріалів тощо;

Експлуатація (Operation) – дії	та задачі оператора – організації, яка
експлуатує програмний продукт;

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

Процеси підтримки (supporting processes):

Документування (Documentation) – формалізований опис інформації, створеної протягом ЖЦ;

Управління конфігурацією (Configuration Management) – застосування адміністративних і технічних процедур протягом ЖЦ для визначення стану компонентів ПЗ, керування його модифікаціями;

7

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Забезпечення якості (Quality Assurance) – забезпечення гарантій того, що програмний продукт та процеси його ЖЦ відповідають заданим вимогам і затвердженим планам;

Верифікація (Verification) – визначення того, що програмні продукти, які є результатами певних дій, повністю задовольняють вимоги чи умови, визначені попередніми діями;

Атестація (Validation) – визначення повноти відповідності заданих вимог і створеного продукту їх конкретному функціональному призначенню;

Загальний огляд (Joint Review) – оцінка стану робіт з проекту: контроль планування і керування ресурсами, персоналом, апаратурою, інструментальними засобами;

Аудит (Audit) – визначення повноти відповідності вимогам, планам та умовам договору)

Вирішення проблем (Problem Resolution) – аналіз і вирішення проблем, незалежно від їх походження чи джерела, які були виявлені під час розробки, експлуатації, супроводу та інших процесів.

Організаційні процеси (organizational processes):

Управління (Management) – дії та задачі, які можуть виконуватись будь-якою стороною, керуючою своїми процесами;

Створення інфраструктури (Infrastructure) – вибір і супровід технології, стандартів та інструментальних засобів, вибір та установка апаратних і програмних засобів, які використовуються для розробки, експлуатації чи супроводу ПЗ;

Вдосконалення (Improvement) – оцінка, вимірювання, контроль та вдосконалення процесів ЖЦ;

Навчання (Training) – початкове навчання та наступне постійне підвищення кваліфікації персоналу.

Стандарт ISO/IEC 12207 надає загальний опис процесів на найвищому рівні, але не зобов'язує використовувати всі процеси ЖЦ одночасно і не ставить особливих вимог до формату і змісту документів, що випускаються на різних процесах. Для кожного з процесів ЖЦ у стандарті визначені види діяльності (дії – activity), задачі, сукупність результатів діяльності і розв’язання задач, а

також деякі специфічні вимоги. Але стандарт не визначає спосіб виконання дій.

Загальна ієрархія (декомпозиція) складових елементів ЖЦ має вигляд:

група процесів

процеси

діїзадачі

Взагальному випадку декомпозиція процесу базується на широко розповсюдженому PDCA-циклі Демінга:

«P» – Plan – Планування

«D» – Do – Виконання

8

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

«C» – Check – Перевірка

«A» – Act – Реакція (дія)

Нижче приведений детальний перелік дій одного із основних процесів ЖЦПЗ, а саме процесу Розробки (Development), який є найбільш важливим в контексті цього навчального курсу:

Process implementation – планування реалізації процесу (підготовка процесу);

System requirements analysis – аналіз системних вимог (аналіз вимог до системи);

System design – проектування системи (проектування архітектури системи);

Software requirements analysis – аналіз програмних вимог (аналіз вимог до програмних засобів);

Software architectural design – проектування архітектури програми;

Software detailed design – детальне проектування програмної системи (технічне проектування програмних засобів);

Software coding and testing – кодування і тестування програмних засобів;

Software integration – інтеграція програмної системи (складання програмних засобів);

Software qualification testing – кваліфікаційні випробування програмних засобів;

System integration – інтеграція системи в цілому (складання системи);

System qualification testing – кваліфікаційні випробування системи;

Software installation – інсталяція (встановлення);

Software acceptance support – забезпечення підтримки програмного

забезпечення.

Необхідно відзначити, що існує ще один стандарт ЖЦ – ISO/IEC 15288 (2002 р.), який регламентує організацію процесів ЖЦ системного рівня (Life Cycle Processes – System) і включає спеціальний процес – «Tailoring», тобто налаштування, адаптацію ЖЦ до конкретних вимог та обмежень, які існують або прийняті в конкретній організації/підрозділі чи для конкретного проекту.

Таким чином організація-користувач стандарту під час розроблення конкретного програмного продукту може створити власні стандарти підприємства, методики і процедури, що деталізуватимуть вибрані для конкретних потреб процеси ЖЦ. Міжнародна організація зі стандартизації ISO випускає також посібники і настанови, що доповнюють стандарт ISO/IEC12207.

1.3. МОДЕЛІ ЖИТТЄВОГО ЦИКЛУ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ.

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

Тобто, модель ЖЦПЗ – це схема виконання робіт і задач у рамках процесів, що забезпечують розробку, експлуатацію і супровід програмного продукту.

9

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

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

Основне призначення моделей ЖЦПЗ:

планування і розподіл робіт і ресурсів між розробниками, а також керування програмним проектом;

забезпечення взаємодії між розробниками проекту і замовником;

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

узгодження проміжних результатів із замовником;

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

оцінка відповідності характеристик якості отриманого продукту заданим вимогам;

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

Модель ЖЦ відображає еволюцію програмного продукту і включає:

1.Стадії;

2.Результати виконання робіт на кожній стадії;

3.Ключові події точки завершення робіт і прийняття рішень.

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

Модель ЖЦПЗ схематично пояснює, яким чином будуть виконуватися дії з розроблення програмного продукту за допомогою опису «послідовності» цих дій. Така послідовність може бути як лінійною, так i нелiнiйною, оскільки стадії можуть слідувати одна за іншою, повторюватися або відбуватися одночасно.

На кожній стадії можуть виконуватись декілька процесів, і навпаки, один і той же процес може виконуватись на різних стадіях. Співвідношення між процесами і стадіями також визначається моделлю ЖЦПЗ.

Відзначимо, що інтерпретація моделей ЖЦ різними учасниками розробки може суттєво відрізнятись, а ряд реальних процесів розробки ПЗ досить складно пояснити в рамках існуючих моделей.

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

Для побудови нової моделі ЖЦ для конкретної ПС (ПЗ, ПП), що задовольняє концептуальній ідеї проектованої системи з урахуванням її складності і масштабу робіт, необхідно зробити правильний вибір процесів, їх дій і задач відповідно до стандарту. На сьогодні основою формування нової моделі ЖЦ для конкретної ПС є стандарт ISO/IEC 12207-95 (ДСТУ 3918-99), який не пропонує конкретну модель ЖЦПЗ, але його положення є загальними

10

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)