Eloquent Javascript – Parte 2

Fevereiro 20, 2012

Esse post é uma continuação do meu estudo do livro Eloquent Javascript, iniciado aqui. Agora eu também mantenho uma página com o índice de livros com todos os posts referentes a eles.

Capítulo 6 – Programação Funcional

Esse capítulo apresenta algumas funcionalidades comuns a linguagens funcionais como funções anônimas, map, reduce, aplicação parcial de função e composição de funções. Boa parte do capítulo é dedicada a apresentar uma solução para um problema de converter texto em HTML. Achei interessante mostrar a aplicação de programação funcional num exemplo real, mas achei que fugiu um pouco do tópico.

Achei estranho o fato de o autor não mencionar closures, que é uma técnica muito empregada em javascript e que a meu ver é base para várias dessas funcionalidades de programação funcional apresentadas.

Em javascript podemos ter funções dentro de funções. Nesse caso, as funções internas têm acesso às variáveis locais definidas nas funções mais externas. No código abaixo, a função interna (anônima) tem acesso (leitura e escrita) à x e também à variável y.

Em geral, quando a função termina, perdemos a referência para as variáveis locais definidas dentro dessa função. Em javascript, funções podem ter comportamento parecido com o de objetos. Uma prova disso é que podemos retornar uma função, como no exemplo abaixo.

Combinado com a propridade de acessar membros das funções externas, temos um mecanismo de acesso indireto aos membros internos da funções. Esse é o conceito mais básico de closures.

function closure(y){
    var x = 10;
    return function(z){
        alert(x + y + z);
        x++;
    }
}
var foo = closure(5);
foo(3); // imprime 18
foo(3); // imprime 19

Com closure podemos fazer a aplicação parcial de funções. O segredo é que a keyword arguments contém todos os argumentos passados para uma função, mesmo que eles não sejam usados pela função. Assim, a função partial definida abaixo recebe uma função func como argumento. Todos os parâmetros adicionais, ele repassa para func, junto com os parâmetros que serão passados para a função anônima quando ela for invocada.

A função asArray serve apenas para converter parameters para um array, pois é esse o tipo esperado pela função apply.

// É preciso converter a lista de argumentos para array
// antes de passar para a função apply
function asArray(quasiArray, start){
    var result = [ ];
    for(var i = (start || 0); i < quasiArray.length; i++)
        result.push(quasiArray[i]);
    return result;
}

// Partial salva os primeiros argumentos da função em 'fixedArgs'
// Quando a função for de fato chamada, apenas os argumentos restantes
// precisam ser passados
function partial(func){
    // O primeiro argumento é func.
    var fixedArgs = asArray(arguments, 1); 
    return function(){
        return func.apply(null, fixedArgs.concat(asArray(arguments)));
    };
}

Para ficar mais claro, considere uma função anônima implementando uma soma e suponha que passamos esta função para partial, mais o parâmetro 3. Este parâmetro será aplicado à soma antes dos parâmetros passados para a função “objeto” foo.

var foo = partial(function(a, b){ return a + b; }, 3);
var res = foo(20); // 23

Usando uma ideia parecida, podemos fazer a composição de duas funções. No exemplo abaixo, se passarmos uma função foo() e bar() para composition, obteremos uma função equivalente a foo(bar()):

// Composição de duas funções
function composition(func1, func2){
    return function(){
        return func1(func2.apply(null, asArray(arguments)));
    };
}

Um exemplo de uso dessa função é a composição de uma função que retorna o dobro do valor da entrada e outra que soma dois elementos.

var composed = composition(
    function(v){ 
        return 2*v;
    }, 
    function(a, b){
        return a + b;
    }
)
alert(composed(6, 7)); // 26

Capítulo 7 – Busca

Logo no começo do capítulo o autor observa que este não introduzirá nenhuma funcionalidade nova de Javascript. De fato, é apresentado o problema do menor caminho, o qual é atacado inicialmente através de um algoritmo aleatório força bruta. Depois ele descreve rapidamente o algoritmo A* e apresenta uma solução em Javascript, usando alguns dos conceitos ensinados até então.

Capítulo 8 – Orientação a Objetos

Neste capítulo são apresentadas técnicas para trabalhar com orientação a objetos em Javascript. Basicamente, podemos criar um objeto a partir de uma função com o operador new.

function Foo(){
}
var obj = new Foo();

Pensando em classes, Foo age como construtor e definidor da classe. Poderíamos declarar membros e métodos dentro desse construtor.

function Foo(int x){
    this.x = x;
    this.bar = function(){
        alert(this.x);
    }
}
var a = new Foo(10);
a.bar();
var b = new Foo(11);
b.bar();

É possível adicionar e modificar métodos da “classe” depois que ela já foi definida através dos chamados protótipos (prototype). Toda função tem uma propriedade chamada prototype e este herda um conjunto de propriedades do protótipo de Object. Entre essas propriedades estão toString e constructor. O constructor aponta para a própria função, de forma que as duas linhas abaixo são equivalentes:

var a = new Foo(10);
var a = new Foo.prototype.constructor(10);

O autor continua apresentando técnicas para se trabalha com OO em Javascript através de um exemplo bem interessante de simulação, consistindo de um mapa 2D e várias criaturas ficam se movimentando. É possível ver a simulação em tempo real (em modo texto) com o interpretador embutido na página.

Ao apresentar o código dessa simulação, ele descreve uma situação problemática: passar um método como parâmetro para uma função externa (callback), como no exemplo abaixo:

function say(func){
    alert(func());
}

function Foo(){
    this.v = [10];
    this.get = function(){
        return this.v;
    };
    this.bar = function(){
        say(this.get);
    };
}
var c = new Foo();
c.bar();

A função foo irá imprimir undefined. Segundo [3], ao executar a função say, a referência ao objeto é perdida. Para contornar a situação, é possível usar um closure, para manter a referência ao objeto.

Nesse sentido, é comum definir a seguinte função:

function bind(func, obj){
    return function(){
        return func.apply(obj, arguments);
    }
}

A função retornada por bind contém a referência ao objeto obj. Podemos reescrever o método bar da seguinte maneira:

this.bar = function(){
    say(bind(this.get, this));
}

Herança

Um mecanismo de herança pode ser obtido em Javascript através de protótipos. A ideia é clonar o protótipo da classe base.

function clone(object) {
    function Constructor(){};
    Constructor.prototype = object;
    return new Constructor();
}

Object.prototype.inherit = function(baseConstructor) {
  this.prototype = clone(baseConstructor.prototype);
  this.prototype.constructor = this;
};

Um exemplo de uso:

function Base(){ } 
Base.prototype.x = 10;
Base.prototype.bar = function(){
    alert(this.x);
}
function Derived(){ }
Derived.inherit(Base);

Capítulo 9 – Modularidade

Este capítulo não apresenta nenhuma novidade de Javascript, focando mais em boas práticas sobre organização do código. São ensinados truques para gerenciar dependências entre módulos e maneiras de se publicar somente um subconjunto das funções presentes no módulo.

Capítulos 10, 11, 12, 13 e 14

O capítulo 10 apresenta expressões regulares em Javascript. Os capítulos restantes falam sobre o básico programação Web, DOM (Document-Object Model), eventos dos browsers e requisições HTTP.

Como eu já conhecia o básico de cada assuntos desses e no livro não foram muito aprofundados, não tenho nenhum comentário adicional para fazer aqui.

Conclusão

Javascript é mais complicado do que parece! Ainda tenho bastante dúvida sobre closure e protótipos e pretendo pesquisar mais sobre o assunto.

Leitura adicional

[1] Stackoverflow – How do JavaScript closures work?
[2] Javascript Closures
[3] Stackoverflow – JavaScript Callback Scope

Anúncios

Equações de Pell

Fevereiro 12, 2012

Equações diofantinas são equações polinomiais que só admitem soluções inteiras. Neste post, vou comentar sobre três casos particulares e me concentrar em um deles, conhecido como equações de Pell.

Triplas de Pitágoras

O caso mais conhecido de equações diofantinas é da forma:

x^2 + y^2 = z^2

As soluções inteiras para essa equação são conhecidas como triplas pitagóricas, por causa do teorema de Pitágoras, sobre a relação entre os comprimentos dos lados de um triângulo retângulo.

Para o caso mais geral, da forma x^n + y^n = z^n com n > 2, o famoso último teorema de Fermat diz que não existem soluções inteiras.

Indentidade de Bézout

Outro caso particular conhecido são as equações diofantinas lineares de duas variáveis, por exemplo, x e y, da forma

ax + by = c

Onde a, b, c são constantes inteiras. No caso em que c é o máximo divisor comum de a, b, temos a identidade de Bézout. É possível encontrar um par x, y inteiro usando o algoritmo de Euclides estendido.

Note entretanto que há infinitas soluções inteiras para essa equação, pois se x, y é uma solução, x' = x + b e y' = y - a é também uma solução.

Equação de Pell

Só recentemente ouvi falar sobre um outro caso particular, conhecido como equações de Pell, com a forma:

(1) x^2 - ny^2 = 1

Onde n é um inteiro positivo. Se n não possui raíz exata, então existem infinitas soluções inteiras x, y (Se n tiver raíz exata dá pra mostrar que a única solução é x = \pm 1 e y = 0). Vamos apresentar um algoritmo para encontrar as soluções para esse caso particular de n.

Frações continuadas

Um conceito usado no algoritmo é o de frações continuadas, que podem ser usadas para aproximar um número irracional através de frações. A fração continuada possui a seguinte forma:

Dado um número d, os coeficientes de sua fração continuada, a_0, a_1, \cdots, a_n são positivos e podem ser calculados através das recorrências, para i \ge 1:

r_i = \frac{1}{r_{i-1} - a_{i-1}}

a_i = \lfloor r_i \rfloor

e com a_0 = \lfloor d \rfloor.

Podemos representar uma fração continuada por seus coeficientes, ou seja, [a_0,a_1,a_2,\cdots]. Incrivelmente, no caso particular em que o número irracional é da forma \sqrt{n}, prova-se que os coeficientes da sua fração continuada são periódicos, ou seja \sqrt{n} = [a_0, \overline{a_1,a_2,\cdots,a_{r-1},a_{r}}] e a_{r} = 2a_0.

Como um exemplo, para n = 14 temos \sqrt{14} = [3,\overline{1,2,1,6}]

É possível calcular explicitamente o numerador p_i e o denominador q_i da fração continuada com i termos, através das recorrências:

\begin{array}{lcl}   p_0 & = & a_0\\  p_1 & = & a_1 a_0 + 1\\  p_n & = & a_n p_{n-1} + p_{n-2}   \end{array}

e

\begin{array}{lcl}   q_0 & = & 1\\  q_1 & = & a_1\\  q_n & = & a_n q_{n-1} + q_{n-2}   \end{array}

A fração p_i / q_i é chamada de n-ésimo convergente. Voltando ao exemplo para n = 14, temos:

\begin{array}{llcl}   i: & p_i / q_i  &  & \\  0:  & 3/1 & = & 3.0\\  1: & 4/1 & = & 4.0\\  2: & 11/3 & = & 3.66666666667\\   3: & 15/4 & = & 3.75\\  4: & 101/27 & = & 3.74074074074  \end{array}

Sendo que \sqrt{14} é aproximadamente 3.74165769645

Uma solução para a equação de Pell

Considere os coeficientes da fração continuada de \sqrt{n} e r o índice a partir do qual os coeficientes ficam periódicos.

Se r é par, seja x = p_{r-1} e y = q_{r-1}. Caso contrário, seja x = p_{2r-1} e y = q_{2r-1}. Surpreendentemente, existe um teorema que diz que x, y representam a menor solução inteira positiva para (1).

Algoritmo

Dadas essas propriedades, um algoritmo para encontrar uma solução para (1), consiste em iterar sobre os coeficientes p_i e q_i, até encontrar r tal que a_r = 2a_0. Segundo Lenstra [2], r \in O(\sqrt{n} \log n), ou seja, tem complexidade pseudo-polinomial. Assim, se d é o número de bits necessários para representar n, temos que r \in O(2^{d/2}d), ou seja, mesmo ignorando as complexidades das operações artiméticas no código, o nosso algoritmo é exponencial no número de bits.

Gerando mais soluções

Dada uma solução fundamental (x_1,y_1), Lenstra [2] afirma que se ordenarmos as soluções por magnitude, então a k-ésima solução (x_k, y_k) é tal que

(2) x_k + \sqrt{n}y_k = (x_1 + \sqrt{n}y_1)^k

Usando a ideia de [1], como ambos (x_1,y_1) e (x_k, y_k) são solução para (1), temos

x_k^2 - ny_k^2 = (x_1^2 - ny_1^2)^k = 1

Fatorando temos,

(x_k + \sqrt{n}y_k)(x_k - \sqrt{n}y_k) = (x_1 + \sqrt{n}y_1)^k(x_1 - \sqrt{n}y_1)^k

Por (2), concluímos que,

(3) x_k - \sqrt{n}y_k = (x_1 - \sqrt{n}y_1)^k

Resolvendo para (2) e (3), chegamos em:

\begin{array}{lcl}   x_k & = & \dfrac{(x_1 + y_1\sqrt{n})^k + (x_1 - y_1\sqrt{n})^k}{2}\\  \\  y_k & = & \dfrac{(x_1 + y_1\sqrt{n})^k - (x_1 - y_1\sqrt{n})^k}{2\sqrt{n}}  \end{array}

Implementação

Com base na teoria apresentada acima, é simples escrever um algoritmo. Adicionei uma implementação em python à minha biblioteca pessoal de teoria dos números, disponível no github.

Encontrei um post bastante interessante sobre equações de Pell e Haskell aqui [3]. Para praticar, resolvi implementar a minha versão antes de olhar o código do post. Apanhei bastante para lidar com o fato do Haskell não fazer conversão de tipos ponto flutuante e inteiro automaticamente. É preciso fazer isso explicitamente e por isso a função fromIntegral no código deste link.

Leitura complementar

[1] Wolfram – Pell Equation
[2] Solving the Pell Equation – H. W. Lenstra Jr.
[3] A Foray into Number Theory with Haskell


Relaxação Lagrangeana – Teoria

Fevereiro 5, 2012

Neste post vamos comentar brevemente sobre relaxações de formulações lineares inteiras e focar especialmente em relaxações lagrangeanas. Depois, vamos demonstrar a aplicação dessa técnica no problema da localização de instalações (facility location). A menos que dito o contrário, estamos falando de problemas de minimização.

Relaxações

Em programação linear inteira, usamos o termo relaxação para indicar que algumas das restrições do problema original foram relaxadas. Provavelmente o exemplo mais conhecido de relaxação é o da relaxação linear. Nesse caso em particular, removemos as restrições de integralidade do modelo.

Mais formalmente, se tivermos uma formulação F representada por

z = \min \{c(x): x \in P\}

sendo P o conjunto de pontos que satisfazem as restrições dessa formulação, c(x) a função objetivo e z o valor da solução ótima. Dizemos que uma formulação F_R, dada por

z_R = \min \{f(x): x \in R\}

é uma relaxação se todo ponto de P está em R, ou seja P \subseteq R e se f(x) \le c(x) para x \in P.

Note que devido a essas propriedades, a solução ótima da relaxação é um limitante dual (ou seja, no nosso caso é um limite inferior e superior no de maximização) para a formulação original ou seja, z_R \le z. Limitantes duais podem ser utilizados, por exemplo, para melhorar o desempenho do algoritmo de Branch and Bound.

A vantagem de se usar relaxações é que em certos casos elas são mais fáceis de serem resolvidas. Por exemplo, as relaxações lineares podem ser resolvidas em tempo polinomial, enquanto a versão restrita a inteiros, em geral, é NP-difícil.

Podemos também relaxar uma formulação removendo algumas de suas restrições. Note, entretanto, que quanto mais relaxamos a formulação pior tende a ser a qualidade do limitante dual (considere o caso extremo onde removemos todas as desigualdades do modelo: não deixa de ser uma relaxação, mas o limitante dual obtido não serve para nada).

O ideal é que encontremos uma relaxação fácil de resolver e que dê limitantes duais de qualidade, ou seja, bem próximos do valor ótimo da formulação original.

Relaxação Lagrangeana

Existe uma técnica denominada relaxação lagrangeana [1], que consiste em remover algumas das restrições da formulação original, mas tenta embutir essas desigualdades na função objetivo. A ideia é penalizar a função objetivo quando as restrições removidas forem violadas. O “peso” dessas penalidades é controlado por coeficientes chamados multiplicadores lagrangeanos.

Em termos de matemáticos, suponha que tenhamos uma formulação com m restrições e n variáveis:

z^* = \min cx

Sujeito a

\begin{array}{llcl}    & A_1x & \le & b_1 \\   & A_2x & \le & b_2 \\   & x & \ge & 0 \\   & x & \in & Z^n  \end{array}

Onde A_1x \le b_1 representa as desigualdades que queremos relaxar e A_2x \le b_2 as desigualdades que vamos manter. A relaxação lagrangeana é então dada por

z(u) = \min cx - u(b_1 - A_1x)

Sujeito a

\begin{array}{llcll}   & A_2x & \le & b_2 & \\  & x & \ge & 0 & \\  & x & \in & Z^n & \\  & u & \ge & 0, & u \in R^m_1  \end{array}

Onde u é um vetor representando os multiplicadores lagrangeanos (um por cada desigualdade removida). Por exemplo, considere a desigualdade j que será removida:

\sum_{i = 1}^n a_{ij} x_i \le b_j

Ao remover (11), o seguinte fator é subtraído da função objetivo

(1) u_j (b_j - \sum_{i = 1}^n a_{ij} x_i)

Note que quanto mais “violada” a desigualdade estiver, mais negativo o termo (1) vai ficar. Como a função é de minimização e estamos subtraindo, intuitivamente a solução ótima para o problema tenderá a não violar as desigualdades, melhorando o resultado do limitante dual.

Escolhe-se remover as desigualdades de forma que o problema resultante seja mais fácil resolver para um valor fixo de multiplicadores lagrangeanos. Porém, agora temos que resolver um outro problema: encontrar um conjunto de multiplicadores lagrangeanos u^* que minimize z(u).

Aplicação ao problema da localização de instalações

O problema da localização de instalações é bastante estudado na literatura. Uma de minhas iniciações científicas consistia em estudar algoritmos aproximados para esse problema.

Basicamente temos um grafo bipartido onde uma partição corresponde ao conjunto de clientes C e a outra ao conjunto de fábricas/instalações F. Cada cliente i pode ser potencialmente atendido pela fábrica j, a custo um c_{i,j}. Além disso, paga-se um custo c_j por abrir a fábrica j, dado por y_j. O objetivo é atender todos os clientes com o menor custo.

Vamos apresentar uma formulação linear inteira para esse problema. Seja x_{i,j} uma variável binária que vale 1 sse o cliente i é atendido pela fábrica j e a variável y_j uma variável binária que vale 1 sse a fábrica j foi aberta. Temos a seguinte formulação:

z = \min \sum_{i \in C, j \in F} x_{ij} c_{ij} + \sum_{j \in F} y_j c_j

Sujeito a

\begin{array}{llcll}   (2) & \sum_{j \in F} x_{ij} & \ge & 1 & \forall \, i \in C \\  (3) & x_{ij} & \le & y_j & \forall i \in C, \forall j \in F \\  & x_{i,j}, y_{j} & \in & \{0, 1\} & \forall i \in C, \forall j \in F  \end{array}

A desigualdade (2) diz que cada cliente deve ser atendido por pelo menos uma fábrica e a desigualdade (3), que uma fábrica deve estar aberta para que possa atender a algum cliente.

Essa é uma formulação bem simples e temos basicamente dois grupos de desigualdades. Vamos tentar relaxar o grupo de desigualdades indicado por (2). Teremos:

z_1(u) = \min \sum_{i \in C, j \in F} x_{ij} c_{ij} +
\sum_{j \in F} y_j c_j - \sum_{i \in C} u_i (\sum_{j \in F} x_{ij} - 1)

Sujeito a

\begin{array}{llcll}   & x_{ij} & \le & y_j & \forall i \in C, \forall j \in F \\  & u_i & \ge & 0 & \forall i \in C\\   & x_{i,j}, y_{j} & \in & \{0, 1\} & \forall i \in C, \forall j \in F  \end{array}

Com um pouco de álgebra, é possível “fatorar” o somatório da função objetivo:

z_1(u) = \min \sum_{j \in F} (\sum_{i \in C} (x_{ij} (c_{ij} - u_{i})) + c_j y_j)) + \sum_{i \in C} u_i

Como o termo \sum_{i \in C} u_i é constante, podemos resolver o problema sem ele e depois somá-lo ao valor da solução obtida. Além disso, note que cada fábrica contribui de maneira independente à função objetivo e em cada restrição só aparecem variáveis associadas a uma dada fábrica.

Desta forma, podemos decompor essa formulação por cada fábrica j:

\min \sum_{i \in C} (x_{ij} (c_{ij} - u_{i})) + c_j y_j

Sujeito a:

\begin{array}{llcll}   & x_{ij} & \le & y_j & \forall i \in C\\  & x_{i,j}, y_{j} & \in & \{0, 1\} & \forall i \in C  \end{array}

Cada um desses problemas pode ser resolvido por inspeção. Seja c'_{ij} = c_{ij} - u_{i}. Vamos considerar duas possibilidades. Se fizermos y_j = 0, não atenderemos nenhum cliente, levando a uma solução de custo 0. Se y_j = 1, só compensa atender aos clientes com c'_{ij} < 0. Assim, o custo ótimo dessa formulação é:

\min\{0, c_j + \sum_{c'_{ij} < 0} c'_{ij} \}

A outra alternativa consiste em relaxar a desigualdade (3). Nesse caso, depois de alguma álgebra, teremos:

z_2(u) = \min \sum_{i \in C, j \in F} x_{ij} (c_{ij} - u_{ij}) + \sum_{j \in F} y_j (c_j + (\sum_{i \in C} u_{ij}))

Sujeito a:

\begin{array}{llcll}   & \sum_{j \in F} x_{ij} & \ge & 1 & \forall \, i \in C \\  & u_{ij} & \ge & 0 & \forall i \in C, j \in F\\  & x_{i,j}, y_{j} & \in & \{0, 1\} & \forall i \in C, \forall j \in F  \end{array}

Note que como não há restrições misturando x e y, podemos resolver o modelo para cada tipo de variável separadamente. No caso da variável y, como c_j \ge 0 e u \ge 0, não compensa abrir fábrica nenhuma. No caso de x, podemos resolver de maneira independente para cada x_i, por inspeção. Seja c'_{ij} = c_{ij} - u_{ij}. Se c'_{ij} > 0, podemos fazer x_{ij} = 1. Caso contrário x_{ij} = 0, exceto no caso em que c'_{ij} \ge 0 para todo j \in F. Nesse caso, devido à restrição (25), temos que fazer x_{ij^*} = 1, onde j^* = \mbox{argmin}_{j \in F} \{c'_{ij} \}.

Temos duas formulações que podem ser facilmente resolvidas. Entretanto, devemos levar em conta qual possui a formulação mais forte. Em outras palavras, dado z_1^* = \max \{ z_1(u) : u \ge 0 \} e z_2^* = \max \{ z_2(u) : u \ge 0 \}, queremos o limitante dual que mais se aproxima de z. Entretanto, não sei dizer qual das duas relaxações apresentadas é a mais forte.

Conclusão

A relaxação Lagrangeana é uma técnica poderosa para se obter limitantes duais de problemas combinatórios que podem ser modelados como programas lineares inteiros. Esses limitantes podem ser usados na tentativa de melhorar o desempenho de algoritmos branch-and-bound.

Além do mais, para certos problemas, existe a possibilidade de ajustar a solução obtida via relaxação de modo a obter uma solução viável para o problema original, esperando que a qualidade da solução não seja muito pior.

Esse post apresentou a teoria por trás da relaxação lagrangeana. Num próximo post vou apresentar uma heurística que visa encontrar bons multiplicadores lagrangeanos.

Referências

[1] The Lagrangian relaxation method for solving integer programming problems – M.L. Fisher Management Science, 1981.