- •Временная сложность алгоритмов
- •Задачи решимости, задачи оптимизации
- •Применение полного перебора для решения задачи коммивояжера. Перебор всех перестановок. Простой рекурсивный алгоритм
- •Применение полного перебора для решения задачи о рюкзаке. Перебор всех подмножеств множества. Сведение к перебору двоичных векторов. Коды Грея.
- •Общая схема метода ветвей и границ. Применение метода ветвей и границ для решения задачи о рюкзаке
- •Динамическое программирование
- •Жадные алгоритмы. Задача о выборе заявок. Свойства задач, для которых применимы жадные алгоритмы.
- •Эвристические методы решения задач. Эвристика жадного выбора и локального поиска. Примеры. Задача о покрытии, задача о камнях. Метаэвристики
- •Абстрактные типы данных. Атд стек, очередь, корневое дерево, множество, словарь, очередь с приоритетом, система непересекающихся множеств, граф и способы их реализации
- •Обходы графа. Поиск в глубину, поиск в ширину
Абстрактные типы данных. Атд стек, очередь, корневое дерево, множество, словарь, очередь с приоритетом, система непересекающихся множеств, граф и способы их реализации
Определение: Абстрактный тип данных (АТД) – матмодель с совокупностью операторов, определённых в рамках этой модели. Они удобны при описании алгоритмов и представляются с помощью структур данных.
Определение: Структуры данных – наборы переменных различных типов, объединённых определённым образом. Некоторые примеры АТД и их операций:
1. Стек – список, в котором вставка и удаление выполняются только на одном конце (принцип LIFO – Last in, First out), называемом вершиной. Операторы – PUSH, POP, PEEK.
2. Очередь – список, в котором элементы добавляются с заднего конца, а удаляются с переднего(принцип FIFO – First in, First out). Операторы – ENQUEUE, DEQUEUE, PEEK.
3. Корневое дерево (дерево) – иерархическая структура данных, состоящая из узлов и ребер. Узлы связаны между собой и имеют один корневой узел.
4. Множество - коллекция уникальных элементов без определенного порядка. Операторы: объединиение, пересечение, разность, принадлежность элемента, вставка и удаление элемента и т.д.
5. Словарь (ассоциативный массив) – множество пар вида {«Ключ»,«Значение»}. Операторы: Insert, Remove, Find, ContainsKey, MakeNull
6. Очередь с приоритетом - коллекция элементов, где каждый элемент имеет свой приоритет, и элементы извлекаются в порядке убывания приоритета. Операторы: Insert, DeleteMin, DeleteMax, MakeNull
7. Система непересекающихся множеств:
Операторы: Merge, Find, Init - Модель: система непересекающихся множеств представляет собой набор непересекающихся множеств, где каждое множество имеет свой уникальный идентификатор.
8. Граф - совокупность вершин и ребер, связывающих эти вершины. Операторы:: добавление и удаление вершин и ребер, поиск пути между вершинами.
Существуют различные способы реализации АТД, включая массивы, связные списки, хэш-таблицы, деревья и т. д. Выбор способа реализации зависит от требований по временной и пространственной сложности операций, типа доступа к данным и другим факторам.
Примеры реализации АТД:
- Хэш-таблица с разным доступом: Хэш-таблица представляет собой структуру данных, которая использует хэш-функцию для преобразования ключа в индекс таблицы. Это позволяет быстро находить элементы по ключу. Примеры операций: добавление элемента, удаление элемента, поиск элемента по ключу.
- Операции с двоичной кучей (на дереве и массиве): Двоичная куча представляет собой структуру данных, где каждый узел имеет значение больше (для макс-кучи) или меньше (для мин-кучи) значений его потомков. Это позволяет эффективно находить и извлекать элемент с наивысшим или наименьшим значением. Примеры операций: вставка элемента, удаление элемента с наивысшим или наименьшим значением.
- Нагруженное дерево: Нагруженное дерево представляет собой структуру данных, в которой каждый узел имеет нагрузку (дополнительное значение, отражающее свойство узла). Это может быть использовано, например, для реализации красно-черного дерева, AVL-дерева или B-дерева. Примеры операций: вставка узла, удаление узла, поиск узла.
- Представление графа: Граф можно представить с помощью матрицы смежности (двумерный массив), списка смежности (список вершин и их соседей) или списка ребер (список пар вершин). Примеры операций: добавление вершины и ребра, удаление вершины и ребра, поиск пути между вершинами.
Время выполнения операций зависит от выбранной реализации и конкретной задачи. Некоторые способы реализации могут обеспечивать более эффективные операции, например, хэш-таблицы могут иметь почти константное время выполнения операций в среднем случае (O(1)), а двоичные кучи могут иметь время выполнения операций в худшем случае O(log n), где n - размер структуры данных.