Algoritmo: Calculando a soma de duas matrizes 3×2

Sendo C=A+B
relação: Cij=Aij+Bij

Tabela

|  10  5  |        | 1   15 |        | 11   20  |
|  7  22  |  +   | 7   2   |  =    | 14   24  |
| -3  14  |       | 3   4   |        |  0   18   |

A resolução deste problema tem um ponto em comum relação ao anterior,já que todos os elementos das matrizes
devem ser acessados

constante N_LIN = 3;
N_COL = 2;
tipo Matriz_3×2: vetor [N_LIN, N_COL] de real;
Soma_Matriz(A, B: Matriz_3×2; ref C: Matriz_3×2): neutro
var i,j:inteiro
inicio
para (i <- 1,i <= N_LIN;i <- i + 1) faça
para (j <- 1,j <= N_LIN;j <- j + 1) faça
C[i,j] <- A[i,j]+B[i,j];
fim

DICA: MATRIZ –> para a turma de LPA

Vetores  bidimensionais  ( MATRIZES )

Entendendo

Primeiro exemplo lógico

constante N_LIN = 2;
N_LIN = 3;

tipo Matriz_2×3: vetor [N_LIN, N_COL] de real;
Lê_Matriz_Versão1(ref M: Matriz_2×3): neutro
início
escreva(“Entre com o elemento – Linha1, Coluna 1: “);
leia(M[1,1];
escreva(“Entre com o elemento – Linha1, Coluna 2: “);
leia(M[1,2];
escreva(“Entre com o elemento – Linha1, Coluna 3: “);
leia(M[1,3];
escreva(“Entre com o elemento – Linha2, Coluna 1: “);
leia(M[2,1];
escreva(“Entre com o elemento – Linha2, Coluna 2: “);
leia(M[2,2];
escreva(“Entre com o elemento – Linha2, Coluna 3: “);
leia(M[2,3];
fim

Bom, neste primeira representação,é de fato inadequada,pois é extremamente trabalhosa.O que de fato iria ter que ser feito basicamente tudo na ‘ unha ‘,isto é,como ficaria para vc manipular uma matriz do tipo 100×100 que seria no caso uma matriz com 10.000 elementos ? É claro que é inviável este tipo de implmentação.

Para resolver o problema teremos de fazer uma manipulação de dois índices simultâneos: um para a linha e outro para a coluna.
Como toda a matriz será lida,teremos que acessar todos os elementos,para isto a estratégia seria varrer todos os elementos de cada  linha por vez.

Uma segunda opção seria criar um laço para tratar o índice das colunas.

Segundo exemplo lógico

constante N_LIN = 2;
N_LIN = 3;

tipo Matriz_2×3: vetor [N_LIN, N_COL] de real;
Lê_Matriz_Versão1(ref M: Matriz_2×3): neutro;
var i : inteiro;
início
para (i <-1; i <= N_COL;i <- i + 1 ) faça
início
escreva(“Entre com o elemento – Linha1, Coluna”,i);
leia(M[1,i];
fim
para (i <-1; i <= N_COL;i <- i + 1 ) faça
início
escreva(“Entre com o elemento – Linha2, Coluna”,i);
leia(M[2,i];
fim
fim

Bom,agora esta implementação ficou bem melhor que a primeira,mais continua apresentando repetição de procedimentos feitos de forma manual.Isto faz com que a abordagem seja inadequada para o caso,imagine uma matriz 100×100.O laço da leitura da coluna seria feito 100 vezes,se tornado algo inviável.

A solução FINAL seria criar um laço para  as linhas.

EXEMPLO

para (i <- 1,i <= N_LIN;i <- i+ 1) faça
início
{ código para tratar a linha }
fim

Então teremos um algoritmo final assim,USANDO 10.OOO ELEMENTOS  =)

constante N_LIN = 100;
N_LIN = 100;

tipo Matriz_100×100: vetor [N_LIN, N_COL] de real;
Lê_Matriz_Versão1(ref M: Matriz_2×3): neutro;
var i,j : inteiro;
início
para (i <-1; i <= N_LIN;i <- i + 1 ) faça
para (j <-1; i <= N_COL;i <- i + 1 ) faça
início
escreva(“Entre com o elemento – Linha”, i,” Coluna”,j);
leia(M[i,j];
fim
fim

Bom,é isso, acredito que os colégas de classe podem agora entender bem o conceito de MATRIZ em usando a LÓGICA DOS ALGORITMOS.

O Visualg (Programa que executa algoritmos)

O Visualg(VisuAlg) é um programa que edita, interpreta e executa algoritmos como um programa normal de computador. Ótimo recurso para quem está iniciando no aprendizado de algoritmos, não só para praticar a sua criação mas também para melhor entender a sua execução através do visualizador de variáveis que funciona como um depurador. O Visualg atualmente se encontra na versão 2.0 e possui recursos como simulação da “tela” do computador, visualização de variáveis, “breakpoints”, ajuda on-line, impressão dos fontes e outras características que auxiliam o aprendizado das técnicas de programação.

Download 

Algoritmo – Classificação por paradigma

Pode-se classificar algoritmos pela metodologia ou paradigma de seu desenvolvimento, tais como:
Divisão e conquista – algoritmos de divisão e conquista reduzem repetidamente o problema em sub-problemas, geralmente de forma recursiva, até que o sub-problema é pequeno o suficiente para ser resolvido. Um exemplo prático é o algoritmo de ordenação merge sort. Uma variante dessa metodologia é o decremento e conquista, que resolve um sub-problema e utilização a solução para resolver um problema maior. Um exemplo prático é o algoritmo para pesquisa binária.
Programação dinâmica – pode-se utilizar a programação dinâmica para evitar o re-cálculo de solução já resolvidas anteriormente.
Algoritmo ganancioso – um algoritmo ganancioso é similar à programação dinâmica, mas difere na medida que as soluções dos sub-problemas não precisam ser conhecidas a cada passo, uma escolha gananciosa pode ser feita a cada momento com o que até então parece ser mais adequado.
Programação linear
Redução – a redução resolve o problema ao transformá-lo em outro problema. É chamado também transformação e conquista.
Busca e enumeração – vários problemas podem ser modelados através de grafos. Um algoritmo de exploração de grafo pode ser usado para caminhar pela estrutura e retornam informações úteis para a resolução do problema. Esta categoria inclui algoritmos de busca e backtracking.
Paradigma heurístico e probabilístico – algoritmos probabilísticos realizam escolhas aleatoriamente. Algoritmos genéticos tentar encontrar a solução através de ciclos de mutações evolucionárias entre gerações de passos, tendendo para a solução exata do problema. Algoritmos heurísticos encontram uma solução aproximada para o problema.

Análise de algoritmos

A análise de algoritmos é um ramo da ciência da computação que estuda as técnicas de projeto de algoritmos e os algoritmos de forma abstrata, sem estarem implementados em uma linguagem de programação em particular ou implementadas de algum outro modo. Ela preocupa-se com os recursos necessários para a execução do algoritmo tais como o tempo de execução e o espaço de armazenamento de dados. Deve-se perceber que para um dado algoritmo pode-se ter diferentes quantidades de recursos alocados de acordo com os parâmetros passados na entrada. Por exemplo, se definirmos que o fatorial de um número natural é igual ao fatorial de seu antecessor multiplicado pelo próprio número, fica claro que a execução de fatorial(10) consome mais tempo que a execução de fatorial(5).

Um meio de exibir um algoritmo afim de analisá-lo é através da implementação por pseudocódigo em português estruturado. O exemplo a seguir é um algoritmo em português estruturado que retorna (valor de saída) a soma de dois valores (também conhecidos como parâmetros ou argumentos, valores de entrada) que são introduzidos na chamada da função:
Algoritmo “SomaDeDoisValores”
VAR
SOMA,A,B: inteiro
inicio
Escreva(“Digite dois numeros”)
Leia(A,B)
SOMA <- A + B
escreva(SOMA)
fim

Algoritmo – Implementação

A maioria dos algoritmos é desenvolvida para ser implementada em um programa de computador. Apesar disso eles também podem ser implementados por outros modos tais como uma rede neural biológica (tal como no cérebro quando efetuamos operações aritméticas) em circuitos elétricos ou até mesmo em dispositivos mecânicos.

Para programas de computador existem uma grande variedade de linguagens de programação, cada uma com características específicas que podem facilitar a implementação de determinados algoritmos ou atender a propósitos mais gerais.

Algoritmo – Formalismo

Um programa de computador é essencialmente um algoritmo que diz ao computador os passos específicos e em que ordem eles devem ser executados, como por exemplo, os passos a serem tomados para calcular as notas que serão impressas nos boletins dos alunos de uma escola. Logo, o algoritmo pode ser considerado uma sequência de operações que podem ser simuladas por uma máquina de Turing completa.

Quando os procedimentos de um algoritmo envolvem o processamento de dados, a informação é lida de uma fonte de entrada, processada e retornada sob novo valor após processamento, o que geralmente é realizado com o auxílio de uma ou mais estruturas de dados.

Para qualquer processo computacional, o algoritmo precisa estar rigorosamente definido, especificando a maneira que ele se comportará em todas as circunstâncias. A corretude do algoritmo pode ser provada matematicamente, bem como a quantidade assintótica de tempo e espaço (complexidade) necessários para a sua execução. Estes aspectos dos algoritmos são alvo da análise de algoritmos.

A maneira mais simples de se pensar um algoritmo é por uma lista de procedimentos bem definida, na qual as instruções são executadas passo a passo a partir do começo da lista, uma idéia que pode ser facilmente visualizada através de um fluxograma. Tal formalização adota as premissas da programação imperativa, que é uma forma mecânica para visualizar e desenvolver um algoritmo. Concepções alternativas para algoritmos variam em programação funcional e programação lógica.

Algoritmo – Etimologia

A palavra algoritmo tem origem no sobrenome, Al-Khwarizmi, do matemático persa do século IX Mohamed ben Musa, cujas obras foram traduzidas no ocidente cristão no século XII, tendo uma delas recebido o nome “Algorithmi de numero indorum”, sobre os algoritmos usando o sistema de numeração decimal (indiano). Outros autores, entretanto, defendem a origem da palavra em Al-goreten (raiz – conceito que se pode aplicar aos cálculos)[1].

Algoritmo

Origem: Wikipédia, a enciclopédia livre.

Um algoritmo é uma sequência não ambígua de instruções que é executada até que determinada condição se verifique. Mais especificamente, em matemática, constitui o conjunto de processos (e símbolos que os representam) para efectuar um cálculo.

O conceito de algoritmo é freqüentemente ilustrado pelo exemplo de uma receita, embora muitos algoritmos sejam mais complexos. Eles podem repetir passos (fazer iterações) ou necessitar de decisões (tais como comparações ou lógica) até que a tarefa seja completada. Um algoritmo corretamente executado não irá resolver um problema se estiver implementado incorretamente ou se não for apropriado ao problema.

Um algoritmo não representa, necessariamente, um programa de computador, e sim os passos necessários para realizar uma tarefa. Sua implementação pode ser feita por um computador, por outro tipo de autômato ou mesmo por um ser humano. Diferentes algoritmos podem realizar a mesma tarefa usando um conjunto diferenciado de instruções em mais ou menos tempo, espaço ou esforço do que outros. Tal diferença pode ser reflexo da complexidade computacional aplicada, que depende de estruturas de dados adequadas ao algoritmo. Por exemplo, um algoritmo para se vestir pode especificar que você vista primeiro as meias e os sapatos antes de vestir a calça enquanto outro algoritmo especifica que você deve primeiro vestir a calça e depois as meias e os sapatos. Fica claro que o primeiro algoritmo é mais difícil de executar que o segundo apesar de ambos levarem ao mesmo resultado.

O conceito de um algoritmo foi formalizado em 1936 pela Máquina de Turing de Alan Turing e pelo cálculo lambda de Alonzo Church, que formaram as primeiras fundações da Ciência da Computação.