_TPLab_My_Посібник

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

ЛАБОРАТОРНИЙ ПРАКТИКУМ З ОСНОВ АЛГОРИТМІЗАЦІЇ

ТА СТРУКТУРНОГО ПРОГРАМУВАННЯ

Навчальний посібник

Вінниця – 2011

УДК 681.3

Рецензенти:

Абрамчук В.С. – кандидат фізико-математичних наук, професор; Клочко В.І. – доктор педагогічних наук, професор.

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

(протокол № 5 від 02.11.2011 р.)

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

Лабораторний практикум з основ алгоритмізації та структурного програмування. Навчальний посібник. - Вінниця, 2011. – 228 с.

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

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

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

ЗМІСТ
ЛАБОРАТОРНИЙ ПРАКТИКУМ.................................................	1
З ОСНОВ АЛГОРИТМІЗАЦІЇ.......................................................	1
ТА СТРУКТУРНОГО ПРОГРАМУВАННЯ.................................	1
Розділ 1. ОСНОВИ АЛГОРИТМІЗАЦІЇ........................................	4
1.1. Життєвий цикл програмного продукту..................................	4
1.2. Процеси життєвого циклу.......................................................	5
1.3. Моделі життєвого циклу ПЗ ...................................................	6
1.4. Методології розробки ПЗ........................................................	8
1.5. Поняття алгоритму..................................................................	9
1.6. Способи запису алгоритму....................................................	11
1.7. Базові структури алгоритму..................................................	12
Розділ 2. ОСНОВИ СТРУКТУРНОГО ПРОГРАМУВАННЯ ....	18
2.1. Вимоги до виконання лабораторних робіт...........................	18

2.2. Вимоги до оформлення та вмісту звіту з лабораторної роботи 18
2.3. Загальні методичні рекомендації до виконання лабораторних робіт		19
2.4. ІНСТРУКЦІЇ ТА ЗАВДАННЯ ДО ЛАБОРАТОРНИХ РОБІТ
ЛАБОРАТОРНА РОБОТА № 1...................................................	20

Текстовий редактор інтегрованого середовища проектування (IDE) Turbo Pascal. 20

ЛАБОРАТОРНА РОБОТА № 2...................................................

25

Проектування та відлагодження програм опрацювання простих типів даних25

ЛАБОРАТОРНА РОБОТА № 3..................................................	38
Проектування та відлагодження програм...................................	38
опрацювання простих типів даних..............................................	38
(РЕАЛІЗАЦІЯ ЦИКЛІЧНИХ АЛГОРИТМІВ)............................	38
ЛАБОРАТОРНА РОБОТА № 4..................................................	48
Проектування та відлагодження програм...................................	48
опрацювання регулярних типів даних (масивів) ........................	48
ЛАБОРАТОРНА РОБОТА № 5..................................................	58
Проектування та відлагодження програм...................................	58
опрацювання рядкових типів даних............................................	58
ЛАБОРАТОРНА РОБОТА № 6..................................................	63
Проектування та відлагодження програм...................................	63
опрацювання записів....................................................................	63

ЛАБОРАТОРНА РОБОТА № 7. Проектування та відлагодження програм опрацювання множин68

ЛАБОРАТОРНА РОБОТА № 8..................................................

75

Проектування та відлагодження програм опрацювання даних з використанням процедур та функцій.

......................................................................................................	75
ЛАБОРАТОРНА РОБОТА № 9..................................................	81
2

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

Проектування та відлагодження програм опрацювання файлових типів даних		81
ЛАБОРАТОРНА РОБОТА № 10.................................................	87

Проектування та відлагодження програм опрацювання посилальних типів даних (вказівників) 87

ЛАБОРАТОРНА РОБОТА № 11.................................................	96
Проектування та відлагодження програм опрацювання однозв’язаних списків даних.		96
ЛАБОРАТОРНА РОБОТА № 12...............................................	109
Проектування та відлагодження програм опрацювання двозв’язаних списків даних.		109
ЛАБОРАТОРНА РОБОТА № 13...............................................	112
Проектування та відлагодження програм опрацювання стеків, деків, черг. 112
ЛАБОРАТОРНА РОБОТА № 14..............................................	122
Графіка в Turbo Pascal................................................................	122
додатки.......................................................................................	125

3

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

РОЗДІЛ 1. ОСНОВИ АЛГОРИТМІЗАЦІЇ

1.1. ЖИТТЄВИЙ ЦИКЛ ПРОГРАМНОГО ПРОДУКТУ

Проектування комп’ютерної системи для розв’язання задачі в конкретній предметній області має свою специфіку. Але всі проекти з розробки програмного забезпечення (ПЗ) виконуються за єдиною уніфікованою схемою, яка називається життєвим циклом ПЗ (Software Life Cycle). Поняття життєвого циклу ПЗ (ЖЦ ПЗ) є фундаментальним поняттям нової галузі науки та індустрії в сфері інформаційних технологій (ІТ) – програмної інженерії (Software Engineering).

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

Екскурс в історію.

Вперше формалізований стандарт життєвого циклу був затверджений в 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 з наступними доповненнями: покращений підхід до сумісності, призначення процесів ЖЦ, призначення даних ЖЦ, список виправлень.

Реалізація ISO/IEC в IEEE також включає:

IEEE/EIA 12207.1-1997, IEEE/EIA Керівництво з інформаційної технології. Процеси життєвого циклу програмного забезпечення. Дані життєвого циклу.

IEEE/EIA 12207.2-1997, IEEE/EIA Керівництво з інформаційної технології. Процеси життєвого циклу програмного забезпечення. Зауваження щодо реалізації.

Доповнення до 11 стандартів SESC (IEEE STD 730, 828, 829, 830, 1012, 1016, 1058, 1062, 1219, 1233, 1362) с метою визначення кореляції між документами, виконаними відповідно до існуючих стандартів SESC, і документами, виконаними відповідно до IEEE/EIA 12207.1-1997.

ВУкраїні розроблені національні стандарти щодо ЖЦ ПЗ, ідентичні (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) є основним нормативним документом, який регламентує ЖЦ програмного продукту.

4

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

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

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

Деталізація, техніки та метрики робіт є питаннями програмної інженерії. Організація послідовності робіт модель життєвого циклу. Сукупність моделей, процесів, технік і організація проектної групи задаються методологією. Зокрема, вибір і застосування метрик оцінки якості програмної системи і процесів знаходяться за рамками стандарту 12207, а концепція вдосконалення процесів розглядається в стандарті ISO/IEC 15504 «Information Technology – Software Process Assessment» («Оцінка процесів <в області> програмного забезпечення»).

1.2. ПРОЦЕСИ ЖИТТЄВОГО ЦИКЛУ

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

Така структура ЖЦ має наступний вигляд:

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

процеси

дії

задачі

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

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

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

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

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

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

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

ОСНОВНІ ПРОЦЕСИ (primary processes)

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

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

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

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

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

ДОПОМІЖНІ ПРОЦЕСИ (supporting processes)

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

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

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

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

5

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

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

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

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

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

ОРГАНІЗАЦІЙНІ ПРОЦЕСИ (organizational processes)

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

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

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

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

Кожний процес включає ряд дій. Наприклад, процес придбання містить наступні дії: 1. Ініціювання придбання; 2. Підготовка пропозицій;

3. Підготовка і корегування договору;

4. Нагляд за діяльністю постачальника;

5. Приймання і завершення робіт.

Кожна дія включає ряд задач. Наприклад, підготовка пропозицій передбачає: 1. Формування вимог до продукту; 2. Формування списку програмних продуктів; 3. Встановлення вимог та узгоджень;

4. Опис технічних обмежень (середовище функціонування системи і т.п.).

1.3. МОДЕЛІ ЖИТТЄВОГО ЦИКЛУ ПЗ

Стандарт ISO/IEC 12207-95 (ДСТУ 3918-99) не пропонує конкретну модель ЖЦ. Його положення є загальними для будь-яких моделей ЖЦ, методів і технологій створення програмного продукту.

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

Модель ЖЦПЗ включає:

1.Стадії;

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

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

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

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

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

Найбільш відомими моделями ЖЦПЗ є: модель водопаду, ітеративна та інкрементальна, спіральна, V- та Y-подібні, прототипування, швидка розробка.

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

Модель водопаду (від англ. Waterfall model) була запропонована в 1970 році Уїнстоном Ройсом.

6

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

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

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

Етапи (стадії) ЖЦ проекту у відповідності з каскадною моделлю:

1.Формування (специфікація) вимог;

2.Проектування;

3.Реалізація (кодування);

4.Інтеграція;

5.Тестування і відлагодження;

6.Впровадження;

7.Експлуатація і супровід.

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

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

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

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

Модель ітеративної та інкрементальної розробки (від англ. iterative and incremental development, IID), яка отримала від Т. Гілба в 70-і рр. назву еволюційної моделі, є альтернативою моделі водопаду.

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

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

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

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

(RUP, MSF, XP).

Спіральна модель (від англ. spiral model) була розроблена в середині 1980-х років Барі Боемом (Barry Boehm). Вона базується на класичному циклі Деминга PDCA (plan-do-check-act). При використання цієї моделі програмний продукт створюється в декілька ітерацій (витків спіралі) методом прототипування.

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

На кожній ітерації оцінюються:

ризик перевищення термінів і вартості проекту;

7

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

необхідність виконання ще однієї ітерації;

степінь повноти і точності розуміння вимог до системи;

доцільність припинення проекту.

Спіральна модель не є альтернативою еволюційній моделі (моделі IID), але спеціально пропрацьованим варіантом. Саме тому сьогодні еволюційна модель часто застосовується у формі спіральної моделі.

1.4. МЕТОДОЛОГІЇ РОЗРОБКИ ПЗ

Так як поглядів на деталізацію опису ЖЦ може бути багато, то, природно, існують різні методології розробки (проектування) ПЗ. Найбільше поширення знайшли наступні методології:

Rational Unified Process (RUP) Раціональний Уніфікований Процес методологія створена компанією Rational Software.

В основі RUP лежать наступні принципи:

Рання ідентифікація і неперервна (до закінчення проекту) ліквідація основних ризиків.

Концентрація на виконанні вимог замовників до програмної системи (аналіз і побудова моделі прецедентів (варіантів використання)).

Очікування змін у вимогах, проектних рішеннях і реалізації в процесі розробки.

Компонентна архітектура, яка реалізується і тестується на ранніх стадіях проекту.

Постійне забезпечення якості на всіх стадіях розробки проекту (продукту).

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

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

Початок (Inception)

Уточнення (Elaboration)

Побудова (Construction)

Впровадження (Transition)

Microsoft Solutions Framework (MSF) – Каркас Рішень (розв’язків) – методологія, запропонована корпорацією Microsoft.

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

MSF включає 4 стадії аналіз, проектування, розробка і стабілізація та передбачає використання об’єктно-орієнтованого моделювання.

В 1994 році, намагаючись досягнути максимальної віддачі від IT-проектів, Microsoft видала пакет керівництв з ефективного проектування, розробки, впровадження і супроводу продуктів, побудованих на основі своїх технологій. Цей пакет представлений в виді двох взаємозв’язаних і добре доповнюючих один одного Microsoft Solutions Framework (MSF) и Microsoft Operations Framework (MOF).

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

Найбільш популярні прикладні варіанти MSF, розроблені Microsoft:

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

методика управління IT-проектами на базі методологій MSF и Agile.

Поточна версія MSF 4.0 була представлена в 2005 році. В даній версії відбулось розділення методології на два напрями: MSF for Agile Software Development и MSF for CMMI Process Improvement.

Модель CMMI® була розроблена інститутом Software Engineering Institute (SEI) університету Carnegie Mellon в 2000 році и стала, по суті, стандартом в області розробки програмного и системного забезпечення.

Гнучка методологія розробки ( від англ. Agile software development) це концептуальний каркас, в рамках якого виконується розробка ПЗ. Існує декілька подібних методик.

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

8

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

Agile сімейство процесів розробки, а не єдиний підхід в розробці ПЗ, і визначається Agile Manifesto, який розроблений і прийнятий 11-13 лютого 2001 року. Маніфест підписали представники методологій: Extreme Programming (ХР), Scrum, DSDM, Adaptive Software Development, Crystal Clear, Feature Driven Development (FDD), Pragmatic Programming.

Agile не включає практик, а визначає цінності і принципи, якими керуються успішні команди, і включає 4 основні ідеї та 12 принципів. Основною метрикою agile-методів є робочий продукт.

Крім вказаних існує ще ряд методологій, які дотримуються принципів Agile: Agile Modeling, Agile Data, Agile Unified Process, Method Essential Unified Process (EssUP), Getting Real, Open Unified Process (Open UP), Lean Software Development (Бережлива розробка ПЗ).

Технологія структурного аналізу і проектування SADT (акронім від англ. Structured Analysis and Design Technique) методологія структурного аналізу і проектування, яка інтегрує процес моделювання, управління конфігурацією проекту, використання додаткових мовних засобів і управління проектом зі своєю графічною мовою. Процес моделювання може бути розділений на декілька етапів: опит експертів, створення діаграм і моделей, розповсюдження документації, оцінка адекватності моделей і прийняття їх для подальшого використання. Цей процес добре відлагоджений, тому що при розробці проекту спеціалісти виконують конкретні обов’язки, а бібліотекар забезпечує своєчасний обмін інформацією.

SADT включає стадії:

1.Аналіз визначення того, що система буде робити;

2.Проектування визначення підсистем та їх взаємодію;

3.Реалізація розробка окремих підсистем та об’єднання їх в одне ціле;

4.Тестування;

5.Впровадження та експлуатація.

1.5. ПОНЯТТЯ АЛГОРИТМУ

Слово «алгоритм» походить від імені перського математика IX ст. Абу Джафара (Абдулаха) Мухамеда ібн Муса аль-Хорезмі, (Abu Jafar Mohammed ibn Musa al-Khorezmi) який біля 825 року вперше описав придуману в Індії позиційну десяткову систему числення. В першій половині XII століття книжка потрапила до Європи в перекладі латинською мовою під назвою Algoritmi de numero Indorum. Вважається, що перше слово в перекладі відповідає невдалій латинізації імені Аль-Хорезмі, а назва перекладу звучить як «Алгорітмі про індійську лічбу». Через невірне тлумачення слова Algoritmi як іменника в множині ним стали називати метод обчислення.

Перший алгоритм, призначений для виконання на автоматичному обчислювальному пристрої (комп'ютері), описала Ада Лавлейс в 1843 році. Алгоритм мав обчислювати числа Бернуллі і працювати на аналітичній машині Беббіджа. Цей алгоритм вважається першою комп'ютерною програмою, а його автор баронеса Ада Лавлейс – першим програмістом

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

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

Сформульоване поняття алгоритму не є точним математичним означенням, а тільки пояснює зміст слова «алгоритм», в якому воно використовується в математиці. Слід відзначити, що єдиного «істинного» означення поняття «алгоритм» не існує. Для прикладу приведемо означення терміну «алгоритм» відомих вчених:

«Алгоритм – це скінченний набір правил, який визначає послідовність операцій для розв’язування конкретної множини задач і має п'ять важливих рис: скінченність, визначеність, введення, виведення, ефективність». (Д.Е. Кнут)

«Алгоритм – це будь-яка система обчислень, що виконуються за строго визначеними правилами, яка після певної кількості кроків обов’язково призводить до розв’язку поставленої задачі». (А.

Колмогоров)

«Алгоритм – це точна інструкція, яка описує обчислювальний процес, який йде від вхідних даних, які варіюються, до шуканого результату». (А. Марков)

9

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

«Під алгоритмом в математиці прийнято розуміти скінченну систему точно визначених правил дії, виконання яких в певному порядку дає можливість розв’язувати всі задачі даного типу». (В.Трохименко)

«Алгоритм – це строго детермінована послідовність дій, що описує процес перетворення об'єкта з початкового стану у кінцевий, записана за допомогою зрозумілих виконавцю команд». (М. Угринович)

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

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

1.Кожен алгоритм передбачає існування деякої множини об’єктів, допустимих в якості початкових (вхідних) даних. Наприклад, в алгоритмі ділення дійсних чисел ділене може бути будь-яким, а дільник не може бути рівним нулю.

2.Виконання алгоритму призводить до отримання певного результату.

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

алгоритмічним процесом.

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

5.Порядок виконання кроків визначається однозначно, тобто після виконання кожного кроку точно відомий наступний крок.

Формальні властивості алгоритмів:

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

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

3.Детермінованість (визначеність) – однозначне визначення результату кожного кроку i порядку їх виконання. Виконання алгоритму є строго детермінованим процесом, який не залежить від виконавця. Таким чином, алгоритм видає один і той же результат для одних і тих же вхідних даних. Існують імовірнісні (стохастичні) алгоритми, в яких кожний наступний крок залежить від поточного стану системи і деякого випадкового числа. Але при включені методу генерування випадкових чисел в список «вхідних даних», імовірнісний алгоритм стає підвидом звичайного.

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

5.Масовість (універсальність) – єдиний алгоритм повинен забезпечувати розв`язання будь-якої задачі з класу однотипних задач за будь-якими вхідними даними, що належать до області застосування алгоритму.

6.Результативність – забезпечення одержання певного результату – розв’язку задачі (в разі існування).

7.Правильність – забезпечення одержання правильного у відношенні до поставленої задачі розв’язку.

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

Приведемо два приклади відомих алгоритмів:

Приклад 1. Алгоритм Евкліда. Цей алгоритм використовується при знаходженні найбільшого спального дільника для довільних двох даних натуральних чисел a i b.

Нехай a > b > 0. Ділимо a на b, отримуємо остачус1 < b. Якщо с1=0, то b є найбільший спільний дільник (НСД), якщо ж с1 > 0, то шуканий дільник співпадає з НСД чисел b i с1 . Тому b ділимо на с1 , i якщо нова остача с2 = 0, то с1 – шуканий дільник, якщо с1 > с2 > 0, то ділимо с1 на с2 . Продовжуючи цей процес, отримаємо:

a > b > c1 > c2 > ... > cn > cn + 1 = 0.

10

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