Контрольные вопросы

1. Дайте определение алгоритма, предназначенного для решения задач обработки информации на ЭВМ.
2. Как называются данные, поступающие на вход алгоритма?
3. Что является выходом алгоритма?
4. Какие конкретные данные могут поступать на вход ЭВМ?
5. Правильно ли сказать, что алгоритм преобразует входные данные в результаты решения задачи?
6. Какие объекты в самом общем виде являются входом алгоритма?
7. Как называются этапы, на которые разбивается алгоритм? Конечно ли их число?
8. Что должен делать алгоритм после выполнения всех этапов?
9. Что означает детерминированность алгоритма?
10. В каком случае можно сказать, что алгоритм решения некоторой задачи существует?
11. Перечислите способы представления алгоритмов.
12. Что представляет собой блок-схема алгоритма?
13. Составьте алгоритм поиска наибольшего числа из множества трех чисел а, Ь, с.
14. Представьте алгоритм в виде блок-схемы и последовательности шагов.
15. Представьте алгоритм в самом укрупненном виде.
16. В чем преимущество представления алгоритмов в виде блок-схем? Какой недостаток этого представления?
17. Что понимается под правильностью алгоритма?
18. Какие этапы включает анализ алгоритмов?
19. Какие способы используются для доказательства правильности алгоритмов?
20. Как осуществляется экспериментальная проверка правильности алгоритма? В нем заключается ее недостаток?
21. Что представляют собой временные оценки алгоритма? Какие пути их получения?
22. Как получают экспериментальные оценки времени работы алгоритма? В чем недостатки экспериментального метода?
23. Как улучшить достоверность экспериментальных оценок временной сложности алгоритмов?
24. Какие параметры алгоритма используются при теоретическом анализе его временной сложности?
25. Как оценивают скорость роста функций от размера входа алгоритма при теоретическом анализе его сложности?
26. Количество основных операций двух алгоритмов в зависимости от размера на входе л описываются функциями f(n) - 10,5п⁷ + 2,1 л⁶ — - 1000, f(n) = 2^2(п+1) + 135. Оцените временные сложности алгоритмов.
27. На какие два класса разбивают алгоритмы по показателю «временная сложность»?
28. Что означают термины «полиномиальный и экспоненциальный алгоритмы»?
29. Почему экспоненциальные алгоритмы считаются неэффективными?
30. Как называются классы полиномиальных и экспоненциальных алгоритмов?
31. Как трактуется понятие недетерминированного алгоритма?
32. Приведите рисунок трехъярусного бинарного дерева и объясните действия недетерминированного алгоритма на этом дереве.
33. Зачем введено понятие недетерминированного алгоритма?
34. Какие задачи относятся к классу NP?
35. Равны ли классы (множества) Р и NP?
36. Чем отличается класс NP-полных задач от класса NP? В чем особенность задач этого класса?
37. Что представляет собой преобразование одной задачи в другую (сведение) и зачем оно осуществляется?
38. Какую возможность предоставляют разработчику алгоритмов понятия классов NP и NP-полных задач?
39. В чем смысл задачи о выполняемости булевой функции и к какому классу задач она относится: Р или NP?
40. Какой порядок доказательства того факта, что задача входит в класс NP-полных задач?