MAC 499

Parte I - Relatório de Atividades da Iniciação Científica

Introdução e objetivo

A iniciação científica com o Prof. Fábio Machado começou em agosto de 2000. O objetivo inicial era o desenvolvimento de programas de simulação. Com o tempo, o objetivo passou a ser o desenvolvimento de um sistema capaz de simular o modelo dos sapos e estimar a velocidade de crescimento da borda da figura formada pelas partículas ativas em Z1 e Z2.

O modelo dos sapos estudado é um sistema de partículas de tempo discreto no Zd. Neste modelo, cada partícula (um "sapo"), move-se fazendo um passeio aleatório simples (SRW - Simple Random Walk) no Zd. No início na simulação, há uma partícula dormindo em cada sítio do Zd, exceto a partícula da origem, que começa o seu passeio aleatório simples. A partir daí, quando uma partícula ativa saltar sobre outra dormente, esta última acordará e passará a se mover independentemente, também iniciando um passeio aleatório simples. O número de partículas aumenta conforme as partículas ativas acordam as partículas dormentes, tendendo ao infinito. As partículas ativas não interagem entre si e pode haver mais de uma partícula por sítio do Zd.

Motivação

A motivação para estimar a velocidade do crescimento da borda no modelo dos sapos vêm de duas fontes. A primeira delas é uma razão prática: o modelo dos sapos é relacionado com a difusão de informações, de acordo com K Ravishankar. A segunda razão é a dificuldade de calcular matematicamente a forma esperada da figura formada pelas partículas ativas.

Simular este modelo também é difícil - o número de partículas cresce rapidamente e computar corretamente a velocidade de crescimento da borda requer simular o modelo por algum tempo. Ou seja, simulá-lo computacionalmente requer muito poder computacional ou a criação de heurísticas.

Software desenvolvido antes do modelo dos sapos

Durante a iniciação científica, foram desenvolvidos vários programas de simulação. Antes de ser escolhido o modelo dos sapos como foco, foram desenvolvidos os seguintes programas:

O SimCancer, desenvolvido em Java, simula a infecção de uma célula nas células vizinhas. Uma célula central começa infectada. Em cada instante, cada célula infectada tem uma probabilidade p de infectar uma de suas vizinhas e 1-p de morrer e ser substituída por uma célula sadia. O sistema permite observar o espalhamento da infecção para diversos valores de p. Este modelo foi implementado para simuladores de tempo discreto e de tempo contínuo, com o objetivo de perceber a diferença de programação entre os dois.

Outro programa criado foi um programa de Cálculo do Pi através de simulação, também desenvolvido em Java. O programa gera pontos aleatórios distribuídos uniformemente num quadrado que possui um círculo circunscrito e conta os pontos gerados dentro do círculo. A relação entre os pontos internos ao círculo e o número de pontos gerados é estatisticamente igual à relação entre área do círculo e a área do quadrado. Portanto:

Uma das utilidades do programa é testar a qualidade do gerador de números aleatórios sendo utilizado.

Um simulador genérico de autômatos celulares

Para as estimativas do modelo dos sapos foi desenvolvido um software inicialmente batizado de Gx4. O software foi escrito para a plataforma Windows em Visual C++ 6.0 e é orientado a objetos.

A simulação do modelo dos sapos possui as mesmas características de muitas simulações de autômatos celulares. As diferenças entre o comportamento dos diversos autômatos celulares em tempo discreto são as ações que são tomadas a cada passo da simulação, ou seja, quando se passa de t para t + 1.

O Gx4 permite simular autômatos celulares em dimensão 1 (linhas) e dimensão 2 (matrizes). Para tal, basta derivar a classe CSim1D (para simulações em dimensão 1) e CSim2D (para simulações em dimensão 2). Uma vez derivada a classe (que é puramente abstrata) é  necessário programar a função OnStep, que é chamada pela interface gráfica e determina o que acontece a cada passo da simulação. Também é necessário programar a função Initialize, que inicializa a matriz que contém as partículas. Cada partícula possui seu próprio gerador de números aleatórios, tornando cada partícula totalmente independente das outras.

Um exemplo muito conhecido de autômato celular é a simulação da ilha dos Lobos e dos Cordeiros: numa ilha (uma matriz de dimensão 2) existem alguns lobos e alguns cordeiros cordeiros. Os lobos tem alguns "pontos de vida" e a cada passo da simulação perdem um "ponto de vida", morrendo quando os pontos chegam a zero. Na ilha também existem cordeiros, que a cada passo possuem uma probabilidade p de se reproduzirem por "divisão". Ou seja, na casa onde havia um cordeiro, passam a haver dois. Lobos e cordeiros movem-se aleatoriamente pela ilha. Se um lobo encontra entra numa casa onde existem n cordeiros, ele os "come", ganhando n pontos de vida.

Para programar a simulação dos lobos e cordeiros, um programador precisaria programar a função Initialize gerando alguns lobos (por exemplo, números positivos na matriz) e alguns cordeiros (números negativos na matriz). O Gx4 fornece ao programador objetos do tipo "lista". Na função de inicialização, o programador também deve preencher uma lista com os lobos que gerou e outra com os cordeiros.

Depois, bastaria programar a função OnStep, que se encarregaria de percorrer sua lista de lobos, movendo-os e comendo os cordeiros e sua lista movendo-se e reproduzindo-se.

Em geral, a implementação desta última função não é trivial, podendo ser muito difícil em alguns casos. Entretanto, o Gx4 facilita o estudo de um determinado modelo de simulação por cuidar automaticamente de muitas coisas, como:

Aplicando o Gx4 ao modelo dos sapos

Foram criadas classes para a simulação do modelo dos sapos em dimensão 1 e dimensão 2.

A simulação em dimensão 1 é bastante simples e foi desenvolvida apenas para auxiliar no desenvolvimento da simulação de dimensão 2 e verificar o funcionamento do simulador. Não foram executados estudos quantitativos sobre esta simulação. É relativamente rápido executar a simulação por 10.000 passos.

A simulação de dimensão 2 apresentou muitas dificuldades - como o número de sapos cresce muito rapidamente, em pouco tempo o número de sapos é tão grande que cada passo da simulação passa a demorar muito. Num computador típico, foi possível simular 1000 passos em quatro horas. Por tal razão, tornou-se necessário desenvolver e implementar uma heurística que permitisse obter o mesmo resultado com um menor número de partículas.

A heurística proposta foi simular apenas as partículas que contribuem para o aumento da figura. Seja p a probabilidade de uma partícula que não está na borda influir na forma da figura. Para voltar a influir mais rapidamente na  forma da figura, a partícula deverá se mover diretamente para a borda. Como a partícula dá um passo na direção correta com probabilidade 0,25, p é no máximo(0,25)d+1 (onde d é a distância da partícula para a borda mais próxima).

Quando uma partícula tiver uma probabilidade muito baixa de influir na forma da figura, ela deixa de ser simulada, sendo removida da fila de simulação. Dizemos, neste caso, que a probabilidade da partícula interferir na forma da figura está abaixo da probabilidade de corte.

Perspectivas Futuras

Atualmente estão sendo desenvolvidos os testes de correlação que permitirão validar a heurística. Tais testes consistem em simular o modelo sem a utilização da heurística por um tempo t. Em seguida, executa-se a mesma simulação, desta vez utilizando a heurística, pelo mesmo tempo. Compara-se o resultado das duas simulações e verifica-se se eles coincidem nas bordas. O objetivo é achar a maior probabilidade de corte que gere uma figura com a mesma forma da simulação sem heurística. Os testes foram iniciados em 04/12/2001.

O trabalho continuará a ser desenvolvido num mestrado em Simulação Estocástica, que deve ser iniciado em 2002, sob a orientação do Prof. Fábio Machado.

Bibliografia

 

Parte II - Experiência Pessoal

Esta não foi minha única atividade extra-curricular. As minhas outras atividades extra-curriculares estão listadas a seguir:

Iniciação Científica com o Prof. Marco Dimas Gubitoso

Em 1996 fiz iniciação científica com o Prof. Marco Dimas Gubitoso na área de processamento de imagens, tendo desenvolvido o software MAP - Máximo à Posteriori, que aumentava a clareza de imagens que continham ruídos. O software era baseado no algoritmo de Ford-Fulkerson, que fui conhecer em 2000.

Estágios

(1997) Cia. de Papel Melhoramentos - implantação de software de ERP

(1997) Editora Abril, no InfoLab da revista InfoExame - desenvolvimento de software de benchmark e de scripts em PERL

Estação Ciência

Em 1997 fui bolsista na Estação Ciência (http://www.eciencia.usp.br) na área de desenvolvimento de software. Foram desenvolvidos diversos programas, juntamente com o Prof. Nelson Canzian ( http://www.fsc.ufsc.br/~canzian).

Alguns desses programas foram ( http://www.eciencia.usp.br/Software/default.html ):

Além do desenvolvimento de software, dei cursos sobre a utilização do Oficina de Funções em cursos do Ensino Médio. Uma das edições desse curso foi apresentada na 50a Reunião Anual da SBPC, tendo obtido muito sucesso na avaliação dos professores participantes.

Também participei do projeto "Uma viagem por dentro do computador", ajudando a traduzir e criar um curso para professores do ensino médio e fundamental. As duas edições deste trabalho, patrocinado pelo MEC e pela Intel, também foram grandes sucessos na avaliação dos professores participantes.

Finalmente, também construí a infra-estrutura de Internet da Estação Ciência, criando sua primeira home page e instalando seus primeiros servidores de e-mail e FTP.

Carreira profissional

Depois disso, desenvolvi e modelei diversos projetos profissionalmente, trabalhando em parceiros da Microsoft. Alguns casos de sucesso são:

Também prestei consultoria (não tendo participado, portanto, do desenvolvimento do projeto) nos seguintes cases:

Também escrevi mais oito projetos e modelos arquitetônicos de aplicações que não posso citar por ter assinado NDAs ("Non-Disclosure Agreements").

Conclusões sobre a experiência de iniciação científica

A atividade de Iniciação Científica é uma das atividades mais interessantes e úteis que desenvolvi durante meu curso. Não consigo pensar em nada que tenha sido mais útil na minha carreira profissional nem na minha carreira acadêmica. Em geral são estudados problemas de difícil solução, que apresentam desafios mais interessantes do que os que são encontrados nas aulas.

O formato da atividade também é bastante diferente - na iniciação científica a participação do aluno normalmente é ativa, em contraposição à sua posição passiva nas matérias regulares. A iniciação científica significa ainda mais trabalho (e, normalmente, muito mais trabalho) do que o curso regular já pede. Os professores são uma fonte inestimável de ajuda para os mais diversos problemas, tanto puramente acadêmicos, quanto de administração de curso, quanto pessoais.

Durante a graduação, a maior parte das minhas pesquisas extra-curriculares foram também fora da área de computação: as duas iniciações científicas foram na área de probabilidade e estatística e o trabalho científico na Estação Ciência foi na área de Física de Partículas e Astronomia. A possibilidade de interagir com outras faculdades da USP e com outras Universidades do Brasil foram as melhores de todas. Primeiro, aprende-se muito (mas infelizmente a maior parte de tal aprendizado não pode ser aproveitada pelo curso). Além disso, os contatos pessoais e profissionais são úteis pelo resto da vida, pelo menos tanto quanto a minha idade permite julgar.

Algumas experiências obtidas na iniciação científica foram aplicadas na minha carreira profissional, sendo que o maior benefício é enfrentar problemas para os quais a solução não é imediatamente conhecida. Tais problemas precisam da cooperação de muitas pessoas para serem resolvidos. A iniciação científica me ensinou que antes de tentar desenvolver a solução para um problema é bom ver se já existe uma solução pronta, ou pelo menos parte dela. Também me mostrou que contar com a ajuda de outras pessoas é bem melhor do que tentar fazer tudo sozinho, principalmente na indicação de fontes de informação confiáveis e relacionadas com um determinado problema.

Conclusões sobre a experiência do IME

A maior parte dos ex-alunos do IME que encontro no mercado de trabalho é relativamente bem sucedida profissionalmente. Todos que encontrei, entretanto, possuem uma auto-confiança extremamente baixa. Algumas vezes isso se reflete na carreira - alguns deles estavam em cargos bastante inferiores à sua qualidade profissional. Talvez tal efeito sobre a auto-confiança tenha sido resultado do curso, mas isso é pura especulação - também poderia, por exemplo, ser a causa dessas pessoas terem escolhido tal curso.

Curiosamente, a parte útil do curso que é útil na minha carreira profissional é a parte teórica. Quanto mais teórica, mais útil - Álgebra e a parte teórica do Cálculo estão entre as matérias que mais me percebo utilizando. Mesmo matérias mais voltadas à prática, como Sistemas de Bancos de Dados, tem uma utilidade maior na parte teórica, como na Álgebra Relacional ou na Teoria de Transações.

Bem no início da carreira, a parte técnica é muito importante: nesta fase é bom ter consigo as anotações de Perl da aula do Prof. Gubi, lembrar as sintaxes do C e do SQL. Conforme o tempo passa, entretanto, passa a ser mais importante o traquejo com modelos matemáticos: sua capacidade de criar um modelo que solucione um problema e de justificar sua argumentação. Algumas vezes é necessário justificar a argumentação por escrito, especialmente quando se escrevem propostas e modelos, mas freqüentemente é necessário justificar a argumentação verbalmente. Este último tipo de justificativa parece ser treinado pelo IME.

De uma maneira geral, a minha experiência com o IME foi muito positiva. Quase todos os desafios que enfrentei no mercado de trabalho foram substancialmente mais simples do que os enfrentados no curso. É comum um ex-aluno do IME estar seguro tecnicamente quanto a prazos e funcionamento da solução enquanto os seus colegas de trabalho estão desesperados. Também é comum que ex-alunos do IME se destaquem rapidamente no ambiente de trabalho.