Engenharia de algoritmos

A engenharia de algoritmos foca no design, análise, implementação, otimização, caracterização e avaliação experimental dos algoritmos de computadores, preenchendo a lacuna entre a teoria dos algoritmos e as aplicações práticas destes na engenharia de software.  Trata-se de uma metodologia geral para pesquisa algorítmica.

Origens

Em 1995, um relatório de um workshop promovido pela NSF "com a finalidade de avaliar os objetivos atuais e direções da comunidade de teoria da computação" identificou a velocidade lenta da adopção de insights teóricos pelos praticantes como uma questão importante e sugeriu medidas para

• reduzir a incerteza dos praticantes se um certo avanço teórico irá, ou não, acrescentar ganhos práticos na sua área de trabalho, e
• combater a falta de bibliotecas de algoritmo pronta-para-uso, que fornecem implementações estáveis, livre de bugs e bem testadas para problemas algorítmicos, e expor uma interface fácil de usar para consumidores deste serviço.

Mas, também, abordagens algorítmicas promissoras têm sido negligenciadas devido às dificuldades de análise matemática.

O termo "engenharia de algoritmo" foi pela primeira vez usado com especificidade em 1997, com a organização do primeiro Workshop de Engenharia de Algoritmo (WAE97).

Diferenças da Teoria dos Algoritmos

A Engenharia de Algoritmo não pretende substituir ou competir com a teoria de algoritmos, mas tenta enriquecer, aperfeiçoar e reforçar suas abordagens formais com algorítmica experimental (também chamada algorítmica empírica).

Desta forma, pode fornecer novos insights sobre a eficiência e desempenho dos algoritmos em casos que

• o algoritmo à mão é menos passível a análise algoritmo-teórica,
• a análise formal sugere de forma pessimista limitantes que não são susceptíveis a aparecer em entradas de interesse prático,
• o algoritmo baseia-se em pormenores de arquiteturas modernas de hardware como localização de dados, branch prediction, stalls de instruções, latências de instruções, etc., que o modelo de máquina usado na abordagem teórica é incapaz de captar em detalhes,
• o cruzamento entre algoritmos concorrentes com diferentes custos constantes e comportamentos assintóticos precisa ser determinado.

Metodologia

Alguns pesquisadores descrevem a metodologia da Engenharia de Algoritmo como um ciclo consistindo do design, análise, implementação e avaliação experimental, junto com outros aspectos como modelos de máquina ou entradas realísticas. Eles argumentam que igualar a engenharia de algoritmo com algorítmica experimental é muito limitado, pois ver design e análise, implementação e experimentação como atividades separadas ignora o laço crucial entre esses elementos da engenharia de algoritmo.

Modelos realísticos e entradas reais

Apesar de aplicações especificas estarem fora da metodologia da engenharia de algoritmo, elas desempenham um papel importante na modelagem dos padrões realísticos do problema e da máquina subjacente, bem como no fornecimento de "entradas reais e outros parâmetros de design para expetimentos".

Design

Comparada com a teoria dos algoritmos, que usualmente foca-se no comportamento assintótico dos algoritmos, engenheiros algorítmicos levar em conta outros requerimentos: a simplicidade do algoritmo, a exequibilidade em linguagens de programação no hardware real, e a possibilidade de reuso do código. Além disso, fatores constantes dos algoritmos tem tanto impacto nas entradas reais que algumas vezes um comportamento assintótico pessimista de um algoritmo tem uma melhor performance na prática devido aos baixos fatores constantes.

Análise

Alguns problemas podem ser resolvidos com algoritmos heurísticos e randomizados de maneira simples e mais eficiente que em algoritmos determinísticos. Infelizmente, isso faz com que mesmo algoritmos randomicos simples seja difícil de analisar, pois há "dependência sutis que devem ser levadas em conta".

Implementação

Grandes lacunas semânticas entre insights teóricos, algoritmos formulados. linguagens de programação e hardware lançam um desafio para implementaçõe eficientes até para algoritmos simples, já que pequenos detalhes de implementação podem ter efeitos de propagação no comportamento de execução. A única maneira confiável de comparar diversas implementações para um algoritmo é gastar uma considerável quantidade de tempo no ajuste e na análise, rodando tais algoritmos em várias arquiteturas, e examinando o código de máquina gerado.

Experimentos

Veja: Algorítmica experimental

Engenharia de Aplicações

Implementações de algoritmos usado em experimentos diferem de maneira significativa do código utilizável em aplicações. Enquanto o primeiro prioriza a prototipação rápida, performance e instrumentação, o último requer "testes minuciosos, facilidade de manutenção, simplicidade e ajustes para classes especificas de entrada".

Bibliotecas de algoritmos

Bibliotecas estáveis e bem testadas de algoritmos, como a LEDA, exercem um importante papel na transferência tecnológica ao acelerar a adoção de novos algoritmos em aplicações. Essas bibliotecas reduzem o investimento necessário e o risco para profissionais, uma vez que remove o fardo de entender e implementar resultados obtidos nas pesquisas acadêmicas.

Conferências

Realizaram-se algumas conferências anuais para engenharia de algoritmo:

• Workshop on Algorithm Engineering (WAE), desde 1997.
• Workshop on Algorithm Engineering and Experimentation (ALENEX), desde 1999.

O Workshop on Algorithm Engineering (WAE'97) de 1997 foi sediado em Veneza (Itália) entre 11 e 13 de setembro. O terceiro International Workshop on Algorithm Engineering (WAE'99) foi sediado em Londres, UK em julho de 1999. O primeiro Workshop on Algorithm Engineering and Experimentation (ALENEX99) foi sediado em Baltimore, Maryland nos dias 15 e 16 de janeiro de 1999. Ele foi patrocinado pela DIMACS, pelo Center for Discrete Mathematics and Theoretical Computer Science (na Rutgers University), com suporte adicional do SIGACT, o Grupo Especial de Interesse em Algoritmos e Teoria da Computação da ACM, e da SIAM, a Sociedade de Matemática Industrial e Aplicada.