Необхідність уточнення поняття алгоритмів.

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

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

Висновок: для доведення факту не існування алгоритму, необхідно мати точне(строге) визначення поняття “алгоритм”.

У 20-х роках минулого сторіччя задача строгого визначення поняття алгоритму, стала однією з центральних математичних проблем. Дана проблема полягає у спробі дати визначення алгоритму, яке б відповідало існуючій в той час, інтуїтивній уяві про алгоритм. Строге визначення поняття алгоритму запропоноване Аленом Черчем і Стефаном Кліні базується на понятті часткової рекурсивної функції. Дані вчені запропонували ототожнювати інтуїтивне поняття “алгоритм” зі строгим математичним поняттям частково рекурсивної функції. З точки зору англійського математика Алана Т’юринга алгоритмічний процес це робота уявної обчислювальної машини – машини Т’юрінга. Він запропонував ототожнювати інтуїтивне поняття алгоритму з точним поняттям “машина Т’юринга”.

Третій варіант визначення алгоритму запропонував у 1947 російський математик А.А. Марков. З його точки зору алгоритмічний процес – це переробка слів деякого уявного алфавіту за допомогою точно встановлених т правил переробки. Замість поняття алгоритму, він ввів поняття “нормальний алгорифм”.

Прикладна теорія алгоритмів:

1) Основні етапи розробки алгоритмів.

2) Основні інформативні розробки структурних даних.

3) Методи розробки алгоритмів.

1. У узагальному вигляді можна виділити дві базові стадії розробки алгоритму:

1) Розробка наближеного алгоритму;

2) Деталізація алгоритму;

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

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

Типові етапи розробки алгоритмів:

1) Постановка задачі (опис узагальненого задуму алгоритму)

2) Формування задачі, тобто формулювання та вибір методу розв’язку задачі.

3) Розробка узагальненої схеми алгоритму.

4) Розробка окремих блоків алгоритму.

5) З’єднання окремих блоків алгоритму в один алгоритм.

6) Визначення можливості використання стандартних блоків, які сприяють зниженню трудомісткості розв’язку задачі.

7) Розробка блоків логічного контролю.

8) Оптимізація схеми алгоритму.

9) Уточнення параметрів.

10) Оцінка машинного ресурсу.

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

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

Вважаємо, що мета розв’язку задачі відома. При цьому потрібно враховувати що:

а) не всяку мету можна досягти;

б) чи можна досягнути поставлену мету в рамках існуючих обмежень;

На даному етапі достатньо уваги потрібно приділяти відношенням,що реально існують між елементами системи, сутності існуючих в системі проблем; а також причин, що створюють дані проблеми.

Проблеми можуть бути:

а) прості (визначення причин яких, не потребує додаткових досліджень);

б) складні (пояснення їх причин потребує спеціальних досліджень);

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

При аналізі проблеми можливі наступні варіанти:

1) проблема нова – раніше не відома;

2) проблема відома раніше – але рішення, щодо проблеми не приймалося;

3) рішення приймались, але були не вірними;

4) рішення було вірним, але не було виконано.

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

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

Зауваження. Дані, що обробляються алгоритмами діляться на:

1) вхідні;

2) проміжні;

3) вихідні.

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

- внутрішнє;

- зовнішнє.

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

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

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

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

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

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

На 4 етапі відбувається розробка окремих блоків алгоритму.

На 5 етапі відбувається з’єднання окремих блоків в єдиний алгоритм (На цьому етапі працюють багато виконавців. Вони повинні узгодити усі моменти.)

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

На 7 етапі відбувається розробка блоків логічного контролю.

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

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