Вопросы и задачи

  • 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. Количество основных операций двух алгоритмов в зависимости от размера на входе п описываются функциями /(л) = 10,5л7 +2,1д6 -1000, /(л) = 22(й+,) +135. Оцените временные сложности алгоритмов.
  • 27. На какие два класса разбивают алгоритмы по показателю «временная сложность»?
  • 28. Что означают термины «полиномиальный» и «экспоненциальный» алгоритм?
  • 29. Почему экспоненциальные алгоритмы считаются неэффективными?
  • 30. Как называются классы полиномиальных и экспоненциальных алгоритмов?
  • 31. Как трактуется понятие недетерминированного алгоритма?
  • 32. Приведите рисунок трехярусного бинарного дерева и объясните действия недетерминированного алгоритма на этом дереве.
  • 33. Зачем введено понятие недетерминированного алгоритма?
  • 34. Какие задачи относятся к классу Л^Р?
  • 35. Равны ли классы (множества) Р и NPr!
  • 36. Чем отличается класс УУР-полных задач от класса NPr! В чем особенность задач этого класса?
  • 37. Что представляет собой преобразование одной задачи в другую (сведение) и зачем оно осуществляется?
  • 38. Какую возможность предоставляют разработчику алгоритмов понятия классов NP и А^Р-полных задач?
  • 39. В чем смысл задачи о выполняемое™ булевой функции и к какому классу задач она относится, к Р или ТУР?
  • 40. Каков порядок доказательства того факта, что задача входит в класс А^Р-полных задач?
 
< Пред   СОДЕРЖАНИЕ     След >