1.2. Стратегії розроблення алгоритмів

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

Стратегія, Strategy - поведінковий шаблон проектування, призначений для визначення сімейства алгоритмів, інкапсуляції кожного з них і забезпечення їх взаємозамінюваності. Це дозволяє вибирати алгоритм шляхом визначення відповідного класу. Шаблон Strategy дозволяє міняти вибраний алгоритм незалежно від об'єктів- клієнтів, які його використовують.

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

До базових алгоритмів програмування можна віднести:

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

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

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

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

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

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

Виділимо алгоритмічні стратегії, які використовуються в алгоритмах :

- алгоритми грубої сили;

- жадібні алгоритми;

- "Розділяй і володарюй";

- алгоритми з поверненням;

- евристичні алгоритми;

- зіставлення із зразком і алгоритми обробки рядків/текстів;

- алгоритми чисельної апроксимації;

- online- і offline-алгоритми;

- динамічне програмування; і інші.

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