Как описать алгоритмы, доказать и проанализировать их?

Прежде чем читать «Искусство компьютерного программирования» (TAOCP) , я не углублялся в эти вопросы. Я бы использовал псевдокод для описания алгоритмов, понимания их и оценки времени выполнения только по порядку роста. TAOCP тщательно меняет свое мнение.

TAOCP использует английский, смешанный с шагами и переходом для описания алгоритма, и использует блок-схемы для более быстрого представления алгоритма. Это кажется низким уровнем, но я нахожу, что есть некоторые преимущества, особенно с блок-схемой, которые я часто игнорировал. Мы можем пометить каждую стрелку утверждением о текущем положении дел в то время, когда вычисление проходит эту стрелку, и сделать индуктивное доказательство для алгоритма. Автор говорит:

Автор утверждает, что мы действительно понимаем, почему алгоритм действует только тогда, когда мы достигаем точки, когда наши умы неявно заполнили все утверждения, как это было сделано на рис.4.

Я не испытывал такие вещи. Еще одним преимуществом является то, что мы можем подсчитать, сколько раз выполняется каждый шаг. Это легко проверить с первым законом Кирхгофа. Я не проанализировал время выполнения точно, поэтому некоторые могли быть опущены при оценке времени выполнения.$\pm1$

Анализ порядков роста иногда бесполезен. Например, мы не можем отличить быструю сортировку от heapsort, потому что они все , где - ожидаемое число случайной величины , поэтому мы должны проанализировать константу, скажем, и , поэтому мы можем сравнить и лучше. А также, иногда мы должны сравнивать другие величины, такие как отклонения. Только грубого анализа порядков роста времени работы недостаточно. Как TAOCPE X X E ( T 1 ( n ) ) = A 1 n lg n + B 1 n + O ( log n ) E ( T 2 ( n ) ) = A 2 lg n + B 2 n + O $E(T(n))=\Theta(n\log n)$$EX$$X$$E(T_1(n))=A_1n\lg n+B_1n+O(\log n)$T 1, T $E(T_2(n))=A_2\lg n+B_2n+O(\log n)$$T_1$$T_2$ переводит алгоритмы на язык ассемблера и вычисляет время выполнения. Это слишком сложно для меня, поэтому я хочу знать некоторые приемы для более точного анализа времени выполнения, что также полезно для языков более высокого уровня, таких как C, C ++ или псевдокоды.

И я хочу знать, какой стиль описания в основном используется в исследовательских работах и ​​как решать эти проблемы.

Существует огромное разнообразие возможных подходов. Что лучше всего подходит, зависит от

• что ты пытаешься показать,
• сколько деталей вы хотите или нуждаетесь.

Если алгоритм широко известен и используется в качестве подпрограммы, вы часто остаетесь на более высоком уровне. Если алгоритм является основным объектом исследования, вы, вероятно, хотите быть более подробным. То же самое можно сказать и о анализах: если вам нужна грубая верхняя граница времени выполнения, вы поступаете иначе, чем когда вам нужно точное количество операторов.

Я приведу три примера для известного алгоритма Mergesort, которые, как мы надеемся, иллюстрируют это.

Высокий уровень

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

Этот алгоритм, очевидно, является правильным алгоритмом сортировки. Разделение списка и его слияние может быть осуществлено за время , что дает нам повторение для наихудшего случая времени выполнения T ( n ) = 2 T ( $\Theta(n)$. По основной теореме это дает оценкуT(n)∈Θ(nlogn).$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$$T(n) \in \Theta(n\log n)$

Средний уровень

Алгоритм Mergesort задается следующим псевдокодом:

procedure mergesort(l : List) {
  if ( l.length < 2 ) {
    return l
  }

  left  = mergesort(l.take(l.length / 2)
  right = mergesort(l.drop(l.length / 2)
  result = []

  while ( left.length > 0 || right.length > 0 ) {
    if ( right.length == 0 || (left.length > 0 && left.head <= right.head) ) {
      result = left.head :: result
      left = left.tail
    }
    else {
      result = right.head :: result
      right = right.tail
    }
  }

  return result.reverse
}

mergesort$n$$n>1$$L$$n+1$leftright$L$whileresultresultleftright$L$

$n>1$whilereverse$n$while$n$reverse$2n$операции со списками - каждый элемент удаляется из ввода и помещается в список вывода. Следовательно, счетчик операций выполняет следующие повторения:

$\qquad \begin{align}T(0) = T(1) &= 0 \\ T(n) &\leq T\left(\left\lceil\frac{n}{2}\right\rceil\right) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + 7n\end{align}$

$T$$n=2^k$

$\qquad \begin{align}T(0) = T(1) &= 0 \\ T(n) &\leq 2T\left(\frac{n}{2}\right) + 7n\end{align}$

$T \in \Theta(n \log n)$mergesort

Ультра-низкий уровень

Рассмотрим эту (обобщенную) реализацию Mergesort в Изабель / HOL :

types dataset  =  "nat * string"

fun leq :: "dataset \<Rightarrow> dataset \<Rightarrow> bool" where
   "leq (kx::nat, dx) (ky, dy) = (kx \<le> ky)"

fun merge :: "dataset list \<Rightarrow> dataset list \<Rightarrow> dataset list" where
"merge [] b = b" |
"merge a [] = a" |
"merge (a # as) (b # bs) = (if leq a b then a # merge as (b # bs) else b # merge (a # as) bs)"

function (sequential) msort :: "dataset list \<Rightarrow> dataset list" where
  "msort []  = []" |
  "msort [x] = [x]" |
  "msort l   = (let mid = length l div 2 in merge (msort (take mid l)) (msort (drop mid l)))"
by pat_completeness auto
  termination
  apply (relation "measure length")
by simp+

Это уже включает в себя доказательства четкости и прекращения. Найти (почти) полное доказательство правильности здесь .

Для «времени выполнения», то есть количества сравнений, можно установить повторение, подобное тому, которое было в предыдущем разделе. Вместо использования основной теоремы и забывания констант, вы также можете проанализировать ее, чтобы получить приближение, которое асимптотически равно истинной величине. Вы можете найти полный анализ в [1]; вот приблизительный план (он не обязательно соответствует коду Изабель / HOL):

Как указано выше, повторяемость числа сравнений

$\qquad \begin{align}f_0 = f_1 &= 0 \\ f_n &= f_{\left\lceil\frac{n}{2}\right\rceil} + f_{\left\lfloor\frac{n}{2}\right\rfloor} + e_n\end{align}$

$e_n$$n$

$\qquad \displaystyle \begin{cases} f_{2m} &= 2f_m + e_{2m} \\ f_{2m+1} &= f_m + f_{m+1} + e_{2m+1} \end{cases}$

$f_n$$e_n$

$\qquad \displaystyle \sum\limits_{k=1}^{n-1} (n-k) \cdot \Delta\kern-.2em\nabla f_k = f_n - nf_1$

$\Delta\kern-.2em\nabla f_k$

$\qquad \displaystyle W(s) = \sum\limits_{k\geq 1} \Delta\kern-.2em\nabla f_k k^{-s} = \frac{1}{1-2^{-s}} \cdot \underbrace{\sum\limits_{k \geq 1} \frac{\Delta\kern-.2em\nabla e_k}{k^s}}_{=:\ \boxminus(s)}$

что вместе с формулой Перрона приводит нас к

$\qquad \displaystyle f_n = nf_1 + \frac{n}{2\pi i} \int\limits_{3-i\infty}^{3+i\infty} \frac{\boxminus(s)n^s}{(1-2^{-s})s(s+1)}ds$ .

Оценка зависит от того, какой случай анализируется. Кроме этого, мы можем - после некоторой хитрости - применить теорему об остатках, чтобы получить$\boxminus(s)$

$\qquad \displaystyle f_n \sim n \cdot \log_2(n) + n \cdot A(\log_2(n)) + 1$

где - периодическая функция со значениями в .$A$$[-1,-0.9]$

1. Преобразования Меллина и асимптотика: повторение слияния по Флаолету и Голину (1992)
2. Лучший вариант: Худший случай: Средний случай:$e_n = \left\lfloor\frac{n}{2}\right\rfloor$
   $e_n = n-1$
   $e_n = n - \frac{\left\lfloor\frac{n}{2}\right\rfloor}{\left\lceil\frac{n}{2}\right\rceil + 1} - \frac{\left\lceil\frac{n}{2}\right\rceil}{\left\lfloor\frac{n}{2}\right\rfloor + 1}$

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

Когда вы начинаете с такой книги, сразу возникает вопрос: «Какой язык программирования я собираюсь использовать?», А это не так.простой вопрос презентации! Наиболее важным, но и самым неуловимым аспектом любого инструмента является его влияние на привычки тех, кто обучается его использованию. Если инструмент является языком программирования, это влияние - нравится нам это или нет - влияет на наши привычки мышления. Проанализировав это влияние, насколько мне известно, я пришел к выводу, что ни один из существующих языков программирования, ни подмножество их, не удовлетворят моей цели; с другой стороны, я знал себя настолько не готовым к разработке нового языка программирования, что я дал клятву не делать этого в течение следующих пяти лет, и у меня было совершенно отчетливое ощущение, что этот период еще не истек! (До этого, помимо прочего, эту монографию нужно было написать.

Позже он объясняет, насколько маленьким ему удалось получить свой мини-язык.

Я должен читателю объяснить, почему я сохранил такой мини-язык настолько маленьким, что он даже не содержит процедур и рекурсии. ... Дело в том, что я не нуждался в них, чтобы донести свое послание, а именно. как тщательно выбранное разделение интересов имеет важное значение для разработки во всех отношениях высококачественных программ; скромные инструменты мини-языка дали нам уже более чем достаточно широты для нетривиальных, но очень удовлетворительных дизайнов.