Реализации алгоритмов, которые мы прошли.

Блок подготовительного курса.

Весс теоретический материал можно найти на канале youtube в виде видеолекций. https://www.youtube.com/playlist?list=PLTpnHAP4hQVfXPFkBRsy8p84rdi-8UKBT Практические примеры реализация некоторых алгоритмов и структур данных имееются в соотвествующих директориях репозитория. Так же по фамилиям есть реализации домашних заданий, которые сдали обучающиеся. Весь перечень курса можно увидеть ниже, в порядке прохождения курса, с примером реализации некоторых алгоритмов.

Сортировки

• Сортировка вставками
• Сортировка расческой
• Поразрядная сортировка
• Сортировка Шелла
• Быстрая сортировка
• Пирамидальная сортировка

Поиск

• Поиск Бойера-Мура(БМ)
• Поиск Кнута-Мориса-Прада(КМП)
• Поиск Рабина-Карпа(РК)

Структуры данных

• Массивы
• Связные списки
• Стэк
• Очередь
• Множества
• Бинарное дерево
• Сбалансированное бинарное дерево поиска

Домашние задания.

• Быстрая сортировка
• Пирамидальная сортировка
• Перемешать одномерный массив. Критерий: максимум два подряд идущих элемента должны быть отсортированы, ЕСЛИ ЭТО ВОЗМОЖНО. Потом рассмотрим лучший алгоритм.
• Поиск k-го элемента порядковой статистики на неупорядоченном массиве. Сложность O(n) по времени.
• Один из поисков: BM, RK, KMP
• Одна из структур данных: Стэк, Очередь
• Бинарное дерево
• Сбалансированное бинарное дерево поиска

Большие задания по блокам.

• Сортировка. Написать функцию, по сортировке N-мерного массива.
  • Условия для работы алгоритма:
    • Все n-мерные массивы, имеют одинаковую размерность внутри своего измерения. Т.е. одномерные массивы все единой длины, двумерные массивы все единой длины и единой высоты и т.д. При этом M != N, где M - длина массива, а N - высота массива.
    • Алгоритм имеет два входа: массив, и кол-во измерений(пространств).
    • Ограничений по O(T) и O(M) нет. Потом будем выбирать лучшее решение.
    • Срок сдачи две недели. Т.е. 8 сентября, + выходные. 10 сентября.
  • Критерии сортировки:
    • Для одномерного массива, простая сортировка.
    • Для двумерного массива, каждая строка должна быть отсортирована внутри себя. Строки между собой должны быть отсортированы по кол-ву минимальных элементов ключей. Сначала сортируем строки по кол-ву минимальных элементов(Например 1), строки где их нет, попадают на первое место, т.к. кол-во минимальных элементов равно 0. Затем, среди строк с одинаковым кол-во минимальных элементов, сортируем по кол-ву след минимальных элементов. Т.е. по 2, если есть 2 и прошлая сортировка была по 1. Затем среди строк с ОДИНАКОВЫМ КОЛ-ВОМ МИНИМАЛЬНЫХ, И СЛЕД МИНИМАЛЬНЫХ ЭЛЕМЕНТОВ, сортируем по след минимальному элементу, например по 3. И т.д.
    • Для Трехмерного массива. Сначала сортируем все двумерные массивы, Потом сортируем двумерные массивы между собой, по кол-ву минимальных элементов ключей. Т.е. на первом месте окажется двумерный массив, у которого меньше всего минимальных элементов, или их вообще нет Например 1. Затем, среди массивов с одинаковым кол-вом минимальных элементов, сортируем по кол-ву второго минимального элемента. Например по 2, если 2 существует и прошлая была по 1. Затем среди массивов с одинаковым кол-вом МИНИМАЛЬНЫХ И СЛЕД МИНИМАЛЬНЫХ ЭЛЕМЕНТОВ сортируем по кол-ву след минимальных элементов, например по 3 если 3 существует и прошлая была по 2. И т.д.
    • И Т.Д. для каждого измерения.
• Поиск. Написать функцию поиска N-мерного массива в M-мерном массиве. При этом N <= M.
  • Условия для работы алгоритма:
    • Все n-мерные массивы, имеют одинаковую размерность внутри своего измерения. Т.е. одномерные массивы все единой длины, двумерные массивы все единой длины и единой высоты и т.д. При этом M != N, где M - длина массива, а N - высота массива.
    • Алгоритм имеет три входа: массив, кол-во измерений(пространств) искомого массива, кол-во измерений(пространств) массива в котором ищем.
    • Ограничений по O(T) и O(M) нет. Потом будем выбирать лучшее решение.
    • Срок сдачи две недели. Т.е. 13 сентября, + выходные. 17 сентября.
  • Критерии поиска:
    • Для одномерного массива простой поиск.
    • Для двумерного массива поиск по полному вхождению одной матрицы в другую.
    • Для трехмерного массива поиск по полному вхождению одного куба элементов в другой.
    • И т.д. для каждого измерения.
• Структуры данных. Программа называется редактор формул.
  • Описание задания. Написать программу, которая позволяет создавать и редактировать формулы. Формулы могут содержать: Числа, операции(+ - * /), приоритеты (, ), заранее известные переменные: x, y, test и т.д. А так же в качестве операнда могут содержать другие формулы. У программы должна быть память. Т.е. сохранение формул не только в оперативной памяти. Переменные задаются как параметры программы, т.е. конфигурация управляемая кодом. Например заранее определить список переменных и их значения(например pi=3.14). У каждой формулы есть название на транслите(по этому названию можно вставлять ее в другую формулу). Программа должна иметь 5 операций:
    • Список имеющихся формул и переменных.
    • Создать формулу - Сохраняет формулу из хранилища.
    • Удалить формулу - Удаляет формулу из хранилища.
    • Редактировать формулу - Загружает формулу позволяя ее редактировать (Можно просто просить писать новую и на место старой ее ставить) с тем же названием.
    • Развернуть формулу - Разворачивает формулу в одну строку. Т.е. заменяет все вложенные формулы на их значения. Пример: f_1 = x + 10 - y; f_2 = f_1 - x * y; f_3 = f_1 + f_2 - 7. Требуется развернуть f_3 = x + 10 - y + x + 10 - y - x * y - 7;
  • Программа должна обрабатывать ситуации когда запрошенных формул/переменныз нет. Ситуации когда вложенность формул является цикличной. Например: f_1 = f_2 + 1; f_2 = f_1 - 3; Так же должна проверять формулу на корректность с точки зрения математики. Пример: валидная - 1+2-3*(2+x). Не валидные: 1+; () - (); 98-++-98; и тд. Все сложные ситуации: -1, 8*(-x), 7-(-5); И т.д. обработка на вшаше усмотрение(смотрите по своим силам).

Блок основого курса.

Весь пройденный материал можно найти на канале youtube в виде видеолекций. https://www.youtube.com/playlist?list=PLTpnHAP4hQVcBCG4ZYEO1PPnyqnF1pB46&disable_polymer=true Практические примеры реализация некоторых алгоритмов и структур данных имееются в соотвествующих директориях репозитория. Так же по фамилиям есть реализации домашних заданий, которые сдали обучающиеся. Весь перечень курса можно увидеть ниже, в порядке прохождения курса, с примером реализации некоторых алгоритмов.

Деревья.

• B - дерево.
• B+, B*, B+* - дерево.
• T - деревья.

Алгоритмы на графах.

• Поиск кратчайшего пути.
• Поиск A*, кратчайшего пути.
• Поиск медианного элемента в графе.
• Поиск длиннейшего пути.
• Поиск независимого множества.