Семенов Алексей 1 курс МО БиТ
| Название тем | Задания |
|---|---|
| Введение. Базовые понятия. Асимптотика. Примеры. Методы оценки. | |
| Сортировки сравнением. Рандомизация. | 1. Реализовать алгоритм сортировки обменами 2. Реализовать алгоритм сортировки выбором 3. Реализовать алгоритм сортировки простыми вставками |
| Сортировки за линейное время. Статистика. | 1. Реализовать алгоритм сортировки слияниями (рекурсивный, использующий стек отложенных заданий) 2. Реализовать метод медианы трех (рекурсивный, использующий стек отложенных заданий) 3. Реализовать алгоритм Хоара (рекурсивный, использующий стек отложенных заданий) 4. Реализовать алгоритм Шелла 5. Реализовать алгоритм сортировки подсчетом |
| Линейные структуры. Коллекции. Очередь. Очередь с приоритетом. Куча. | 1. Напечатать в порядке возрастания первые n натуральных чисел, в разложение которых на простые множители входят только числа 2, 3 и 5. Алгоритм использует очереди. 2. Алгоритм сортировки HeapSort как пример использования приоритетной очереди 3. Реализовать операции ADD и GET для двоичной кучи |
| Поиск по образцу. Хэширование. Хэш-таблицы. Карп-Рабин. | 1. Реализовать Hash-таблицу со списками. 2. Реализация алгоритмов Бойера-Мура, Рабина и Кнута-Морриса-Пратта. 3. Реализация алгоритма Эдмондса-Карпа для максимального потока в сети. |
| Деревья. 2-3. Red-Black. B-tree. | 1. Построить бинарное дерево по его скобочной инфиксной записи 2. Реализация одного рекурсивного алгоритма префиксного,постфиксного и инфиксного обхода бинарного дерева. |
| Метод «разделяй и властвуй». Динамическоепрограммирование. – Числа Фибоначчи – Задача пути на Манхэттене – Др. |
1. Вычисление числа Фибоначчи методом динамического программирования. 2. Алгоритм задачи о перемножении матриц |
| Поиск кратчайшего пути. | 1. Реализация алгоритма поиска в ширину 2. Реализация алгоритма поиска в глубину 3. Алгоритма Дейкстры поиска кратчайшего пути из одной вершины |