18 de setembro de 2010

As matrizes

Já vimos o conceito de vetores, anteriormente. Veremos agora o que chamamos de vetores bi-dimensionais, ou ainda arrays bi-dimensionais.

Matriz, de acordo com a wikipedia: "In mathematics, a matrix (plural matrices, or less commonly matrixes) is a rectangular array of numbers". Ou: "Em matemática, a matriz é um vetor retangular de números".

Amplamente utilizado nas ciências matemáticas, esse conceito ajuda a resolver problemas de álgebra linear, resolução de sistemas lineares, análise numérica, etc. E como a Ciência da Computação é muito matemática, as matrizes também são utilizadas. Uma área bem interessante que se aplica - e muito - é a da computação gráfica. Matrizes de projeção, transformação, etc, são a base de todo trabalho gráfico renderizado pelo computador que estamos acostumados a ver.

Uma matriz A é composta por m linhas e n colunas, e é representada matematicamente da seguinte maneira:
A = ( 123)
456

Nesse caso, A é 2 x 3.

Em computação nós dizemos que uma matriz é um vetor de vetores. Hã?
Calma, pequeno padawan. Imagine um vetor v, com 2 posições. Imaginou? Agora, imagine outros dois vetores, k e r, com 3 posições cada, e preenchidos com números inteiros qualquer.
Se v for um vetor de vetores, atribuimos as duas primeiras posições de v para k e r:

k = { 1
     ,2
     ,3 };

  r = { 4
       ,5
       ,6 };

v[0] = k;
v[1] = r;


Agora, podemos dizer que v é um array bi-dimensional. Porque? Porque podemos acessar, por exemplo, o número 5 da seguinte maneira: v[1][1]. Assim, acessamos o número na segunda linha, na segunda coluna.

Entendeu, pequeno padawan? v é uma matriz, um vetor de vetores.

Vamos ilustrar como se faz o algoritmo de soma de duas matrizes:


O algoritmo faz o seguinte:

  • Inicializamos as variáveis i e j, para poder iterar sobre a matriz

  • Inicializamos a matriz a, que é 2 x 3 e a matriz b, de mesmo tamanho.

  • Criamos a matriz c, para poder guardar o valor da soma de a e b.

  • Vem a parte que realiza a soma. Aqui, iteramos com dois laços de repetição, dois for's. O primeiro for faz o loop pelas linhas, enquanto o segundo faz o loop pelas colunas. Ou seja, para cada linha, o for de j itera em todas as colunas. Assim, colocamos a soma dos valores de a[i][j] com b[i][j] em c[i][j].

Por hoje é isso! Em breve, passarei as operações básicas sobre matrizes.

23 de fevereiro de 2010

Recursão - Potência

Olá!

Você lembra das famosas potências? Daquelas do tipo 2³?
Hoje vamos criar duas formas de realizar esse cálculo.
Queremos criar uma função que receba um número inteiro a (base) e outro n (expoente) e retorne o resultado da multiplicação de a por ele mesmo n vezes (ou, de um modo mais fácil, a elevado à n).

Primeiro, vamos pensar numa versão iterativa, utilizando laços de repetição.
Criamos uma variável para guardar o nosso resultado. Assim, para realizar a multiplicação de a por ele mesmo n vezes, podemos realizar com um laço for: E pronto! temos nossa função potencia:

Como já temos nossa versão iterativa, vamos agora pensar na versão recursiva.
Qual seria o caso base da nossa recursão?
Uma linha de raciocínio seria pensar em um a = 2 e n = 3.
2³ = 2 * (2²)
Certo? Pensando assim, podemos continuar:
2³ = 2 * (2²) = 2 * (2 * (2¹)) = 2 * (2 * (2 * (2^0)))
Logo, o nosso caso base é quando o expoente é zero, ou n == 0, que sabemos que o resultado é 1[1]. E nosso passo da recursão é dado por base * potencia(base, expoente - 1).
Colocando assim, temos:
Potencia(a, n) = a * Potencia(a, n - 1).

Pronto! Temos nossa função recursiva!
Obs.: Perceba que a função funciona adotando n >= 0. Não estamos preocupados em tratar exceções como n = -1, por enquanto =)

Eu acho a função recursiva bem mais elegante =P
Mas é isso ai! Apenas mais um exemplo de recursão!

Até a próxima!

[1] Curiosidade: Pra quem não sabe o porque de um número elevado a zero resultar em 1, o processo é esse: x/x = x¹ : x¹ = x1 - 1 = 1. Explicando: Se você tem 2 objetos e quer dividir para 2 pessoas, sabemos que o resultado é 1. Qualquer número dividido por ele mesmo resulta em 1. Logo, por propriedades de potência, quando há divisão de potências de mesma base pode-se manter a base e subtrair os expoentes, resultando em 2^0. =)

18 de fevereiro de 2010

Recursão

Olá!
Quando você começa a estudar a Ciência da Computação, você aprende (ou pelo menos deveria aprender) muita matemática. Uma técnica matemática aplicada à essa ciência é recursão.
De acordo com o verbete Recursion, da Wikipedia:
"Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.[1] The approach can be applied to many types of problems, and is one of the central ideas of computer science."
ou, em Português:
"Recursão na ciência da computação é um método onde a solução de um problema depende de soluções de problemas menores em instâncias do mesmo problema. O método pode ser aplicado em vários tipos de problemas, e é uma das ideias centrais da ciência da computação."

Há também uma frase muito legal para entender a recursão, que diz:
"Para entender a recursão, é preciso primeiro entender a recursão"

Hã? Calma, pequeno padawan. =)
Imagine o seguinte problema: Você está no seu colegial, e o seu professor de matemática que você adora tanto que até deixou você de recuperação pra não sentir saudades, pede uma lista enorme, só com fatoriais. Você, um aluno calmo e consciente, respira fundo e pensa, dentre seus pensamentos matemáticos: "Qual será a relação matemática entre todos esses fatoriais?"
Então, você tem uma luz, daquelas que iluminam quarteirão em dia de apagão, e escreve:

fatorial(n) =
| 1 ,se n = 0
| n * fatorial(n - 1) ,se n > 0

Claro! Se o número que ele pedir for zero, então eu sei que o resultado é 1, por definição. Mas se for maior do que zero, o resultado nada mais é do que ele vezes o fatorial do número anterior à ele! E então você faz no seu rascunho algumas provas reais:

fatorial(1) = 1 * fatorial(0) = 1 * 1 = 1
fatorial(2) = 2 * fatorial(1) = 2 * 1 = 2
fatorial(3) = 3 * fatorial(2) = 3* ( 2*fatorial(1)) = 3* ( 2* ( 1* fatorial(0))) = 3*2*1*1 = 6

Você acaba de entender a recursão!

Passar esse conceito para um algoritmo em C, é fácil. Ficaria dessa forma:
Perceba a estrutura recursiva da função.
Temos o caso base, que encerra a recursão em algum momento, para não entrar em algo infinito:
E então, o passo da recursão, que reduz o problema a uma instância menor, chamando a mesma função
Na grande maioria dos casos (pra não dizer todos), uma solução recursiva pode ser escrita de forma iterativa. Veja o exemplo que eu dei quando falei sobre laços de repetição: A função fatorial, em sua versão iterativa.

Uma função recursiva é, sem dúvida, muito elegante. Hoje, muitas pessoas que estão na área da computação não conseguem utilizar recursão, outras não a entendem, e outras sequer sabem da sua existência. Então, é algo que merece um pouco de estudo e atenção.
E lembre-se: Para fazer um procedimento recursivo, é preciso ter fé! =)

Vou postar mais alguns problemas com resoluções recursivas e, para comparação e estudo, suas soluções iterativas.

Até lá!