Month: June 2009

If something can be computed in lambda-calculus, it can be computed. But lambda-calculus is not implementable because it is non-deteministic and computations may not terminate. It is non-deterministic because it doesn’t have a rule for the order in which reductions are applied. Sometimes the same term can have an infinite reduction and a terminating one, depending on the order in which things are done. That’s why we should study other possible calculi to implement. It would be nice to have termination garantees. When a calculus has this property we say that it is strong normalizing (all the derivations terminates). It may also be weak normalizing, meaning that some derivation terminates. The name comes from the fact that a derivation (computation, sequence of reductions) terminates when it reaches a normal form. So, there is the need to define what is a normal form of the calculus. It is important as well to garantee that, if a term has two or more derivations, these should all end up in the same normal form (somewhere during the derivation terms get together again). That is called the confluence property. Therefore, a calculus should also be confluent because we don’t like inconsistencies.

One of the forms of garanteeing normalization could be to define an order in which the reduction rules are applied.

Rewriting systems are systems formed with rules that tells you how things can be rewritten. For example:

s(0) -> 1
s(x + y) -> x + s(y)

So we could say that the lambda-calculus with its beta-reduction is a rewriting system. Actually, I might say that all calculi are rewriting systems. These systems can also define computations depending on the way terms ans rules are defined. They are also worried with termination and confluency.

(Maybe not that organized…)

Quem reclama das calçadas para pedestres em BH é porque nunca veio em Brasília… pelo menos lá as calçadas existem.

Aliás, cidade estranha essa viu… BH também foi planejada mas pelo menos tem cara de cidade. Aqui os prédios são todos distantes, muitos lugares gramados, os canteiros centrais de algumas avenidas têm o tamanho de um quarteirão e quase não tem calçadas!! Sério, algumas “ruas” só tem caminhozinho pra pedestre de um lado. “Ruas” porque do pouco que andei aqui, só vi ruas dentro do campus mesmo… o resto da cidade toda é formada por avenidas de 6 pistas onde os carros andam em altíssima velocidade. E quase não têm sinal também. E se vc quer atravessar é só parar na faixa de pedestres que os carros começam a reduzir lááá de longe pra não ter q parar pra te deixar passar. Aí vc passa  tranquilo confiando que eles não vão acelerar de novo e te atropelar.

Eu sei que contando assim dos gramados e das ruas gigantes e dos carros que param pra vc atravessar a cidade fica até parecendo agradável. Mas na verdade eu não achei não. Fiquei com a impressão de que é tudo meio artificial… feito pra enfeitar e que na verdade é tudo de mentira. Tudo muito impessoal tb, não sei… Não tive uma boa impressão não, e não gostaria de morar aqui. Parece lugar de passagem, que vc vem, olha e vai embora.

Ah! E o campus é igual… mini cidade. E é enorme!!

“If your compiler produces a NaN, it has the unusual property that it is not equal to any value, including itself. For example, if a is NaN, then a == a is false. In fact, if a is NaN, then a will be neither less than, equal to, nor greater than any value including itself. In other words, regardless of the value of b, a < b, a <= b, a > b, a >= b, and a == b will all return false.”

That’s a nice thing to remember =)

Transformar o problema do tangram para um problema de decisão: Dado um conjunto de peças e um contorno, existe alguma configuração dessas peças (sem sobreposição) que forme este contorno?

Esse problema é NP?

Muito similar ao problema de 2D bin packing, mas ele também não é de decisão, e sim de minimização. Como foi provado que o bin packing é NP-hard?

O tangram também pode ser um problema de minimização (otimização) se enunciado da seguinte forma: Dado um contorno e um conjunto de peças, como arranjar essas peças tais que elas fiquem o mais próximo possível do contorno? (será?)

Talvez não seja possível fazer uma redução ao problema de 2D bin packing porque ele é enunciado para peças retangulares de mesmo tamanho. Muito mais específico que o problema do tangram. E se eu transformar as peças to tangram em triângulos, como já foi feito pra provar outras coisas (e.g. a existência de somente 13 formatos convexos)?

Se eu conseguir fazer o contorno com os triângulos, talvez eu tenha uma solução para as peças inteiras. Se não for possível, com certeza não haverá solução:

Solução para as peças inteiras => solução com os triângulos iguais

Só umas ideias….