Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

Контрольные вопросы и задания

  • 1. Что такое трудоемкость алгоритма и от чего она зависит?
  • 2. Что называется функцией трудоемкости и как определяется операционная сложность алгоритма?
  • 3. Какие виды сложности алгоритма Вам известны?
  • 4. Сколько видов асимптотик принято использовать в асимптотическом анализе алгоритмов и как обозначаются асимптотики различных видов?
  • 5. Каково формальное определение асимптотически точной оценки функции трудоемкости?
  • 6. Каковы формальные определения асимптотически точных верхней и нижней оценок функции трудоемкости?
  • 7. В каких случаях возможно совпадение верхней и нижней оценок трудоемкости алгоритма?
  • 8. Каковы правила оценки порядка операционной сложности?
  • 9. Каковы асимптотические оценки функции трудоемкости изученных ранее алгоритмов поиска и сортировки для массива размером п (последовательный и бинарный поиск, сортировка методом простого обмена)?
  • 10. Каковы отличия массовых и индивидуальных задач?
  • 11. Какие задачи называются алгоритмически разрешимыми?
  • 12. Что является целью теоретического исследования задачи?
  • 13. Какие процедуры используются для решения алгоритмически не разрешимых задач?
  • 14. Как определяется сложность задачи и на какие группы делятся алгоритмически разрешимые задачи?
  • 15. Какова классификация распознавательных задач?
  • 16. Каковы отношения между задачами классов Р, 1МР, 1ЧРС?
  • 17. Каковы особенности задач, относящихся к классам Р, 1ЧР, 1ЧРС?
  • 18. Каковы асимптотические оценки сложности задачи о выполнимости схемы?
  • 19. Каковы особенности и возможные интерпретации недетерминированной машины Тьюринга?
  • 20. Каковы особенности 1Р-трудных задач?
  • 21. Каким образом можно графически изобразить схему соотношения степеней сложности задач классов ]Р И 1ЧРН?
  • 22. В чем состоит суть проблемы Р = 1ЧР?
 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы