Algorithms-and-Data-Structures

Данный репозиторий создан для изучения теоретической составляющей и реализации основных структур данных и алгоритмов.

Будут затронуты следующие области теории алгоритмов:

Численные алгоритмы:

• Нахождение наибольшего общего делителя
• Возведение в степень
• Нахождение простых множителей
• Нахождение простых элементов (решето Эратосфена)
• Проверка на простоту (тест простоты Ферма)

Связные списки:

• Однонаправленные связные списки (передвижение по списку, нахождение ячеек по данным и по индексу, использование ограничителей, добавление и удаление ячеек, изменение элемента по индексу, очистка, получение максимума)
• Двунаправленные связные списки (передвижение по списку, нахождение ячеек по данным и по индексу, использование ограничителей, добавление и удаление ячеек, изменение элемента по индексу, очистка, получение максимума)
• Копирование связного списка (singly, doubly)
• Сортировка вставкой (singly, doubly)
• Сортировка выбором (singly, doubly)
• Поиск цикла (помеченные ячейки, метод кролика и черепахи, повторная трассировка списка)

Массивы:

• Одномерные массивы (линейный поиск, нахождение минимальной, средней и максимальной величин, вставка и удаление элементов)
• Двумерные массивы (линейный поиск, нахождение минимальной, средней и максимальной величин)
• Массивы высокой размерности (3D)
• Треугольные массивы

Стеки и очереди:

• Стеки
  • Стеки связных списков
  • Стеки массивов
  • Двойные стеки
  • Алгоритмы с использованием стеков
• Очереди
  • Очереди связных списков
  • Очереди массивов

Сортировка:

• Алгоритмы O(N ^ 2)
  • Сортировка вставкой
  • Сортировка выбором
  • Пузырьковая сортировка
• Алгоритмы O(N * log N)
  • Пирамидальная сортировка
  • Быстрая сортировка
  • Сортировка слиянием
• Алгоритмы быстрее O(N * log N)
  • Сортировка подсчетом
  • Блочная сортировка

Поиск:

• Линейный поиск
• Бинарный поиск
• Интерполяционный поиск

Хеш-таблицы:

• Открытая адресация (удаление элементов, линейное пробирование, квадратичное пробирование, псевдослучайное пробирование, двойное хеширование, упорядоченное хеширование)

Графы:

• Поиск в ширину
• Поиск в глубину
• Топологическая сортировка
• Поиск компонент связности
• Поиск кратчайшего пути

Рекурсия:

• Базовые алгоритмы
  • Факториал
  • Числа Фионаччи
  • Ханойские башни
• Алгоритмы с возвратом
  • Задача о восьми ферзях
  • Ход коня
  • Сочетания и размещения
  • Сочетания с циклами
  • Сочетания с повторениями
  • Сочетания без повторений
  • Размещения с повторениями
  • Размещения без повторений

Деревья:

• Обход дерева
  • Обход в прямом порядке
  • Симметричный обход
  • Обход в обратном порядке
  • Обход в ширину
• Упорядоченные деревья:
  • Добавление вершин
  • Поиск вершин
  • Удаление вершин
• Связные деревья

Сбалансированные деревья:

• АВЛ-деревья
  • Добавление значений
  • Удаление значений
• 2-3-деревья
  • Добавление значений
  • Удаление значений
• В-деревья
  • Добавление значений
  • Удаление значений
• Иерархически организованные В-деревья
• В+-деревья

Деревья принятия решений:

• Поиск по деревьям принятия решений
  • Задачи оптимизации
  • Метод полного перебора
  • Метод ветвей и границ
  • Эвристика дерева принятия решений

Строковые алгоритмы:

• Парные скобки
  • Вычисление арифметических выражений
  • Синтаксические деревья
• Сопоставление с шаблоном
  • Детерминированные конечные автоматы
  • Построение ДКА для регулярных выражений
  • Недетерминированные конечные автоматы
• Поиск строк
• Вычисление редакционного расстояния

Криптография:

• Перестановочные шифры
  • Перестановка строк/столбцов
  • Перестановка столбцов
  • Маршрутные шифры
• Шифры подстановки
  • Шифр Цезаря
  • Шифр Виженера
  • Простая подстановка
  • Схема одноразовых блокнотов
• Блочные шифры
  • Шифр Фейстеля
• Шифрование с открытым ключом и RSA (Python)

Все перечисленные выше структуры данных и алгоритмы будут реализованы на языке C++ или Python.

Источники:

• http://www.e-maxx-ru.1gb.ru/algo/
• "Алгоритмы, теория и практическое применение", Род Стивенс