Які алгоритми потрібно знати, щоб стати добрим програмістом Бібліотека програміста

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

Для початку давайте почнемо з лінійних структур даних та алгоритмів

  • Масиви
  • Зв'язковий перелік
  • Стек
  • Черги

Перейдемо до базових алгоритмів

  • Сортування — Сортування злиттям, Сортування вставками, Швидке сортування, Декілька взаємних перестановок.
  • Множення матриць (Не обов'язково реалізовувати, головне знати алгоритм)
  • Основні алгоритми просіювання
  • Беззнакова математика, включаючи множення та розподіл
  • Алгоритм Евкліда для знаходження НОД (найбільший спільний дільник), Модульна інверсія, Швидке зведення в ступінь
  • Числа Фібоначчі з матричним множенням
  • Нормальний розподіл та математичне очікування
  • Статистика – середнє ймовірнісне значення випадкової величини, медіана, дисперсія, теорема Байєса

Також можна вивчити найпопулярніші алгоритмічні методи:

  • Алгоритми декомпозиції – Бінарний пошук, Знаходження підмасиву з найбільшою сумою елементів
  • Жадібні алгоритми – Вибір завдань, кодування за алгоритмом Хаффмана
  • Динамічне програмування - Ланцюгове матричне множення, Алгоритм розв'язання задачі по укладанню ранця
  • Лінійне програмування – Максимізація параметра, Лінійний час сортування
  • Криптографічні алгоритми – Алгоритм Манакера за знаходженням найдовшого підрядка-паліндрому, алгоритм знаходження найбільшої загальної підпослідовності (LSC), відстань Левенштейна

Тепер перейдемо до типових нелінійних структур даних

Розглянемо графи

  • Список суміжних вершин графа, Матриця суміжності графа, Зважені ребра графа
  • Основні алгоритми обходу - Пошук завширшки, Пошук у глибину і т.д.
  • Алгоритми знаходження найкоротшого шляху - Алгоритм Дейкстри, Алгоритм Флойда-Уоршелла, Алгоритм Беллмана-Форда
  • Мінімальне остовне дерево - Алгоритм Крускала, Алгоритм Пріма

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