- •Список вопросов по дисциплине «Структуры и алгоритмы обработки данных»
- •Алгоритм. Свойства алгоритма.
- •Понятие сложности алгоритма.
- •Классы сложности алгоритмов.
- •Структуры данных. Массив
- •Структуры данных. Связный список.
- •Структуры данных. Хэш-таблицы.
- •Структуры данных. Бинарное дерево. ??
- •Алгоритмы сортировки. Сортировка выбором.
- •Алгоритмы сортировки. Вставкой.
- •Алгоритмы сортировки. Обменом.
- •Алгоритмы сортировки. Шелла.
- •Алгоритмы сортировки. Турнирная.
- •Алгоритмы сортировки. Пирамидальная.
- •1. Постройте максимальную кучу из входных данных.
- •2. В этот момент самый большой элемент хранится в корне кучи. Замените его на последний элемент кучи, а затем уменьшите размер кучи на 1. Наконец, наведите корень дерева.
- •3. Повторите вышеуказанные шаги, пока размер кучи больше 1.
- •Алгоритмы сортировки. Быстрая.
- •Методы поиска. Бинарный.
- •Методы поиска. Бинарное дерево.
- •Методы поиска. Фибоначчиев.
- •Методы поиска. Интерполяционный.
- •Методы поиска в строке. Кнута-Морриса-Пратта.
- •Методы поиска в строке. Бойера-Мура.
- •Понятие стека.
- •Поиск в глубину.
- •Остовное дерево.
- •Минимальное остовное дерево Алгоритм Прима(Хахаха, прям как в дискретке) Нам нужно связать все точки, чтобы не было цикла из точек(Это объяснение для нас)
- •Алгоритмы поиска путей. Флойда-Уоршелла.(Динамическое программирование)- самый эффективный
- •Алгоритмы поиска путей. Дейкстры.(Динамическое программирование)
- •Алгоритмы поиска путей. Беллмана-Форда.(Динамическое программирование)
- •Алгоритмы поиска путей. Джонсона.(Динамическое программирование)
- •Алгоритмы поиска путей. Йена.(Динамическое программирование) Алгоритм для поиска альтернативных кратчайших путей в графе
- •Алгоритмы поиска путей. А*.(Эвристический алгоритм)
Список вопросов по дисциплине «Структуры и алгоритмы обработки данных»
Алгоритм. Свойства алгоритма.
Алгоритм - это набор инструкций для выполнения некоторой задачи.
Свойства алгоритмов:
Дискретность. Процесс решения задачи должен быть разбит на последовательность отдельных шагов — простых действий, которые выполняются одно за другим в определенном порядке. Каждый шаг называется командой (инструкцией). Только после завершения одной команды можно перейти к выполнению следующей.
Конечность. Исполнение алгоритма должно завершиться за конечное число шагов; при этом должен быть получен результат.
Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм должен содержать только те команды, которые входят в систему команд его исполнителя.
Определенность (детерминированность). Каждая команда алгоритма должна быть точно и однозначно определена. Также однозначно должно быть определено, какая команда будет выполняться на следующем шаге. Результат выполнения команды не должен зависеть ни от какой дополнительной информации. У исполнителя не должно быть возможности принять самостоятельное решение (т. е. он исполняет алгоритм формально, не вникая в его смысл). Благодаря этому любой исполнитель, имеющий необходимую систему команд, получит один и тот же результат на основании одних и тех же исходных данных, выполняя одну и ту же цепочку команд.
Массовость. Алгоритм предназначен для решения не одной конкретной задачи, а целого класса задач, который определяется диапазоном возможных входных данных.
Понятие сложности алгоритма.
Сложность - это количественная оценка ресурсов, затрачиваемых алгоритмом.
Вычислительная сложность алгоритма — это функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от свойств входных данных. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения проблемы, тогда как пространство определяется объёмом памяти или места на носителе данных.
Ресурсы:
Человеческие (создание и понимание алгоритма). Оценивает интеллектуальная сложность. Единого критерия оценки не существует.
Вычислительные (на выполнение алгоритма):
Память. Оценивает пространственная сложность - количество памяти, требующееся для выполнения алгоритма.
Процессорное время. Оценивает временная сложность - количество времени, необходимое на выполнение алгоритма.
Получаемая в асимптотическом анализе оценка функции трудоемкости, называется сложностью алгоритма.
Вычислительная временная сложность (time complexity) — это максимальное возможное количество выполненных алгоритмом элементарных операций, как функция от размера входных данных.
Вычислительная ёмкостная сложность (space complexity) — это максимальный возможный размер занятой алгоритмом дополнительной памяти, как функция от размера входных данных.