Питання на 4 бали до тестування за курсом «Теорія алгоритмів і матлогіка»

Страницы работы

Содержание работы

Питання на 4 бали до тестування за курсом «Теорія алгоритмів і матлогика»

1.  Що мається на увазі в теорії алгоритмів коли говорять, що час виконання алгоритму Т(n) має порядок О(n2)?

Квадратна сложность О(n2)

Ес>0^n:n>=n0

2.  Яке співвідношення прийняте між класами задач P, NP і NPC у теорії алгоритмів?

P содержится в классе NP  -полные задачи составляя.т подмножество NP- задач

3.   Дано фрагмент програми рекурсивної функції.
Function F( n : integer ) : longint;
 begin
 if n < 2 then F := n
 else F := F( n-1)+ F( n-2)
 end;

1. Який буде результат при n=3?

2. Яку послідовність чисел описує цей фрагмент програми? (Напишіть перших п¢ять членів цього ряду. Введіть числа через кому без пропусків.)

4.  Нехай заданий двомісний предикат P(x,y) : «x є дільником y». Оціните істинність виразу на множині натуральних чисел.

Вираз хибний

5.  На множині цілих чисел побудовано відношення  R = {(x,y): x+y – парне число}.

Які властивості має це відношення?

6.  Укажіть причини, у зв'язку з якими дискретна задача про рюкзак не може бути оптимально вирішена з використанням жадібного алгоритму.

Потому что оптимальное решение каждой подзадачи не приведет к оптимальному решению в целом потому что она требует проверки всех возможных вариантов решения или выполнение принципа жадного выбора

7.  Який з алгоритмів розв’язує задачу про максимальну течію в графі?

Алгоритм Форда-Фалкенсона

8.  Оцініть трудомісткість двох алгоритмів із заданими асимптотичними оцінками:

 O(n2) і O(n*log2n), якщо кількість даних на вході алгоритму дорівнює n=10.

 Який алгоритм кращий за оцінками?

9.  На множині цілих чисел побудовано відношення  R = {(x,y): x+y – не парне число}.

Які властивості має це відношення?

10.  Опишіть алгоритм швидкого сортування.

Массив А[ ] разбивается ( путем переупорядочевания его элементов) на два подмасива. Каждый элеиент подмассива A[p..q-1] не привишает элемент A[q]  а каждый элемент подмассива  [q+1..r]  не менше элемента A[q].   Индекс вычисляется в ходе процедуры расбиения.

Подмассивы   A[p..q-1] и  А[q+1..r] сортируются путем рекурсивного вызова процедуры быстрой сортировки.

Комбинирование. Поскольку массивы сортируются на месте для их объединения не нужны никакие действияи весь массив А  оказуется отсортирован

11.  Порівнюючи ітераційну і рекурсивну реалізацію певного алгоритму можна вважати: ...

Рекурсивные алгоритмы намного проще с логической  точки зрения чем итерационные. Рекурсии  может не хватать  для работы стека.

12.  Алгоритм Дейкстры

Алгоритм пошуку найкоротшого шляху з одніэї вершини до іншої в ширину.

13.  Множина А складається з 3-х елементів, множина У – із двох. Скільки існує : 1) ін'єкцій А в В; 2) сюр’єкцій А в В; 3) ін'єкцій В в А; 4) сюр’єкцій В в А ?

14.  До якого типу алгоритмів відноситься алгоритм побудови кодів Хаффмана?

Жадні алгоритми

15.  Оцініть складність роботи додавання, пошук і видалення одного вузла у червоно-чорному дереві:

O(n*log2n)

16.  Алгоритм Прима

Алгоритм знахождення мінімального каркасного дерева, починаючи з однієї будь-якої вершини.

17.  Які з методів сортування використовують ідею динамічного програмування

Злиття, швидке сортування

18.  На множині цілих чисел побудовано відношення  R = {(x,y): x+хy – не парне число}.

Які властивості має це відношення?

19.  Впорядкуйте за спаданням використаного процесорного часу ділення, множення, додавання двох чисел, з точки зору алгоритмічної складності.

Ділення мнодення  додавання, деление віполняется дальше остальніх

20.  Для реалізації певного алгоритму вам необхідно зберігати число 1032451, яку систему числення бажано використовувати, щоб максимально зменшити використання оперативної пам’яті.

16-річну

Похожие материалы

Информация о работе

Тип:
Тестовые вопросы и задания
Размер файла:
53 Kb
Скачали:
0