Vamos experimentar algumas somas?

21 de Dezembro de 2008, por Desconhecido - 2222 comentários
Durante a graduação, aprendemos (e bem) a integrar funções reais e, dependendo do curso, complexas (a uma variável, ao menos). E em geral nos baseamos na integral dada pela definição de Riemann. Vamos rapidamente definir esta integral, de forma coloquial e descontraída, para mais adiante chegarmos no que gostaria de discutir.

O intervalo entre dois números reais a e b é denotado por [tex][a,b][/tex]. Se [tex]f[/tex] for uma função real nesse intervalo, então podemos particionar o intervalo [tex][a,b][/tex], sendo os pontos que iniciam e finalizam cada partição os [tex]x_0, x_1, \dots x_n[/tex]. A cada intervalo, indicamos um ponto interior (ao intervalo) intervalo, denotado por [tex]t_i[/tex]. Por exemplo, no intervalo [tex][x_3, x_4][/tex] temos o número [tex]t_3[/tex]. A soma de Riemann então desta função é dada por
[tex]\mathfrak{I} = \sum\limits_{j=0}^{n-1} f \left( t_j \right) \left(x_{j+1} - x_j\right) . [/tex]
Gostaríamos que esse valor, [tex]\mathfrak{I}[/tex], fosse a área sob a curva definida por [tex]f[/tex] no intervalo. O mais fabuloso dessa história toda é que a grandeza [tex]\mathfrak{I}[/tex] de fato converge para essa área quando as diferenças [tex]x_{j+1} - x_j[/tex] tendem a zero para uma grande gama de funções. O número de partições, naturalmente, cresce de forma exorbitante. Quando tomamos  esse processo limite, transformamos a soma de Riemann na intergral de Riemann.

Sabe aquelas pessoas que sempre que ouvem um assunto sobre o qual já leram alguma pegadinha ou detalhezinho, acabam provocando alguma discussão nesse sentido? Pois é, por meio de pessoas assim e livros afins, existe um exemplo interessante que ficou famosíssimo. Suponha que, por algum motivo, desejamos integrar a função
[tex] R_{id}(x) = \left\{\begin{array}{l} 0 \mbox{ se } x \mbox{ for irracional} \\ 1 \mbox{ se complementar} \end{array} \right.[/tex]
É possível? A pergunta mais natural, até mais que esta primeira: a resposta é intuitiva? A mim, não parece nada intuitiva. E é neste contexto [1] que surgiram métodos mais elegantes para o cálculo de integrais. A Teoria da Medida, uma extensa área autosuficiente [2] da matemática que tenta extender a noção de "área" (comprimentos, áreas, volumes, etc), entra como sendo o centro da definição mais utilizada de integração: a integral de Lebesgue-Stieltjes. Mas não se assuste: sinteticamente, apenas o nome ficou mais feio. Como agora temos mais de uma definição (ou técnicas) de integração, cria-se a chamada Teoria de Integração, o que vamos tratar aqui apenas como o estudo destas técnicas.

Mas como toda teoria charmosa, a Teoria da Integração dá nomes interessantes. Freqüentemente, encontramos as integrais de Lebesgue, desacompanhadas de Stieltjes. Isto porque a integral de Lebesgue é a extensão da integral de Riemann usando medidas muito especiais: a medida de Lebesgue [3]. Trata-se do caso mais recorrente e o que vai tomar um pouco de nossa atenção. Para as demais medidas e a maioria dos casos, usamos o nome Stieltjes ou Radon acompanhando o de Lebesgue.

A medida de Lebesgue pode ser compreendida como uma função que atribui a toda região de um espaço Euclidiano um valor real positivo (ou infinito, inclusive). Este valor é o que chamamos de comprimento, área ou volume, se a região tem dimensão 1, 2 ou 3 (respectivamente). O intervalo anterior, [tex][a,b][/tex], teria, na reta real, que medida? Essa é uma pergunta que não deve ser feita: nós é que definimos a medida. Mas pensando na medida usual, aquela em que o resultado teria que coinscidir com o resultado usado por uma régua, poderíamos definir como sendo a diferença [tex]b - a[/tex]. Então, podemos definir a função [tex]\mu[/tex] como [4]
[tex] \mu ([a,b]) = b - a . [/tex]
Faz sentido perguntarmos de conjuntos em que [tex]\mu([a,b]) = 0[/tex]? Para que isto ocorra, [tex]b = a[/tex]. Estes são os conhecidos conjuntos de medida nula. Mesmo se não definirmos [tex]\mu[/tex] dessa forma óbvia, ainda assim poderíamos ter conjuntos de medida nula.

Mas e quanto à integral? Lembra-se da definição da soma de Riemann dada logo acima? Então, podemos reescrevê-la usando uma medida [tex]\mu[/tex] qualquer, definindo com isto a soma de Lebesgue
[tex]\mathfrak{L} = \sum\limits_{j=0}^{n-1} f \left( t_j \right) \mu \left( [ x_j, x_{j+1} ] \right) . [/tex]
A definição dos termos [tex]f(t_j)[/tex] são os valores da função escolhidos de forma esperta (utilizamos funções simples). Ao tomarmos um processo limite parecido com aquele em que fazíamos a as partições terem comprimentos cada vez menores para a soma de Riemann, a soma de Lebesgue transforma-se na integral de Lebesgue. Obviamente, para diferentes medidas, a integral deve mudar. Mas se usarmos aquela medida mais óbvia, aquela usual que definimos logo antes nos baseando na reta real, então a integral de Lebesgue deve coincidir exatamente com a integral de Riemann. A diferença está no seguinte...
Toda função Riemann integrável é Lebesgue integrável, mas nem toda função Lebesgue integrável é Riemann integrável.
Assim, há funções que poderemos integrar utilizando a definição de Riemann e há funções que só poderíamos integrar usando a definição de Lebesgue (ou Stieltjes, Radon, etc). Portanto, se pudermos calcular a integral via Lebesgue, já será o suficiente.

A definição da integral de Lebesgue sugere uma soma, assim como a de Riemann, só que com um peso diferente: o peso é a medida do intervalo. Imagine duas funções quaisquer. Suponha que em todo o domínio estas funções sejam idênticas, a menos de um único conjunto de valores. O que deve ocorrer se esse conjunto de valores tiver medida nula?... Isso mesmo, a integral de ambas deverá ser igual [5]. Unindo estas últimas informações à citação acima, podemos sempre calcular via Lebesgue as integrais apenas tomando cuidado com os conjuntos de medida não nula. Motivo, aliás, pelo qual a integral da função [tex]R_{id}[/tex] é nula.

Aplicação direta.
Eu costumo me sentir muito mal quando falo, falo, falo, e não apresento nenhum exemplo. Vamos tentar integrar uma função, que não aquela que mensionei acima (nula se argumento é irracional, senão 1). Eu gostaria de integrar a função [6]

[tex] \delta (x) = \left\{\begin{array}{l} 0 \mbox{ se } x \neq 0 \\ C \in  \hat{\Re} \mbox{ se } x = 0 \end{array} \right.[/tex]

Não se assuste com o nome: [tex]\hat{\Re}[/tex] é um conjunto conhecido como reais extendidos e serve para adicionarmos à brincadeira o [tex]\infty[/tex] [7]. Portanto, [tex]C[/tex] pode assumir qualquer valor, inclusive infinito. A primeira coisa que podemos ver é que [tex]\delta[/tex] assume valor não nulo (e, portanto, contribui para a integral) apenas no conjunto {0}, que refere-se ao intervalo [0,0]. Como naturalmente gostaríamos de conhecer sua integral via medida de Lebesgue com medida usual, sabemos que [tex] \mu ([a,b]) = b - a[/tex] e [tex] \mu ([0,0]) = 0[/tex]. Portanto, [tex] \delta [/tex] é nula a menos de um conjunto de medida nula. Com base nisso, concluímos que
[tex] \int\limits_{-\infty}^{\infty} \delta (x) dx = 0. [/tex]
Esta é a aplicação mais simples e menos viciada que pude encontrar, além de podermos explorar uma função que freqüentemente encontramos em livros. Notemos, por fim, que [tex]\delta[/tex] é identicamente nula [5].

Notas:

  1. Não tem nada a ver, historicamente, com a função maluca que nos propusemos a integrar.
  2. Palavras do professor Hernandes, trata-se de uma teoria que se basea no estudo de funções muito específicas e necessita apenas de Teoria de Conjuntos, mas que aplica-se a inúmeras áreas (probabilidades, integração, grupos, etc). Para uma idéia da aplicabilidade desta teoria, veja os Axiomas de Kolmogorov, que geram toda a probabilidade (e, naturalmente, formam um conjunto axiomático "isomórfico" às outras maneiras de se "compreender" a teoria da probabilidade.
  3. Se alguém sugerir algum artigo bom para linkar, eu adicionarei aqui!
  4. Sim, [tex]\mu[/tex] é uma função de um conjunto.
  5. Se uma função tem integral nula a menos de um conjunto de medida nula, então chamamos esta função de identicamente nula.
  6. Não, esta não é a Delta de Dirac, e portanto a resposta não precisa necessariamente ser 1.
  7. Talvez assunto para outro post... Se esse funcionar ^^

Post Scriptum:

Gostaria de agradecer a discussões prévias com Brenno G. Barbosa, grande colega com quem me graduei mas que infelizmente mudou-se de instituto. Saudações a ele!

 Atualizações:

  1. Assim como sugerido em comentários, especifiquei alguns detalhes sobre a definição da integral de Lebesgue.


Pode Orientação a Objetos em Computação Numérica?

20 de Dezembro de 2008, por Desconhecido - 77 comentários
Na verdade, o título não é muito adequado (menos que eu com respeito aos tremas), mas gostaria de discutir a possibilidade de utilizarmos orientação a objetos em programas voltados à solução de problemas numéricos.

Eu não gostaria de comparar o desempenho de Java contra o de Fortran para a solução de uma EDP. Provavelmente, aliás, exista alguma forma de integrarmos rotinas de Fortran para realizar os cálculos pesados e utilizar o Java para criar uma GUI. O que eu gostaria de discutir é a possibilidade de utilizarmos a orientação a objetos em programas voltados para cálculos numéricos. Realmente cai o desempenho do programa, se comparados dois algoritmos similares? Se cai, por que isso ocorre? Há decidibilidade sobre as situações críticas? [1]

De fato a Orientação a Objetos (abreviamos como OOP) não foi criada para esse propósito. Mesmo assim teimo em utilizar linguagens que oferecem este recurso. O que me atrai nisso tudo é a organização do código e a facilidade para desenvolver rotinas (reutilizáveis ou não). Em comparação com Fortran, as rotinas e funções têm argumentos gigantes. Muitos dos erros que cometo enquanto escrevo meus programas estão em passagens de parâmetros para subrotinas. Para fazer um teste, implementei a solução da equação de Poisson em Fortran e C++ [2]. A diferença na clareza do código é evidente (constatada por programadores neutros). Além do mais, não há perda nenhuma em velocidade (se há, não pude perceber), mesmo utilizando grades finas e densidades exorbitantemente grandes. Isto se deve a optimizações aplicadas usando o compilador g++ da GNU, naturalmente [3]. Há diversas ferramentas que a OO traz ao trabalho de programar que podem ser aproveitadas nesse ramo. Eu inclusive já cheguei a utilizar alguns gráficos UML para melhor compreender programas que escrevi e que eu precisava compartilhar com colegas de trabalho.

Há, nesse sentido, muita discussão. Veja este texto que encontrei enquanto lia sobre o assunto. Temos uma abordagem diferente ao assunto: a primeira tentativa de "defender" a OOP é dada via "clareza de código". Afinal, se um desenvolvedor não entende o próprio código, como ele poderá trabalhar com as ineficiências escondidas pela falta de clareza? Eu acho um argumento interessante, mas razoavelmente fraco. A programação procedural (entenda-se como a não orientada a objetos) não deixa de ser compreensível, mas menos clara. Mesmo assim, este fator muitas vezes ajuda (e, assim comentado acima, uma das razões por eu escolher OOP). Logo, pergunta parece passar para "quanto você quer de desempenho? O suficiente para perder em clareza o tanto que se perde na troca de uma linguagem OOP por uma procedural?" Continuando a ler o mesmo texto, ele traz alguns exemplos interessantes em que a "clareza faz a diferença".

Além desta discussão, há algumas previsões de melhora para a performance das linguagens OOP. Podemos ver diversos grupos que utilizam OOP para suas pesquisas acadêmicas (principalmente grupos relacionados à computação em sistemas distribuídos). Nesse sentido, encontrei um projeto, chamado Blitz, interessante (visite a home page) sobre o desenvolvimento de programas, para "cálculos científicos", de alta performance usando OOP. "Blitz++ is a C++ class library for scientific computing which provides performance on par with Fortran 77/90." Ainda não tive oportunidade de fazer os devidos testes, mas parece funcionar muito bem. Segundo a documentação, o Blitz utiliza técnicas de templates para obter tal desempenho [4].

Um exemplo pessoal. Uma vez me meti a fazer um dos projetos de minha namorada (aluna de física com ênfase em computação). O projeto visava o entendimento do algoritmo de escalonamento do processador e a implementação de uma simulação de alguns algoritmos de alocação da memória. Foi um projeto que realmente me animou muito e decidi por fazê-lo em Java. Naturalmente, não seria um programa pesado e que demoraria meses para rodar. Logo, foi uma escolha que me rendeu o aprendizado definitivo de Java e algum conhecimento em sistemas operacionais. Isto porque utilizei classes para demarcar componentes diferentes, tais como memória, processador, etc. Assim, usando filas, pude criar ciclos de escalonamento com sintaxes do tipo: "processador recebe processo de identificação x; processador deve rodar o próximo processo da lista; ...". Como as classes (juntamente com seus métodos) permanecem em arquivos separados, a classe Main tornava-se muito clara e simples de ser compreendida. Por fim, fizemos diversas medidas para os diferentes algoritmos de escalonamento (throughput, por exemplo).

Gostaria muito de ver os comentários dos experts no assunto. Tentei não ser técnico acima por esta razão: ficaria muito feliz se os computeiros pudessem se manifestar sobre esse assunto. Gostaria de entender se de fato existe uma limitação atrelada à orientação a objetos e se essa limitação poderá, eventualmente, ser eliminada. Se realmente tivermos alguma discussão, eventualmente posso postar alguns exemplos concretos. [5]

Notas:

  1. Na verdade, a questão é muito bem resolvida, mas muito dificilmente escrita. Tente, por exemplo, definir algoritmos idênticos a menos da OOP. Em geral, acredita-se que se o algoritmo realizar "as mesmas tarefas", então o desempenho do processo que utilizar algoritmo OOP é menor.
  2. Utilizei diferenças finitas e um método alternatico, conhecido como Numerov. Este segundo me fornece precisão de sexta ordem.
  3. Em muitas situações, podemos alcançar o desempenho do Fortran utilizando bem optimizações.
  4. Gostaria muito de ver isso de perto!
  5. Talvez, num post futuro, eu chame à discussão o POG, o novo paradigma. Mas quanto a este, imagino que já estejamos mais acostumados...


Powered by ScribeFire.



Verve!

19 de Dezembro de 2008, por Desconhecido - 0sem comentários ainda

Muito interessante! Exprimente também!



Arquivos MKV em Ubuntu 8.04

19 de Dezembro de 2008, por Desconhecido - 0sem comentários ainda

Eu tive diversos problemas para assistir alguns AVI específicos no Ubuntu (na verdade, Xubuntu) versão 8.04. Mas o que mais me assustou foi a quase que impossibilidade de assistir arquivos MKV, que são arquivos razoavelmente novos.

Tudo começa com o MMC (Matroska Multmedia Container), que é um padrão para formatação de Container open source. Para os que estiverem enfrentando problemas, o tutorial a seguir me ajudou muito. Leia mais.

http://alyssontiberio.wordpress.com/2008/05/30/visualizando-arquivos-avi-rmvb-mkv-e-outros-no-linux-ubuntu/

Este é o endereço de um Blog muito interessante que trata de diversos detalhes técnicos para configuração de Ubuntu. No entanto, sugiro também a verificação do VLC (visite a home page), que inclusie está disponível para Ubuntu.



Detalhe da Instalação do TeXnicCenter

19 de Dezembro de 2008, por Desconhecido - 2525 comentários

O software TeXnicCenter (visite  home page) é um software excelente para a edição de documentos em [tex]\LaTeX[/tex] quando estamos usando o Windows (seja XP, seja Vista). Aliás, de passagem: ele parece ter evoluído um bucado desde a última vez em que o usei efetivamente, meados de 2006.

Pedido da ocalização da pasta com executáveis.Existe um detalhe que vive assombrando colegas meus. Para compilar os arquivos TeX, o TeXnicCenter precisa conhecer a localização da pasta bin do MikTeX (visite a home page do projeto). Esta pasta contém o compilador do sistema [tex]\LaTeX[/tex]. É muito difícil achar quem use uma pasta diferente da padrão, e por isso resolvi deixar escrita esta informação.

Vamos agora desacelerar. Supondo que o TeXnicCenter (e, naturalmente, o MikTeX) já esteja instalado no seu computador, na primeira vez em que executá-lo, o programa pedirá para que você forneça a localização da pasta com os executáveis tex e latex. Se, durante a instalação do MikTeX você não alterou a localização padrão, basta usar a seguinte:

C:\Program Files\MikTeX 2.5\miktex\bin

Se seu Windows estiver em português, basta alterar Program Files por Arquivos de Programas. O TexnicCenter também pedirá o caminho para um visualizador de pdf's. Em geral, as pessoas usam o Acrobat Reader. Exclusivamente para o caso da versão 7, vale

C:\Program Files\adobe 7.0\acrobat\acrobat.exe

Note que neste momento, é necessário fornecer o executável. No passo anterior, fornecemos apenas a pasta (como pedido pelo programa).  Em geral, se esta opção for deixada em branco o próprio TeXnicCenter trata de preenchê-la.

Janela com os perfis de compilação!

Aproveitando o fim deste post, sugiro àqueles que estejam utilizando o TeXnicCenter para procurarem sobre os Build Profiles. São perfis para compilação dos documentos. Eu, pessoalmente, construi um que sempre o utilizo (mas com o Kile) que automaticamente faz as seguintes tarefas: compila para dvi, converte de dvi pra ps e reconvernte de ps pra pdf. Para quem quiser criar seus próprios Build Profiles, basta seguir o caminho

Build -> Define Output Profiles

Por enquanto, é isso. Para qualquer dúvida, comentem ou enviem algum e-mail.

Até!