Me desafiando...

Oi pessoal, já faz uns meses que não escrevo aqui, mas resolvi voltar. Neste segundo semestre do mestrado estou cursando três disciplinas: Análise de Algoritmos, Sistemas Operacionais e Introdução à Computação Paralela e Distribuída. Acho que por isso está sobrando menos tempo para escrever por aqui. Além disso, tenho gastado parte do meu tempo livre treinando programação com problemas típicos de maratonas de programação. Não que eu tenha interesse em participar destas maratonas, mas gosto de resolver os problemas propostos nelas, sem compromisso, apenas para treinar conceitos que já aprendi.

Há algum tempo já sou cadastrado no UVA e recentemente me cadastrei no SPOJ e no SPOJ_BR, e me animei bastante pois sem ter resolvido tantos problemas já apareci no ranking e aí o ânimo/vício fica como quando jogamos um RPG e ganhamos um nível de experiência. Queremos então evoluir e evoluir a cada vez mais, o que agora vejo como possibilidade nestes desafios. Só que o vício de programar é um vício bom na minha opinião (que sou desta área), diferente dos RPGs e jogos online onde o tempo se esvai e você nem percebe o que aprendeu depois. Ou seja, quem evolui sou eu, e não meu avatar que nem se quer é "real" e posso acabar apagando o mesmo daqui alguns dias/meses/anos (o que confirmaria que joguei meu tempo no lixo).

Desde que comecei a resolver os problemas do SPOJ, sinto que melhorei na concepção de algoritmos e na programação com linguagem C e até um pouquinho com a C++. Utilizei de funções como a qsort da stdlib.h na linguagem C (que antes eu só ouvia falar) e que é uma implementação do algoritmo QuickSort. Para problemas que envolviam números primos, utilizei o Crivo De Eratóstenes, que já tinha visto na graduação mas nunca tinha utilizado em implementações e percebi que sem ele, quando os números são muitos grandes, é Time Limit Exceeded (TLE) com certeza.

No momento estou tentando aumentar o nível de dificuldade dos problemas que estou resolvendo, pois percebo que só assim vou conseguir aprender mais. Os problemas que estou tentando atualmente são basicamente sobre a utilização de grafos, aliás, acabo de resolver este que é relacionado a conexidade em grafos. Resolvi utilizando busca em profundidade.

Gostei de escrever sobre minhas experiências com os desafios de programação, possivelmente minhas próximas postagens serão sobre o mesmo assunto. Para quem se interessa no assunto, existe um livro chamado Programming Challenges, onde os exercícios são problemas do UVA, recomendo também. E nas minhas próximas férias, provavelmente vou gastar alguns dias lendo esse livro.

Programming Challenges

Bom, por hoje é só, espero que tenham gostado.

Abraços

O Brasil pode mais

Oi pessoal, o título ficou meio político, mas hoje li uma notícia que me deixou contente e resolvi deixar anotado aqui no blog.

Normalmente, quando abrimos páginas na web sobre notícias aqui no Brasil sempre tem aquelas mesmas informações sobre futebol, corrupção ou escândalos de pessoas famosas. Muitas pessoas que passam a vida se esforçando e superando diversos obstáculos acabam não sendo tão reconhecidas apesar de merecerem.

O que me deixou contente foi ver que um matemático brasileiro, chamado Jacob Palis Júnior (professor do IMPA - Instituto De Matemática Pura e Aplicada), conquistou um prêmio reconhecido internacionalmente chamado Prêmio Balzan que é concedido anualmente para pesquisa científica desenvolvida em determinadas áreas emergentes. A área de pesquisa deste brasileiro é chamada Sistemas Dinâmicos (para quem quiser pesquisar a respeito =)).

Postei esta notícia porque além de ter ficado contente, algo que eu sempre quis ver é um brasileiro conquistando o Prêmio Turing. O Prêmio Turing tem esse nome como homenagem a Alan Turing, que foi um famoso cientista da computação. Esse prêmio é visto como o "Prêmio Nobel da Computação". Ainda não tive a oportunidade de ver um brasileiro ganhando, mas sei que é possível.

A tabela a seguir mostra de onde são os premiados até então e o número de pessoas premiadas na região (de acordo com a Wikipédia):

País	Laureados
Estados Unidos	38
Reino Unido	5
Israel	3
Canadá	2
Noruega	2
Holanda	1
Suíça	1
Dinamarca	1
Grécia	1
Venezuela	1
China	1

Achei curioso o fato de uma pessoa ter sido premiada na Venezuela.
O nome desse Venezuelano é Manuel Blum, e foi premiado em 1995 por pesquisas em Complexidade Computacional e a aplicação desta para a Criptografia.

Para quem tiver interesse, clique aqui para visitar a página de Manuel Blum que possui inclusive alguns links para artigos e notas de aula do mesmo.

Seguem alguns dos nomes de cientistas da computação que já receberam o prêmio e que são muitas vezes citados em livros. Os nomes dos cientistas aparecem seguidos por alguns de seus feitos:

Ronald L. Rivest, Adi Shamir e Leonard M. Adleman - Se lembra do RSA? Observe os nomes dos autores de "Introduction to Algorithms" também, um deles está nesta lista.

Ivan Sutherland - Alguns algoritmos que resolvem problemas da computação gráfica levam o nome Sutherland.

C. A. R. Hoare - Lembram do Quicksort? E das cláusulas de Hoare?

Donald E. Knuth - Talvez na próxima postagem eu escreva um tutorial bem iniciante (já que é assim que me sinto) sobre LaTeX.

Edsger W. Dijkstra - Algoritmo de Dijkstra para caminhos mínimos em grafos e a utilização de semáforos nos problemas de concorrência.

Richard Hamming - Códigos de Hamming para detecção e correção de erros.

Alan J. Perlis - O primeiro a conquistar um prêmio e que tinha idéias interessantes sobre programação. Uma que eu não me esqueço é a seguinte, "se a sua função recebe dez parâmetros, provavelmente você está esquecendo algum...".

Frances E. Allen - Primeira mulher a conquistar o prêmio Turing.

Ainda existem vários outros de grande importância, mas vou parar por aqui. Por hoje é só.

Referências:

http://g1.globo.com/ciencia-e-saude/noticia/2010/09/matematico-brasileiro-ganha-premio-balzan-de-r-128-milhao.html

http://en.wikipedia.org/wiki/Turing_Award

http://pt.wikipedia.org/wiki/Pr%C3%AAmio_Turing

Recompilando o núcleo (=Kernel) do Ubuntu 9.04

Se forem tentar replicar o que eu fiz, recomendo que criem também máquinas virtuais e não saiam testando tudo no seu próprio SO. Seguem minhas experiências.

Primeira tentativa:
Criei uma instância da Virtual Box com a seguinte configuração:

Nome: Ubuntu
Sistema Operacional: Linux
Versão: Ubuntu
RAM: 640 MB
Armazenamento de Tamanho Fixo com 4.5 GB

Instalei o Ubuntu 9.04 através do CD. (até aqui tudo bem...)

Utilizei 4.5 GB porque estava com pouco espaço em disco e esta limitação gerou um problema
durante a compilação do núcleo. Houve um erro, e quando verifiquei pela manhã, o espaço em disco
da máquina virtual estava zerado. Achei interessante colocar essa experiência aqui.

Segunda tentativa:

Nome: Ubuntu
Sistema Operacional: Linux
Versão: Ubuntu
RAM: 1 GB
Armazenamento de Tamanho Fixo com 8 GB

Utilizei 8 GB porque estava ainda com pouco espaço em disco e esta limitação gerou um outro problema mas
durante a instalação do núcleo. Não houve erros desta vez, mas o espaço do HD foi zerado novamente.
Mas como precisava de mais espaço para gerenciar as versões do núcleo após algumas modificações, ainda achei
8 GB pouco espaço.

Terceira tentativa:

Nome: Ubuntu
Sistema Operacional: Linux
Versão: Ubuntu
RAM: 1 GB
Armazenamento de Tamanho Fixo com 16 GB

Como eu sou um cara que gosta de potências de 2. Para a terceira tentativa coloquei 16 GB do HD para a Virtual Machine.

Instalei o Ubuntu 9.04 através do CD.

Versão do núcleo: 2.6.28-11

Desta vez não houveram problemas.

Compilação

O processo de compilação do núcleo é um pouco demorado. Inicialmente precisaremos baixar alguns pacotes. Segue uma breve descrição de cada um deles e o comando utilizado para baixar os pacotes.

Utilitário para a construção do núcleo Linux.
> apt-get install kernel-package

Bibliotecas e documentação para desenvolvedores ncurses (biblioteca de desenvolvimento de aplicações em linha de comando com um estilo GUI)
> apt-get install libncurses5-dev

Possibilita um ambiente root falso.
> apt-get install fakeroot

Entra no diretório onde será armazenado o código-fonte baixado.
cd /usr/src

Baixa o código fonte do Linux.
apt-get install linux-source

Descompacta o código-fonte baixado.
tar -xjvf linux-source-2.6.28.tar.bz2

Cria um link simbólico para o diretório descompactado e entra no diretório através do link simbólico.
sudo ln -s linux-source-2.6.28 linux
cd linux

Cria uma cópia do arquivo de configuração que contém informações específicas do hardware utilizado reconhecidas durante o boot.
sudo cp /boot/config-2.6.28-11-generic ./.config

O comando seguinte permite abrir uma tela de configuração de recursos específicos do núcleo. Como não conhecemos muito, não faremos nenhuma alteração nesta tela.
make menuconfig

Ao concluir, será salvo um novo arquivo config.

O comando seguinte realiza uma limpeza antes de iniciar a compilação.
make-kpkg clean

O comando seguinte compila o código. É muito importante incluir o parâmetro
--apend-to-version pois ele quem identificará o seu núcleo nas entradas do arquivo de configuração da GRUB.

fakeroot make-kpkg --initrd --revision=nomedasuaversao --append-to-version=-fms-version núcleo_image núcleo_headers

Depois de compilar, basta instalar a versão customizada do núcleo com os
seguintes comandos:

dpkg -i linux-image...NomeDoPacoteGeradoParaImagem.deb
dpkg -i linux-headers...NomeDoPacoteGeradoParaHeaders.deb

Após a instalação, podemos ver o novo núcleo como entrada no arquivo de configuração da grub. Verifique o arquivo /boot/grub/menu.lst.

Reinicie o sistema da máquina virtual. Pressione 'ESC' na tela do GRUB.
Neste momento, deverá ser exibido o núcleo que foi compilado por você. No meu caso, o que aparece de novo é:

Ubuntu 9.04, núcleo 2.6.28.10-fms-version
Ubuntu 9.04, núcleo 2.6.28.10-fms-version (recovery mode)

Achei interessante deixar também o tempo gasto na última compilação:

Hora inicial: 22:12
Hora final: 02:10

Bom, é isso pessoal.
Espero ter sido claro em todas as etapas.
Se eu aprender mais sobre a configuração em si, postarei aqui. =)

Referências:
http://easylinuxcds.com/blog/?p=3244
https://help.ubuntu.com/9.04/installation-guide/i386/núcleo-baking.html

Aprendendo a usar o Blender

E ae pessoal.
Prometi que ia escrever mais nas férias, mas só agora consegui algo legal para postar.
Estou em Muriaé-MG e aqui não tenho muito o que fazer.
Estava aprendendo a modelar com Blender e resolvi modelar algumas coisas que tem na cozinha da casa onde estou.
Vou passar então em duas imagens o que fiz:

Armário da cozinha

Cozinha

Tentei integrar os objetos das duas imagens anteriores, mas estou tendo problemas. Se eu conseguir, depois mostro o resultado final por aqui. Mas para quem gosta de modelar em 3D, é bem interessante utilizar o Blender. Principalmente por ser software livre e por não ser tão complicado quanto parece no início.

Férias

Oi pessoal, estive bastante ausente nos últimos meses, mas não desisti da ideia de ter um blog.

O mestrado estava agitado com muitos trabalhos, listas de exercícios, provas e cansaço da minha parte é claro, e tudo isso impediu que eu escrevesse aqui. Mas agora terei uns 20 dias de folga e pretendo escrever um pouco.

O que ficou de interessante para escrever aqui foi o que implementei para a disciplina de Estrutura de Dados: uma versão do algoritmo de Dijkstra onde consegui usar Heap (Fila de Prioridade), e para a disciplina de Computação Gráfica: uma ferramenta de modelagem 3D voltada para crianças chamada KLearning. O K vem de Kids.

O mais interessante de apresentar aqui acredito que seja o KLearning. Por ter imagens mais concretas. Mas talvez eu inclua o algoritmo de Dijkstra no VejoGrafos e mostre o resultado aqui também.

Então vamos ao KLearning.

O KLearning foi desenvolvido por mim e por mais 3 colegas do mestrado. Utilizamos Java e JOGL que é a combinação que utilizei em algumas das postagens anteriores. Como já disse, é uma ferramenta que pode ser útil para crianças/pré-adolescentes, principalmente no estudo de geometria espacial, formas geométricas e claro, diversão. Acreditamos que é uma ferramenta que incentiva a criatividade das crianças. Bom, agora seguem algumas imagens da ferramenta. As imagens são desde as primeiras etapas do desenvolvimento até a versão atual que ainda não é completa e merece alguns ajustes.

Uma cena com uma chaleira e um cubo sobre a mesa.

Uma bandeira do Brasil modelada com 3 Cubos e uma Esfera

Essa foi nossa tentativa de implementar Geometria Sólido Construtiva. A operação que tentei fazer para essa imagem foi Cilindro1 - Cilindro0, onde Cilindro0 era mais fino que o Cilindro1 e branco. O Cilindro1 é o de cor laranja. Mas como podem ver, existem algumas falhas no resultado.

Uma pequena vizinhança.

Dois jogadores treinando.

Como podem ver, a interface variou bastante durante o desenvolvimento. A última imagem é do modelo que foi utilizado para a apresentação do trabalho. Vou tentar disponibilizar um .jar da aplicação e como utilizá-la.

Bom, por hoje é só.

Abraços

Mais Computação Gráfica

Depois de alguns dias estudando OpenGL/JOGL, resolvi postar mais algumas imagens do que tenho feito. Na primeira, tentei melhorar o copo que exibi na última postagem. Apliquei uma técnica chamada Blending nele, que nada mais é do que uma mistura de cores dos pixels na cena. Assim, consegui obter a transparência.

Para dar mais realismo a essa cena do copo e da chaleira ainda faltam as sombras desses objetos, mas isso ainda estou tendo problemas para implementar, apesar de já ter uma idéia do caminho a seguir. Fica para uma próxima postagem.

A próxima imagem é de um outro programa que fiz e que exibe o Sistema Solar. Tudo começou quando tentei aplicar uma textura a uma esfera, começando pelo planeta Terra. Mas depois animei e quis fazer o Sol, Mercúrio, Vênus, Marte, Júpiter, etc. Para finalizar, coloquei todos dentro de uma outra esfera maior, com a textura de estrelas, galaxias (algo que simbolizasse o universo). Enquanto implementava fiquei realmente intrigado com o tamanho do planeta Terra com relação a Jupiter, Saturno, Urano e Netuno. Não consegui fazer com que a distância entre os planetas fosse algo similar à realidade, mas o tamanho dos planetas eu fiz questão. Se observarem nas primeiras figuras, parece que só têm 4 planetas, quando na verdade, têm 8 alinhados. Se aumentarem a imagem com o zoom, perceberão. (Pois é, somos mesmo pequenos.)

Segue algumas screens que tirei enquanto implementava. Talvez eu disponibilize esse programa em arquivo jar.

Na última imagem centralizei a fonte de luz do OpenGL no mesmo lugar onde estava o sol e aumentei a sua luminosidade. Por isso o sol está parecendo mais claro que nas outras 3 imagens.

Bom, por hoje é só.

Se Computação Gráfica, então Matemática

Fala pessoal!
Resolvi postar em português hoje.
Vou valorizar um pouco mais nosso idioma, pelo menos aqui no blog. =)

Nas últimas semanas não tive tempo para postar nada por causa de duas provas do mestrado. Tive que trancar uma matéria como disse no post anterior, mas isso está permitindo que eu consiga mais tempo para estudar as outras e para lembrar alguns assuntos que sempre preciso, mas que são assuntos mais elementares.

Semana que vem devo começar o projeto de computação gráfica e nesta semana já treinei um pouco a programação em 3D com Java e OpenGL. Não modelei uma guitarra ou um violão como disse que ia tentar, mas hoje modelei um copo e o incluí em uma cena 3D. Achei bastante interessante a modelagem, foi algo bem matemático.

Modelei o copo utilizando senos, cossenos e conversão de graus para radianos (e muita gente diz que matemática não serve para nada, odeio quando escuto isso). Entretanto, a parte de reflexão do copo não ficou tão boa porque o cálculo dos vetores normais em cada face não está totalmente correto, ou então, o problema está no meu modelo de iluminação.

A imagem a seguir é a imagem da cena completa, incluindo o copo (sem o cálculo de vetores normais).




A próxima imagem, é apenas do copo e incluindo o cálculo dos vetores normais nas faces. O copo ficou parecendo de alumínio. Mas durante a execução, a luz não pára de refletir entre as faces, causando um efeito um tanto quanto desagradável. Por isso, deixei na imagem anterior o copo sem o cálculo das normais.


Bom, por hoje é só.
Espero que tenha sido interessante.
E aproveitando, Feliz dia nacional da Matemática!

[]'s

Algorithms, Paradigms and Languages

Hi!
After two weeks, I think I have some interesting to share.
Yesterday and today I am developing an application using the C language.
I've already imagined the solution, designed the algorithm and I thought that I would be prepared for implementing it. But, in the last years I've developed with Java language, and I forgot many things about C. We know there's a different paradigm between them. My mistake was that I tried to do some things like I do using Java, but it doesn't work, it's obvious.
So, my ask is: couldn't we have a layer between the algorithms and the implementation. We have the paradigm. But, I'm thinking in something that could convert the algorithm to any language, based only on the algorithm and on the paradigm.
Do we have something like this? I think this is something to research.

What follows is a small diagram of the idea.


I know for example that with a classes diagram we can obtain source code in Java or C# with some tools. But I'm thinking in something more generic. I'll think more about this.

See you in a next post.

Stormy Saturday

Hey people!
Today I was trying to solve some graph's exercises but I still coudn't convince myself that I'm correct. This is a signal that I'm not, but maybe almost.
So, I decide to write this post and think about where could I be wrong.
Another thing is that I had a crazy idea (with a cousin's help rs), about computer graphics. I'll try to model a guitar in C with OpenGL. And maybe I'll post the result here as an image (depends on the result). It's a small challenge.
I'll take this opportunity to write about my other projects that I've just mentioned in the previous post.

The first: I'm developing a tool, called VejoGrafos (and you can laugh), to help the comprehension about graphs, the development is stopped cause I have little time to spend with it. Follow some images about the tool:


VejoGrafos: this is a functionality that shows vertices with degree equals to 0 in a graph.

The second: The second is about to start. It will be in the computer graphics discipline. The idea that I've mentioned above about OpenGL is a trainning to this second project.

Now it's time to come back to my exercises. In this stormy saturday I coudn't have anything better to do. Why stormy saturday? Cause I like the stormy monday blues song, the only difference it's that today it's not monday.

Well, today it's only this.

Beginning master's degree

Hi again.
This week I started with only one thing in my head. To pass in the Sun Certified Java Programmer 6.0 exam (SCJP 6.0). I studied so much for one year and now I've passed =D. However, in the master's degree that I started this year, this facts doesn't count too much. So, yesterday (one day after I've passed in the SCJP exam), I tried to study a little because in the next week I'll have an exam in introduction to graph theory. But I couldn't because I was still thinking in Java.

Even being an introduction discipline, the exercises lists given before in Graph Theory left me worried. Other disciplines that I'm sdutying are Introduction to Computer Graphics and Data Structures and your Manipulation. These disciplines seems to be easier than Graph Theory, but they still deserve concern.

This weekend will be the easter. I will be studying graphs and eating chocolates. There's a positive side. =D

In the next posts I want to talk about some projects that I'm developing or almost starting.
Sorry if my english is horrible, but I'm trying to get better.

Happy Easter!

The First One

Hi people,
I've made this blog with the intent of train my english.
I'll post here things about my life, my routine and ideas.
So, this is a first post, without anything else than this.