Задачі для самостійного розв’язання
1. Наведіть приклади рефлективності, транзитивності та симетричності для асимптотичних оцінок.
2. Нехай f(n) і g(n) - невід'ємні функції. Доведіть за допомогою базового означення θ-позначень, що max(f(n),g(n)) = θ(f(n) + g(n)).
3. Чи є алгоритм динамічного програмування для рішення дискретної задачі про рюкзак алгоритмом з поліноміальним часом? Відповідь обґрунтуйте.
4. Доведіть таке твердження - якщо NP – повна задача розв’язна на протязі поліноміального часу, то P = NP.
Коментарі
В цьому розділі значна частина матеріалу представлена із [13]. Використовується також матеріал Internet- ресурсів (Вікіпедії) та праць [8-11, 16, 28].
