- •Глава 1
- •§ 1. Затраты алгоритма для данного входа, алгебраическая сложность
- •§ 1. Затраты алгоритма для данного входа
- •§ 1. Затраты алгоритма для данного входа
- •§ 1. Затраты алгоритма для данного входа
- •§ 1. Затраты алгоритма для данного входа
- •§ 2. Асимптотические оценки (формализм)
- •§ 2. Асимптотические оценки (формализм)
- •§ 2. Асимптотические оценки (формализм)
- •§ 3. Асимптотические оценки (два примера) 23
- •§ 3. Асимптотические оценки (два примера)
- •§ 3. Асимптотические оценки (два примера)
- •§ 3. Асимптотические оценки (два примера)
- •§ 3. Асимптотические оценки (два примера)
- •§ 4. Длина числа как возможный размер входа
- •§ 4. Длина числа как возможный размер входа
- •§ 4. Длина числа как возможный размер входа
- •§ 4. Длина числа как возможный размер входа
- •Глава 2
- •§ 5. Понятие сложности в среднем
- •§ 5. Понятие сложности в среднем
- •Глава 2. Сложность в среднем
- •§ 5. Понятие сложности в среднем
- •Глава 2. Сложность в среднем
- •§ 6. Сортировка и конечные вероятностные пространства.
- •§ 6. Сортировка и конечные вероятностные пространства 47
- •Глава 2. Сложность в среднем
- •§ 6. Сортировка и конечные вероятностные пространства 49
- •Глава 2. Сложность в среднем
- •§ 6. Сортировка и конечные вероятностные пространства 51
- •Глава 2. Сложность в среднем
- •§ 7. Пример медленного роста сложности в среднем
- •§ 7. Пример медленного роста сложности в среднем в сравнении со сложностью в худшем случае
- •Глава 2. Сложность в среднем
- •§ 7. Пример медленного роста сложности в среднем 55
- •Глава 2. Сложность в среднем
- •§ 7. Пример медленного роста сложности в среднем
- •Глава 2. Сложность в среднем
- •§ 8. Функция затрат рандомизированного алгоритма
- •§ 8. Функция затрат рандомизированного алгоритма
- •Глава 2. Сложность в среднем
- •§ 8. Функция затрат рандомизированного алгоритма
- •Глава 2. Сложность в среднем
- •§ 8. Функция затрат рандомизированного алгоритма
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 3
- •§ 9. Функции, убывающие по ходу выполнения алгоритма
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 75
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 77
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 79
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 81
- •§ 10. Качество оценок
- •§ 10. Качество оценок
- •§ 10. Качество оценок
- •§ 10. Качество оценок
- •§ 11. Завершимостъ работы алгоритма
- •§ 11. Завершимость работы алгоритма
- •§ 11. Завершимостъ работы алгоритма
- •§ 11. Завершимостъ работы алгоритма
- •§ 12. Вложенные циклы (дополнительные примеры)
- •§ 12. Вложенные циклы (дополнительные примеры)
- •§ 13. Нецелые размеры входа и непрерывные оценочные функции 97
- •§ 13. Нецелые размеры входа и непрерывные оценочные функции
- •§ 13. Нецелые размеры входа и непрерывные оценочные функции 99
- •Глава 4
- •§ 14. Понятие нижней границы сложности
- •§ 14. Понятие нижней границы сложности
- •§ 15. Оптимальные алгоритмы
- •§ 15. Оптимальные алгоритмы
- •§ 15. Оптимальные алгоритмы
- •§ 15. Оптимальные алгоритмы
- •§ 16. Асимптотические нижние границы. Алгоритм, оптимальный по порядку сложности
- •§ 16. Асимптотические нижние границы
- •§ 16. Асимптотические нижние границы
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем 125
- •§ 18. Нижние границы сложности рандомизированных алгоритмов. Принцип Яо
- •§18. Нижние границы сложности рандомизированных алгоритмов 127
- •Глава 5
- •§ 19. Битовые операции
- •Глава 5. Битовая сложность
- •§ 19. Битовые операции
- •Глава 5. Битовая сложность
- •§ 20. Наивная арифметика: умножение
- •§ 20. Наивная арифметика: умножение
- •Глава 5. Битовая сложность
- •§ 20. Наивная арифметика: умножение
- •Глава 5. Битовая сложность
- •§ 21. Наивная арифметика: деление с остатком
- •§ 21. Наивная арифметика: деление с остатком
- •Глава 5. Битовая сложность
- •§ 21. Наивная арифметика: деление с остатком
- •Глава 5. Битовая сложность
- •§ 22. Модулярная арифметика
- •§ 22. Модулярная арифметика
- •Глава 5. Битовая сложность
- •§ 22. Модулярная арифметика
- •Глава 5. Битовая сложность
- •§ 22. Модулярная арифметика
- •Глава 5. Битовая сложность
- •§ 23. Булева арифметика
- •§ 23. Булева арифметика
- •Глава 5. Битовая сложность
- •§ 23. Булева арифметика
- •Глава 5. Битовая сложность
- •Глава 5. Битовая сложность
- •Глава 6
- •§ 24. Простейшие рекуррентные уравнения
- •§ 24. Простейшие рекуррентные уравнения
- •§ 24. Простейшие рекуррентные уравнения
- •§ 25. Об одном классе нелинейных рекуррентных соотношений 163
- •§ 25. Об одном классе нелинейных рекуррентных соотношений
- •§ 25. Об одном классе нелинейных рекуррентных соотношений 165
- •§ 25. Об одном классе нелинейных рекуррентных соотношений 167
- •§26. Асимптотические оценки решений рекуррентных неравенств 169
- •§ 26. Асимптотические оценки решений рекуррентных неравенств
- •§ 26. Асимптотические оценки решений рекуррентных неравенств 171
- •§ 27. Добавление нулей
- •§ 27. Добавление нулей 173
- •§ 27. Добавление нулей 175
- •§ 27. Добавление нулей
- •§ 27. Добавление нулей 179
- •Глава 7 Сводимость
- •§ 28. Линейная сводимость
- •Глава 7. Сводимость
- •§ 28. Линейная сводимость
- •Глава 7. Сводимость
- •§ 28. Линейная сводимость
- •Глава 7. Сводимость
- •§ 29. Линейная сводимость и нижние границы сложности
- •§ 29. Линейная сводимость и нижние границы сложности 191
- •Глава 7. Сводимость
- •§ 29. Линейная сводимость и нижние границы сложности 193
- •Глава 7. Сводимость
- •§ 30. Классы PиNp
- •§ 30. Классы р и np
- •Глава 7. Сводимость
- •§ 30. Классы PuNp
- •Глава 7. Сводимость
- •§ 30. Классы PuNp
- •Глава 7. Сводимость
- •§ 31. Существование задач распознавания, не принадлежащих р 201
- •§ 31. Существование задач распознавания, не принадлежащих р. Связь моделей мт и рам
- •Глава 7. Сводимость
- •§ 31. Существование задач распознавания, не принадлежащих р 203
- •Глава 7. Сводимость
- •§ 32. Полиномиальная сводимость. Np-полные задачи
- •§ 32. Полиномиальная сводимость. Np-полные задачи
- •Глава 7. Сводимость
- •Глава 7. Сводимость
- •Глава 7. Сводимость
- •Глава 7. Сводимость
- •Глава 1. Сложности алгоритмов как функции числовых аргументов. Сложность в худшем случае
- •119002, Москва, Большой Власьевский пер., 11. Тел. (499) 241-74-83
Глава 2. Сложность в среднем
n, m размера входа. Беря максимум этих сложностей по всем m таким, что l^m^n, определяем сложности T{n), T{n) по числу сравнений в худшем случае и в среднем с использованием n в качестве размера входа. Показать, что T{n) = Q{n2) и T(n)<4n.
Указание. Возьмем U(n) = max T(k). Очевидно, что U(n) не убывает при
ЫЫn
возрастании n и что T(n) ^ U(n). Доказывается неравенство
U(n) г£ i(U(n - 1) + тах{U(1), U n - 2)} + ... n
... + max{U(n - 2), U(1)} + U(n - 1)) + n - 1, из которого, в силу неубывания U(n), следует
U(n)s£-(U(n-l) + U(n-2) + ... + U(|nJ))+n. Отсюда с помощью индукции выводится, что U(n) <4n для всех n> 1.
36. В инверсионном векторе (bъ b2,..., bn) произвольной переста новки (a1,a2,...,an)бПn каждая компонента bi равна количеству це лых j таких, что 1 ^ j <i и aj >ai. Например, инверсионный вектор перестановки (2, 4, 3,1, 6, 5) —это (0, 0,1, 3, 0,1). Показать, что каж дому целочисленному вектору (bъ b2, •••, bn), для которого 0 ^ bi < i, i = 1, 2,..., n, соответствует некоторая перестановка длины n, для ко торой этот вектор является инверсионным.
Указание. Очевидно, что если bn = k, 1Цk<n, то an=n-k, и это соображение приводит к алгоритму построения (a1,a2,...,an), применимому к любому вектору b, удовлетворяющему оговоренным условиям: просматриваем компоненты вектора b, продвигаясь от последней к первой, находим значение соответствующей компоненты перестановки a и удаляем найденное значение из множества M, первоначально равного {1, 2,..., n}; при этом значение ai , i = n,n — 1,..., 1, определяется как (bi - 1)-й наибольший в множестве M (самый большой элемент —это первый наибольший, следующий по величине элемент —это второй наибольший и т.д.).
37. Показать, что один этап пузырьковой сортировки понижает на единицу значение каждой неотрицательной компоненты инверсион ного вектора перестановки (см. предыдущую задачу) и не изменяет нулевые компоненты. Показать, что вероятность того, что значение максимума компонент инверсионного вектора выбранной наугад пе рестановки длины n равно k, 0^k<n, есть —j—1.
Указание ко второй части задачи. Количество векторов (b1; b2,..., bn), для каждого из которых bi е N+, 0 г£ bi < i, i = 1,2,..., n, и max{b1; b2,..., bn} г£ k,
Задачи
71
1 ^ к ^ п - 1, равно к\ кп к г, так как Ь; может принимать любое значение между 0 и £ - 1 при £ ^ к и любое значение между 0 и к - 1 для k<i^n.
38. Показать, что математическое ожидание числа этапов пузырьковой сортировки совпадает с (6.9).
Указание. Пользуясь решением предыдущей задачи, легко получить, что это математическое ожидание есть
J(fc(fcn-fc/c!-(/c-l)n-fc+1(fc-l)!),
J_ n!
fc=l
что равно
— (>(fcn-fc+1fc! - № - l)n-fc+2№ - 1)!) - V(fc - l)"-k+1(k - 1)! V
' k=l k=l
В упрощении последнего выражения поможет дискретный аналог формулы Ньютона—Лейбница (см. задачу 27).
Используя идею решения задачи 35, предложить рандомизированный алгоритм восстановления перестановки длины п по ее инверсионному вектору (см. задачу 36), имеющий сложность в среднем по числу сравнений 0{п2).
Пусть {аъа2,...,ап)— произвольная перестановка длины п. Ее преобразование
for i = n downto 2 do j := 1 + random(i - 1); щ^а} od
может дать любую перестановку длины п с вероятностью —. (Это дает алгоритм построения случайных перестановок с равномерным распределением вероятностей.)
41. Предположим, что у нас нет другого генератора случайных чи сел, кроме генератора, в результате обращения к которому появля ется 0 или 1 с одинаковой вероятностью | (аналог подбрасывания монеты), и пусть р, O^p^l, — заданное вещественное число. Ка ким образом с помощью этого генератора можно определить гене ратор randp, в результате обращения к которому появляется 0 или 1 с вероятностями соответственно р и 1 - р (незначительные отклоне ния допустимы)? Сложность в среднем алгоритма получения одного случайного числа с помощью randp должна быть меньше 2 (затраты определяются числом обращений к изначально имеющемуся генера тору).
Указание. Представить р (возможно, с небольшой погрешностью) в виде конечной суммы вида —- Н—| + ... + -|, где а{ —это 0 или 1 для всех £, а к — некоторое целое положительное число.
72