Definição e Níveis de Algoritmos

Prévia do material em texto

Algoritimos.
Definição informal:
Algoritimo é uma sequência de instruções explicitas e não ambíguas que podem ser
executadas mecanicamente , que recebe uma entrada e produz uma saída depois de um
tempo finito.
Definição formal:
1936 Alan Turing/
Descrição de algoritimos :
depende do nível de abstração.
 +| 1) Alto nível ­ Linguagem natural/ ignora detalhes de implementação.
 a|
 b|
 s|2)Nível de implementação ­ descrição do processamento + armazenamento de
 t| informação.
 r|
 a|
 ç|
 ã|
 o|3)Descrição formal ­ Descrever estado e transições da maquina de Turing .
 ­|
Boa representação:
sucinta, clara, suficiente precisa para permitir a tradução em um “programa”.
Exemplo 1(Os elementos de Euclides, livro x ­ proposição 3):
Linguagem natural(Não foi feito por ser muito extenso e enfadonho.)
Exemplo 2(Mips Assembly):
Mdc:
move $T0, $a0
move $t1, $a1
Loop:
beq $T1, $0, done
div $T0, $T1
move $T0,$T1
mfhi $T1
j loop
done:
move4V0, $T0
jr $Ra
Exemplo 3(fluxograma):
Neste curso usaremos pseudo­linguagem.
Exemplo4(Pseudo­linguagem):
Algoritimo mdc
Entrada: A,B são inteiros e não negativos.
Saída: O máximo divisor comum entre A e B.
Início
Enquanto B≠0 faça
C <­ A mod B
A <­ B
B <­ C
Fim­faça
Retorno A
Fim