Experimentação Algorítmica

Aula 2Baseada em B. M. E. Moret,

Towards a Discipline of Experimental Algorithms

Introdução (1)

Implementação era característica dos primeiros trabalhos em algoritmos e estruturas de dados.

Knuth e Floyd pioneiros em “dicas” práticas.

Bentley demonstrou o valor da implementação e teste de algoritmos.

Introdução (2) Somente nos últimos anos voltou-se a

ter a implementação e teste como parte do desenvolvimento de algoritmos.

Experimentação como parte de uma ciência exata.

Empirismo Aceitável em ciências naturais, na qual as

“leis da natureza” podem ser modeladas.

Introdução (3)

Os algoritmos em si é que são medidos e não um modelo.

Não há como compará-los com um resultado padrão, somente comparar com outros experimentos do mesmo tipo.

Análise Teórica (1)

Análise teórica baseada no comporta-mento assintótico de pior caso.

Comportamento assintótico elimina confusões potenciais no comportamento em instâncias pequenas devido ao tempo de inicialização e mostra a taxa de crescimento no tempo de execução.

Análise Teórica (2)

O pior caso fornece limites claros e simplifica a análise pois elimina suposições sobre os dados.

Este tipo de análise: Fácil de comunicar e entender. Independente de máquina.

Problemas com a Análise Teórica (1)

A faixa de valores na qual o comportamento assintótico aparece pode incluir valores que estão bem além de qualquer aplicação.

A constante oculta pode ser proibitiva a qualquer implementação, mesmo que a taxa de crescimento seja baixa.

Problemas com a Análise Teórica (2) O comportamento de pior caso pode

ser restrito a um pequeno subconjunto de instâncias encontradas na prática.

A obtenção de bons limites assintóticos pode ser muito difícil.

A análise assintótica de pior caso tende a favorecer o desenvolvimento de algoritmos de “lápis e papel”.

Algoritmos em “lápis e papel”

Muitos algoritmos foram desenvolvidos baseados em outros algoritmos e estruturas de dados teóricos, o que dificulta suas implementações, uma vez que seria necessário implementar os algoritmos e estruturas de dados intermediários.

Engenharia de Algoritmos (1) Transformação de algoritmos

“lápis e papel” em implementações úteis e eficientes.

Pode melhorar sensivelmente o tempo de execução do código.

Levar a bibliotecas robustas de estruturas de dados com overhead mínimo.

Engenharia de Algoritmos (2) Muitos algoritmos devem ser

implementados e não só projetados. Uma implementação força os teóricos

a visualizar detalhes escondidos na fase de projeto de alto nível.

Aprofunda o conhecimento do algoritmo e pode resultar em uma simplificação ou levar a novas conjecturas.

Modelos de Avaliação Empírica

Checagem de exatidão e corretude em casos extremos. Séries de testes padronizados para

computação numérica. Avaliação da qualidade das

heurísticas para a solução aproximada de problemas NP-difíceis.

Em computação numérica isto já é feito com certo grau de maturidade.

Modelos de Avaliação Empírica

Medidas de tempo de execução de algoritmos exatos em instâncias reais de problemas NP-difíceis.

Comparação de desempenho real de algoritmos “rivais” para problemas tratáveis e caracterização dos efeitos da Engenharia de Algoritmos.

Modelos de Avaliação Empírica Determinação de ganho obtido por

algoritmos paralelos em máquinas reais.

Investigação e refinamento de modelos e critérios de otimização. O que poderia ser otimizado? Que parâmetros importam?

Teste da qualidade e robustez de simulações, de estratégias de otimização, etc.

•Esforço particularmente especializado.

•Ausência de um bom modelo.

É de grande interesse atualmente, prin-cipalmente em Biologia Computacional e Química Computacional

Avaliação de Algoritmo “Rivais” e Estruturas de Dados para Problemas Tratáveis Objetivo é medir o desempenho

real de algoritmos “rivais” para problemas bem solucionados.

Construção de algoritmos e implementações nos quais são explorados detalhes de cache e arquitetura, que melhoram o desempenho dos algoritmos.

Avaliação de Heurísticas (1)

O objetivo é medir o desemplenho de heurísticas em instâncias reais e artificiais e melhorar o entendimento teórico do problema, de forma a obter heurísticas melhores ainda ou mostrar que já se tem a melhor.

No desempenho, mede-se o tempo de execução e a qualidade da solução.

Avaliação de Heurísticas (2)

Geração de instâncias de testes significativos.

Derivação de limites inferiores fortes.

Permitem a avaliação da qualidade das heurísticas.

O que está sendo feito Teste e melhora de algoritmos para

problemas difíceis. Comparação de algoritmos existentes e

estruturas de dados para problemas tratáveis.

Engenharia de Algoritmos. Conjecturas de suporte e refinamento. Ferramentas de Desenvolvimento. Condução de experimentos para avaliar a

relevância de critérios de otimização.

Teste e melhora de algoritmos para problemas difíceis (1)

Avaliação mais simples através da caracterização do tempo de execução de pior caso do que o desenvolvimento de uma classificação de dados de entrada em termos de alguns parâmetros suficientes para prever o desempenho dos algoritmos para a maioria dos casos.

Teste e melhora de algoritmos para problemas difíceis (2)

Experimentação auxilia a avaliação de desempenho de um algoritmo em instâncias reais e desenvolver limites nas quais a execução é rápida e instâncias em que comportamento exponencial ocorre.

Comparação de algoritmos e estruturas de dados existentes para problemas tratáveis Diferencia boas e más

implementações. Evidencia se boas vantagens teóricas

também o são na prática. Leva a refinamentos e simplificações. Permite a determinação das

constantes do tempo de execução. Experimentação inclui os efeitos do

cache.

Engenharia de Algoritmos Procura produzir a mais eficiente e útil

implementação possível. Teste e refinamento são usados para

melhorar o desempenho. Podemos destacar:

Redução do uso da memória. Alteração dos padrões de endereçamento. Desenrolando laços de forma a manter as

variáveis em registradores. Verificar quais informações são realmente úteis

e como são usadas em cada etapa do algoritmo.

Obteve-se um ganho de 3 ordens de magnitude.

Apoiando e Refinando Conjecturas

Teste de conjecturas para um intervalo de instâncias.

Experimentos são fontes de novas conjecturas e teoremas.

Ferramentas de Desenvolvimento

Configurando Experimentos

O que medir?

Como apresentar e analisar os dados?