Classificação por paradigma
Pode-se classificar algoritmos pela metodologia ou paradigma de seu desenvolvimento, tais como:
Divisão e conquista - algoritmos de divisão e conquista reduzem repetidamente o problema em sub-problemas,
geralmente de forma recursiva, até que o sub-problema é pequeno o suficiente para ser resolvido. Um exemplo
prático é o algoritmo de ordenação merge sort. Uma variante dessa metodologia é o decremento e conquista, que
resolve um sub-problema e utilização a solução para resolver um problema maior. Um exemplo prático é o algoritmo
para pesquisa binária. Programação dinâmica - pode-se utilizar a programação dinâmica para evitar o re-cálculo de
solução já resolvidas anteriormente. Algoritmo ganancioso - um algoritmo ganancioso é similar à programação
dinâmica, mas difere na medida que as soluções dos sub-problemas não precisam ser conhecidas a cada passo, uma
escolha gananciosa pode ser feita a cada momento com o que até então parece ser mais adequado. Programação
linear Redução - a redução resolve o problema ao transformá-lo em outro problema. É chamado também
transformação e conquista. Busca e enumeração - vários problemas podem ser modelados através de grafos. Um
algoritmo de exploração de grafo pode ser usado para caminhar pela estrutura e retornam informações úteis para a
resolução do problema. Esta categoria inclui algoritmos de busca e backtracking. Paradigma heurístico e
probabilístico - algoritmos probabilísticos realizam escolhas aleatoriamente. Algoritmos genéticos tentam encontrar
Definições sobre Lógica de Programação 10
a solução através de ciclos de mutações evolucionárias entre gerações de passos, tendendo para a solução exata do
problema. Algoritmos heurísticos encontram uma solução aproximada para o problema.
Classificação por campo de estudo
Cada campo da ciência possui seus próprios problemas e respectivos algoritmos adequados para resolvê-los.
Exemplos clássicos são algoritmos de busca, de ordenação, de análise numérica, de teoria de grafos, de manipulação
de cadeias de texto, de geometria computacional, de análise combinatória, de aprendizagem de máquina, de
criptografia, de compressão de dados e de interpretação de texto.
Classificação por complexidade
Ver artigo principal: Complexidade computacional. Alguns algoritmos são executados em tempo linear, de acordo
com a entrada, enquanto outros são executados em tempo exponencial ou até mesmo nunca terminam de serem
executados. Alguns problemas possuem múltiplos algoritmos enquanto outros não possuem algoritmos para
resolução.
Para lembrar
• Definição de Ciências da Computação
História da Programação
A mais antiga programadora de computadores de que se tem notícia é Ada Lovelace, que descreveu o funcionamento
da máquina analítica de Charles Babbage, que nunca ficou pronta. O primeiro programador que completou todos os
passos para a computação, incluindo a compilação e o teste, foi Wallace Eckert. Ele usou linguagem matemática
para resolver problemas astronômicos na década de 1930. Alan Turing elaborou e programou um computador
destinado a quebrar o código alemão ENIGMA na Segunda Guerra Mundial.
Lógica 11
Lógica
Lógica binária
A lógica binária, ou bitwise operation é a base de todo o cálculo computacional. Na verdade, são estas operações
mais básicas que constituem todo o poderio dos computadores. Qualquer operação, por mais complexa que pareça, é
traduzida internamente pelo processador para estas operações.
Operações
NOT
O operador unário NOT, ou negação binária resulta no complemento do operando, i.e., será um bit '1' se o operando
for '0', e será '0' caso contrário, conforme podemos confirmar pela tabela de verdade:
A ¬A
1 0
0 1
Implementação:
Se isto NOT aquilo
AND
O operador binário AND, ou conjunção binária devolve um bit 1 sempre que ambos operandos sejam '1', conforme
podemos confirmar pela tabela de verdade:
A B A ∧ B
1 1 1
1 0 0
0 1 0
0 0 0
Implementação:
Se isto AND aquilo, Fazer assim
OR
O operador binário OR, ou disjunção binária devolve um bit 1 sempre que pelo menos um dos operandos seja '1',
conforme podemos confirmar pela tabela de verdade:
Lógica 12
A B A ∨ B
1 1 1
1 0 1
0 1 1
0 0 0
Implementação:
Se isto OR aquilo, Fazer assim
XOR
O operador binário XOR, ou disjunção binária exclusiva devolve um bit 1 sempre que apenas um dos operandos
seja '1', conforme podemos confirmar pela tabela de verdade:
A B ∨ A ∨ B
1 1 0
1 0 1
0 1 1
0 0 0
Implementação:
isto XOR aquilo, Fazer assim
Shift
O operador unário de bit shifting, ou deslocamento bit-a-bit, equivale à multiplicação ou divisão por 2 do operando
que, ao contrário dos casos anteriores, é um grupo de bits, e consiste no deslocamento para a esquerda ou para a
direita do grupo de bits. O bit inserido é sempre 0, e o bit eliminado pode ser opcionalmente utilizado (flag CF dos
registos do processador).
( 101011(43) >> 1 ) = 010101[1]
( 101011(43) << 1 ) = [1]010110
Comentários
Postar um comentário