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

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

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

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

Ес>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(n²) і O(n*log₂n), якщо кількість даних на вході алгоритму дорівнює 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*log₂n)

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

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

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

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

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

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

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

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

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

16-річну