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

20

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

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

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

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

Анализ порядков роста иногда бесполезен. Например, мы не можем отличить быструю сортировку от 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))=Θ(nlogn)EXXE(T1(n))=A1nlgn+B1n+O(logn)T 1, T 2E(T2(n))=A2lgn+B2n+O(logn)T1T2 переводит алгоритмы на язык ассемблера и вычисляет время выполнения. Это слишком сложно для меня, поэтому я хочу знать некоторые приемы для более точного анализа времени выполнения, что также полезно для языков более высокого уровня, таких как C, C ++ или псевдокоды.

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

Yai0Phah
источник
6
Вы должны быть очень осторожны при тщательном сравнении времени выполнения алгоритмов. Реальные компьютеры имеют кэши, регистры и конвейеры, которые могут радикально изменить время работы. Если вы хотите узнать, какой алгоритм на самом деле быстрее, вы должны запустить его на компьютере.
svick
1
На самом деле, анализировать ассемблер, такой как использует Кнут, намного проще, чем анализировать реальный код, потому что ничего не скрыто, а процесс управления легок. Вы просите практики; Я думаю, что комментарий Дейва применим. Практики более склонны разрабатывать свои алгоритмы, используя измерения времени выполнения, чем проводить тщательный анализ. Но тогда я не практикующий, поэтому примите то, что я говорю, с долей соли.
Рафаэль
1
@Raphael My на практике означает, что на практике исследовательские работы , а не программирование .
Yai0Phah
@ Фрэнк, что ты имеешь в виду под дисперсией ? Мои тесты производительности дают мне временные различия.
edA-qa mort-ora-y
@ Рафаэль, твое первое замечание, это больше не так. Современные микросхемы переупорядочивают вашу сборку, делают склады / загружаются не по порядку, а также прогнозируют работу и загрузку. Для параллелизма и предыдущих проблем действительно необходим тщательный анализ, но я не делаю это в формальной форме.
edA-qa mort-ora-y

Ответы:

18

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

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

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

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

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

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

Этот алгоритм, очевидно, является правильным алгоритмом сортировки. Разделение списка и его слияние может быть осуществлено за время , что дает нам повторение для наихудшего случая времени выполнения T ( n ) = 2 T ( n).Θ(n). По основной теореме это дает оценкуT(n)Θ(nlogn).T(n)=2T(n2)+Θ(n)T(n)Θ(nlogn)

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

Алгоритм 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
}

mergesortnn>1Ln+1leftrightLwhileresultresultleftrightL

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

T(0)=T(1)=0T(n)T(n2)+T(n2)+7n

Tn=2k

T(0)=T(1)=0T(n)2T(n2)+7n

TΘ(nlogn)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):

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

f0=f1=0fn=fn2+fn2+en

enn

{f2m=2fm+e2mf2m+1=fm+fm+1+e2m+1

fnen

k=1n1(nk)Δfk=fnnf1

Δfk

W(s)=k1Δfkks=112sk1Δekks=: (s)

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

fn=nf1+n2πi3i3+i(s)ns(12s)s(s+1)ds .

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

fnnlog2(n)+nA(log2(n))+1

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


  1. Преобразования Меллина и асимптотика: повторение слияния по Флаолету и Голину (1992)
  2. Лучший вариант: Худший случай: Средний случай:en=n2
    en=n1
    en=nn2n2+1n2n2+1
Рафаэль
источник
Мой вопрос анализа времени выполнения состоит в том, как точно определить и , что близко к практике (например, есть возможность сравнивать сортировку слиянием и сортировку по qsort). β T ( n ) = T ( n / 2 ) + T ( n / 2 ) + α n + βαβT(n)=T(n/2)+T(n/2)+αn+β
Yai0Phah
@Frank: краткий ответ: не можете ; константы зависят от деталей реализации, включая архитектуру машины, язык и компилятор, которые не имеют значения для базового алгоритма.
Джефф
@JeffE Я должен утверждать, что и должны быть достаточно точными, чтобы провести некоторое сравнение. Вкратце, математическая модель, которая может выполнять множество работ без машинных языков для определения констант. βαβ
Yai0Phah
@JeffE, например, MIX / MMIX в taocp есть, но слишком сложно перевести алгоритм на такой машинный язык.
Yai0Phah
@FrankScience: чтобы приблизиться к практике, вам нужно сосчитать все операции (как делает Кнут). Затем вы можете создать свой результат с конкретными операционными затратами, чтобы получить реальное время выполнения (игнорируя эффекты, которые может иметь порядок операций, кэширование, конвейеры и т. Д.). Обычно люди считают только некоторые операции, и в этом случае исправление и говорит вам немного. βαβ
Рафаэль
3

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

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

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

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

Майк Самуэль
источник