Контрольные вопросы
1. Дайте определение понятия алгоритма.
2. Назовите основные свойства алгоритма.
3. Перечислите виды алгоритмов.
4. Приведите классификацию алгоритмов.
5. Назовите основные виды универсальных алгоритмических моделей.
6. Что представляет собой первая алгоритмическая модель?
7. Каким образом строятся рекурсивные алгоритмы?
8. Опишите принцип работы машины Тьюринга.
9. Приведите основные правила построения ЛСА.
10. Приведите основные правила построения ГСА.
11. Приведите основные правила построения структурных схем алгоритмов.
12. Что представляют собой «жадные» алгоритмы?
13. Для каких задач наиболее целесообразно применять «жадные» алгоритмы?
14. Как определяется временная сложность алгоритма?
15. Перечислите параметры, характеризующие эффективность алгоритма.
16. Поясните, в чем состоят отличия между полиномиальными и экспоненциальными алгоритмами.
17. Определите алгоритмы подклассов P, NP, NPC.
18. Поясните принципы анализа алгоритмов.
19. Каким образом определяется время работы алгоритмов?
20. Перечислите методы математического программирования.
21. Приведите примеры и дайте определение задач на допустимость и оптимальность.
Задания для самостоятельной работы
1. Дана последовательность чисел x1, x2, ... , хn. Покажите, что за время O(n log n) можно определить, есть ли в этой последовательности три одинаковых числа.
2. Как записать выражение n3/1000 - 100n2 - 100n + 3 с помощью O(n) - обозначений?
3. Дан массив S из n действительных чисел, а также число x. Как за время O(n log n) определить, можно ли представить x в виде суммы трех элементов массива S?
4. При каком наименьшем значении n алгоритм, требующий 1000n2 операций, эффективнее алгоритма, требующего 3n операций?
5. Пусть имеется алгоритм, решающий задачу размера n за время f(n) микросекунд. Каков максимальный размер задачи, которую он может решить за время t? Заполнить таблицу.
|
1 сек |
1 минута |
1 час |
1 день |
1 месяц |
1 год |
1 век |
log n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
n log n |
|
|
|
|
|
|
|
n2 |
|
|
|
|
|
|
|
n3 |
|
|
|
|
|
|
|
n4 |
|
|
|
|
|
|
|
2n |
|
|
|
|
|
|
|
3n |
|
|
|
|
|
|
|
n! |
|
|
|
|
|
|
|
6. Следуя примеру, покажите работу сортировки слиянием для массива А = (3, 41, 52, 26, 38, 57, 9, 49).
7. Напишите текст процедуры СЛИЯНИЕ(A, p, q, r).
8. Сортировку вставками можно оформить как рекурсивную процедуру: желая отсортировать A[1, ..., n], мы рекурсивно сортируем А[1, …, n - 1], а затем ставим А[n] на нужное место в отсортированном массиве A[1, …, n - 1]. Напишите рекуррентное соотношение для времени работы такой процедуры.
9. Для задачи о выборе заявок возможно несколько способов жадного выбора. Покажите на примере, что правила «на каждом шаге выбирать заявку наименьшей длительности, совместную с уже выбранными», а также «на каждом шаге выбирать заявку, совместную с наибольшим количеством остающихся», не годятся.