Алгоритми

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

Гнучкі алгоритми, наприклад, стохастичні, тобто імовірнісні та евристичні.

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

Евристичний алгоритм (від грецького слова "еврика") - алгоритм, що використовує різні розумні міркування без суворих обґрунтувань.

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

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

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

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

Структурна блок-схема, граф-схема алгоритму — графічне зображення алгоритму як схеми пов'язаних між собою з допомогою стрілок (ліній переходу) блоків — графічних символів, кожен із яких відповідає одному кроці алгоритму. Усередині блоку дається опис відповідної дії. Графічне зображення алгоритму широко використовується перед програмуванням завдання внаслідок його наочності, оскільки зорове сприйняття зазвичай полегшує процес написання програми, її коригування за можливих помилок, осмислення процесу обробки інформації. Можна зустріти навіть таке твердження: «Зовні алгоритм є схемою — набір прямокутників та інших символів, усередині яких записується, що обчислюється, що вводиться в машину і що видається на друк та інші засоби відображення інформації».

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

Часткова коректність - програма дає правильний результат для випадків, коли вона завершується.

Повна коректність – програма завершує роботу та видає правильний результат для всіх елементів із діапазону вхідних даних.

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

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

Для розробки алгоритмів та програм використовується алгоритмізація – процес систематичного складання алгоритмів для вирішення поставлених прикладних завдань. Алгоритмізація вважається обов'язковим етапом у процесі розробки програм та вирішення завдань на ЕОМ. Саме для прикладних алгоритмів та програм принципово важливі детермінованість, результативність та масовість, а також правильність результатів вирішення поставлених завдань.

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

Форми запису алгоритму:

• словесна чи вербальна: природною мовою;

• алгоритмічною мовою: мовою програмування або псевдокодом;

• у машинному коді (код процесора ЕОМ);

• у математичній нотації;

• схематична:

  • графічна (наприклад, блок-схеми та ДРАКОН-схеми);

  • структурограми (діаграми Нассі-Шнейдермана)

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

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

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

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

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

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

• Завершуваність (кінцевість) — у вужчому розумінні алгоритму як математичної функції, за правильно заданих початкових даних алгоритм повинен завершувати роботу і видавати результат за певну кількість кроків. Дональд Батіг процедуру, яка задовольняє всім властивостям алгоритму, крім, можливо, кінцівки, називає методом обчислення (англ. computational method). Проте досить часто визначення алгоритму не включає завершальність за кінець. І тут алгоритм (метод обчислення) визначає часткову функцію. Для ймовірнісних алгоритмів завершуваність зазвичай означає, що алгоритм видає результат з ймовірністю 1 для будь-яких правильно заданих початкових даних (тобто може в деяких випадках не завершитися, але ймовірність цього повинна дорівнювати 0).

• Масовість (універсальність). Алгоритм може бути застосований до різних наборів початкових даних.

• Результативність - завершення алгоритму певними результатами.

Цикл (повторення) – це тип алгоритму, у виконання якого одне чи кілька дій потрібно повторити кілька разів.