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

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

Уривок з курсу

Граф (див. рисунок) – це набір вершин та ребер, де вершина – це математична абстракція, яка моделює певні об’єкти (кожен такий об’єкт ототожнюється з ідентифікатором, скажімо цілим числом), а ребро – це певний зв’язок між двома фіксованими вершинами. Наприклад, карту автомобільних доріг між містами можна зображати у вигляді графа: місто – це вершина, ребро – це дорога між двома містами. Якщо кожне ребро має різну "ціну" переходу між вершин, то такий граф називається зваженим, а ця "ціна" називається вагою ребра.

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

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

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