Tiago Madeira

O que é um vetor?

Vetor é uma estrutura de dados que serve para substituir várias variáveis. Para um problema pequeno onde desejo armazenar dois inteiros e tirar o MMC deles eu posso usar duas variáveis: n1 e n2. Mas existem casos em que seria um número muito grande de variáveis (e em alguns deles nem sabemos ao certo, porque faremos uma alocação a partir de um número que o usuário pedir), por isso vetores são extremamente úteis.

No que consiste a ordenação?

Os algoritmos de ordenação tem como objetivo permutar uma seqüência \(n_{1}, n_{2}, n_{3}, \ldots{}\) de forma que \(n_{1} \leq{} n_{2} \leq{} n_{3} \leq{} \ldots{}\). A ordenação não precisa ser exatamente de um vetor, mas vetor é geralmente a estrutura que usamos para guardar uma lista de números para podermos ordená-los.

Por que ordenar?

Citando o Cormen:

• Às vezes, a necessidade de ordenar informações é inerente a uma aplicação. Por exemplo, para preparar os extratos de clientes, os bancos precisam ordenar os cheques pelo número do cheque.
• Os algoritmos freqüentemente usam a ordenação como uma sub-rotina chave. Por exemplo, um programa que apresenta objetos gráficos dispostos em camadas uns sobre os outros talvez tenha de ordenar os objetos de acordo com uma relação “acima”, de forma a poder desenhar esses objetos de baixo para cima.
• Existe uma ampla variedade de algoritmos de ordenação, e eles empregam um rico conjunto de técnicas. De fato, muitas técnicas importantes usadas ao longo do projeto de algoritmos são representadas no corpo de algoritmos de ordenação que foram desenvolvidos ao longo dos anos. Desse modo, a ordenação também é um problema de interesse histórico.

No primeiro artigo desta série, o Hélio comentou: ‘Algoritmos’ é um tema pouco valorizado por muitos programadores iniciantes, que querem logo botar a mão na massa.

É a mais pura verdade. Quando eu tive a minha primeira noção do que são algoritmos (no dia 12 de julho de 2004, no Curso de Programação da Olimpíada Brasileira de Informática na UNICAMP), confesso que fiquei decepcionado. Qual a utilidade de algo tão formal pra algo que já sabemos fazer? Eu já programava em C e achei um saco o professor escrevendo no quadro aqueles pseudocódigos de problemas super simples, perdendo tempo com isso ao invés de programar. Porém, hoje percebo que algoritmos são muito mais legais (e importantes) do que eu pensava. Claro que para somar dois inteiros não há necessidade de escrever um pseudocódigo, mas algoritmos são representações essenciais para problemas mais complexos e grandes aplicações.

Acredito que você que já leu os dois primeiros artigos já deve saber, mas não custa lembrar: algoritmo é a relação entre entrada e saída do programa, é o rascunho do programa, o projeto. E um projeto antes de colocar a mão na massa é indispensável. Enquanto a implementação é a função dos pedreiros, o algoritmo é a função dos engenheiros. Se os engenheiros não existissem, acho que os pedreiros não iam conseguir fazer as casas e os prédios que eles constroem hoje em dia!

Não querendo desmerecer alunos de sistemas de informação, mas a maioria deles não passa de pedreiros.

O algoritmo sempre existe, mesmo que apenas no seu pensamento. A primeira coisa que você pensa quando quer fazer uma aplicação (a não ser que você seja louco) é: o que é a aplicação? O que ela vai fazer? E se você sair implementando uma coisa complexa, você vai se decepcionar depois demorando mais do que o tempo de fazer a implementação só para limpar o código! Por isso, representar algoritmos complexos é essencial.

E mais… Mesmo se você tivesse tempo infinito, memória infinita, etc. e tal (não tivesse necessidade de limpar o código), você vai precisar de um algoritmo pra provar que o seu programa funciona, para se organizar e para estudar a sua lógica. Se você não planejar um algoritmo para o caso acima, qualquer funcionalidade que você queira adicionar no meio, por falta de projeto e organização, vai demorar bem mais tempo. Por isso, algoritmo não é uma perda de tempo antes da programação, mas a programação é que se torna uma perda de tempo quando não teve um algoritmo (ou, um projeto). O livro Algoritmos: Teoria e Prática reforça essa interessante idéia na página 7:

Suponha que os computadores fossem infinitamente rápidos e que a memória do computador fosse livre. Você teria alguma razão para estudar algoritmos? A resposta é sim, se não por outra razão, pelo menos porque você ainda gostaria de demonstrar que o método da sua solução termina, e o faz com a resposta certa.

Outra utilidade do algoritmo é compartilhar idéias de problemas complexos. Todo programador entende um pseudocódigo e por isso convém muitas vezes apresentar sua idéia de um programa em forma de um algoritmo, num pseudocódigo, ao invés de passar um programa implementado em C para uma dúzia de programadores de VBScript (e sem dúvidas é muito melhor do que ter que aprender uma linguagem da Microsoft!!!).

Existe uma série de algoritmos comuns que todo programador deve conhecer (projetos prontos para muitas coisas complicadas que precisamos implementar no dia-a-dia) e isso é o que vamos começar a estudar no próximo artigo. :)

No primeiro artigo desta série, expliquei o que é um algoritmo e até citei exemplos do cotidiano, como acordar ou falar com outra pessoa. Talvez você nem tenha se dado conta, mas usando listas numeradas eu representei os algoritmos ali presentes, inclusive destacando a entrada e a saída de cada situação-problema. Porém, não é sempre assim que representamos algoritmos.

Não existe uma regra padrão para a representação de algoritmos. Cada pessoa escreve de forma diferente, mas o importante é ser legível e convencionado. Por exemplo, o livro Algoritmos: Teoria e Prática* traz nas páginas 14 e 15 convenções do pseudocódigo que utiliza no livro inteiro. Já eu, quando vou passar o mesmo algoritmo, utilizaria outro tipo de código, você pode utilizar outro, e por aí vai. Mas todos têm que ter o mesmo foco: legibilidade e fácil implementação para qualquer linguagem.

* A partir deste artigo, sempre que eu falar “Cormen”, “CLRS”, “Introduction to Algorithms” ou “Algoritmos: Teoria e Prática” estarei me referindo a um livro que é referência essencial nessa área. A versão que tenho (de onde tiro o número das páginas) é a tradução da segunda edição americana publicada pela Elsevier em 2002.

Os pseudocódigos costumam parecer um código em linguagem Pascal traduzido para a sua língua. :) Usam quase sempre estruturas que estamos acostumados a usar na programação, como se, enquanto, para, arrays, etc. Eles existem para que o algoritmo seja de fácil leitura para qualquer programador, que programe em qualquer linguagem “normal”. Veja o pseudocódigo do Insertion Sort, um algoritmo de ordenação de vetores bastante simples:

para j \leftarrow{} 2 até comprimento do vetor, faça
    elemento \leftarrow{} vetor[j]
    i \leftarrow{} j - 1
    enquanto i > 0 e vetor[i] > elemento, faça
        vetor[i + 1] \leftarrow{} vetor[i]
        i \leftarrow{} i - 1
    fim-enquanto
    vetor[i + 1] \leftarrow{} elemento
fim-para

(Não se preocupe em entender o que ele faz, AINDA, pois veremos isso mais adiante)

Se você programa em qualquer linguagem, você não terá dificuldade em traduzir esse pseudocódigo para ela. O pseudocódigo é sempre uma maneira bem simples de escrever o código. Veja por exemplo, o mesmo código em C:

for (j=2; vetor[j]!=NULL; j++) {
    elemento = vetor[j];
    for (i = j-1; i > 0 && vetor[i] > elemento; i--) {
        vetor[i+1] = vetor[i];
    }
    vetor[i+1] = elemento;
}

Você deve ter percebido que ao invés de usar três linhas com uma declaração, um condicional e um incremento, eu juntei todos num só for. Mas por isso o algoritmo é bem simples e sempre parte do princípio de que a sua linguagem é simples. Veja só a implementação do código em Pascal e compare-a com a do pseudocódigo:

for j:=2 to comprimento, do begin
    elemento := vetor[j];
    i := j-1;
    while i>0 && vetor[i] > elemento, do begin
        vetor[i+1] := vetor[i];
        i := i-1;
    end;
    vetor[i] := elemento;
end;

Linha por linha ela é exatamente igual! A única diferença é que o pseudocódigo é traduzido… Geralmente os pseudocódigos são parecidos sempre com essa base e suas implementações não são muito diferentes. E vai ser sempre dessa maneira que eu vou representar os algoritmos (usando pseudocódigos e alguns traduzindo para C para mostrar implementações). No entanto, qualquer dúvida sobre essa representação, fique a vontade para perguntar através dos comentários.

Depois de uma semana em Florianópolis, estou novamente em Itajaí. Voltei anteontem no final da tarde e o motivo de não ter postado nada é que eu tinha que acabar um trabalho, o site da BEMFAM: tableless, padrões web, cross-browser, PHP/MySql, totalmente administrável. Esse foi o segundo serviço que eu fiz para a Meetweb, depois da Coalizão Antituberculose. Esse ano estou deixando de trabalhar fora (no Colégio) para pegar esses sites de fora que me rendem um pouco mais e são bem mais legais de se fazer (principalmente quando trabalho com designers).

Na semana em Floripa, além de ir à práia, li três livros que merecem ser sugeridos: o best-seller O Código da Vinci, de Dan Brown; Fortaleza Digital, também de Dan Brown; e Harry Potter e o Enigma do Príncipe, o sexto livro de J. K. Rowling. O estilo do Dan Brown é muito legal. Além de ser um cara extremamente inteligente, criando enigmas muito interessantes durante o livro, ele consegue prender a atenção do leitor de forma incrível. Gostei bastante… Agora estou querendo comprar o seu outro livro, Anjos e Demônios. Ou se alguém quiser me presentear, ficarei grato. :D

Passei o ano novo em um lugar de Laguna chamado “Mato Alto”, uma região que, segundo meus cálculos, está no mínimo uns 10 anos atrasada no tempo. :) O bom é que num lugar desses, não se tem nada pra fazer e então eu aproveitei pra ficar lendo sem stress o livro Algoritmos: Teoria e Prática e; aliás, fiz alguns testes inúteis, como descobrir o custo dos algoritmos de ordenação se forem executados por pessoas. Os resultados são bem interessantes. Por exemplo, o Insertion Sort é MUUUITO mais rápido que o Merge Sort, já que você põe todas as cartas que já foram empilhadas na sua mão e com a outra simplesmente coloca uma carta no meio do bolo. O Merge Sort já é bem mais difícil porque você precisa fazer pilhinhas na mesa… :)

Nessa semana, vou tentar pegar o PhotoX, mas não muito intensamente, porque estou agora mais tranquilo lendo e estudando de leve.

Ah… Finalmente o desktop de minha casa tem um novo HD. Foi uma troca boa… Um HD corrompido de 20gb por um de 80gb… :D Agora tenho um bom lugar pra backups! Já tá particionado pra Linux e pra Windows.

Vou começar a postar alguns artigos explicativos, pequenos tutoriais, sobre coisas simples para quem está iniciando em algoritmos computacionais, PHP, tableless, Linux, etc. Tenho recebido vários e-mails pedindo sugestões de apostilas e essas coisas de onde começar e acho que seria legal até pra aumentar as visitas do meu site, meu pagerank, e conseqüentemente, o dinheiro do Google Adsense. :D Aliás, você já acessou meu site usando Internet Explorer? Acho que o negócio que eu fiz foi um dos mais legais pra ganhar uns trocados com o Firefox / Google Toolbar.