Документування даних

У документацію, що відноситься до організації даних, входять схеми й діаграми, що характеризують відносини між елементами потоків даних і програмами, між елементами потоків даних і областями зберігання даних і різні рівні структурування даних [1].

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

Інформація про логічну й фізичну організацію обов'язково повинна бути включена в документацію. Крім словника даних у документацію повинні входити:

• схема й форма організації зовнішніх даних;

• визначення тих компонентів апаратного й програмного забезпечень системи, які є джерелами даних;

• визначення тих частин системи, які звертаються до даних;

• визначення тих частин системи, які змінюють дані;

• опис усіх рівнів організації складних структур даних;

• опис пам'яті, необхідної для розміщення даних, включаючи розмір файлу, блокування, мітки й т.п..

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

Поняття алоритму. Зображення алгоритмів. Алгоритмічна складність. Поліноміальна та неполіноміальна складність алгоритмів.

ЛЕКЦІЯ 2. АЛГОРИТМИ. СКЛАДНІСТЬ АЛГОРИТМІВ.

2.1. Зображення алгоритмів

Алгоритм – це формально описана обчислювальна процедура, яка отримує вихідні дані та видає результат обчислень на виході [3]. Вихідні дані також називаються входом алгоритму або його аргументом. Алгоритми будуються для розв‘язку тих або інших обчислювальних задач. Формулювання задачі описує, яким вимогам повинен задовольняти розв‘язок задачі. Алгоритм, що розв‘язує цю задачу, знаходить об‘єкт, який задовольняє даним вимогам.

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

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

Зображення алгоритмів найкраще пояснити на прикладі. Розглянемо алгоритм знаходження елемента вектора з найбільшим алгебраїчним значенням.

АЛГОРИТМ GТ визначає найбільший за значенням елемент вектора А, що містить n елементів, і присвоює його значення величині МАХ. Символ і використовується у ролі індексу елемента вектора А.

G Т1. Перевірка умови - чи вектор не порожній?

Якщо n <1, то - друк повідомлення; à G Т 6.

GТ2. Початок: МАХ = А[1], i=2.

GТЗ. Повторення кроків GТ4, G Т5 доти, доки i<=n.

GТ4. Заміна значення MA Х, якщо воно менше від значення наступного елемента: якщо МАX <A[i], то MAX = А[i]

GТ5. i= i + 1.

GТ6. Кінець, вихід.

Алгоритму присвоєно ім'я G Т. За ним іде короткий опис задачі, яку розв'язує алгоритм, і водночас описуються всі змінні, які тутвикористовуються. Після цього наводиться сам алгоритм у вигляді послідовності кроків. Кожний крок описується фразою, яка коротко пояснює дію, що виконується. Символ " à " замінює оператор переходу go to в мовах програмування. Крок GT3 є аналогом заголовку циклу в мовах програмування. Коли значення індексу і перевершить величину n, відбудеться перехід на крок GT6 (наступний після кінця циклу).

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

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

2.2. Складність алгоритмів

Час роботи будь-якого алгоритму залежить від кількості вхідних даних. Так при роботі алгоритму сортування час залежить від розміру вхідного масиву. В загальному вивчають залежність часу роботи алгоритму від розміру входу. В одних задачах розмір входу це кількість елементів на вході (задача сортування, перетворення Фур‘є). В інших випадках розмір входу це загальна кількість бітів, що необхідні для представлення всіх вхідних даних.

Часом роботи алгоритму називається число елементарних кроків, які він виконує [3]. Вважається, що один рядок псевдокоду вимагає не більше ніж фіксованого числа операцій.

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

Якщо алгоритм призначений для обробки рівних за об‘ємом даних, тривалість його роботи щораз залишається незмінною й складністьалгоритму є постійною. Час роботи алгоритму обробки яких-небудь масивів даних залежить від розмірів цих масивів. Час роботи алгоритму, що виконує тільки операції читання й занесення даних в оперативну пам'ять, визначається формулою an+b, де а - час, необхідний для читання й занесення в пам‘ять однієї інформаційної одиниці, і b - час, затрачуваний на виконання допоміжних функцій. Оскільки ця формула виражає лінійну залежність від n, складність відповідного алгоритму називають лінійною.

Якщо алгоритм передбачає виконання двох незалежних циклів, перший від 1 до k, і другий від 1 до t, то загальна кількість кроків буде k+t, а час роботи Т(k+t). Якщо алгоритм передбачає виконання двох вкладених циклів, від 1 до k і від 1 до t, то загальна кількість кроків буде k*t, а час роботи Т(k*t). Це є лінійна функція. І вона є найбільш сприятливою для оцінки швидкодії алгоритму. Чим більша степінь складностіалгоритму в залежності від розміру входу (n², n³, nⁿ …) тим ефективність алгоритму нижча.

Час роботи алгоритму також залежить від подачі вхідних даних. Так для алгоритму сортування «бульбашкою» суттєво як розміщені елементи вхідного масиву. Якщо вони частково відсортовані, то вихід за прапорцем відбудеться швидше. Якщо елементи стоять в різнобій, тоалгоритм відпрацює всі цикли повністю.

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

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

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

1) це гарантує, що виконання алгоритму закінчиться за деякий час, незалежно від розміру входу;

2) на практиці «погані» входи трапляються частіше;

3) час роботи в середньому є достатньо близьким до часу роботи в гіршому випадку.

Розглянемо три позначення асимптотики росту часу роботи алгоритму].

Q - позначення (тета)

Наприклад, якщо час роботи Т(n) деякого алгоритму становить залежність n² від розміру входу, то знайдуться такі константи c₁, с₂ > 0 і таке число n₀ що с₁n² ≤ Т(n) ≤ с₂ n² при всіх n≥0. Взагалі, якщо g(n) - деяка функція, то запис f(n) = Q (g(n)) (тета) означає, що знайдуться такі c₁, с₂ > 0 і таке n₀, що 0 ≤c₁g(n) ≤ f(n) ≤ c₂g(n) для всіх n > n₀. Тобто складність алгоритму геометрично розміщена в межах умовної смуги між функціями c₁g(n) і c₂g(n) (рис.2.1.а).

О- позначення (о)

Запис f(n) = Q (g(n)) включає дві оцінки: верхню і нижню. Їх можна розділити. Говорять, що f(n) = О(g(n)), якщо знайдеться така константа c > 0 і таке число n₀, що 0 < f(n) ≤ сg(n) для всіх n ≥ n₀ – верхня оцінка, тобто складність алгоритму не перевищує деякої функції сg(n) і геометрично знаходиться нижче її графіку (рис.2.1.б).

Ω – позначення (омега)

Говорять, що f(n) = Ω(g(n)), якщо знайдеться така константа c > 0 і таке число n₀, що 0 ≤ сg(n) ≤ f(n) для всіх n ≥ n₀ – нижня оцінка, тобто складність алгоритму не менша деякої функції сg(n) і геометрично знаходиться вище її графіку (рис.2.1.в).

Рис. 2.1. Визначення оцінок складності:

а) для f(n) = Q (g(n)); б) для f(n) = О(g(n)); в) для f(n) = Ω(g(n)).

Введені позначення володіють властивостями транзитивності, рефлективності та симетричності.

Транзитивність:

f(n) = Q (g(n)) і g(n) = Q (h(n)) то f(n) = Q (h(n))

f(n) = O(g(n)) і g(n) = O (h(n)) то f(n) = O (h(n))

f(n) = Ω (g(n)) і g(n) = Ω (h(n)) то f(n) = Ω (h(n))

Рефлексивність:

f(n) = Q (f(n)), f(n) = O(f(n)), f(n) = Ω (f(n)).

Симетричність:

f(n) = Q (g(n)) якщо і тільки якщо g(n) = Q (f(n)).

Наприклад, алгоритм зчитування й занесення в пам‘ять множини даних має оцінку О(n). Алгоритм двійкового пошуку в таблиці з упорядкованими елементами оцінюється як О (log₂ n). Просте обмінне сортування має оцінку О (n²), a множення матриць - О (n³). Коли говорять, що складність сортування рівна О (n²), під цим мається на увазі, що сортування інформації буде виконано в найкращому випадку за час, пропорційний n².

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

У таблиці 2.1 показана залежність різних видів складності алгоритмів від зростання n. Логарифмічна залежність більш прийнятна, ніж лінійна, а лінійна залежність переважніше поліноміальної й експонентної [1].

Таблиця 2.1.

Складність алгоритмів

2.3. Класи алгоритмів

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

Якщо задача може бути вирішена прямим способом, говорять, що вона має детермінований метод розв'язку [1]. Детерміновані алгоритми завжди забезпечують регулярні розв'язки. В них відсутні елементи, що вносять невизначеність, крім того для них неможлива довільність у виборі рішень, що визначають послідовність дій. Для побудови детермінованих алгоритмів неприпустиме застосування методів проб і помилок. До задач, що мають детермінований розв'язок відносяться математичні рівняння, перевірка даних, друк звітів.

Якщо розв'язок задачі не може бути отриманий прямим методом, а вибирається із заздалегідь визначеної множини варіантів, така задача має недетермінований розв'язок [1]. Алгоритм недетермінований, якщо для його реалізації використовуються методи проб і помилок, повторів або випадкового вибору. До подібних задач належать такі, як знаходження дільників числа, пошук сторінки, а також класичні задачі про комівояжера, про вісім ферзів і задачі знаходження найкоротшого шляху через лабіринт.

Третій, основний тип алгоритмів, призначений не для пошуку відповіді на поставлену задачу, а для моделювання фізичних систем з використанням комп‘ютера.

2.4. Документація алгоритмів

Документація алгоритмів є частиною документації програм і модулів. Якщо використовуваний алгоритм добре відомий або його опис можна знайти в спеціальному джерелі, документація повинна містити ім'я алгоритму або посилання на джерело і авторів. Так, наприклад, для розв'язку задачі про комівояжера можна скористатися алгоритмом Дейкстри. Для знаходження квадратного кореня в основному використовується метод Ньютона - Рафсона, а для обчислення sin(x) - поліноми Чебишева. Упорядкування списків виконується за допомогою сортування Шелла, а також різних видів бульбашкового сортування.

Якщо в алгоритмі використаний спеціальний математичний апарат (як, наприклад, у випадку біноміальних коефіцієнтів), у документацію повинне бути включене математичне обґрунтування методу.

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

Сортування даних. Сортування вибіркою. Метод простої вибірки. Метод бульбашки. Швидкий метод сортування. Порівняння алгоритмічної складності методів.

ЛЕКЦІЯ 3. МЕТОДИ СОРТУВАННЯ.