Введення в базові структури даних та алгоритми

Привіт друзі! Вітаю вас на каналі kostrub.online

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



Отож поїхали. Розпочнемо ми з основ computer science - це структури даних.

Концепт структур даних є найбільш фундаментальним для розробника. 
Ці знання є must have для дизайну та проєктування ефективних digital систем.

Ми зіштовхуємось з даними щодня. І тому, те як ми зберігаємо та обробляємо дані має велике значення. Наприклад, візьмем словник українсько-англійської мови.



Ми можемо швидко шукати та перекладати слова. Завдяки тому що усі слова в словнику посортовані за алфавітом. Якби слова були у рандомному / хаотичному порядку - таким словником було б дуже важко користуватись.

Наступний приклад, мапа міста:



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

Наступний приклад, товарний чек:



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

Таким чином, ми бачимо, що нам потрібні різні структури даних для організації різної інформації. Комп'ютер також працює з різними типами даних текст, відео , аудіо, зображення та будь-що. Взагалі організація та групування таких даних має значення, тому що комп'ютери працюють з великою кількістю таких даних. І тому якщо не використовувати оптимальні структури для зберігання - багато обчислювальних ресурсів буде витрачатись дарма.

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

Ми можемо описати такі структури як:

1. Математичні / логічні моделі у абстрактному вигляді

Наприклад

Модель телевізора може бути визначена як електричний прилад, який може:
  • включатись / вимикатись
  • отримувати сигнал
  • програвати аудіо та відео


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

Тож ідемо далі. Визначимо абстрактну модель для списку List. Який може:
  • Зберігати наданні числа
  • Отримувати числа за порядковим номером / індексом у списку
  • Може змінювати числа за індексом
Це і є модель, яку ми незабаром реалізуємо за допомогою мови програмування.

Конкретною реалізацією абстрактного типу даних List наприклад є Array.

2. Ми можемо говорити про структури даних як про реалізацію, тобто про конкретний тип даних.

Наприклад, іншою імплементацією структури List є LinkedList. Цей конкретний тип ми також розглянемо пізніше.

Таким чином ми бачимо, що абстрактна модель описує дані та операції над ними, але нічого не каже про імплементацію.

Ми будемо розглядати структури даних спочатку як абстрактні моделі - а потім будемо робити конкретну реалізацію. Наразі планую розглянути такі базові структури у наступних відео:
  • Array (масив)
  • Linked List (зв'язаний список)
  • Stack (стек)
  • Queue (черга)
  • Tree (дерево)
  • Graph (граф)
Ми розглянемо:
  • Логічну модель (на прикладах TDD / BDD)
  • Операції для структури
  • Ціна операції O(n) / або складність маніпуляції над даними
  • Імплементація структури даних за допомогою мови програмування. Скоріше за все це буде typescript
  • Буду шарити код на github із задачками.
Тому якщо вам цікаві ці теми, чи ви готуєтесь до складного інтерв'ю, раджу вам підписатись на наш канал щоб не пропустити наступні відео. Також пишіть у коментарях ваші питання - будемо розбиратися разом! Далі більше 👍


Опублікувати коментар

0 Коментарі