sexta-feira, 20 de dezembro de 2013

Quer aprender a programar?

Programar é uma atividade muito comum hoje em dia, seja um #roteador para acessar a Internet sem fio, um #computador, um #smartphone, #tablet, até mesmo as #SmartTVs podem ser programadas facilmente em casa.

O que as pessoas não sabem é que desenvolver software pode render um bom salário. Várias empresas precisam de bons programadores, e o melhor, não importa se você está ou não na universidade, o que elas desejam é o seu talento!

Quer aprender a programar? Comece enviando esse cartão de natal aos seus amigos e incentive eles a aprenderem também.

Não precisa ficar com receio, se você irá programar pela primeira vez, eu fiz um cartão reusável, você vai ver como é fácil programar o seu!
  
#HappyNewCode


How journals like Nature, Cell and Science are damaging science

The incentives offered by top journals distort science, just as big bonuses distort banking

I am a scientist. Mine is a professional world that achieves great things for humanity. But it is disfigured by inappropriate incentives. The prevailing structures of personal reputation and career advancement mean the biggest rewards often follow the flashiest work, not the best. Those of us who follow these incentives are being entirely rational - I have followed them myself - but we do not always best serve our profession's interests, let alone those of humanity and society.

We all know what distorting incentives have done to finance and banking. The incentives my colleagues face are not huge bonuses, but the professional rewards that accompany publication in prestigious journals - chiefly Nature, Cell and Science.

These luxury journals are supposed to be the epitome of quality, publishing only the best research. Because funding and appointment panels often use place of publication as a proxy for quality of science, appearing in these titles often leads to grants and professorships. But the big journals' reputations are only partly warranted. While they publish many outstanding papers, they do not publish only outstanding papers. Neither are they the only publishers of outstanding research.

These journals aggressively curate their brands, in ways more conducive to selling subscriptions than to stimulating the most important research. Like fashion designers who create limited-edition handbags or suits, they know scarcity stokes demand, so they artificially restrict the number of papers they accept. The exclusive brands are then marketed with a gimmick called "impact factor" - a score for each journal, measuring the number of times its papers are cited by subsequent research. Better papers, the theory goes, are cited more often, so better journals boast higher scores. Yet it is a deeply flawed measure, pursuing which has become an end in itself - and is as damaging to science as the bonus culture is to banking.

It is common, and encouraged by many journals, for research to be judged by the impact factor of the journal that publishes it. But as a journal's score is an average, it says little about the quality of any individual piece of research. What is more, citation is sometimes, but not always, linked to quality. A paper can become highly cited because it is good science - or because it is eye-catching, provocative or wrong. Luxury-journal editors know this, so they accept papers that will make waves because they explore sexy subjects or make challenging claims. This influences the science that scientists do. It builds bubbles in fashionable fields where researchers can make the bold claims these journals want, while discouraging other important work, such as replication studies.

In extreme cases, the lure of the luxury journal can encourage the cutting of corners, and contribute to the escalating number of papers that are retracted as flawed or fraudulent. Science alone has recently retracted high-profile papers reporting cloned human embryos, links between littering and violence, and the genetic profiles of centenarians. Perhaps worse, it has not retracted claims that a microbe is able to use arsenic in its DNA instead of phosphorus, despite overwhelming scientific criticism.

There is a better way, through the new breed of open-access journals that are free for anybody to read, and have no expensive subscriptions to promote. Born on the web, they can accept all papers that meet quality standards, with no artificial caps. Many are edited by working scientists, who can assess the worth of papers without regard for citations. As I know from my editorship of eLife, an open access journal funded by the Wellcome Trust, the Howard Hughes Medical Institute and the Max Planck Society, they are publishing world-class science every week.

Funders and universities, too, have a role to play. They must tell the committees that decide on grants and positions not to judge papers by where they are published. It is the quality of the science, not the journal's brand, that matters. Most importantly of all, we scientists need to take action. Like many successful researchers, I have published in the big brands, including the papers that won me the Nobel prize for medicine, which I will be honoured to collect tomorrow.. But no longer. I have now committed my lab to avoiding luxury journals, and I encourage others to do likewise.

Just as Wall Street needs to break the hold of the bonus culture, which drives risk-taking that is rational for individuals but damaging to the financial system, so science must break the tyranny of the luxury journals. The result will be better research that better serves science and society.

Source: http://www.theguardian.com/commentisfree/2013/dec/09/how-journals-nature-science-cell-damage-science




This email is free from viruses and malware because avast! Antivirus protection is active.


Nobel winner declares boycott of top science journals

Randy Schekman says his lab will no longer send papers to Nature, Cell and Science as they distort scientific process

Leading academic journals are distorting the scientific process and represent a "tyranny" that must be broken, according to a Nobel prize winner who has declared a boycott on the publications.

Randy Schekman, a US biologist who won the Nobel prize in physiology or medicine this year and receives his prize in Stockholm on Tuesday, said his lab would no longer send research papers to the top-tier journals, Nature, Cell and Science.

Schekman said pressure to publish in "luxury" journals encouraged researchers to cut corners and pursue trendy fields of science instead of doing more important work. The problem was exacerbated, he said, by editors who were not active scientists but professionals who favoured studies that were likely to make a splash.

The prestige of appearing in the major journals has led the Chinese Academy of Sciences to pay successful authors the equivalent of $30,000 (£18,000). Some researchers made half of their income through such "bribes", Schekman said in an interview.

Writing in the Guardian, Schekman raises serious concerns over the journals' practices and calls on others in the scientific community to take action.

"I have published in the big brands, including papers that won me a Nobel prize. But no longer," he writes. "Just as Wall Street needs to break the hold of bonus culture, so science must break the tyranny of the luxury journals."

Schekman is the editor of eLife, an online journal set up by the Wellcome Trust. Articles submitted to the journal – a competitor to Nature, Cell and Science – are discussed by reviewers who are working scientists and accepted if all agree. The papers are free for anyone to read.

Schekman criticises Nature, Cell and Science for artificially restricting the number of papers they accept, a policy he says stokes demand "like fashion designers who create limited-edition handbags." He also attacks a widespread metric called an "impact factor", used by many top-tier journals in their marketing.

A journal's impact factor is a measure of how often its papers are cited, and is used as a proxy for quality. But Schekman said it was "toxic influence" on science that "introduced a distortion". He writes: "A paper can become highly cited because it is good science - or because it is eye-catching, provocative, or wrong."

Daniel Sirkis, a postdoc in Schekman's lab, said many scientists wasted a lot of time trying to get their work into Cell, Science and Nature. "It's true I could have a harder time getting my foot in the door of certain elite institutions without papers in these journals during my postdoc, but I don't think I'd want to do science at a place that had this as one of their most important criteria for hiring anyway," he told the Guardian.

Sebastian Springer, a biochemist at Jacobs University in Bremen, who worked with Schekman at the University of California, Berkeley, said he agreed there were major problems in scientific publishing, but no better model yet existed. "The system is not meritocratic. You don't necessarily see the best papers published in those journals. The editors are not professional scientists, they are journalists which isn't necessarily the greatest problem, but they emphasise novelty over solid work," he said.

Springer said it was not enough for individual scientists to take a stand. Scientists are hired and awarded grants and fellowships on the basis of which journals they publish in. "The hiring committees all around the world need to acknowledge this issue," he said.

Philip Campbell, editor-in-chief at Nature, said the journal had worked with the scientific community for more than 140 years and the support it had from authors and reviewers was validation that it served their needs.

"We select research for publication in Nature on the basis of scientific significance. That in turn may lead to citation impact and media coverage, but Nature editors aren't driven by those considerations, and couldn't predict them even if they wished to do so," he said.

"The research community tends towards an over-reliance in assessing research by the journal in which it appears, or the impact factor of that journal. In a survey Nature Publishing Group conducted this year of over 20,000 scientists, the three most important factors in choosing a journal to submit to were: the reputation of the journal; the relevance of the journal content to their discipline; and the journal's impact factor. My colleagues and I have expressed concerns about over-reliance on impact factors many times over the years, both in the pages of Nature and elsewhere."

Monica Bradford, executive editor at Science, said: "We have a large circulation and printing additional papers has a real economic cost … Our editorial staff is dedicated to ensuring a thorough and professional peer review upon which they determine which papers to select for inclusion in our journal. There is nothing artificial about the acceptance rate. It reflects the scope and mission of our journal."

Emilie Marcus, editor of Cell, said: "Since its launch nearly 40 years ago, Cell has focused on providing strong editorial vision, best-in-class author service with informed and responsive professional editors, rapid and rigorous peer-review from leading academic researchers, and sophisticated production quality. Cell's raison d'etre is to serve science and scientists and if we fail to offer value for both our authors and readers, the journal will not flourish; for us doing so is a founding principle, not a luxury."

Source:  http://www.theguardian.com/science/2013/dec/09/nobel-winner-boycott-science-journals

 




This email is free from viruses and malware because avast! Antivirus protection is active.


quarta-feira, 27 de novembro de 2013

 

Top 5 Big Challenges on Software Engineering 2013

 

1 - Mapping between requirements and design; and mismatches at the boundaries between business and SE.

2 - Resource estimation.

3 - Product-line engineering.

4 - Development of emerging computational systems (e.g. SaaS, Smart TV).

5 - Scalability and dependability.

 

terça-feira, 29 de outubro de 2013

Cálculo de Sequências de Polinômios

Resumo

O problema "Palácio dos Espelhos" deseja encontrar uma solução algorítmica para calcular as possibilidades de caminhos que um raio de luz pode percorrer de acordo com um número variado de k reflexões em n placas de vidros. O estudo realizou diversas simulações e apresenta uma abordagem que utiliza o cálculo de seqüências de polinômios.

Introdução

O problema "Palácio dos Espelhos" deseja encontrar uma solução a qual se origina em uma situação física. Se colocarmos várias placas de vidro umas sobre as outras, conforme exibição na Figura 1 (que contém 3 placas de vidro), os raios de luz terão múltiplos caminhos, originados pelas reflexões entre as placas. Os raios poderão ter um número variado de reflexões, entre zero e ∞. Na figura 1 são ilustrados alguns desses caminhos.
Figura 1 – Simulação de algumas reflexões usando 3 placas de vidro.

O objetivo deste trabalho é apresentar uma proposta de solução algorítmica para determinar de quantas formas um raio de luz poderá sofrer k reflexões em uma pilha de n placas de vidro. O estudo realizou simulações para reconhecer um padrão e em seguida apresentou os valores para 1, 2 e 3 placas, após generalizou a solução para  combinações de n números de placas e k reflexões. Apresentando o resultado no final deste trabalho para uma simulação feita com 16 placas de vidros e 16 reflexões.

O trabalho apresenta os padrões encontrados, o método de solução proposto e o algoritmo proposto para solução do problema na seção de solução e os resultados encontrados e a conclusão na parte final deste trabalho.

Solução
Reflexões em apenas uma placa terão apenas uma possibilidade, por isso o estudo procurou uma relação de recorrência a partir de duas placas. Após a simulação, foi encontrado o resultado apresentado na Tabela 1.

N Placas
2
2
2
2
2
2
K Reflexões
0
1
2
3
4
5
Possibilidades K
1
2
3
5
8
13
Tabela 1 – Simulação de Reflexões em 2 Placas de Vidro.

Teorema 1 - As possibilidades para k reflexões em duas placas de vidro demonstraram uma cadeia de equações de polinômios, onde o seu crescimento pode ser dado pela seguinte relação de recorrência: Pk = Pk-1 + Pk-2 para todo k maior que 2.

Prova 1 – A possibilidade de 3 reflexões, por exemplo, poderia ser dada pelo seguinte cálculo: se Pk-1 = 3 e PK-2 = 2 então PK = 5, pois 5=3+2, assim sucessivamente para todas as possibilidades de K reflexões, conforme exibição (em negrito) da Tabela 2.

Para todo N = 2 e K menor ou igual a 2, ou ainda um k números de reflexões maior que 2 temos a seguinte relação de recorrência:

CalculeDuasPlacas(k)=<![if !msEquation]><![endif]>

Após encontrar a relação de recorrência, foi desenvolvido o algoritmo para resolver o problema usando duas placas de vidro:

Inteiro CalculeDuasPlacas(int placa, int reflexao)

Se reflexao <= 2 Então
                Retorne  reflexao + 1
Senão 
                Retorne  CalculeDuasPlacas (k-1) + CalculeDuasPlacas (k-2)
Listagem 1 – Algoritmo Desenvolvido para Solução de duas Placas.

O estudo avançou na investigação de uma nova relação de recorrência para 3 placas  e os seus resultados são apresentados na Tabela 2.

N Placas
3
3
3
3
3
3
K Reflexões
0
1
2
3
4
5
Possibilidades K
1
3
6
14
31
70
Tabela 2 – Simulação de Reflexões em 3 Placas de Vidro.

Teorema 2 - As possibilidades para k reflexões em três placas de vidro demonstraram uma nova relação de recorrência, onde o seu crescimento pode ser dado por: Pk = 2 * Pk-1 + Pk-2 – PK-3 para todo k maior que 2.

Prova 2 – Para 3 reflexões, por exemplo, poderia ser feito o seguinte cálculo: se Pk-1 = 6, PK-2 = 3 e PK-1 = 1 então PK = 14, pois 14 = 2*6+3-1, assim sucessivamente para todo cálculo de possibilidades de K, conforme exibição (em negrito) da Tabela 3.

Assim, para todo N = 3 e K reflexões que seja menor ou igual a 2, ou ainda que tenhamos um k maior que 2 existem as seguintes possibilidades:

CalculePlacas(n,k)=<![if !msEquation]><![endif]>
                                                        
Após encontrar a relação de recorrência foi construído o algoritmo para resolver o problema usando 3 placas de vidro:

Inteiro CalculePlacas(int placa, int reflexao)
int k0 = 1 ;            int K1 = n ;            int K2 = 2 * n ;     int possibilidades = 0;

Se (reflexao = 0)
                Retorne 1

Se (reflexao >=1 e reflexao <=2)
                Retorne reflexao * placa
Senão
Para i=3 onde i <= reflexão Faça
                               possibilidades = 2 * k2 + K1 – K0
                               K0 = K1
                               K1 = K2
                               K2 = possibilidades            
                              
                Retorne Numero
Listagem 2 – Algoritmo Desenvolvido para Resolver o Problema com 3 Placas.

Generalização do algoritmo

A partir do padrão encontrado no cálculo das 3 placas de vidro, foi feita uma tentativa de generalização do caso para n placas e k reflexões, porém os valores estavam incorretos de acordo com os casos de teste. Assim, foi necessário realizar uma nova simulação para encontrar um novo padrão de recorrência. Após a simulação, foi percebido que existe uma relação de recorrência diferente, onde uma seqüência de polinômios demonstra uma forma de solução para cada número de placa, conforme exibição da Tabela 3.

Polinômios
Placa
N-1 * K-1
N-2 * K-2
N-2 * K-3


3
N-2 * K-1
N-1 * K-2
N-3 * K-3
N-3 * K-4

4
N-2 * K-1
N-2 * K-2
N-1 * K-3
N-4 * K-4
N-4 * K-5
5
Tabela 3 – Exemplo de Seqüências de polinômios.

Uma nova simulação buscou o número de possibilidades de k reflexões em 4 placas, conforme demonstração apresentada na Tabela 4.

N Placas
4
4
4
4
4
4
K Reflexões
0
1
2
3
4
5
Possibilidades K
1
4
8
27
73
215
                                   Tabela 4 – Simulação de Valores para 4 Placas.

Teorema 3 - A fórmula encontrada para cálculo é uma seqüência de polinômios: (N-2 * Pk-1) + (N-1 * PK-2) – (N-3 * Pk-3) – (N-3 * PK-4). Onde: N-2 = 2; N-1 = 3; K = 3; Pk-1 = 19; Pk-2 = 8; Pk-3 = 4; Pk-4 = 1;.

Prova 3 – Substituindo os valores contidos na Tabela 5, é possível realizar o cálculo com mais facilidade: (2 * 19) + (3 * 8) – (1 * 4) – (1 * 1) = 57.

O caso de generalização buscou uma aproximação com cálculos de seqüências de polinômios, onde a partir de uma configuração de n placas e k reflexões, é encontrada uma relação de recorrência em uma seqüência a ser utilizada para calcular as possibilidades. Para facilitar o entendimento, o algoritmo foi divido em 3 partes: (I) geração da seqüências de placas, (II) geração da seqüência de termos e cada operando dos polinômios e (III) algoritmo principal.

A geração das seqüências de placas encontrou uma padronização de crescimento (Tabela 5), onde existia uma diferença para os números de placas pares e ímpares (vermelho), a forma de crescimento dos elementos à direita (amarelo), à esquerda (azul) e o elemento central que sempre se repete (verde).

N-1
N-2
N-2





3
N-2
N-1
N-3
N-3




4
N-2
N-2
N-1
N-4
N-4



5
N-3
N-2
N-2
N-1
N-5
N-5


6
N-3
N-3
N-2
N-2
N-1
N-6
N-6

7
N-4
N-3
N-3
N-2
N-2
N-1
N-7
N-7
8
Tabela 5 - Padrão de Formação Encontrado no Crescimento das Placas de Vidro.

De posse dessa padronização, foi desenvolvido o algoritmo para resolver o padrão de crescimento das placas:

inteiro[] geraSequenciaPlacas(int n){
                int[n] placa;
                int i=-1;
               
                se (n>2){   
                    se ((n>3) e (n%2==0)) {se par em vermelho}{
                                placa[++i] = n/2;
                                
                                se ((n>5) e (count >0)){
                                    incrementaPar++;
                                }
                    }
                    Senão ((n>3) e (n%2!=0)) {se impar em vermelho}{
                               placa[++i] = (n-1)/2;
                               placa[++i] = (n-1)/2;
                    }
                   
                    se(count>0) {parte em azul} {
   
                               enquanto (posicao < count){
                               arrayAux[posicao] = incrementaPar;
                               posicao++;
                               }
                              
                               count=0;
                              
                               j= posicao-1
                              
                               enquanto j>=0 decremente j-1 {
                                  se arrayAux[j] <> 0 {
                                               placa[++i]=arrayAux[j];
                                   }
                               }             
                    }
                   
                    placa[++i] = n-(n-1) {parte em verde};
                    placa[++i] = n-1 {parte em amarelo};
                    placa[++i] = n-1 {parte em amarelo};
                   
                    para j=0 se j<n incremente j+1 faça{
                               se (placa[j]==0){
                                   count++;
                               }
                    }
                   
                    se (count>0){
                               retorne geraSequenciaPlacas(n);
                    }
                }
                retorne placa;
    }
Listagem 3 - Algoritmo Desenvolvido para Geração das Seqüências de Placas.

A próxima geração de seqüência é apresentada na Tabela 6, onde é demonstrado o padrão de crescimento para os valores das possibilidades de k reflexões de placas de vidro. Uma explicação sobre como serão feitos os cálculos usando essa padronização será demonstrada adiante.

+K-1
+K-2
-K-3





3
+K-1
+K-2
-K-3
-K-4




4
+K-1
+K-2
-K-3
-K-4
+K-5



5
+K-1
+K-2
-K-3
-K-4
+K-5
+K-6


6
+K-1
+K-2
-K-3
-K-4
+K-5
+K-6
-K-7

7
+K-1
+K-2
-K-3
-K-4
+K-5
+K-6
-k-7
-k-8
8
Tabela 6 - Padrão de Formação das Possibilidades de k Reflexões por Número de Placas.

Conforme a geração dos termos dos polinômios foi encontrada uma nova seqüência de padronização para adição e subtração dos seus termos (Tabela 7).

+
+
-





3
+
+
-
-




4
+
+
-
-
+



5
+
+
-
-
+
+


6
+
+
-
-
+
+
-

7
+
+
-
-
+
+
-
-
8
Tabela 7 - Padrão de Formação das Operações por Número de Placas.

Com base nessa informação e simulação de casos de testes, foi possível desenvolver um algoritmo para resolver o padrão de crescimento das possibilidades de k reflexões e padrão de formação das operações por número de placas:

inteiro[] geraSequenciaTermos(int n){
            int[n] termos;
            string[n]operandos;
            int incrementaPares=1;
            String sinal="+";
           
            se (n>3){

                para i de 0 até n-1 {

                        termos[i] = n/2+i+1-n/2;

                        se (incrementaPares==3){
                           
                            if (sinal == "+")
                                   sinal="-";
                            else
                                   sinal="+";
                                      
                            incrementaPares=1;
                        }
                        operandos[i] = sinal;
                        incrementaPares++;
                }
            }
            retorne termos;
    }
Listagem 4 – Algoritmo para de termos do polinômio e seu operando.

De posse das informações contidas nas Tabelas 5, 6 e 7, cada linha dessas tabelas serão iteradas conjuntamente, buscando a formação de uma seqüência de polinômios, de acordo com a demonstração apresentada no Teorema 3 e Prova 3.

N-1 *
N-2 *
N-2 *
Tabela 5

K-1
K-2
K-3
Tabela 6


+
-
Tabela 7

N-1*K-1
+ N-2*K-2
-N-2 *k-3
Seqüência
N=3
3-1*6
+3-2*3
-3-2*1
Resultado
K=3
Tabela 8 - Cálculo dos Termos dos Polinômios.

O algoritmo inicia o cálculo para k reflexões com atribuição de valores para todo k < 3 da mesma forma que apresentada na solução anterior para 3 placas de vidro, pois não houve mudança nesse padrão. Quando o valor de k >= 3 é realizado o cálculo de cada termo do polinômio, que depende da quantidade de placas e reflexões. O resultado de cada termo é acumulado e realizado o cálculo repetidamente até findar o cálculo de todos os termos da seqüência. Essa iteração é demonstrada nas Tabelas 8 e 9, onde k possibilidades são calculadas utilizando uma seqüência de polinômios gerada automaticamente pelo algoritmo, dada a configuração inicial de 3 placas e 3 reflexões.


N-1*K-1
+ N-2*K-2
-N-2 *k-3
Seqüência
N=3

3-1*31
+3-2*14
-3-2*6

k=6

S= 62
S =S + 14 = 76
S = S -6 = 70
Resultado

Possibilidades K
1
3
6
14
31
70

Tabela 9 – Simulação do Algoritmo para 3 Placas.


N-2*k-1
+N-1*K-2
-N-3*K-3
-N-3*k-4
N=4

4-2*73
+4-1*27
-4-3*8
-4-3*4
k=6

S= 146
S=S+ 81 = 227
S= S -8 = 219
S=S -4 = 215

Possibilidades K
1
4
8
27
73
215



N-2*k-1
+N-2*K-2
-N-1*K-3
-N-4*k-4
+N-4 *K-5
N=5

5-2*132
+5-2*41
-5-1*10
-5-4*5
+5-4*1
k=3

S= 396
S=S+123= 519
S=S -40 = 479
S=S-5 = 474
S=S-1= 475

Possibilidades K
1
5
10
41
132
475




Após a averiguação dos resultados com base nos casos de testes, foi possível desenvolver o algoritmo final para calcular as possibilidades de n de placas e k reflexões:

Inteiro CalculePlacas(int p, int r)
Int k = 0;
long soma = 0;
int[] placa;
int[] termo;
String[] operando;
long[] possibilidades;

Se (r = 0)
            Retorne 1
Se (r >=1 e r <=2)
            Retorne r * p
Senão
     placa = geraSequenciaPlacas(p);
     termo = geraSequenciaTermos(p);

      possibilidades[k] = 1
      possibilidades[k++] = p
      possibilidades[k++] = 2* p

       Para i=3 to reflexões faça
            Para j=0 até j < termo.lenght – (termo.lenght-k) Faça
               Se (operando[j+1]=="+")
       soma = soma + p-placa[j] * possibilidades[k-termo[j]]
  Senão
                  soma = soma - p-placa[j] * possibilidades[k-termo[j]]
               Fim- Para

            Se (p>i) {
                 possibilidades[k++] = soma;
                    soma = 0;
}
     Fim – Para
Retorne Numero
Listagem 5 – Algoritmo para Calcular as Possibilidades de Placas maiores que 2.

Assim, é exibida a combinação dos algoritmos desenvolvidos neste trabalho para solução de qualquer configuração de n placas e k reflexões:

Inteiro CalculaCombinacoes(int placa, int reflexao)
Se placa = 1 Então
Retorne 1
Se placa = 2 Então
Retorne CalculeDuasPlacas(placa, reflexao)
Se placa > 2 Então
                Retorne CalculePlacas(placa, reflexao)
Listagem 6 – Algoritmo Proposto para Solução do Problema.

Complexidade

De posse da solução algorítmica foi possível realizar o cálculo da sua complexidade, que será apresentado brevemente. A complexidade do algoritmo desenvolvido para calcular duas placas de vidro pode ser dada pela análise de sua recorrência, onde Θ(log n), conforme demonstração exibida na listagem 7.

T(n) = T(k-1) + T(K-2)
T(n) = 2T(K-3)

2 (2T(k-2)+K-4) = 4T(K-2)+K-4
4(2T(K-4)+K-8) = 8T(K-4)+K-8
8(2T(K-6)+K-16) =16T(K-6)+K-16

<![if !msEquation]><![endif]>T(K-<![if !msEquation]><![endif]>)+<![if !msEquation]><![endif]>
T(n) = <![if !msEquation]><![endif]> + T(K-<![if !msEquation]><![endif]>+<![if !msEquation]><![endif]>
T(n) = log n + T(K-log n) + K-log n
T(n) = log n

Θ(g(n)) = {f(n): 0 ≤ 1 ≤ f(n) ≤ log n}
Listagem 7 – Complexidade do Algoritmo para Cálculo de 2 Placas.

A complexidade total do algoritmo para solução do problema proposto é O(<![if !msEquation]><![endif]>) ou quadrática, pois o trecho de maior complexidade é o cálculo de 3 placas ou mais, onde existem duas iterações para o cálculo do termos das seqüências de polinômios. O cálculo realizado nas iterações pode ser dado pelos seguintes somatórios <![if !msEquation]><![endif]>.

Resultados

Os resultados (Tabela 10) foram obtidos com base em diversas configurações até o limite proposto no estudo (16) para que pudesse ser feita uma comparação de resultados com outros trabalhos.

Configuração
Possibilidades
2 placas e 2 reflexões
3.0

3 placas e 3 reflexões
14.0

4 placas e 4 reflexões
73.0

5 placas e 5 reflexões
475.0

6 placas e 6 reflexões
2595.0

7 placas e 7 reflexões
32559.0

8 placas e 8 reflexões
228846.0

9 placas e 9 reflexões
3990398.0

10 placas e 10 reflexões
3.2507383E7

11 placas e 11 reflexões
7.4364286E8

12 placas e 12 reflexões
6.871305104E9

13 placas e 13 reflexões
1.96500637364E11

14 placas e 14 reflexões
2.026070737423E12

15 placas e 15 reflexões
7.0003023618478E13

16 placas e 16 reflexões
7.95674567041916E14

Tabela 10 – Resultados.
Conclusão

O problema proposto buscava determinar de quantas formas um raio de luz poderia sofrer k reflexões em uma pilha de n placas de vidro. O estudo realizou simulações para reconhecer um padrão de recorrência e em seguida apresentou soluções com teoremas e provas para 2 e 3 placas. Após a verificação dos casos de testes, foi descoberto um padrão de crescimento em relação ao aumento das placas de vidro. Assim, generalizando a solução para atender o padrão, tornou-se possível realizar o cálculo de k possibilidades. A aproximação utilizada foi a geração de polinômios, dada uma configuração inicial (placa e reflexões), onde foi gerada automaticamente uma seqüência de solução para a recorrência encontrada de acordo com a quantidade de placas de vidro. Após a construção e execução do algoritmo, os resultados foram apresentados em uma simulação com base em diversas configurações de n placas e k reflexões até o limite de 16 placas e 16 reflexões (Tabela 10).

Este estudo utilizou uma junção de diversas técnicas de análise de algoritmos, como: reconhecimento de padrões, sistemas lineares e programação dinâmica, entretanto, podem existir outras soluções para o mesmo problema originadas de uma forma mais simples a partir da análise das recorrências. Um dos objetivos principais do autor ao evidenciar a aplicação conjunta de tais técnicas, foi aprimorar os estudos das técnicas de análise de algoritmos e se preparar para resolver problemas computacionais com nível de complexidade igual ou ainda maior que o problema proposto neste trabalho.

Inscreva-se

Creative Commons 3.0. Tecnologia do Blogger.

Teste a Velocidade da Internet

Siga-me

Curta