Файл: Экзаменационные вопросы по курсу Структуры и алгоритмы обработки данных.pdf

Вопрос 9. Абстрактный тип данных «словарь». Основные операции словаря.
Бинарные деревья поиска. Основные операции, их вычислительная сложность.
Анализ эффективности бинарного дерева поиска в среднем и худшем случае.
Абстрактный тип данных «словарь» - структура данных, которая хранит пары ключ- значение и позволяет быстро находить значение по заданному ключу.
Основные операции словаря:
-
Вставка элемента (put): добавляет новую пару ключ-значение в словарь
-
Удаление элемента (remove): удаляет пару ключ-значение из словаря по заданному ключу
-
Поиск элемента по ключу (get): находит значение по заданному ключу
-
Проверка наличия элемента (contains): проверяет, содержится ли элемент с заданным ключом в словаре
Бинарное дерево поиска - это структура данных, которая представляет собой бинарное дерево, в котором каждый узел содержит ключ и значение, а также имеет не более двух потомков. Ключи в левом поддереве меньше, чем ключ в корне, а ключи в правом поддереве больше, чем ключ в корне.
Основные операции бинарного дерева поиска:
-
Вставка элемента (insert): добавляет новый узел с заданным ключом и значением в дерево
-
Удаление элемента (delete): удаляет узел с заданным ключом и значением из дерева
-
Поиск элемента по ключу (search): находит узел с заданным ключом и возвращает его значение
-
Обход дерева (traversal): позволяет обойти все узлы дерева в заданном порядке
Вычислительная сложность операций бинарного дерева поиска зависит от его высоты.
В среднем случае, когда дерево сбалансировано, высота равна O(log n), где n - количество узлов в дереве. В худшем случае, когда дерево несбалансированно и имеет форму списка, высота равна O(n). Следовательно, операции поиска, вставки и удаления в среднем случае имеют сложность O(log n), а в худшем случае - O(n).
Анализ эффективности бинарного дерева поиска в среднем и худшем случае
Структура данных эффективна для хранения и поиска элементов, если дерево сбалансировано.
Если дерево не сбалансировано, то его эффективность значительно снижается и может быть хуже, чем у других структур данных.
Для эффективности операций поиска, вставки и удаления в бинарном дереве поиска необходимо поддерживать его сбалансированность.

Вопрос 10. Абстрактный тип данных «словарь». Хеш-таблицы. Основные операции
хеш-таблицы. Хеш-функции. Методы разрешения коллизий.
Абстрактный тип данных «словарь» - структура данных, которая хранит пары ключ- значение и позволяет быстро находить значение по заданному ключу. Словарь может быть реализован с помощью хеш-таблицы.
Хеш-таблица представляет собой массив, в котором каждый элемент содержит пару ключ- значение. Хеш-функция используется для преобразования ключа в индекс массива, где будет храниться соответствующее значение.
Основные операции хеш-таблицы включают:
-
Вставка элемента (put): добавляет новую пару ключ-значение в хеш-таблицу
-
Удаление элемента (remove): удаляет пару ключ-значение из хеш-таблицы по заданному ключу
-
Поиск элемента по ключу (get): находит значение по заданному ключу
-
Проверка наличия элемента (contains): проверяет, содержится ли элемент с заданным ключом в хеш-таблице
Хеш-функции используются для преобразования ключей в индексы массива. Хорошая хеш- функция должна распределять ключи равномерно по всему массиву, чтобы минимизировать количество коллизий.
Коллизии возникают, когда два или более ключей преобразуются в один и тот же индекс массива.
Методы разрешения коллизий:
-
Метод цепочек (chaining): каждый элемент массива содержит связанный список пар ключ- значение. Когда возникает коллизия, новый элемент добавляется в соответствующий список.
-
Метод открытой адресации (open addressing): при возникновении коллизии новый элемент помещается в первый свободный слот в массиве, начиная с индекса, полученного с помощью хеш-функции.
Хеш-таблицы имеют высокую эффективность операций вставки, удаления и поиска в среднем случае. Однако, при плохой хеш-функции или большом количестве коллизий, эффективность может значительно снижаться. Поэтому, для обеспечения эффективности операций в хеш-таблице необходимо выбирать хорошую хеш-функцию и метод разрешения коллизий.

Вопрос 11. Очереди с приоритетом. Бинарные кучи. Реализация бинарной кучи на
основе массива. Построение бинарной кучи за время O(n).
Очередь с приоритетом - это абстрактный тип данных, который поддерживает операции добавления элемента с приоритетом и удаления элемента с наивысшим приоритетом.
Приоритет может быть определен различными способами, например, числовым значением или порядком элементов.
Бинарная куча - это структура данных, которая представляет собой полное двоичное дерево, где каждый узел имеет значение больше (или меньше) значений его потомков.
Бинарная куча обычно реализуется в виде массива, где элементы располагаются по уровням дерева слева направо.
Реализация бинарной кучи на основе массива:
-
Корень дерева хранится в первом элементе массива (индекс 0)
-
Для каждого узла i, его левый потомок имеет индекс 2i+1, а правый потомок - 2i+2
-
Для каждого узла i, его родитель имеет индекс (i-1)/2
Операции добавления и удаления элемента с приоритетом в бинарной куче выполняются за время O(log n), где n - количество элементов в куче.
Построение бинарной кучи за время O(n):
-
Изначально массив элементов рассматривается как бинарная куча с единственным узлом
(корнем)
-
Для каждого узла i, начиная с последнего узла и до корня, выполняется процедура
просеивания вниз (sift down), которая перемещает элемент вниз по дереву, пока он не займет свое место в куче.
Процедура просеивания вниз для узла i:
-
Если у узла i нет потомков, то просеивание завершается
-
Если у узла i есть только левый потомок j, то если значение j больше, чем значение i, то элементы меняются местами, а просеивание продолжается для узла j
-
Если у узла i есть оба потомка j и k, то если значение j больше, чем значение k и больше, чем значение i, то элементы меняются местами, а просеивание продолжается для узла j.
Если же значение k больше, чем значение j и больше, чем значение i, то элементы меняются местами, а просеивание продолжается для узла k. Если же значения j и k меньше или равны значению i, то просеивание завершается.

Вопрос 12. Графы. Виды графов. Способы представления графов в памяти.
Реализация графа на основе матрицы смежности.
Граф - это абстрактный математический объект, который представляет собой набор вершин
(узлов) и ребер (связей) между ними.
Виды графов:
В зависимости от свойств вершин и ребер, графы могут быть ориентированными или неориентированными, взвешенными или невзвешенными, связными или несвязными и т.д.
Способы представления графов в памяти: матрица смежности, список смежности и список ребер.
Матрица смежности - это двумерный массив, где каждый элемент a[i][j] равен 1, если между вершинами i и j есть ребро, и 0 в противном случае (для неориентированного графа матрица симметрична относительно главной диагонали). Для взвешенного графа элементы массива могут хранить веса ребер. Матрица смежности позволяет быстро проверять наличие ребра между двумя вершинами, но занимает O(n^2) памяти, где n - количество вершин в графе.
Реализация графа на основе матрицы смежности заключается в создании двумерного массива и заполнении его значениями 0 или 1 (или весами ребер). Для добавления нового ребра между вершинами i и j необходимо установить значение a[i][j] (или a[j][i] для неориентированного графа) равным 1 (или весу ребра). Для удаления ребра достаточно установить значение a[i][j] равным 0 (или удалить значение веса). Операции добавления и удаления вершин требуют пересоздания всей матрицы смежности.

Вопрос 13. Обход графа. Обход в глубину (DFS). Обход в ширину (BFS).
Обход графа - это процесс посещения каждой вершины графа ровно один раз. Обходы графа используются для поиска путей между вершинами, проверки связности графа, поиска циклов и т.д.
Обход в глубину (DFS) - это алгоритм, который начинает с одной вершины и идет как можно глубже по каждому ребру, пока не достигнет конца пути. Затем он возвращается на предыдущий уровень и продолжает идти в другом направлении. Алгоритм DFS использует стек для хранения вершин, которые нужно посетить.
Обход в ширину (BFS) - это алгоритм, который начинает с одной вершины и идет по всем смежным вершинам на текущем уровне, затем переходит на следующий уровень и повторяет процесс. Алгоритм BFS использует очередь для хранения вершин, которые нужно посетить.
Каждый из этих алгоритмов имеет свои преимущества и недостатки в зависимости от задачи, которую необходимо решить. Например, обход в глубину может быть более эффективным для поиска путей между вершинами, тогда как обход в ширину может быть более эффективным для поиска кратчайшего пути между вершинами.
Вопрос 14. Задача поиска кратчайшего пути в графе. Постановки задачи о кратчайшем
пути. Алгоритмы поиска кратчайшего пути в графе. Алгоритм Дейкстры.
Вычислительная сложность алгоритма Дейкстры.
Задача поиска кратчайшего пути в графе заключается в нахождении пути между двумя вершинами графа с минимальной суммой весов ребер на этом пути.
Постановки задачи о кратчайшем пути:
-
В невзвешенном графе ищется кратчайший путь между двумя вершинами, где каждое ребро имеет одинаковый вес.
-
Во взвешенном графе каждое ребро имеет свой вес, и необходимо найти кратчайший путь между двумя вершинами с учетом этих весов.
Алгоритмы поиска кратчайшего пути в графе, например:
-
Алгоритм Дейкстры - находит кратчайший путь от одной из вершин до всех остальных вершин в графе. Алгоритм работает только для неотрицательных весов ребер.
-
Алгоритм Беллмана-Форда - находит кратчайший путь от одной из вершин до всех остальных вершин в графе. Алгоритм работает для графов с отрицательными весами ребер.
-
Алгоритм Флойда-Уоршелла - находит кратчайшие пути между всеми парами вершин в графе.
Алгоритм Дейкстры - алгоритм поиска кратчайшего пути в графе. Он использует жадный подход и работает только для неотрицательных весов ребер. Алгоритм Дейкстры начинает с одной вершины и находит кратчайший путь до каждой другой вершины в графе. Алгоритм использует очередь с приоритетом для хранения вершин, которые нужно посетить.
Вычислительная сложность алгоритма Дейкстры зависит от структуры данных, используемых для реализации очереди с приоритетом. В худшем случае алгоритм имеет временную сложность O(|E| + |V| log |V|), где |V| - количество вершин в графе, а |E| - количество ребер в графе.

Вопрос 15. Остовные деревья минимальной стоимости (minimum spanning tree, MST).
Алгоритмы построения MST. Система непересекающихся множеств.
Алгоритм Крускала. Алгоритм Прима.
Остовное дерево минимальной стоимости (MST) - это подграф связного взвешенного графа, который содержит все вершины графа и имеет минимальную сумму весов ребер.
Алгоритмы построения MST:
Алгоритм Крускала начинает с того, что все вершины графа являются отдельными компонентами. Затем ребра графа сортируются по возрастанию весов, и для каждого ребра проверяется, принадлежат ли его конечные вершины разным компонентам. Если да, то ребро добавляется в MST и две компоненты объединяются. Алгоритм продолжается до тех пор, пока все вершины не станут частью одной компоненты.
Алгоритм Прима начинает с выбора одной вершины и добавления всех ее соседних ребер в приоритетную очередь. Затем выбирается ребро с наименьшим весом из очереди, и его конечная вершина добавляется в MST. Затем все соседние ребра этой вершины добавляются в очередь, если они не принадлежат уже MST. Алгоритм продолжается до тех пор, пока все вершины не станут частью MST.
Алгоритм Крускала имеет временную сложность O(|E| log |E|), где |E| - количество ребер в графе.
Алгоритм Прима имеет временную сложность O(|E| log |V|), где |V| - количество вершин в графе. В общем случае алгоритм Прима работает быстрее, если |E| много меньше, чем |V|^2.

Вопрос 16. Основные методы разработки алгоритмов. Метод «грубой силы» (brute
force). Метод декомпозиции. Алгоритмы, основанные на методе декомпозиции.
Метод "грубой силы" заключается в переборе всех возможных вариантов решения задачи и выборе наилучшего. Этот метод может быть очень медленным и неэффективным для больших задач.
Метод декомпозиции состоит в разбиении задачи на более мелкие подзадачи, которые могут быть решены отдельно. Затем результаты решения каждой подзадачи объединяются для получения решения всей задачи
Алгоритмы, основанные на методе декомпозиции, могут быть различными, например, это может быть алгоритм динамического программирования или алгоритм разделяй и властвуй.

Вопрос 17. Методы разработки алгоритмов. Динамическое программирование.
«Жадные» алгоритмы (greedy algorithms). Код Хаффмана. Поиск с возвратом
(backtracking). Задача о восьми ферзях. Задача о раскраске графа в k цветов.
Локальный поиск.
Методы разработки алгоритмов - это способы создания алгоритмов для решения задач.
Они включают в себя такие методы, как динамическое программирование, жадные алгоритмы, код Хаффмана, поиск с возвратом, локальный поиск и другие.
Динамическое программирование - это метод решения задач, основанный на разбиении задачи на более мелкие подзадачи и сохранении результатов каждой подзадачи для последующего использования. Этот метод часто используется для оптимизации решения задач, таких как нахождение наибольшей общей подпоследовательности или нахождение кратчайшего пути в графе.
Жадные алгоритмы - это метод решения задач, основанный на выборе локально оптимального решения на каждом шаге.
Жадные алгоритмы могут быть эффективными для некоторых задач, таких как задача о минимальном остовном дереве или задача о рюкзаке.
Код Хаффмана - это метод сжатия данных, основанный на построении оптимального префиксного кода для каждого символа в сообщении.
Этот метод используется для сжатия текстовых данных и изображений.
Поиск с возвратом - это метод решения задач, основанный на переборе всех возможных вариантов решения и откате к предыдущему шагу, если текущее решение не является оптимальным. Этот метод часто используется для решения задач, таких как задача о
восьми ферзях или задача о раскраске графа в k цветов.
Локальный поиск - это метод решения задач, основанный на поиске локально оптимального решения путем изменения текущего решения на каждом шаге.
Этот метод часто используется для задач оптимизации, таких как задача о коммивояжере или
задача о раскраске графа.

Вопрос 18. Трудноразрешимые задачи. Классы сложности P. Класс сложности NP.
Гамильтонов цикл. Задача коммивояжёра. Задача упаковки корзин. Сводимость задач.
NP-
полнота.
Трудноразрешимые задачи - это задачи, для которых не существует эффективного алгоритма решения, т.е. алгоритма, который работает за разумное время для любого размера входных данных. Примерами таких задач являются задача о выполнимости булевой формулы и задача о рюкзаке.
Классы сложности P и NP - это классы задач, которые могут быть решены за полиномиальное время и нерешаемые за полиномиальное время соответственно. Задачи из класса P могут быть решены эффективно, в то время как задачи из класса NP могут быть решены только с использованием экспоненциального времени или более сложных алгоритмов.
Гамильтонов цикл - это путь в графе, который проходит через каждую вершину ровно один раз и заканчивается в начальной вершине. Задача о нахождении гамильтонова цикла является NP-полной.
Задача коммивояжера - это задача нахождения кратчайшего пути, проходящего через все города, которые должен посетить коммивояжер. Эта задача также является NP-полной.
Задача упаковки корзин - это задача нахождения оптимального способа упаковки предметов в ограниченное количество корзин. Эта задача также является NP-полной.
Сводимость задач - это процесс преобразования одной задачи в другую с сохранением свойств и решений. Например, задача о выполнимости булевой формулы может быть сведена к задаче о гамильтоновом цикле.
NP-
полнота - это свойство задачи, которое означает, что она является одной из самых сложных задач в классе NP. Задачи, которые могут быть сведены к NP-полным задачам, также являются NP-полными.