Список вопросов по дисциплине «Структуры и алгоритмы обработки данных»

1. Алгоритм. Свойства алгоритма.

Алгоритм - это набор инструкций для выполнения некоторой задачи.

Свойства алгоритмов:

1. Дискретность. Процесс решения задачи должен быть разбит на последовательность отдельных шагов — простых действий, которые выполняются одно за другим в определенном порядке. Каждый шаг называется командой (инструкцией). Только после завершения одной команды можно перейти к выполнению следующей.

2. Конечность. Исполнение алгоритма должно завершиться за конечное число шагов; при этом должен быть получен результат.

3. Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм должен содержать только те команды, которые входят в систему команд его исполнителя.

4. Определенность (детерминированность). Каждая команда алгоритма должна быть точно и однозначно определена. Также однозначно должно быть определено, какая команда будет выполняться на следующем шаге. Результат выполнения команды не должен зависеть ни от какой дополнительной информации. У исполнителя не должно быть возможности принять самостоятельное решение (т. е. он исполняет алгоритм формально, не вникая в его смысл). Благодаря этому любой исполнитель, имеющий необходимую систему команд, получит один и тот же результат на основании одних и тех же исходных данных, выполняя одну и ту же цепочку команд.

5. Массовость. Алгоритм предназначен для решения не одной конкретной задачи, а целого класса задач, который определяется диапазоном возможных входных данных.

2. Понятие сложности алгоритма.

Сложность - это количественная оценка ресурсов, затрачиваемых алгоритмом.

Вычислительная сложность алгоритма — это функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от свойств входных данных. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения проблемы, тогда как пространство определяется объёмом памяти или места на носителе данных.

Ресурсы:

• Человеческие (создание и понимание алгоритма). Оценивает интеллектуальная сложность. Единого критерия оценки не существует.

• Вычислительные (на выполнение алгоритма):

  • Память. Оценивает пространственная сложность - количество памяти, требующееся для выполнения алгоритма.

  • Процессорное время. Оценивает временная сложность - количество времени, необходимое на выполнение алгоритма.

Получаемая в асимптотическом анализе оценка функции трудоемкости, называется сложностью алгоритма.

Вычислительная временная сложность (time complexity) — это максимальное возможное количество выполненных алгоритмом элементарных операций, как функция от размера входных данных.

Вычислительная ёмкостная сложность (space complexity) — это максимальный возможный размер занятой алгоритмом дополнительной памяти, как функция от размера входных данных.