Теормин по 2-й части (1123849), страница 2
Текст из файла (страница 2)
(стр. 191) Функция ( ) ⌈Является нижней гранью сложности по числу сравнений алгоритмов сортировки массивовдлинны попарно-различных вещественных числе с помощью сравнений и 4-харифметических операций64. Сложность алгоритма построения выпуклой оболочки (стр. 193) с помощьюарифметических операций и сравнений, который имеет сложность O(n log n)Равна Θ(n log n) и является оптимальнымАлгоритм Грехема - оптималенЭтого не будет:65.66.67.68.69.70.71.72.Задача NP – это задача, на которую ответ либо «да», либо «нет»Задача класса P – задача распознавания свойства с полиномиальной сложностьюP вложен в NP, но не равенТеорема Фишера-Рабина (стр.
197) – она доказывает, основываясь на арифметикеПресбургера, что класс P не равен классу NPСтр 199 – определения Полиномиальной сводимости, NP-полных задачЗадача Sat (стр. 200) – задача выполнимости заданной в КНФ булевой формулы (задачавыполнимости КНФ)Задача Sat полиномиально сводится к задаче о существовании «клики с m вершинами»(т.е. существует в данном графе набор из m вершин, любые 2 из которых соединеныребром) (стр.
200)Задача распознавания гамильтоновости графа является NP-полнойПример задачи из NP, но не P – Для заданных k и l неотрицательных целых и k < nвыяснить, имеется ли у числа l делитель n, такой что 1 < l <= k.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
