 |
|
Алгоритм. Властивості алгоритмів. Етапи розв’язування прикладної задачі з допомогою ЕОМ.
У 820 р. нашої ери в Багдаді був написаний підручник «Аль-Джабр Ва-Аль-Мукабала» («Наука виключення скорочення»), у якому були представлені правила виконання чотирьох арифметичних дій над числами в десятковій системі числення. Автором підручника був арабський математик Мухаммед бен Муси аль-хорезмі. Від слів «Аль-Джабр» у назві підручника пішло слово «алгебра», а від імені аль-хорезмі слово «алгоризм», що пізніше перейшло в «алгоритм» і що розуміється, як сукупність правил.
Найдавнішому записаному алгоритму вже 3800 років. Близько 1800 р. до н.е. житель Вавилона зобразив на глиняній табличці процедуру рішення задачі, у якій було потрібно знайти, скільки часу піде на подвоєння наявної кількості зерна при річному приросту в 20%. Цей алгоритм використовується і зараз у банківських розрахунках.
У ІІІ ст. до н.е. в класичному трактаті «Початок» грецького математика Евкліда був описаний алгоритм, застосовуваний і зараз для знаходження найбільшого загального дільника двох чисел.
Інтуїтивне уявлення про значення слова «алгоритм» має кожний. Це процедура, рецепт рішення задачі, що однозначно наказує, як і в якій послідовності виконувати дії. Незважаючи на простоту і гнучкість такого представлення, воно нечітке й обмежене. Кожний з вас уміє зав'язувати шнурки. Спробуйте (без картинок і демонстрацій) описати алгоритм зав'язування шнурків. Великий розділ математики за назвою «алгоритмізація» вивчає алгоритми, їхні властивості, методи і прийоми побудови алгоритмів.
Будь який алгоритм припускає виконавця. Оскільки мова йде про рішення задач за допомогою комп'ютера, то виконавцем є комп'ютер. Можна сказати, що алгоритм це однозначна кінцева послідовність точно визначених кроків чи дій, що забезпечує рішення задачі і для виконання якої потрібно кінцевий обсяг оперативної пам'яті і кінцевий час.
Властивості алгоритмів
Масовість. Алгоритм може застосовуватися для рішення цілого класу однотипних задач.
Закінченість. Алгоритм повинний складатися з кінцевого числа кроків, кожний з яких вимагає для свого виконання кінцевого проміжку часу.
Результативність. По закінченні виконання алгоритму повинний бути отриманий деякий передбачуваний результат.
Однозначність. Виконання кожного кроку алгоритму і всієї послідовності кроків повинно здійснюватися єдиним чином. Це означає, що скільки б раз алгоритм не застосовувався до тих самих вихідних даних, результати виконання кожного кроку і всієї послідовності в цілому будуть ті самі. Іноді цю вимогу називають визначеністю або детермінованістю (від анг. to determine визначати).
Операції, які використовуються в алгоритмі, не повинні мати двоякого тлумачення; не повинно виникати питання: що саме і як треба робити? Порядок виконання операцій має бути строго визначеним
Правильність. При застосуванні алгоритму до припустимих вихідних даних повинний бути отриманий необхідний результат. Доказ правильності алгоритму один з найбільш важких етапів його створення. Найбільш розповсюджена процедура перевірки правильності алгоритму (як і програми) це обґрунтування правомірності і перевірка правильності виконання кожного з кроків на наборі тестів, підібраних так, щоб охопити всі припустимі вхідні і всі припустимі вихідні дані.
Ефективність. Алгоритм повинний забезпечувати рішення задачі за мінімальний час з мінімальними витратами оперативної пам'яті. Для оцінки алгоритмів існує багато критеріїв. Найчастіше аналіз алгоритму (чи, як говорять, аналіз складності алгоритму) складається з оцінки тимчасових витрат рішення задачі в залежності від «розміру» вихідних даних; використовуються також терміни «тимчасова складність» чи “трудомісткість” алгоритму. Фактично, ця оцінка зводиться до визначення кількості основних операцій, виконуваних в алгоритмі, оскільки кожна конкретна операція виконується за кінцевий заздалегідь відомий час.
Формальність. Будь-який виконавець, здатний сприймати і виконувати вказівки алгоритму (навіть не розуміючи їх змісту), діючи за алгоритмом, може виконати поставлене завдання
Алгоритм чітко задана послідовність кроків, які мають бути виконані для розв'язання завдання.
Базові структури алгоритмів
При конструюванні алгоритму кожну вказівку можна подати у вигляді трьох типів простих вказівок, так званих базових алгоритмічних структур: слідування, розгалуження, повторення.
1. Слідування.
Вказівка подається у вигляді послідовності двох (або більше) виконуваних одна за одною простих команд
2. Розгалуження (вибір).
Для виконання вказівки треба спочатку визначити, хибне чи істинне деяке твердження. Якщо твердження істинне, то виконується перша команда і на цьому вказівка розгалуження закінчується. Якщо твердження хибне, то виконується 2 команда і на цьому виконання вказівки розгалуження закінчується.
3. Повторення.
Розрізняють два типи циклів цикл-ПОКИ і цикл-ДО.
а) У структурі цикл-Поки для виконання вказівки спочатку треба визначити, істинне чи хибне твердження. Якщо твердження істинне, то виконується вказівка №1 і знову повертаються до визначення "Істинності твердження”. Якщо ж твердження хибне, то виконання вказівки повторення вважається закінченим.
б) У структурі цикл-ДО спочатку виконується вказівка, а потім визначається істинність твердження. Якщо твердження хибне, то знову виконується вказівка і визначається істинність твердження. Якщо ж твердження істинне, то виконання вказівки повторення вважається закінченим.
Будь-який алгоритм подається у вигляді лінійної послідовності базових алгоритмічних структур.
Лінійний алгоритм - алгоритм, в якому використовується тільки структура "слідування".
Алгоритмом з розгалуженням називається алгоритм, в основі якого лежить структура "розгалуження".
Циклічний алгоритм - алгоритм, в основі якого лежить структура "повторення" .
Етапи розв’язування прикладної задачі за допомогою ЕОМ
На жаль, готове ПЗ (програмове забезпечення) існує не для всіх задач, що приходиться вирішувати. У таких випадках необхідно створювати ПЗ для рішення поставленої задачі самостійно. Розглянемо докладніше етапи цього процесу.
Перший етап постановка задачі.
Другий етап побудова моделі.
Наступний, третій етап, при відсутності готового ПЗ це вибір чи розробка методу рішення задачі.
Під методом розуміється конкретний спосіб рішення поставленої задачі в рамках побудованої моделі. Звичайно метод рішення задачі полягає в застосуванні набору спеціально розроблених прийомів для рішення задач даного типу. Якщо відомих методів немає чи наявні не можуть бути застосовані для рішення даної конкретної задачі, наприклад, коли умови на вихідні дані обмежують застосування загального методу, то необхідно розробити придатний метод самостійно.
Четвертий етап розробка алгоритму рішення задачі відповідно до обраного методу.
Розробка і складання алгоритму є одним з найважливіших етапів у процесі рішення задачі.
Якщо розроблений неправильний алгоритм, то задача не буде вирішена, тому що необхідний результат отриманий не буде. Якщо розроблений поганий алгоритм, то процес рішення задачі зажадає великої кількості часу або великих витрат оперативної пам'яті комп'ютера. Якщо розроблений гарний алгоритм, то задача буде вирішена найбільше ефективно.
П'ятий етап складання програми за розробленим алгоритмом. Цей етап вимагає уміння програмувати.
Шостий етап налагодження і тестування програми
Налагодження програми це процес виявлення помилок і неточностей у програмі, що виникають на етапі її компіляції, інтерпретації чи виконання.
Тестування це один зі способів верифікації, тобто перевірки правильності
Тестування полягає в перевірці правильності роботи програми на різних тестових прикладах. У тестових прикладах заздалегідь відомий результат, так що можна порівняти результати роботи програми і дійсне рішення задачі (тобто те, що повинно бути отримане в результаті роботи програми). Особливу роль грає повнота системи тестів. Вона забезпечує перевірку правильності роботи програми у всіх можливих ситуаціях.
Правильна робота програми на повній системі тестів це майже повна гарантія її правильності. Існують більш строгі методи верифікації програм. Для налагодження і верифікації програм розроблені різні підходи.
Сьомий етап виконання програми з вихідними даними розв'язуваної задачі.