Сортировка и поиск. Проверка упорядоченности массива. Способы сортировки.

Вопросы к экзамену по курсу

«Основы алгоритмизации и программирования»

ИСиТ- I 2010/2011

1. Основы теории сложности. Классы сложности: NP, P.

Трудоемкость – кол-во элементарных операций, которых необходимо выполнить для решения задачи с помощью данного алгоритма.

Сложность алгоритма (О большое) – оценка функции трудоемкости, определяет как быстро растет трудоемкость алгоритма с увеличением объема данных.

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

Класс Р содержится в классе NP.

Сортировка и поиск. Проверка упорядоченности массива. Способы сортировки.

Сортировка – процесс упорядочивания набора элементов в возрастающем или убывающем порядке.

Алгоритмы поиска: последовательный, бинарный(в упорядоченных массивах).

Сортировки по размещению: внутренние(в памяти), внешние(в файле).

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

3. Обменная сортировка (метод «пузырька», шейкер- сортировка).

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

4. Сортировка разделением (быстрая сортировка) Распределяющая сортировка.(?)

Разделением – берем 1-ый эл-т, сортируем относительно него массив, получаем левую и правую часть, этот же алгоритм рекурсивно применяем к каждой части и так пока есть перестановки.

Сортировка подсчетом. Сортировка выбором (прямой выбор, линейный выбор, квадратичная).

Подсчетом - считается для каждого эл-та кол-во меньших и это его индекс.

Прямой – минимальное меняем с начальным и так до конца.

Квадратичная – берем корень из кол-ва эл-тов, после эл-та с этим индексом граница, с левой и правой части мин, потом из этих мини в исходный, опять из левой иправой мин, потом из этих мин в исходный и так пока есть эл-ты.

6. Сортировка вставками. (Простая вставка, вставка погружением, метод Шелла)

Простая – массив делится на 2 части: неупорядоченная и упорядоченная, берется первый эл-т из неупорядоченной, вставляется в упорядоченную на своё место, затем опять 1 из неупорядоченной в упорядоченную и т.д.

Погружением – очередной эл-т путем ряда обменов погружается до требуемой позиции в уже упорядоченную часть массива.

Шелла – кол-во эл-тов делится на 2, это шаг, с этим шагом выбираются эл-ты, которые будут меняться, потом от них выбираются эл-ты правее и меняются, если есть ещё правее. Затем шаг уменьшается на 1 и процедура повторяется пока шаг не станет 1 и перестановок больше не будет.

Пирамидальная сортировка. Сортировка слиянием (однократное и циклическое слияние(?)).

Пирамидальная – состоит из 2-х фаз: построение пирамиды и сортировка.

Однократное - массив разбивается на n частей, каждая сортируется независимо, затем они объединяются слиянием.

Циклическое - массив разделяется на n последовательностей. Затем в каждой из них выбирается по одному элементу (первому) в таком порядке, чтобы получилась упорядоченная группа из n элементов, которая запоминается в выходной последовательности (слияние). Выходная последовательность будет состоять из групп по n элементов, каждая из которых упорядочена. Далее файл опять распределяется, но уже группами по n элементов по тем же самым n входным последовательностям. В результате слияния образуются упорядоченные группы из n*n элементов. Затем процесс повторяется группами по n*n*n и т.д.

Деки. Логическая структура дека.

Очередь с двумя концами. Включение и исключение производится с двух концов.

Основные операции – включение/исключение справа/слева, определение размера, очистка.

Красно-черные деревья.

Каждый узел дерева окрашен либо в красный, либо в черный, причем: каждый нулевой узел – черный, корневой – черный, у красного дети черные, всякий путь от корня к произвольной вершине имеет одинаковое кол-во черных узлов.

Вопросы к экзамену по курсу

«Основы алгоритмизации и программирования»

ИСиТ- I 2010/2011

1. Основы теории сложности. Классы сложности: NP, P.

Трудоемкость – кол-во элементарных операций, которых необходимо выполнить для решения задачи с помощью данного алгоритма.

Сложность алгоритма (О большое) – оценка функции трудоемкости, определяет как быстро растет трудоемкость алгоритма с увеличением объема данных.

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

Класс Р содержится в классе NP.

Сортировка и поиск. Проверка упорядоченности массива. Способы сортировки.

Сортировка – процесс упорядочивания набора элементов в возрастающем или убывающем порядке.

Алгоритмы поиска: последовательный, бинарный(в упорядоченных массивах).

Сортировки по размещению: внутренние(в памяти), внешние(в файле).

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

3. Обменная сортировка (метод «пузырька», шейкер- сортировка).

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

4. Сортировка разделением (быстрая сортировка) Распределяющая сортировка.(?)

Разделением – берем 1-ый эл-т, сортируем относительно него массив, получаем левую и правую часть, этот же алгоритм рекурсивно применяем к каждой части и так пока есть перестановки.