lógica de programação

TI: Conceitos ou Tecnologia, eis a questão!

 

 

Quando se fala em conhecimento de TI por muitas vezes nos deparamos com o seguinte dilema: aprender tecnologia/ ferramentas ou conceitos. A melhor resposta no caso seria, os dois! Porém é difícil, e por muitas vezes custoso, ter o domínio dos dois.

Freqüentemente o profissional de TI é cobrado e exigido por ter conhecimento ou certificações em ferramentas especificas.  Isto está, por muitas vezes, ligado ao que a empresa utiliza em seu ambiente operacional.

No entanto, mais do que a ferramenta é preciso também, e talvez com uma maior importância, que o profissional de TI tenha os conceitos bem claros e definidos. Não basta apenas conhecer uma determinada ferramenta que automatiza aquele conceito.

Basicamente, a importância maior  dada para se conhecer o conceito invés da tecnologia ou ferramenta empregada, está em dois fatores:

1 – A ferramenta que hoje sustenta e automatiza o conceito pode não ser a mais indicada em um futuro. Futuro, por muitas vezes, que pode ser muito próximo pela própria velocidade da área de TI.

2 – Conhecendo apenas a ferramenta ou tecnologia aplicada na automatização de um conceito pode fazer com que o profissional fique “cego” em relação ao desempenho da ferramenta. Conhecer o conceito pode levar ao profissional a procurar e pesquisar outras formas de automatizar este.

Eu sempre dei preferência, em termos de programação, em conhecer os conceitos de lógica de programação muito mais do que linguagens especificas. É muito mais fácil construir programas se tendo a lógica de programação com um manual do C, C++, Java ou Cobol do que se saber muito – ou pelo menos pensar que se sabe – de “VB” e ser deficiente em lógica de programação…

Fica a dica!

Anúncios

Grafos – Algoritmo do Caminho Mínimo

Anteriormente vimos que os Grafos são objetos abstratos muito interessantes e constantemente utilizados como forma de resolver problemas através de conceitos de redutibilidade.

Uma aplicação bastante comum para os grafos é a representação de mapas: As ruas são representadas por arestas, as distâncias são custos atribuídos às arestas e os locais (cidades, casas, paises, etc.) são representados pelos vértices.

Achar um caminho entre dois pontos quaisquer neste grafo é trivial: basta testar todas as possibilidades. Entretanto, esta abordagem (conhecida como método de força bruta) traz alguns incovenientes: É bastante demorada e não garante que o caminho mais curto (ou com menor custo) seja encontrado.

O grande desafio para a computação, é encontrar o caminho mais curto num espaço de tempo curto. Este problema é tradicionalmente conhecido como Problema do Caixeiro Viajante e é extremamente importante, sendo exaustivamente explorado pela computação, logística, economia, administração, biologia e várias outras áreas do conhecimento.

Na computação diversas soluções tornaram-se célebres ao longo do tempo, como o Algoritmo de Djkstra (pronuncia-se Déikstra) e o Algoritmo do Caminho Mínimo, este ultimo sendo o foco principal deste texto.

Apesar de simples, é um algoritmo eficiente, que roda em tempo quadrático (isso significa que dada uma quantidade n de vértices, um computador levará n² unidades de processamento para chegar a uma resposta).

Coloco a seguir a representação do algoritmo, uma prova matemática da sua corretude e um exemplo de implementação na linguagem de programação C.

Entrada: v0, G = V(G), A(G) onde v0, a fonte, pertence a V(G), e G é um grafo orientado, com custo real não-negativo associado a cada aresta em A(G) – custo (v,w), o custo associado à aresta (v,w), é 0 se v = w, e é infinito se (v,w) não é uma aresta.

Saída: (Dist), onde Dist(v) é a distância mínima de v0 a cada v em V(G).

1. C <– v0; Dist(v0)  0;
2. para cada v em V(G) – v0 faça {
3. Dist(v) <–  custo(v0), v(); } (* fim para *)
4. enqto C <> V(G) faça {
5. (*abaixo, incrementa-se C de um elemento*)
6. “escolha w em V(G) – C tal que Dist(w) seja mínimo”;
7. Ins(w,C);
8. para cada v em vG – C faça { (* atualiza Dist *)
9. Dist(v) <– min(Dist(v), Dist(w) + custo(w, v));
10. } (* fim-para *)
11. } (* fim-enqto *)
12. resulta saída (Dist)

Corretude do algoritmo
TEOREMA O algoritmo CamMin determina corretamente os valores de Dist(v) para cada vértice v, com tempo O(n2), onde n é o número de vértices no grafo considerado.

DEMONSTRAÇÃO No algorimto acima pode-se verificar que as linhas 1-3 são executáveis em tempo O(n).

Em cada iteração das linhas 4-12, as linhas 6-8 requerem tempo O(n), e as linhas 9-11
também requerem tempo O(n). Como as linhas 4-12 são executadas n – 1 vezes, a complexidade de tempo total destas linhas é O(n2), que é a parcela dominante da complexidade de tempo de todo o algoritmo.

A certificação será provada por indução em C, e consiste de duas partes:
1. Para qualquer v em C, Dist(v) é a distância mínima de v0 a v ;
2. Para qualquer v em vG – C, Dist(v) é a distância mínima de v0 a v através de um caminho que passa só por vértices em C, exceto v ;

Para |C| – 1, o único elemento em C é v0 e é óbvio que (1) e (2) acima são válidos de acordo com as linhas 1-3 do algoritmo CamMin.
Para o passo indutivo, vamos supor que (1) e (2) acima são válidos para |C| = k – 1, isto é, vamos supor que o algoritmo CamMin é correto até antes da k-ésima iteração das linhas 4-12, para 1 < k <= n – 1. Na k-ésima iteração, w é escolhido conforme as linhas 6-8.

Vamos supor, por absurdo, que Dist(w) não é igual à distância mínima de v0 a w. Então deve existir um caminho M de v0 a w de custo menor do que Dist(w). M deve conter um outro vértice, além de w, fora de C, pois se tal vértice não existisse, w contrariaria a hipótese indutiva referente ao item (2) acima. Seja v o primeiro nestas condições. Então, a distância de v0 a v é menor do que Dist(w), pois os custos são não-negativos. Ademais, o segmento do caminho M de v0 até v está inteiramente contido em C (exceto v). Pela hipótese indutiva referente ao item (2) acima, Dist(v) é menor ou igual ao custo deste segmento de M. Conclui-se então que Dist(v) < Dist(w), mas isto contradiz a escolha de w nas linhas 6-8 (v deveria ter sido escolhido no lugar de w). Portanto, tal caminho M não deve existir e Dist(w) é o custo do caminho mínimo de v0 a w, conforme queriamos provar.

Versão em C com tempo O(n²)


Arquivos:
• Main.c: Arquivo que contém as funções para leitura e gravação de arquivos, execução do algoritmo que calcula o caminho mínimo.
Informções Técnicas:
• Computador: Intel Pentium 4
• Compilador C: Code::Blocks, gcc 4.9.9.1
• Sistema Operacional: Microsoft Windows Vista

Como utilizar o programa:

O arquivo compilado sempre busca um arquivo de texto com o nome “grafo.txt” para receber as informações sobre o grafo na forma 00 00 00, sendo que o primeiro bloco define o vértice de origem, o segundo o vértice destino e o terceiro o custo entre os dois vértices. Á partir dai a execução ocorre sem necessidade de intervenção do usuário.
O resultado final (menor distância entre v0 e os demais vértices do grafo) é impresso na tela.

O código:

/**********************************************************************
* CALCULO DA DISTANCIA MINIMA EM UM GRAFO *
* *
* MAIN.C *
* *
**********************************************************************/

/* Inclusão de Bibliotecas */
#include
#include
#include
#include

/* Valor padrão para definir vértices não adjacentes */
#define INFINITO_POSITIVO 1000

/* FUNÇÃO PRINCIPAL DO PROGRAMA */
int main()
{

/*********************************************************************/
/***************** DECLARAÇÃO DE VARIÁVEIS ************************/
/********************************************************************/

/* Variavel para trabalhar com o arquivo de texto */
FILE *txt;

/* Variaveis para trabalhar com o grafo */
int origem, destino, peso, grafo[100][100];

/* Armazena a menor distancia de v0 a todos os outros i vértices de G. */
int dist[100];

/* Vetor booleano:
1 significa que o vetor está em C. 0 significa que não está */
int C[100];

/* Variáveis auxiliares para a execução de laços no programa. */
int i,j;

/* Variável Auxiliar, para definir o vértice de V(G) analisado */
int w = 0;

/* Variavel auxiliar para definir a posição do w escolhido dentro do vetor
de distâncias. */
int posicao_w;

/* Variavel posicao_wiliar para definir |V(C)| */
int tamanho_C = 0;

/**********************************************************************/
/**************** TRABALHANDO COM O GRAFO *************************/
/*********************************************************************/

/* Atribuindo um valor infinito à todas as posições da matriz, fazendo com que
caso alguma aresta não exista, não seja utilizada pelo algoritmo de menor
caminho */
for(i = 0; i < 100; i++){
for(j = 0; j < 100; j++){
grafo[i][j] = INFINITO_POSITIVO;
}
}

/**********************************************************************/
/******************** LEITURA DE ARQUIVOS ***************************/
/*********************************************************************/

/* Abrindo o arquivo que contém o grafo */
if ( (txt = fopen(“grafo.txt”, “a+”) ) == NULL) {
/* mensagem exibida caso haja algum problema durante a abertura do arquivo */
printf(“Erro ao abrir o arquivo.”);
system(“PAUSE”);
exit(1);
}

/* Construindo o grafo em uma matrix para uso do algoritmo */
while (!feof(txt)) {
fscanf(txt,”%d”,&origem);
fscanf(txt,”%d”,&destino);
fscanf(txt,”%d”,&peso);
grafo[origem][destino] = peso; /* Atribui um peso às arestas do grafo */
}
fclose(txt);

/*********************************************************************/
/*************************** INICIO DO ALGORITMO ********************/
/*********************************************************************/

/* Começar em v0 e colocar todas as distancias num vetor de distancias */
for(i = 0; i < 100; i++){ // “Laço 1”
dist[i] = grafo[0][i];
} // Fim “Laço 1”

C[0] = 1; /* C <– v0 */
dist[0] = 0; /* Dist{v0} <– 0 */

/* Enquanto C != V(G): Enquanto houverem vértices de G fora de C, o algoritmo
será executado. Noto que o algoritmo só funciona com grafos conexos. */
while (tamanho_C < 100) { /* “Enquanto 1″ */

/* Abaixo, incrementa-se C em um elemento. */
tamanho_C += 1;

/* Define em w um custo infinito. Se houver algum vértice com custo menor
que 1000 ele será escolhido. Caso contrário, v0 é isolado e o algoritmo
é encerrado. */
w = INFINITO_POSITIVO;

/* Escolher menor das distâncias em vet_dist tal que distância n esteja em C */
for(i = 0; i < 100; i++){ /* Laço 2 */ if (C[i] == 0 & w > dist[i]) {
w = dist[i];
posicao_w = i;
} /* fim se */
} /* fim Laço 2 */

C[posicao_w] = 1; /* setando o w escolhido como vértice visitado */

/* atualizando custos em dist i a partir do w escolhido */
for(i = 0; i < 100; i++){ /* Laço 3 */ if (C[i] == 0) { if (dist[i] > (w + grafo[posicao_w][i])) dist[i] = w + grafo[posicao_w][i]; //tem que ser em V(G) – C
}
} /* Fim Laço 3 */
} /* Fim Enquanto */

/*********************************************************************/
/* *********************** Fim do algoritmo ****************************/
/*********************************************************************/

/**********************************************************************/
/***** Exibindo as menores distâncias de v0 até os demais vértices em G ******/
/*********************************************************************/

printf(” Origem Destino Distancia\n\n”);
for(i = 0; i < 100; i++){ // Laço 4 /* Como o algoritmo funciona para qualquer grafo com até 100 vértices, grafos pequenos terão muitas arestas e vértices marcados como “infinito”, ou naão existente. Para facilitar a visualização, vértices não existentes não são exibidos. */ if (dist[i] != 1000) printf(” v0 –> v%d %d \n”,i, dist[i]);
} /* Fim laço 4 */

/* Pulo de linha meramente estetético para separar mensagem de fim do
programa dos resultados (no Windows). */
printf(“\n”);

system(“pause”);
return 0;
}

O uso da abstração para resolução de problemas – Recursividade

Imagine que seja possível, à partir de regras claras, tomar um objeto ou informação inicial e começar a construir, indefinidamente, novos objetos ou informações e que as novas cópias possam ser ou idênticas ou ligeiramente diferentes ao objeto inicial.
É fácil perceber a utilidade da construção de cópias idênticas: fábricas e linhas de montagem, por exemplo, funcionam desta forma. Mas e quanto à cópias ligeiramente diferentes? Qual a utilidade disto? Por que alguém se preocuparia em estudar casos assim?
Bom, a resposta reside em um processo chamado de recursão: no ambito geral, a recursão é um processo de repetição onde, a partir de uma informação ou objeto, uma nova informação (ou objeto) é gerada. Assim como a redutibilidade, a recursividade também é uma forma de resolução de problemas que exige grande estudo e compreensão das regras do problema tratado.
Para que possa ocorrer, geralmente precisa de uma base e os elementos gerados à partir desta base pela recursão formam uma classe de objetos (ou informações).
A recursão é bastante conhecida em sequências numéricas, como a de Fibonacci: na matemática, os Números de Fibonacci são uma sequência definida pela fórmula abaixo: F(n) = {0 se n = 0, 1 se n = 1, (F(n) – 1) + (F(n) – 2) nos demais casos}.
Na prática: você começa com 0 e 1, e então produz o próximo número de Fibonacci somando os dois anteriores para formar o próximo. Os primeiros Números de Fibonacci são 0, 1, 1, 2, 3, 5, 8, 13…
A recursão também pode ser usada para definir e resolver problemas como a Torre de Hanoi: é um quebra cabeça lógico que trata da movimentação de discos em uma base. A base é composta de três pinos. O primeiro pino (ou pino inicial) contém uma determinada quantidade de discos que devem ser movidos para o terceiro pino (pino final) de forma que fiquem na mesma ordem em que se encontram no pino inicial. O jogo conta com duas restrições: Apenas um
disco pode ser movido por vez e, um disco só pode ser colocado sobre um disco de tamanho menor a ele mesmo (não existem dois discos com o mesmo tamanho no jogo). O segundo pino pode ser utilizado para auxiliar na movimentação das peças.
A dificuldade da solução manual deste problema é gigantesca: o número mínimo de “movimentos” para conseguir transferir todos os discos da primeira estaca à terceira é 2^n-1, sendo n o número de discos. Logo:
Para solucionar um Hanói de 3 discos, são necessários 7 movimentos. Com 7 discos, são necessários 127 movimentos, com 15 discos são 32.767 movimentos.
Com a recursão e auxilio de um computador, este problema pode ser rapidamente resolvido. Sem o computador, se você tentar resolver o problema com 15 discos, levando 1 segundo para mover cada disco e não cometer nenhum erro, vai precisar de mais de 9 horas para resolve-lo.
E não apenas nós, seres humanos, utilizamos de recursão para a resolução (ou criação) de problemas. A prórpia natureza parece ter seus truques: Um artigo escrito por uma equipe de Harvard, liderada por James Bird, descreve uma série de processos que leva que bolhas de sabão sobre um fluido não desaparecem depois de estourar. Em vez disso, elas geram um anel formado por outras bolhas menores.
Isso ocorre porque a bolha estourada se retrai sobre o líquido, capturando ar.
O processo é recursivo: uma bolha gera um círculos de bolhinhas; cada uma das bolhinhas, por sua vez, gera um novo círculo de bolhinhas, e assim sucessivamente. A série de processos que leva à formação das minibolhas, descritas no artigo, permite que a presença de minibolhas seja minimizada em determinados ambientes: “Em casos em que pequenas bolhas são prejudiciais, como na produção de vidros, nossos resultados podem ajudar”, disse Bird à “BBC News”.
Sim, recursão também pode fazer com que nerds com pesquisas estranhas fiquem ricos se acharam a aplicação correta e patentearem as descobertas.