Algoritmos empíricos - Empirical algorithmics

Em ciência da computação , a algorítmica empírica (ou algorítmica experimental ) é a prática de usar métodos empíricos para estudar o comportamento de algoritmos . A prática combina desenvolvimento e experimentação de algoritmos: algoritmos não são apenas projetados, mas também implementados e testados em uma variedade de situações. Neste processo, um projeto inicial de um algoritmo é analisado para que o algoritmo possa ser desenvolvido de forma gradual.

Visão geral

Métodos de algoritmos empíricos complementam métodos teóricos para a análise de algoritmos . Por meio da aplicação de métodos empíricos, particularmente de estatísticas , muitas vezes é possível obter insights sobre o comportamento de algoritmos, como algoritmos heurísticos de alto desempenho para problemas combinatórios difíceis que são (atualmente) inacessíveis à análise teórica. Métodos empíricos também podem ser usados ​​para alcançar melhorias substanciais na eficiência algorítmica .

A cientista da computação americana Catherine McGeoch identifica dois ramos principais da algoritmos empírica: o primeiro (conhecido como análise empírica ) lida com a análise e caracterização do comportamento de algoritmos , e o segundo (conhecido como projeto de algoritmo ou engenharia de algoritmo ) é focado em métodos empíricos para melhorar o desempenho dos algoritmos . O primeiro muitas vezes depende de técnicas e ferramentas de estatística , enquanto o último é baseado em abordagens de estatística , aprendizado de máquina e otimização . Ferramentas de análise dinâmica , normalmente perfis de desempenho , são comumente usadas ao aplicar métodos empíricos para a seleção e refinamento de algoritmos de vários tipos para uso em vários contextos.

A pesquisa em algoritmos empíricos é publicada em vários periódicos, incluindo o ACM Journal on Experimental Algorithmics (JEA) e o Journal of Artificial Intelligence Research (JAIR). Além de Catherine McGeoch, pesquisadores conhecidos em algoritmos empíricos incluem Bernard Moret , Giuseppe F. Italiano , Holger H. Hoos , David S. Johnson e Roberto Battiti .

Perfil de desempenho no projeto de algoritmos complexos

Na ausência de algoritmos empíricos, analisar a complexidade de um algoritmo pode envolver vários métodos teóricos aplicáveis ​​a várias situações em que o algoritmo pode ser usado. Considerações sobre memória e cache são freqüentemente fatores significativos a serem considerados na escolha teórica de um algoritmo complexo, ou na abordagem para sua otimização, para um determinado propósito. O perfil de desempenho é uma técnica de análise dinâmica de programa normalmente usada para localizar e analisar gargalos no código de um aplicativo inteiro ou para analisar um aplicativo inteiro para identificar o código de baixo desempenho. Um criador de perfil pode revelar o código mais relevante para os problemas de desempenho de um aplicativo.

Um criador de perfil pode ajudar a determinar quando escolher um algoritmo em vez de outro em uma situação particular. Quando um algoritmo individual é perfilado, como ocorre com a análise de complexidade, as considerações de memória e cache são frequentemente mais significativas do que contagens de instruções ou ciclos de clock; no entanto, as descobertas do criador de perfil podem ser consideradas à luz de como o algoritmo acessa os dados, em vez do número de instruções que usa.

A criação de perfil pode fornecer uma visão intuitiva do comportamento de um algoritmo, revelando as descobertas de desempenho como uma representação visual. O perfil de desempenho foi aplicado, por exemplo, durante o desenvolvimento de algoritmos para correspondência de curingas . Os primeiros algoritmos para combinar curingas, como o algoritmo wildmat de Rich Salz , normalmente dependiam da recursão , uma técnica criticada por motivos de desempenho. O algoritmo de correspondência de curingas Krauss foi desenvolvido com base na tentativa de formular uma alternativa não recursiva usando casos de teste seguidos por otimizações sugeridas por meio de perfis de desempenho, resultando em uma nova estratégia algorítmica concebida à luz do perfil, juntamente com outras considerações. Perfiladores que coletam dados no nível de blocos básicos ou que contam com assistência de hardware fornecem resultados que podem ser precisos o suficiente para auxiliar os desenvolvedores de software na otimização de algoritmos para um determinado computador ou situação. O perfil de desempenho pode ajudar o desenvolvedor a entender as características de algoritmos complexos aplicados em situações complexas, como algoritmos coevolucionários aplicados a problemas arbitrários baseados em teste, e pode ajudar a levar a melhorias de design.

Veja também

Referências