С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 26

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 26)

Имеется плитка шоколада размера k × l клеток, которую требуется разломать на отдельные клетки. Каждый разлом применяется к одному куску плитки и производится по прямой линии. Затраты каждого алгоритма решения этой задачи применительно к конкретной плитке измеряются числом потребовавшихся разломов.

Указать оптимальный алгоритм решения этой задачи и выписать егосложность. Числа k, l считаются параметрами размера входа алгоритмов.. Если условно изобразить элементы массива длины n точкамина плоскости, соединяя отрезками те из них, которые непосредственно сравнивались в процессе некоторого алгоритма поиска, — скажем,поиска наименьшего элемента, одновременного поиска наибольшегои наименьшего элементов, поискаl m k-го по величине элемента (в частn-го элемента), — то получающийсяности, поиска медианы, т.

е.2граф должен быть связным, иначе мы бы ничего не могли сказатьо том, как соотносятся между собой элементы из разных компонент.Показать, что для всех алгоритмов поиска, сопоставляющих указанным (неявным) образом связные графы конкретным массивам, n − 1является нижней границей сложности по числу сравнений (как в худшем случае, так и в среднем); в частности, это верно для алгоритмовпоиска медианы.Указание. Дерево с n вершинами имеет n − 1 ребро.. Рассмотрим класс алгоритмов поиска k первых (меньших) повеличине элементов массива без установления порядка между найденными элементами и класс алгоритмов поиска k-го по величинеЗадачиэлемента. Как обычно, имеется в виду поиск с помощью сравнений.Доказать, что любая нижняя граница сложности по числу сравненийалгоритмов первого класса является нижней границей и для второгокласса..

Дать доказательство предложения ., построенное по той жесхеме, что и доказательство предложения ..Указание. Рассмотреть тройки множеств (A, B, C), включая в A на каждомэтапе алгоритма все те элементы, которые еще не сравнивались, в B — всете, которые участвовали в сравнениях и всегда оказывались меньшими,в C — все те, которые участвовали в сравнениях и в некоторых оказывалисьбо́льшими.. Доказать содержащееся в доказательстве предложения . утверждение, что после первого сравнения постоянно будет выполненоb ¾ 1, c ¾ 1.. В классе алгоритмов вычисления an с помощью умножений (aфиксировано, n ∈ N) при рассмотрении n в качестве размера входасуществует оптимальный алгоритм.

То же самое — при рассмотренииm = λ(n) в качестве размера входа.. Бинарный алгоритм возведения в степень n не является оптимальным по числу умножений и при использовании m = λ(n) в качестве размера входа.Указание. Рассмотреть алгоритм, который для всех n 6= 15 работает какбинарный алгоритм, а при n = 15 — несколько быстрее (см. задачу ), и показать, что такой алгоритм при m = 4 имеет сложность меньшую, чем бинарный.. (Продолжение задачи .) Является ли оптимальным по порядку сложности бинарный алгоритм возведения в степень n при использовании m = λ(n) в качестве размера входа?. Рассмотренный в задаче  алгоритм поиска фальшивой монеты, требующий в худшем случае не более ⌈log3 n⌉ взвешиваний,является оптимальным для худшего случая.. Нижней границей сложности любого алгоритма деления отрезка на n равных частей с помощью циркуля и линейки (см. задачу ) при рассмотрении числа n в качестве размера входа является,n−1.в частности,2.

Отсутствие указания основания логарифма в (.) являетсякорректным.. Функция log2 (n + 1) является нижней границей сложности всреднем алгоритмов поиска места элемента в упорядоченном массиве Глава . Нижняя граница сложности. Оптимальные алгоритмыдлины n с помощью сравнений (считаем, что в диапазоне от 1 до1).n + 1 место может быть любым с одинаковой вероятностьюn+1Указание. Для доказательства воспользоваться предложением ...

(Продолжение предыдущей задачи.) Алгоритм бинарного поиска является оптимальным в среднем по порядку сложности в классеалгоритмов поиска места элемента с помощью сравнений.. Алгоритм, описанный в задаче , является оптимальным какв худшем случае, так и в среднем.. Пусть ¯T¯QS (n) и ¯T¯opt (n) — сложности в среднем быстрой сортировки и оптимальной в среднем сортировки. Верно ли, что ¯T¯QS (n) ∼∼¯T¯opt (n)? Если нет, то можно ли подобрать константу c такую, что¯T¯Q (n) ∼ c¯T¯opt (n)?.

Утверждение теоремы . перестает быть верным, если егоизменить, удалив условие, что τ < ∞ всюду на рассматриваемом вероятностном пространстве: при выполнении всех остальных условий∞Pможет оказаться, что τ = ∞ при том, чтоhk имеет конечное значение.k =1Указание. Рассмотреть постоянные величины ξk =1, k = 1, 2, ... ,k(k + 1)взяв hk = ξk для всех k; при любом q ¾ 1 получается противоречие с измененным утверждением. . Функция log2 (n + 1) является нижней границей сложности рандомизированных алгоритмов поиска места элемента в упорядоченном массиве длины n с помощью сравнений. (Предполагается, чтокаждый из рассматриваемых рандомизированных алгоритмов можетбыть задан как конечное множество детерминированных алгоритмовпоиска места элемента в упорядоченном массиве длины n, с приписанными этим детерминированным алгоритмам вероятностями,в сумме дающими единицу; при этом такое вероятностное пространство алгоритмов не должно зависеть от конкретного входа размера n.)Эта задача сообщена автору А.

В. Бернштейном.Глава Битовая сложность§ . Битовые операцииКаждый алгоритм строится на основе некоторого фиксированногонабора базовых операций, и, согласно определениям из § , алгебраическая сложность алгоритма рассматривается при допущении, чтозатратность операций не зависит от размеров операндов. С позицийкомпьютерной арифметики это допущение вполне приемлемо, есликаждый из операндов умещается в одном слове памяти. Но оно перестает быть приемлемым, если разрешаются операнды любой длиныи вычисления проводятся в рамках арифметики многократной точности (арифметики длинных чисел).

Здесь анализ сложности долженисходить из других принципов.Приемлемой является, например, следующая модель как система допущений, принимаемых нами при анализе алгоритмов. Числопредставляется набором бит, являющихся содержимым его двоичныхразрядов (знак числа — тоже бит, например, обычно знаки + и −изображаются соответственно нулем и единицей), и все арифметические операции сводятся, в конечном счете, к битовым операциям. В качестве битовых операций могут выступать булевы операции∨, ∧, ¬ (другая нотация: or, and, not) при интерпретации 1 = «истина»,0 = «ложь» встречающихся бит; эти операции считаются равнозатратными.

Все биты, участвующие в записи числа, считаются равнодоступными.Можно смотреть на все это так, что ячейки памяти машины содержат по одному биту каждая, а в остальном действует принципРАМ — ячеек бесконечно много и они в любой момент равнодоступны. Это — битовая модель вычислений (соответствующее сокращениеБМ может расшифровываться как «битовая модель» и как «битоваямашина»).Для анализа сложности с использованием БМ нет необходимостипереписывать алгоритмы, детализируя их до уровня битовых опера-Глава . Битовая сложностьций.

Вместо этого можно рассматривать привлекаемые алгоритмомбазовые арифметические операции как основанные на битовых вычислениях процедуры, полагая временные и пространственные затраты алгоритма равными числу затрачиваемых битовых операций и,соответственно, требующихся дополнительных бит памяти. В качестве размера входа часто рассматривается либо суммарная битоваядлина всего входа (всех входных данных), либо максимум этих длин.В некоторых случаях вместо битовых длин целых чисел берутся самиэти числа.

Возможно и использование нескольких параметров размера входа.Определение .. Пусть выбран какой-то размер входа. Рассмотрение каждой из базовых операций алгоритма A как процедуры, основанной на битовых вычислениях, и измерение затрат на выполнение A для каждого конкретного входа в битовых операциях или,соответственно, в хранимых дополнительных битах, приводит к битовой сложности (временной или пространственной) алгоритма A.Для нахождения битовой сложности какого-либо алгоритма, построенного на основных арифметических операциях над целыми числами, полезно знать битовые сложности самих основных арифметических операций. Мы исследуем школьные алгоритмы сложения, вычитания, умножения и деления «столбиком» неотрицательных целыхчисел в двоичной системе.В процессе сложения «столбиком» мы шаг за шагом вычисляемдвоичные цифры суммы, продвигаясь от младших разрядов к старшим.

При этом в старшие разряды каждый раз переносится 0 или 1.Таким образом, на каждом шаге мы работаем с тремя битами (на начальном шаге, когда рассматриваются самые младшие разряды, битпереноса полагаем равным нулю). Для сложения многозначных чисел нам нужны две битовые процедуры трех аргументов (два аргумента — это цифры одноименных разрядов двух данных чисел, третий — это бит переноса из предшествующих разрядов), одна из процедур дает цифру соответствующего разряда суммы, вторая — новыйбит переноса в старшие разряды.

Характеристики

Список файлов лекций