Arquivo mensais:junho 2006

Xico Xavier (cópia de segurança)

ATENÇÃO: Este conteúdo foi publicado há 11 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Venho percebendo que o Atum está fora do ar, então fiz uma busca no cache do Google para copiar um documento que não poderia ser perdido: as parábolas de Xico Xavier, o maior programador da história. Estavam no wiki do Ribamar, um cara que conheci em Campinas em 2004 e que me apresentou três dos meus softwares preferidos: Slackware, Mutt e LaTeX. Nem pedi autorização dele para copiar essa página, mas espero que ele não se importe… :) Não modifiquei absolutamente nada no texto.

Breve Introdução

O Estudo da filosofia Xiquista foi muito explorado pela humaninade até hoje, porque a programação é um ramo relativamente novo no campus do conhecimento humano (embora ela tenha sempre existido). O que se conhece até hoje são as Parábolas, Frases Cérebres, e Canções Xiquistas. As parábolas são passagens marcantes da Vida de Xico Xavier (por favor, não confundir com Chico Xavier), que devem ser absolvidas como lições por todos que não querem ser culpados depois de não saber programar. Cada Frase Cérebre está associada a uma Parábola (você entederá isso na hora em que começar a ler). Já as Canções Xiquistas são profundamente avançadas e não serão aqui estudadas, a princípio. Não existem ainda literaturas sobre o Xiquismo, tamanho mistério é. Somente é possível obter alguma informação por intermédium dessa página, ou se conhecer algum Xiquista (seguidor do Xiquismo) ou se você possuir uma conexão à rede Mentenet.

1ª Parábola

Xico Xavier foi simplesmente o maior programador da história. Ele foi o maior programador da história porque descobriu o Pascal. E o Pascal ‘ a melhor linguagem de programação contemporânea da situação porque foi descoberta por Xico Xavier.

Xico Xavier descobriu o Pascal tentando provar que o winchester era redondo. No início pensara ele haver chegado ao então ultrapassado Windows. Mas ao reconhecer tamanha evolução, logo percebeu: Descobriu uma nova linguagem de programação.

Xico Xavier foi quem realmente descobriu o Pascal, embora muitos digam que os indígenas já estavam lá. No começo não havia nada. Só BEGIN e END. Xico Xavier pegou o manual (escrito por ele mesmo) e começou a construir as funções. Xico Xavier mostrou ao seu professor sua descoberta. Mas o coordenador do curso DENNIS RITCHIE descobriu que Xico descobriu o Pascal. Dennis obrigou Xico Xavier a mostrar como desenvolveu as funções . Xico a princípio não percebeu a má-fé de Dennis. Após tudo explicado, Dennis ordenou que o Pascal fosse deletado em todas as máquinas e produziu o Basic.

Xico Xavier ressuscitou o Pascal ao terceiro dia com um Undelete. Um(a) aluno(a) do curso viu e foi correndo dedar Xico a Dennis. Não deram direito a Xico se explicar e expulsaram-no. E antes de se ir, pensou:

A sociedade é burra, nua, crua e cruel. Mas o homem que não xifra é fiel. E o homem que não se curva aos Estados Unidos é Fidel.

2ª Parábola

Xico Xavier então foi expulso do curso de Processamento de Dados. Dennis Ritchie também saiu da coordenadoria do curso. É que, a linguagem Basic fez tanto sucesso que Dennis enriqueceu e parou de trabalhar.

Para o lugar Dennis a escola chamou Bill Gatuno. Xico Xavier sabia o perigo disto e se inscreveu para o exame de seleção. Ele passou em primeiro, excedente. Ele sabia muito, mas não sabia o que os elaboradores das questões queriam.

As questões eram mais ou menos assim: 11+10 (na base decimal) é igual a: A) 15 na base 16; B) 10101 na base 2; C) 25 na base 8; D) Pó pará; tá tudo errado.

Mas os candidatos não podiam reclamar. A frase no início da prova era legível:

A interpretação das questões é parte integrante da prova. É proibido vendê-la separadamente.

Felizmente os $ortudo$ que ganharam as vagas, conscientes de que Xico estava ficando de fora, se converteram ao Xiquismo e desistiram.

Xico constatou que o curso estava fraco. Os aluno sabiam tudo de cor. Só de cor. As máquinas estavam com baixo rendimento. Xico Xavier decidiu que a primeira coisa a fazer era mudar de Sistema Operacional. Usando o Basic, a única linguagem encontrada no HD, Xico fez um e o chamou de Linux. Bill Gatuno deixou Xico de recuperação paralela em Pirataria de Software e em Pirataria da Computação e em recuperação serial, Piratéricos. A prova foi unificada. Veja ela:

1) Faça o melhor SO possível, comentado, documentado e explicado sucintamente com detalhes. Diga se ele é o melhor possível e justifique sua resposta. Cite e exemplifique !@&encentos sistemas operacionais, relacione e apresente objetivamente as melhorias. Analise e não se esqueça de calcular o tempo de execução dos sistemas. Tempo: 2 minutos.

A prova era prática. Não houve tempo nem de ligar o computador. Xico então foi obrigado a mostrar o Linux.

Bill Gatuno disse que não gostou do software: Como vai ser bom gastando tão pouca memória?De graça? De graça só software pirata.Código fonte aberto? Ninguém quer saber como foi feito. Mas quando Xico apresentou a interface gráfica, o X-Window, Bill Gatuno deu um pulo e gritou:

Tive uma idéia. Vou fazer um SO com interface gráfica. Vai se chamar Windows. Estou tão feliz! Xico, se você pagar o registros dos softwares pirateados desta máquina, você passou! Windows, Windows, Windows, hã, hã, hã! Então Bill fez o Bug, cheio de Windows, digo o Windows, cheio de bugs; que foi um sucesso de vendas. Todos perceberam o que Xico já dizia:

O Programa depende da Interface assim como a célula depende da Interfase

E Xico sabia mais:

Toda Interface é amigável, Basta que o usuário seja seu amigo

3ª Parábola

Xico Xavier, além de ser o maior programador da Matemática, da Física e da Geografia, foi o maior programador da História.

Pode-se assim considerá-lo por ter sido o mestre do grande filósofo do pensamento Maxista – Alienista Val_Max. O programador leitor já deve provavelmente ter alguma vez usado em seus programas uma constante ou uma variável denominada Val_Max, para armazenar um valor máximo. Talvez o programador não saiba, mas está homenageando o grande filósofo alimão Val_Max.

Val_Max foi quem criou a POO, a programação orientada a objetos, inspirado – por ser Xiquista – nos pensamentos de Xico Xavier, o maior programador de todos os tempos. Val_Max considerou que a luta de classes só terminaria quando fossem criados os objetos. As classes sempre existiram, mas antes da POO, o justiceiro máximo, o todo-poderoso, o Compilador, não reconhecia sua existência.

Val_Max observou que a luta entre classes só se extinguiria após o fim da propriedade privada de atributos. Para acabar com a propriedade privada, Val_Max tece uma grande sacada: todo objeto deveria ter um método CONSTRUTOR. Para construir um objeto público, o Construtor utilizaria toda a matéria-prima feita na privada. Com toda a matéria da privada sendo gasta pelo objeto público, os capitalistas, birrentos do jeito que são, deixariam de fezer suas aplicações nesse local. Como as aplicações de um capitalistas são suas necessidades, não podendo então deixar de fezê-las, eles procurariam um outro lugar para fezê-las, talvez o campo. Se passassem a fezê-las no campo, deixariam de ser Capitalistas para serem Interioristas, e estaria acabada a classe Capitalista.

Aí está a grande geniosidade de Val_Max: sem os Capitalistas, ninguém se apropriaria da privada; ninguém teria tanta necessidade de fazer aplicações; ninguém ficaria tanto tempo na fila do banco para aplicar; e acabaria o sobe-e-desce das bolsas nas mãos das mulheres que ficam nervosas quando estão vendo a cor do déficit e esses locais estão apropriados.

No entanto, os capitalistas deram um golpe. Obrigaram o compilador a aceitar a chave “private” na POO, o que transformou o materialismo-dialético em socialismo-utopléxico, que são as mesmas coisas mas são diferentes. Ainda assim, antes de morrer, Val_Max reascenderia para sempre a discussão proferindo, oh, atravessantemente por todas as veias de cada capitalista, a seguinte frase (inspirado nos pensamentos de Xico Xavier, o maior programador da história):

Programadores de todo o mundo: concatenai-vos

Resultado do DNA 2006

ATENÇÃO: Este conteúdo foi publicado há 11 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Saiu ontem o resultado do Desafio Nacional Acadêmico. Minha equipe, 2 Pi ficou em 24º lugar no Brasil e em 2º lugar em Santa Catarina depois de acabarmos o desafio no dia 15 às 20h00 (screenshot do término)

Poderíamos ter ido melhor se a organização não tivesse mudado a data do desafio final (eu estava em Campinas, fazendo a seletiva para IOI e não pude participar do jeito que deveria) e um participante da nossa equipe priorizasse o desafio ao invés do download do Missão Impossível III. De qualquer maneira, valeu!

There and back again…

ATENÇÃO: Este conteúdo foi publicado há 11 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Eu até tentei escrever um artigo por dia na semana passada, durante o curso da seletiva brasileira para a Olimpíada Internacional de Informática, mas não deu tempo… Então aqui vai um resumo feito uma semana depois do final do curso, separado em tópicos, com o título pouco criativo “There and back again…”

Nível mais alto

Comparando a prova da segunda fase da OBI2006 com a prova da OBI do ano passado, já era possível perceber que o nível esse ano subiu. E, como já esperado, o nível do curso e das pessoas também subiu, o que é excelente para o Brasil.

Mais prática, menos teoria

Neste ano não aconteceu a programação “normal” que tivemos nos últimos dois anos: aula teórica (só um professor apresentando slides e nós anotando, sem computadores) durante a manhã e aula prática durante a tarde.

Nos dois períodos nossas aulas foram no laboratório, com computadores, onde resolvemos uma porção de problemas do treinamento para a ACM da Universidade de Valladollid.

Criei uma pasta no meu servidor com todos os problemas que eu consegui resolver (alguns deles ficaram pela metade): http://tiagomadeira.net/pub/uva/.

Problemas sobre mais de um conteúdo

Uma característica interessante dos problemas desse ano (do treinamento e da prova) foi o uso de mais de um tipo de algoritmo para fazer a solução. A combinação mais comum foi geometria + grafos, que caiu inclusive na prova da Seletiva, no problema Labirinto.

A Prova

Primeiro Dia – Quadrado Romano

[Enunciado] 30 minutos tentando pensar em algum tipo de recorrência, 1h implementando uma solução força bruta! No final, pensei que faria uns 50 pontos (perderia um pouco por causa do tempo), mas perdi alguns pontos por resposta errada, ainda não sei por quê!

Solução: romano.c

Pontos: 10/100

Segundo Dia – Euros

[Enunciado] Durante as duas horas da prova fiquei procurando uma recorrência. Descobri que estou muito newbie em programação dinâmica. Não programei uma linha de código…

Pontos: 0/100

Terceiro Dia – Labirinto

[Enunciado] Olhei o enunciado e já saquei o que o problema queria. Eu tenho uma boa noção de grafos (embora precise estudar fluxos) e o curso trabalhou bastante algoritmos geométricos, então sem maiores problemas fiz o algoritmo, testei várias vezes, achei que ia tirar 100. No fim, não sei o que houve, se foi falta de tempo ou resposta errada. Só vi que fiz 40 pontos…

Solução: labirinto.c

Pontos: 40/100

Quarto Dia – Prova Final

[Caderno de Tarefas] Li todos os problemas e achei que poderia ir bem na prova (o primeiro problema eu tinha certeza que não conseguiria, mas o segundo e o terceiro dava pra fazer). Então, fui direto para o segundo problema, acreditando que era o mais fácil. Mas depois de bolar vários algoritmos, ter respostas erradas e tempos muito altos, tive que ficar com uma solução precária, um Floyd Warshall para cada troca de vértices (resultado: [tex]O(n^{5})[/tex]!) Aí depois não deu tempo de fazer o terceiro problema, mesmo eu tendo esboçado sua solução.

Solução do Teletransporte: tele.c

Pontos: 40/300

Conclusão

O legal é que esse curso sempre dá vontade de estudar, além de ensinar bastante… Aqui ficam registrados meus objetivos e metas pro segundo semestre de 2006 e primeiro semestre de 2007.

Objetivos

Metas

  • Comprar e ler Programming Challenges.
  • Estudar programação dinâmica. Conhecer os algoritmos mais comuns.
  • Estudar fluxos em rede e ordenação topológica.
  • Estudar matemática, inclusive recorrências e geometria (que não ajudam só para olimpíada de matemática, mas pras olimpíadas de informática também)

Curso da Seletiva IOI 2006: Primeiro Dia

ATENÇÃO: Este conteúdo foi publicado há 11 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Estou hospedado na casa do meu irmão, em Campinas, desde ontem de manhã (viajei domingo a noite de ônibus). Hoje foi o primeiro dia do curso preparatório para a seletiva da IOI2006, que começou às 9h00 devagarinho.

O dia hoje serviu para “nivelar” os participantes e treinar um pouquinho a resolução de problemas. De manhã, algumas pessoas tiveram uma aula sobre estruturas de dados, grafos e o básico de programação dinâmica e outras (a maioria) resolveram três problemas da Universidade de Valladollid:

412 – Pi

EnunciadoMinha Solução

Não é um problema muito complexo, mas eu usava um algoritmo muito demorado para determinar se dois números tinham ou não um fator comum, que não passava por tempo limite excedido. Então, o Fábio Dias Moreira nos passou uma propriedade bem interessante de MDC (Máximo Divisor Comum):

mdc(x, y) = mdc(x%y, y)

(onde o % é o resto da divisão, no C)

Aí dá pra fazer uma função recursiva mdc bem rápida, que eu apliquei na minha solução.

441 – Lotto

EnunciadoMinha Solução

Esse problema nem tem muito o que comentar. Implementação de dois minutos… hehehe… Eu podia ter feito uma função recursiva pra ficar um pouco mais “decente” (e poder mudar de 6 para outro número no futuro), mas não tinha necessidade, então ficou assim mesmo (e passou de primeira no site).

543 – Goldbach’s Conjecture

EnunciadoMinha Solução

O objetivo é provar a Conjectura de Goldbach para todos os pares menores que 1000000. Meu programa ainda não roda dentro do tempo, mas depois vou continuar a adapta-lo. Eu posso, por exemplo, ir fazendo a média entre o maior possível e o menor possível (aquele “algoritmo” que usamos quando alguém fala: “Pensei num número de 1 a 100. Tente advinhar…”) ao invés desses loops, o que já vai tornar o programa mais rápido (não sei se o suficiente).

Nesse problema, o Fábio me lembrou do Crivo de Eratóstenes. Bem interessante, nunca tinha implementado. :)


Provavelmente pela primeira vez, o almoço dos participantes do curso não foi no “bandeijão”, mas sim num restaurante chique perto do IC. Achei bem legal… Além de andar menos, o ambiente é melhor e a comida também.

Durante a tarde, o Fábio nos passou o algoritmo de Longest Common Subsequence (esse eu já sabia… hehehe) e depois o algoritmo que resolve o problema Subseqüências que caiu na prova da segunda fase (esse um pouquinho mais complicado!). Esse segundo eu pretendo implementar e depois até fazer um artigo sobre…

Depois, o Fábio nos deu algumas dicas, principalmente sobre os cálculos problemáticos que o computador faz com pontos flutuantes (algo bem interessante, que eu não entendia porque acontecia). Por exemplo, quando criamos um double x=0.1 o seu valor não é 0.1, mas sim o 1/1010 (em binário) que dá uma dízima periódica! E isso não é muito agradável, pode gerar até loops infinitos… Então, ele sugeriu que criássemos uma função para comparar dois números reais, com um código como esse:

/*
USO: Substituir...
x == y <==> cmp(x, y) == 0
x != y <==> cmp(x, y) != 0
x < y <==> cmp(x, y) < 0
x ### y <==> cmp(x, y) ### y
 
O "###" é "qualquer-coisa". Hehehe...
*/
 
#include <math.h>
 
const double EPS = 1.0e-10
 
int cmp(double x, double y) {
	if (fabs(x-y)<EPS) {
		return 0;
	} else if (x>y) {
		return 1;
	} else {
		return -1;
	}
}

Foi um bom ponto de partida legal, começamos de leve. Ainda não sei sobre o quê será a aula de amanhã…

Seletiva IOI

Neste ano vão haver quatro provas para selecionar os quatro participantes que irão representar o Brasil na Olimpíada Internacional de Informática em agosto, no México. As três primeiras, identificadas como “testes” no calendário da seletiva, terão apenas um problema e durarão duas horas cada uma. A última será no domingo, às 7h45min, terá três questões e durará cinco horas (pô, vou perder o comecinho do jogo de Brasil contra Austrália!). Achei legal esse método, mas como o César Kawakami disse: dessa maneira, não treinamos a estratégia, que é algo importante para a prova da IOI.


Por enquanto é só. Se der tempo, pretendo colocar um post por dia sobre o curso até o final dessa semana. :)

DNA2006: Desafio legal, mas mal planejado…

ATENÇÃO: Este conteúdo foi publicado há 11 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Você, que é aluno do ensino médio, não pode ficar de fora do maior evento virtual já organizado no Brasil.

Serão milhares de escolas inscrevendo seus representantes para participar do Desafio Nacional Acadêmico – DNA 2006.

O DNA 2006 será a maior Gincana de Conhecimento já realizada pela internet. Fundamentado na filosofia pedagógica WebQuest, o DNA é uma fantástica oportunidade para os participantes ampliarem seus conhecimentos, ao mesmo tempo em que desenvolvem a criatividade, a noção de liderança, o trabalho em equipe e a tomada de decisão. Para mais informações leia o Manual do Participante.

Somado a isso, os participantes poderão fazer novas amizades e conhecer alunos do Brasil inteiro. O DNA será um encontro marcado para um público estimado em milhares de jovens.

Pô… A idéia dos caras foi ótima. As perguntas foram super criativas e as equipes pesquisaram um monte, trocaram um monte de informações… O DNA apareceu em vários fóruns de discussão, comunidades do Orkut; nos mais diversos meios de comunicação na internet. Minha equipe se divertiu bastante, pesquisando exaustivamente durante cinco dias e duas noites viradas.

Entre vários desafios difíceis (de coisas que não se achava na internet ou que eram muito difíceis de serem encontradas – como por exemplo o nome da mãe de um marinheiro brasileiro pouco conhecido, que só aparece num PDF em francês pesquisando no Google), uns foram mais divertidos por causa do que tivemos que fazer para conseguir a resposta.

Como exemplo, vou citar um desafio que era traduzir um arquivo de áudio (MP3) com quatro palavras em russo. Primeiro tinha o trabalho de identificar a linguagem… Mas vinha uma imagem junto que era de um astronauta russo, então fomos direto pro caminho certo. Aí depois de ligar para a embaixada russa (e descobrir que ninguém lá fala português) e pra mais um monte de gente, adicionar 40 contatos russos no ICQ (usando as White Pages) e perguntar para vários russos que estavam ausentes ou não queriam ajudar (teve um que ficou me criticando porque eu estava falando inglês ao invés da minha língua materna – reflexos da Guerra Fria?), encontramos UM que falava inglês (bem mal, mas pelo menos falava). Aí depois de eu explicar 100 vezes pra ele o que tinha que fazer e ele me xingar de beach (dá pra ver que o cara não fala inglês, né?) e eu quase desistir dele, vieram as quatro palavras desse MP3: peixe água açúcar cozinha. Aleluia!

Trecho da conversa cômica com o russo que nos ajudou no DNA

[…]
Russo: i fuck your Grandpa and she Scream ” YES !!! BABY !
Eu: cool… now, listen to the mp3 file…
Russo: i am Terminator
Eu: ok, me too
Russo: COOL
Eu: ok. now, please listen to the file.
Russo: i am Usama BenLaden
Eu: ok, cool. you can explode my house after you say me what the words mean
Russo: i sit not on the full internet (não entendi o que isso significa, mas acho que ele não conseguia baixar)
Eu: how can i send you? can you receive it by e-mail?
Russo: BEACH
Eu: are you in a beach? nice… what’s your e-mail address?

Agora a parte chata…

Já começava a desconfiar do evento quando percebi que o site deles era hospedado num servidor Microsoft/IIS, programado em ASP e só funcionava no Internet Explorer (hehehe, nenhum defensor dessa combinação mortífera precisa se sentir ofendido)… Pior ainda foi quando minha equipe começou o desafio e, além do congestionamento, nos deparamos com vários erros de programação, server e client-side.

A decepção final foi hoje, quando foi divulgado no site oficial que o final do evento será prorrogado. Pô, minha equipe pulou três questões por causa do tempo! Além disso, o “desafio final” (o último desafio, que promete ser muito difícil e vale mais pontos) vai ser nessa quinta-feira e eu vou estar viajando. Infelizmente, tornou-se impossível vencer.

O desafio foi muito legal e ano que vem sem dúvidas participarei de novo, mas a organização e o planejamento do evento foram péssimas; houve incompetência principalmente por parte dos programadores. Bom… Espero que ano que vem seja melhor… Aproveito pra agradecer para os amigos (em especial pro Reinaldo, que conseguiu a resposta de uma questão de biologia, na etapa surpresa, que iríamos demorar muito pra conseguir – se conseguíssemos…) e professores que nos ajudaram. E também um agradecimento especial para o nosso amigo russo. :)

Ah, no fim o russo perguntou pra quê queríamos saber o que as palavras significavam (eu já tinha falado umas três vezes que era um “virtual challenge”), então resolvi inventar um motivo fictício que ele pudesse entender: “O prêmio é uma viagem à Rússia.” Ele disse que vai nos mostrar a sua cidade quando formos lá e que vamos jogar Counter-strike! :D

[editado] Parece que consideraram nosso recurso, estamos com a pontuação máxima. Agora é só pesquisar pro desafio final! [/editado]

[editado de novo] Se for fácil como parece, acho que descobrimos a resposta do desafio final (sem nem ter a pergunta)! Agora é só digitar rápido na quinta-feira… :) [/editado de novo]

Primeira fase das Olimpíadas de Matemática

ATENÇÃO: Este conteúdo foi publicado há 11 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Ocorreu hoje a tarde a prova da primeira fase da Olimpíada Brasileira de Matemática (e da Regional/catarinense também, a primeira fase é igual). A prova tava difícil, ao menos pros padrões daqui… :) Acertei 16 de 25 questões, segundo gabarito extra-oficial, três delas foram chutes! Mas tá bom, creio que isso classifique pra segunda fase sem problemas.