Автор работы: Пользователь скрыл имя, 03 Сентября 2013 в 11:10, реферат
Среди подходов к решению NP-трудных задач можно выделить два. Первый заключается в построении приближенных алгоритмов с гарантированными оценками точности получаемого решения, а второй — в отказе от анализа сложности алгоритмов по наихудшему случаю и переходе к анализу сложности в среднем.
Настоящая лекция посвящена изучению второго подхода (анализу сложности в среднем) применительно к задаче упаковки.
При анализе сложности в среднем вводится некоторая вероятностная мера на
исходных данных. Средним временем работы алгоритма называется математическое ожидание времени его работы (по всем исходным данным с заданным распределением).