Контрольные вопросы. 
Теоретические основы информатики

• 1. Что называется сложностью алгоритма? Какие факторы влияют на сложность алгоритма?
• 2. Что называется степенью роста? Какими свойствами обладает степень роста?
• 3. Каким образом можно определить порядок сложности алгоритма, но программному коду?
• 4. Что называется сортировкой данных? В чем заключается сортировка различных типов данных?
• 5. В чем заключаются алгоритмы сортировки выбором, вставками, Шелла? Какой порядок сложности имеют эти алгоритмы?
• 6. Охарактеризуйте алгоритмы пузырьковой и шейкерной сортировки. Какой порядок сложности имеют эти алгоритмы?
• 7. Для каких данных используется сортировка слиянием? В чем суть этого алгоритма? Какой порядок сложности имеет этот алгоритм?
• 8. В чем заключается быстрая сортировка? Какие особенности имеет этот алгоритм?
• 9. В чем состоит задача информационного поиска? Охарактеризуйте последовательный поиск, бинарный, интерполяционный, Фибоначчи.
• 10. В чем заключается алгоритм поиска Кнута — Морриса — Пратта? Какова роль префикс-функции в этом алгоритме?

Задания для самостоятельного решения

Задание 1. Покажите, что алгоритм сортировки вставками имеет сложность 0(п²). Задание 2. Дано множество числовых элементов А = {4,7,1,0,2,1,6}. Примените следующие алгоритмы сортировки: выбором, вставками, Шелла, пузырьковую, шейкерную, слиянием, быструю.

Задание 3. Дано множество числовых элементов.

В предположении, что искомым элементом является 55, примените следующие алгоритмы поиска данных: последовательный, бинарный, Фибоначчи, интерполяционный. Задание 4. Пусть в строке у = acbbacbcbbabcaabbcbabs выполняется поиск подстроки х = babcaa. Выполните поиск, используя КМП-алгоритм.