Como descrever algoritmos, provar e analisá-los?

20

Antes de ler A arte da programação de computadores (TAOCP) , não considerei essas questões profundamente. Eu usaria pseudo-código para descrever algoritmos, entendê-los e estimar o tempo de execução apenas sobre ordens de crescimento. O TAOCP muda completamente de idéia.

O TAOCP usa inglês misturado com etapas e para descrever o algoritmo e usa fluxogramas para visualizar o algoritmo mais rapidamente. Parece baixo, mas acho que há algumas vantagens, especialmente no fluxograma, que eu ignorei bastante. Podemos rotular cada uma das setas com uma afirmação sobre o estado atual das coisas no momento em que o cálculo atravessa essa seta e fazer uma prova indutiva do algoritmo. O autor diz:

É a afirmação do autor que realmente entendemos por que um algoritmo é válido somente quando atingimos o ponto em que nossas mentes preencheram implicitamente todas as afirmações, como foi feito na Fig.4.

Eu não experimentei essas coisas. Outra vantagem é que podemos contar o número de vezes que cada etapa é executada. É fácil verificar a primeira lei de Kirchhoff. Não analisei exatamente o tempo de execução; portanto, ±1 pode ter sido omitido quando eu estava estimando o tempo de execução.

A análise das ordens de crescimento às vezes é inútil. Por exemplo, não podemos distinguir quicksort de heapsort porque eles são todos E(T(n))=Θ(nlogn) , onde EX é o número esperado de variável aleatória X , portanto devemos analisar a constante, digamos, E(T1(n))=A1nlgn+B1n+O(logn)e E(T2(n))=A2lgn+B2n+O(logn) , assim podemos comparar T1 e T2 melhor. E também, às vezes, devemos comparar outras quantidades, como variações. Apenas uma análise aproximada das ordens de crescimento do tempo de execução não é suficiente. Como TAOCP traduz os algoritmos para a linguagem assembly e calcula o tempo de execução. É muito difícil para mim, então eu quero conhecer algumas técnicas para analisar o tempo de execução um pouco mais a fundo, o que também é útil para linguagens de nível superior, como C, C ++ ou pseudo-códigos.

E quero saber que estilo de descrição é usado principalmente em trabalhos de pesquisa e como tratar esses problemas.

Yai0Phah
fonte
6
Você deve ter muito cuidado ao comparar os tempos de execução dos algoritmos de perto. Computadores reais possuem caches, registradores e pipelines, o que pode alterar drasticamente o tempo de execução. Se você deseja descobrir qual algoritmo é realmente mais rápido, é necessário executá-lo em um computador.
precisa
1
Na verdade, analisar assembler como Knuth usa é muito mais fácil do que analisar código da vida real, porque nada está oculto e o fluxo de controle é fácil. Você está pedindo prática; Eu acho que o comentário de Dave se aplica. Os profissionais são mais propensos a projetar seus algoritmos usando medições de tempo de execução do que a fazer análises rigorosas. Mas, como não sou praticante, tome o que digo com um grão de sal.
Raphael
1
@ Rafael Na minha prática , isso significa que, na prática de trabalhos de pesquisa , não de programação .
Yai0Phah
@ Frank, o que você quer dizer com variação ? Meus testes de desempenho me dão variações de tempo.
EdA-qa mort-ora-y
@ Rafael, seu primeiro ponto, isso não é mais verdade. Os chips modernos reordenam sua montagem, armazenam / carregam fora de ordem e executam e carregam preditivamente. Para simultaneidade e os problemas anteriores, é necessária uma análise completa, mas eu não faço isso de forma formal.
EdA-qa mort-ora-y

Respostas:

18

Existe uma enorme variedade de abordagens viáveis. Qual é o mais adequado depende da

  • o que você está tentando mostrar,
  • quantos detalhes você deseja ou precisa.

Se o algoritmo é amplamente conhecido e usado como sub-rotina, você geralmente permanece em um nível superior. Se o algoritmo for o principal objeto sob investigação, você provavelmente desejará ser mais detalhado. O mesmo pode ser dito para análises: se você precisar de um limite superior de tempo de execução aproximado, proceda de maneira diferente de quando deseja contagens precisas de instruções.

Vou dar três exemplos para o conhecido algoritmo Mergesort, que espero ilustrar isso.

Alto nível

O algoritmo Mergesort pega uma lista, divide-a em duas (aproximadamente) partes igualmente longas, repete-se nessas listas parciais e mescla os resultados (classificados) para que o resultado final seja classificado. Em listas singleton ou vazias, ele retorna a entrada.

Esse algoritmo é obviamente um algoritmo de classificação correto. Dividir a lista e mesclá-la podem ser implementadas no tempo , o que nos dá uma recorrência para o pior tempo de execução T ( n ) = 2 T ( nΘ(n). Pelo teorema do mestre, isso é avaliado comoT(n)Θ(nlogn).T(n)=2T(n2)+Θ(n)T(n)Θ(nlogn)

Nível médio

O algoritmo Mergesort é dado pelo seguinte pseudocódigo:

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>1whilereversenwhilenreverse2noperações de lista - cada elemento é removido da entrada e colocado na lista de saída. Portanto, a contagem de operações cumpre a seguinte recorrência:

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

Nível ultra baixo

Considere esta implementação (generalizada) do Mergesort em Isabelle / 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+

Isso já inclui provas de bem-definição e rescisão. Encontre aqui uma prova de correção (quase) completa .

Para o "tempo de execução", ou seja, o número de comparações, é possível configurar uma recorrência semelhante à da seção anterior. Em vez de usar o teorema mestre e esquecer as constantes, você também pode analisá-lo para obter uma aproximação assintoticamente igual à quantidade verdadeira. Você pode encontrar a análise completa em [1]; Aqui está um esboço (não necessariamente se encaixa no código Isabelle / HOL):

Como acima, a recorrência do número de comparações é

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)

que, juntamente com a fórmula da Perron, nos leva a

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

A avaliação de depende de qual caso é analisado. Fora isso, podemos - depois de alguns truques - aplicar o teorema do resíduo para obter(s)

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

onde é uma função periódica com valores em .A[1,0.9]


  1. Transformações e assintóticos de Mellin: a recorrência da fusão de Flajolet e Golin (1992)
  2. Melhor caso: Pior caso: Caso médio:en=n-1en=n- nen=n2
    en=n1
    en=nn2n2+1n2n2+1
Rafael
fonte
Minha pergunta sobre a análise do tempo de execução é que, como determinar e exatamente , que está próximo da prática (por exemplo, está disponível para comparar a classificação de mesclagem e qsort). β T ( n ) = T ( n / 2 ) + T ( n / 2 ) + α n + βαβT(n)=T(n/2)+T(n/2)+αn+β
Yai0Phah
@ Frank: A resposta curta é que você não pode ; as constantes dependem dos detalhes da implementação - incluindo a arquitetura, a linguagem e o compilador da máquina - que são irrelevantes para o algoritmo subjacente.
Jeffe
@ Jeffff Eu tenho que afirmar que, o e só devem ser exatos o suficiente para fazer alguma comparação. Resumidamente, um modelo matemático que pode fazer muitos trabalhos , sem linguagens de máquina, para determinar as constantes. βαβ
Yai0Phah
@ Jeff, por exemplo, o MIX / MMIX no taocp é, mas é muito difícil traduzir um algoritmo para uma linguagem de máquina.
Yai0Phah
@FrankScience: Para se aproximar da prática, você teria que contar todas as operações (como Knuth faz). Em seguida, você pode instanciar seu resultado com custos de operação específicos da máquina para obter um tempo de execução real (ignorando os efeitos que a ordem das operações pode ter, armazenamento em cache, pipelines, ...). Normalmente, as pessoas contam apenas algumas operações e, nesse caso, corrigir e não diz muito. βαβ
Raphael
3

A "Disciplina de Programação" de Dijkstra trata de analisar e provar algoritmos e projetar para provabilidade. No prefácio desse livro, Dijkstra explica como uma minilinguagem construída muito simples, projetada adequadamente para ser analisada, é suficiente para explicar formalmente muitos algoritmos:

Ao iniciar um livro como este, imediatamente se depara com a pergunta: "Qual linguagem de programação eu vou usar?", E isso não éuma mera questão de apresentação! Um aspecto mais importante, mas também mais evasivo, de qualquer ferramenta é sua influência nos hábitos daqueles que se treinam em seu uso. Se a ferramenta é uma linguagem de programação, essa influência é - gostemos ou não - de influenciar nossos hábitos de pensamento. Tendo analisado essa influência da melhor maneira possível, cheguei à conclusão de que nenhuma das linguagens de programação existentes, nem um subconjunto delas, atenderia ao meu propósito; por outro lado, eu me conhecia tão pouco para o design de uma nova linguagem de programação que prometi não fazê-lo pelos próximos cinco anos e tive uma sensação muito distinta de que esse período ainda não havia passado! (Antes disso, entre muitas outras coisas, essa monografia tinha que ser escrita.

Mais tarde, ele explica o quão pequeno conseguiu obter sua mini-linguagem.

Devo ao leitor uma explicação de por que mantive a minilíngua tão pequena que nem sequer contém procedimentos e recursão. ... O ponto é que eu não sentia necessidade deles para transmitir minha mensagem, viz. como uma separação de preocupações cuidadosamente escolhida é essencial para a concepção de todos os aspectos, programas de alta qualidade; as ferramentas modestas da mini-língua já nos deram latitude mais do que suficiente para projetos não triviais, mas muito satisfatórios.

Mike Samuel
fonte