Лекція 7.1. Алгоритмізація
ДЕ 7. Алгоритмізація та програмування. Мови програмування високого рівня
Слово «алгоритм» походить від «algorithmi» - латинської форми опису імені великого узбецького математика IX ст. аль - Хорезмі, який сформулював правила виконання арифметичних дій. Спочатку під алгоритмом і розуміли тільки правила виконання чотирьох арифметичних дій над багатозначними числами.
Поняття алгоритму - одне з фундаментальних понять інформатики.
Алгоритм - це формальний опис способу вирішення завдання, шляхом розбиття її на кінцеву за часом послідовність дій (елементарних операцій). Під словом «формальне» мається на увазі, що опис має бути абсолютно повним і враховувати всі можливі ситуації, які можуть зустрітися по ходу рішення. Під елементарної операцією розуміється дія, яка за певними критеріями (наприклад, очевидності) не має сенсу деталізувати.
Алгоритм на обраною мовою програмування записується за допомогою команд опису даних, обчислення значень і управління послідовністю виконання програм.
Алгоритм повинен бути складений таким чином, щоб виконавець, в розрахунку на якого він створений, міг однозначно і точно слідувати командам алгоритму і ефективно отримувати певний результат. Це накладає на записи алгоритму ряд обов'язкових вимог, суть яких випливає з наведеного вище неформального тлумачення поняття алгоритму. Сформулюємо ці вимоги у вигляді переліку властивостей, яким повинні задовольняти алгоритми.
Дискретність (розривність) - це властивість алгоритму, що характеризує його структуру: кожен алгоритм складається з окремих закінчених дій. Кажуть: «Ділиться на кроки».
Масовість - придатність алгоритму до всіх завдань даного типу, при будь-яких вихідних даних. Наприклад, алгоритм вирішення квадратного рівняння в області дійсних чисел повинен містити всі можливі результати рішення, тобто розглянувши значення дискримінанту, алгоритм знаходить або два різних кореня, або два рівних, або робить висновок про те, що дійсних коренів немає.
Визначеність (детермінованість, точність) - властивість алгоритму, яке вказує на те, що кожен крок алгоритму має бути строго визначений, і не допускати різних тлумачень; також строго повинен бути визначений порядок виконання окремих кроків. В алгоритмах неприпустимі ситуації, коли після виконання чергової команди виконавцю неясно, яка з команд алгоритму повинна виконуватися на наступному кроці.
Результативність - властивість, що складається в тому, що будь-який алгоритм повинен завершуватися за кінцеве число кроків. Висновок про те, що рішення не існує - теж результат. Питання про розгляд нескінченних алгоритмів залишається за рамками теорії алгоритмів.
Формальність - це властивість вказує на те, що будь-який виконавець, здатний сприймати і виконувати інструкції алгоритму, діє формально, тобто відволікається від змісту поставленого завдання і лише строго виконує інструкції. Міркувати «що, як і чому?» Повинен розробник алгоритму, а виконавець формально (не думаючи) по черзі виконує запропоновані команди і отримує необхідний результат.