Теорія Складності Обчислень:Контрольна

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Варіант - 1

Завдання 1

Оцініть кількість бітових операцій, потрібних для обчислення виразів:

• kⁿ - Відповідь має бути виду O(f(k,n))
• $\sum_{i=1}^n(a^{2n}_i + \frac{n^4}{\prod_j^i j})$. Довжина чисел a_i обмежені довжиною n. Відповідь має бути виду O(f(n))

Завдання 2

Вкажіть, чи належать наступні задачі до класу NP і обґрунтуйте свою відповідь:

а) Нехай є додатнє ціле число N. Чи є число Π(N) - кількість простих чисел, менших за N парним?

б) Задача про виконуваність 4-ДНФ (диз'юнкція елементарних кон'юнкцій, кожне з яких складається з 4ох літералів)

Варіант - 2

Завдання 1

Оцініть кількість бітових операцій, потрібних для обчислення виразів:

• $C_n^k$ - Відповідь має бути виду O(f(n,k))
• $\prod_{i=1}^n(a_i! + \frac{a_i^3}{n+2})$. Розклад чисел a_i обмежені довжиною n. Відповідь має бути виду O(f(n))

Завдання 2

Вкажіть, чи належать наступні задачі до класу NP і обґрунтуйте свою відповідь:

а) Нехай є додатнє ціле число N. Чи є число Π(N) - кількість простих чисел, менших за N непарним?

б) Нехай є граф G - заданий матрицею суміжності. Чи існує в ньому Ейлерів цикл?