Pseudocódigo. Outra forma de representar algoritmos

Nós já vimos duas das principais formas de representar algoritmos, a descrição narrativa e os fluxogramas. Hoje vamos ver a terceira.

A representação e descrição de algoritmos é uma parte fundamental da programação. Ela permite que os desenvolvedores comuniquem de forma clara e concisa a lógica e os passos necessários para resolver um problema ou realizar uma tarefa. O pseudocódigo é uma forma de representação de algoritmos que combina elementos de linguagem de programação com linguagem natural, tornando-o mais compreensível para humanos, independentemente da linguagem de programação específica.

O pseudocódigo não é uma linguagem de programação real, mas sim uma maneira de descrever a sequência de passos lógicos de um algoritmo. Ele utiliza convenções e estruturas de controle semelhantes às linguagens de programação, como declarações condicionais, loops e instruções de atribuição, permitindo que o desenvolvedor descreva a lógica de um algoritmo de maneira clara e estruturada.

Vamos considerar um exemplo simples para ilustrar o uso do pseudocódigo. Suponha que queremos escrever um algoritmo para calcular a média aritmética de três números. Utilizando pseudocódigo, poderíamos representar o algoritmo da seguinte forma:

1. Ler três números (num1, num2, num3)
2. Calcular a soma dos três números (soma = num1 + num2 + num3)
3. Calcular a média (media = soma / 3)
4. Exibir a média

Nesse exemplo, cada linha descreve uma etapa do algoritmo. Na linha 1, estamos lendo os três números, e na linha 2, calculamos a soma dos três números. Em seguida, na linha 3, calculamos a média dividindo a soma pelo número de elementos (3). Por fim, na linha 4, exibimos o resultado da média.

O pseudocódigo permite que o desenvolvedor se concentre na lógica do algoritmo, independentemente da sintaxe de uma linguagem de programação específica. Isso facilita a compreensão e a comunicação do algoritmo entre os membros da equipe de desenvolvimento.

Além disso, o pseudocódigo é altamente flexível e pode ser adaptado de acordo com as necessidades do projeto. Por exemplo, se desejarmos adicionar uma verificação de erro para garantir que os números inseridos sejam válidos, poderíamos modificar o pseudocódigo da seguinte maneira:

1. Ler três números (num1, num2, num3)
2. Verificar se os números são válidos
   2.1. Se algum número for inválido, exibir uma mensagem de erro e encerrar o programa
3. Calcular a soma dos três números (soma = num1 + num2 + num3)
4. Calcular a média (media = soma / 3)
5. Exibir a média

Nesse caso, adicionamos uma etapa extra (2) para verificar se os números são válidos. Se algum número for inválido, exibimos uma mensagem de erro e encerramos o programa. Essa modificação pode ser facilmente realizada no pseudocódigo, sem se preocupar com a sintaxe de uma linguagem de programação específica.

O uso de pseudocódigo também é comum em documentação técnica e algoritmos complexos, onde a compreensão do fluxo lógico é essencial. Ele pode ser facilmente convertido em código real em uma linguagem de programação específica, pois o pseudocódigo é projetado para ser independente de uma linguagem em particular.

Basicamente, o pseudocódigo é uma forma eficaz de representar e descrever algoritmos. Ele combina elementos de linguagem de programação com linguagem natural, permitindo que os desenvolvedores expressem a lógica do algoritmo de forma clara e estruturada. O pseudocódigo facilita a comunicação, a compreensão e a implementação dos algoritmos, independentemente da linguagem de programação utilizada.

Portugol

A representação e descrição de algoritmos utilizando o pseudocódigo conhecido como Portugol é uma prática amplamente utilizada no ensino e aprendizado de programação. O Portugol é uma linguagem de programação simplificada que permite aos iniciantes compreenderem a lógica e a estrutura dos algoritmos de forma mais clara e intuitiva, sem se preocuparem com a sintaxe complexa de linguagens de programação reais.

Ao utilizar o Portugol para representar algoritmos, é possível descrever passos sequenciais, estruturas condicionais e repetições de forma fácil e compreensível. Vamos considerar um exemplo simples de cálculo de média aritmética utilizando o Portugol:

Algoritmo "CalculaMedia"
   Var
      num1, num2, num3, soma, media: Real

   Início
      Escreva("Digite o primeiro número: ")
      Leia(num1)

      Escreva("Digite o segundo número: ")
      Leia(num2)

      Escreva("Digite o terceiro número: ")
      Leia(num3)

      soma <- num1 + num2 + num3
      media <- soma / 3

      Escreva("A média é: ", media)
   Fim

Neste exemplo, utilizamos o pseudocódigo Portugol para representar um algoritmo que lê três números, calcula a soma e a média aritmética dos mesmos, e exibe o resultado. As palavras-chave “Algoritmo”, “Var”, “Início” e “Fim” são utilizadas para definir a estrutura básica do algoritmo em Portugol.

Dentro da estrutura do algoritmo, utilizamos comandos como “Escreva” para exibir mensagens na tela, “Leia” para receber valores digitados pelo usuário, e os operadores matemáticos para realizar os cálculos necessários.

O uso do pseudocódigo Portugol é especialmente útil para iniciantes na programação, pois permite que eles se concentrem na lógica e na sequência de passos necessários para resolver um problema, sem se preocuparem com os detalhes específicos de uma linguagem de programação real. Dessa forma, os iniciantes podem aprender a estrutura básica dos algoritmos e ganhar confiança antes de se aventurarem em linguagens de programação mais complexas.

É importante ressaltar que o Portugol é apenas uma representação simplificada e não é executável diretamente. Ele serve como um meio de compreensão e aprendizado dos conceitos fundamentais da programação. Uma vez que o algoritmo tenha sido representado em Portugol, é possível traduzi-lo para uma linguagem de programação real, como Java, Python ou C, para que possa ser compilado e executado.

Como exemplo de pseudocódigos (em formas de programas) temos o Visualg (que usa uma versão do Portugol mais parecida com a usada no texto) e o Portugol Studio.

Até a próxima.

Recursividade: a multiplicação recursiva, as definições matemáticas por indução/recursão e os axiomas de Peano

A recursividade, como já vimos anteriormente deve primeiro sempre ser pensada nos casos mais simples (os casos bases ou casos básicos). Vamos ver um exemplo para nos ajudar.

É possível, por exemplo, definir a multiplicação de dois números inteiros m e n, sendo n > 0, em termos da operação de adição. O caso mais simples dessa operação é aquele no qual n = 0. Nesse caso, o resultado da operação é igual a 0, independentemente do valor de m. De acordo com a idéia exposta acima, precisamos agora pensar em como podemos expressar a solução desse problema no caso em que n > 0, supondo que sabemos determinar sua solução para casos mais simples, que se aproximam do caso básico. Neste caso, podemos expressar o resultado de m × n em termos do resultado da operação, mais simples m × (n − 1); ou seja, podemos definir m × n como sendo igual a m + (m × (n − 1)),
para n > 0. Ou seja, a operação de multiplicação pode então ser definida indutivamente pelas seguintes equações:

• ,

• 

Uma maneira alternativa de pensar na solução desse problema seria pensar na operação de multiplicação m * n como a repetição, n vezes, da operação de adicionar m, isto é:

• 

Raciocínio análogo pode ser usado para expressar a operação de exponenciação, com expoente inteiro não-negativo, em termos da operação de multiplicação (que será visto em outro post).

“Para entender a recursão, a pessoa deve primeiro entender a recursão.”

O programa a seguir apresenta, na linguagem C, uma forma computar o resultado da multiplicação de dois números, dados como argumentos dessas operações de forma recursiva. As função multiplica é definida usando-se chamadas à própria função, razão pela qual ela é chamada de recursiva.

int multiplica(int num1, int num2){
    //multiplicação por zero
    if (num1 == 0 || num2 == 0) {       
        return 0;
    }
    //caso base, onde a recursão para:
    else if (num2 == 1) {        
        return num1;
    }
    //multiplicando através da soma com recursividade:
    else {        
        return (num1 + multiplica(num1,num2 - 1));        
    }
}

Considere a função multiplica definida acima. A sua definição espelha diretamente a definição recursiva da operação de multiplicação, em termos da adição, apresentada anteriormente. Ou seja, multiplicar m por n  (onde n é um inteiro não-negativo) fornece:

• 0, no caso base (isto é, se n==0);
• m + multiplica(m, n-1), no caso indutivo/recursivo (isto é, se n!=0).

Vejamos agora, mais detalhadamente, a execução de uma chamada multiplica(3,2). Cada chamada da função multiplica cria novas variáveis, de nome m e n. Existem, portanto, várias variáveis com nomes (m e n), devido às chamadas recursivas. Nesse caso, o uso do nome refere-se à variável local ao corpo da função que está sendo executado. As execuções das chamadas de funções são feitas, dessa forma, em uma estrutura de pilha. Chamamos, genericamente, de estrutura de pilha uma estrutura na qual a inserção (ou alocação) e a retirada (ou liberação) de elementos é feita de maneira que o último elemento inserido é o primeiro a ser retirado.

Em resumo, na tabela abaixo, representamos a estrutura de pilha criada pelas chamadas à função multiplica. Os nomes m e n referem-se, durante a execução, às variáveis mais ao topo dessa estrutura. Uma chamada recursiva que vai começar a ser executada está indicada por um negrito. Nesse caso, o resultado da expressão, ainda não conhecido, é indicado por “…”.

---

Tabela 4.2: Passos na execução de multiplica(3,2)

Comando/Expressão	Resultado (expressão)	Estado (após execução/avaliação)
multiplica(3,2) …		m↦ 3 n↦ 2
n == 0	falso	m↦ 3 n↦ 2
return m + multiplica(m,n-1)	…	m↦ 3   m↦ 3 n↦ 2   n↦ 1
n == 0	falso	m↦ 3   m↦ 3 n↦ 2   n↦ 1
return m + multiplica(m,n-1)	…	m↦ 3   m↦ 3   m↦ 3 n↦ 2   n↦ 1   n↦ 0
n == 0	verdadeiro	m↦ 3   m↦ 3   m↦ 3 n↦ 2   n↦ 1   n↦ 0
return 0		m↦ 3   m↦ 3 n↦ 2   n↦ 1
return m + 0		m↦ 3 n↦ 2
return m + 3
multiplica(3,2)	6

E assim vemos como o procedimento recursivo para multiplicar dois números funciona com um exemplo em linguagem C, facilmente portável para outra linguagem.

Agora, para uma visão matematicamente mais precisa, continue lendo…

---

Definições por indução

As definições por indução (usando o princípio da indução dos axiomas de Peano) se baseiam na possibilidade de se iterar uma função um número arbitrário , n, de vezes.

Mais precisamente, seja uma função cujo domínio e contradomínio são o mesmo conjunto . A cada podemos, de modo único, associar uma função de tal maneira que . Em particular, se chamarmos , teremos . (lembrando que s(n) é o sucessor de um número natural n, conforme descrito nos axiomas de Peano).

Numa exposição mais, digamos, sistemática da teoria dos números naturais, a existência da n-ésima iterada de uma função é um teorema, chamado (lindamente) de “Teorema da Definição por Indução”.

É importante ressaltar que não é possível, nesta altura, definir simplesmente como pois “n vezes” é uma expressão sem sentido no contexto dos Axiomas de Peano, já que um número natural n é, por enquanto, apenas um elemento do conjunto (um número ordinal), sem condições de servir de resposta à pergunta “quantas vezes”?, até que lhe seja dada a condição de número cardinal.

Admitamos assim que, dada uma função , sabemos associar, de modo único, a cada número natural , uma função , chamada a n-ésima iterada de f, de tal modo que .

Agora, podemos ver um exemplo de definição por indução (recursão) usando o que acabamos de ver, as iteradas da função . Vamos ver o produto de números naturais (semelhantemente a soma e a exponenciação podem ser definidas da mesma forma). Sigamos com a multiplicação… (que vimos acima de forma menos formal e mais voltada para a lógica da programação)… Vejamos.

O produto, a multiplicação, de dois números naturais é definido da seguinte forma:

e

Em outras palavras: multiplicar um número por não o altera. Multiplicar por um número maior do que , ou seja, por um número da forma , é iterar a operação de somar , começando com .

Assim, por exemplo, ; e

.

Lembrando a definição de , vemos que o produto está definido indutivamente (ou recursivamente) pelas propriedades abaixo:

,

.

Que é exatamente a mesma definição recursiva que vimos acima!

Como calcular o custo de um algoritmo?

De forma rápida, existem duas formas de se calcular o custo de um algoritmo:

• Usando o cálculo de complexidade de tempo[1] (em que o custo é expresso por uma função que varia sobre o tamanho da entrada do algoritmo) e
• Usando o cálculo de complexidade de espaço (em que o custo é expresso por uma função que varia também sobre o espaço em memória, primária ou secundária, usado para finalizar o algoritmo).

A mais comum é calcular a complexidade de tempo ou através de uma função de custo associada ao algoritmo[2] ou à complexidade do pior caso expresso em termos da Notação Assintótica do pior caso[3] (que representa um limite superior[4] para o algoritmo).

Para se chegar à função de custo, normalmente se conta quantas instruções são executadas para o algoritmo para resolver um problema. A função de custa é expressa por um polinômio, em relação ao tamanho da entrada.

Por exemplo, no algoritmo

 for(i=0; i<N; i++){
     print(i);
 }

poderíamos dizer que o tempo gasto é

T(N) =
    N*(tempo gasto por uma comparação entre i e N) +
    N*(tempo gasto para incrementar i) +
    N*(tempo gasto por um print)

Isso daria, no caso, a função de custo T(N) em relação ao tamanho da entrada N.

Já a complexidade usando notação assintótica é, geralmente, mais usada para classes de algoritmos por conta da sua simplicidade e abstração. Siga o raciocínio:

Ao ver uma expressão como n+10 ou n²+1, a maioria das pessoas pensa automaticamente em valores pequenos de n. A análise de algoritmos faz exatamente o contrário: ignora os valores pequenos e concentra-se nos valores enormes de n. Para valores enormes de n, as funções n² , (3/2)n² , 9999n² , n²/1000 , n²+100n , etc. crescem todas com a mesma velocidade e portanto são todas equivalentes.

Esse tipo de matemática, interessado somente em valores enormes de n, é chamado comportamento assintótico[5]. Nessa matemática, as funções são classificadas em ordens[6] (como as ordens religiosas da Idade Média); todas as funções de uma mesma ordem são equivalentes. As cinco funções acima, por exemplo, pertencem à mesma ordem.

Essa ideia reflete que precisamos focar, na verdade, em quão rápido uma função cresce com o tamanho da entrada.(essa é a base da “análise de algoritmos” e o centro de como se calcular o custo de um algoritmo).

Nós chamamos isso de taxa de crescimento do tempo de execução. Para manter as coisas tratáveis, precisamos simplificar a função até evidenciar a parte mais importante e deixar de lado as menos importantes.

Por exemplo, suponha que um algoritmo, sendo executado com uma entrada de tamanho n, leve 6n²+100n+300 instruções de máquina. O termo 6n² torna-se maior do que os outros termos, 100n+300 uma vez que n torna-se grande o suficiente. A partir de 20 neste caso.

Abaixo temos um gráfico que mostra os valores de 6n² e 100n+300 para valores de n variando entre 0 e 100:

Podemos dizer que este algoritmo cresce a uma taxa n², deixando de fora o coeficiente 6 e os termos restantes 100n+300. Não é realmente importante que coeficientes usamos, já que o tempo de execução é an²+bn+c, para alguns números a>0, b, e c, sempre haverá um valor de n para o qual an² é maior que bn+c e essa diferença aumenta juntamente com n. Por exemplo, aqui está um gráfico mostrando os valores de 0,6n² e 1000n+3000 de modo que reduzimos o coeficiente de n² por um fator de 10 e aumentamos as outras duas constantes por um fator de 10:

O valor de n para o qual 0,6n² se torna maior que 1000n+3000 aumentou, mas sempre haverá um ponto de cruzamento, independentemente das constantes. E a partir deste valor de cruzamento, 0,6n² sempre crescerá mais rapidamente (e sempre será maior).

Descartando os termos menos significativos e os coeficientes constantes, podemos nos concentrar na parte importante do tempo de execução de um algoritmo — sua taxa de crescimento — sem sermos atrapalhados por detalhes que complicam sua compreensão. Quando descartamos os coeficientes constantes e os termos menos significativos, usamos notação assintótica. Usa-se, normalmente, três formas: notação Θ[7] , notação O[8] , notação Ω[9] .

Por exemplo, suponha que tenhamos nos esforçado bastante e descoberto que um certo algoritmo gasta tempo

T(N) = 10*N² + 137*N + 15

Nesse caso o termo quadrático 10*N² é mais importante que os outros pois para praticamente qualquer valor de N ele irá dominar o total da soma. A partir de N ≥ 14 o termo quadrático já é responsável pela maioria do tempo de execução e para N > 1000 ele já é responsável por mais de 99%. Para fins de estimativa poderíamos simplificar a fórmula para T(N) = 10*N² sem perder muita coisa.

Vamos começar pelo O-grande, que é uma maneira de dar um limite superior para o tempo gasto por um algoritmo. O(g) descreve a classe de funções que crescem no máximo tão rápido quanto a função g e quando falamos que f ∈ O(g) queremos dizer que g cresce pelo menos tão rápido quanto f. (isso é, claro, um “abuso” matemático. Lembre-se sempre que é uma classe de funções, representando um conjunto de funções)

Formalmente:

Dadas duas funções f e g, dizemos que f ∈ O(g) se existem constantes x0 e c tal que para todo x > x0 vale f(x) < c*g(x)

Nessa definição, a constante c nos dá margem para ignorar fatores constantes (o que nos permite dizer que 10*N é O(N)) e a constante x0 diz que só nos importamos para o comportamento de f e g quando o N for grande e os termos que crescem mais rápido dominem o valor total.

Para um exemplo concreto, considere aquela função de tempo f(n) = 10*N2 + 137*N + 15 de antes.

Podemos dizer que o crescimento dela é quadrático:

Podemos dizer que f ∈ O(N²), já que para c = 11 e N > 137 vale

10*N² + 137*N + 15 < c * N2

Podemos escolher outros valores para c e x0, como por exemplo c = 1000 e N > 1000 (que deixam a conta bem óbvia). O valor exato desses pares não importa, o que importa é poder se convencer de que pelo menos um deles exista.

Na direção oposta do O-grande temos o Ω-grande, que é para limites inferiores. Quando falamos que f é Ω(g), estamos dizendo que f cresce pelo menos tão rápido quanto g. No nosso exemplo recorrente, também podemos dizer que f(n) cresce tão rápido quanto uma função quadrática:

Podemos dizer que f é Ω(N²), já que para c = 1 e N > 0 vale

10*N² + 137*N + 15 > c*N2

Finalmente, o Θ-grande tem a ver com aproximações justas, quando o f e o g crescem no mesmo ritmo (exceto por um possível fator constante). A diferença do Θ-grande para o O-grande e o Ω-grande é que estes admitem aproximações folgadas, (por exemplo, N² ∈ O(N³)) em que uma das funções cresce muito mais rápida que a outra.

Dentre essas três notações, a mais comum de se ver é a do O-grande. Normalmente as análises de complexidade se preocupam apenas com o tempo de execução no pior caso então o limite superior dado pelo O-grande é suficiente.

Para algoritmos recursivos usa-se normalmente uma equação de recorrência[10] para se chegar á função de custo. Então, resolve-se essa equação de recorrência para se chegar à fórmula fechada da recorrência.

Muitas vezes é muito difícil se chegar a uma fórmula fechada, então usa-se outros métodos, como a árvore de recursão e o teorema-mestre[11] para se chegar à análise assintótica (usando a notação O-grande).

Exemplos da taxa de crescimento das principais classes de funções

Notas de rodapé:

[1] Complexidade de tempo – Wikipédia, a enciclopédia livre
[2] Análise de Algoritmos
[3] Big O notation – Wikipedia
[4] Limit superior and limit inferior – Wikipedia
[5] Asymptotic notation
[6] Time complexity – Wikipedia
[7] Notação Big-θ (Grande-Theta) 
[8] Grande-O – Wikipédia, a enciclopédia livre
[9] Notação Big-Ω (Grande-Omega)
[10] http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf
[11] Teorema mestre (análise de algoritmos) – Wikipédia, a enciclopédia livre

Essa foi a minha resposta no Quora à pergunta: “Como calcular o custo de um algoritmo”.

Link: https://pt.quora.com/Como-calcular-o-custo-de-um-algoritmo

Representando e descrevendo algoritmos…

Já sabemos o que é um algoritmo e com o que ele se parece, mas como representar os algoritmos? Como descrevê-los? Como podemos ter uma representação física ou “tangível” da ideia que o algoritmo representa e do problema que ele resolve?

Há, basicamente, 3 formas de se representar algoritmos:

1. Representação descritiva (ou descrição narrativa).
2. Fluxogramas.
3. Pseudocódigo.

Há também uma quarta forma, mas essa é especial  e falaremos dela depois.

A descrição narrativa (ou representação descritiva)

Bom, essa é a mais simples e menos formal de todas as formas de se representar um algoritmo. Consiste simplesmente de descrever ou narrar como o algoritmo funciona. Basicamente, serve para todos os tipos de algoritmos dada a sua generalidade. Exemplos:

Algoritmo para escovar os dentes:

1. Pegar a escova de dentes e lavá-la.
2. Pegar o tubo de creme dental .
3. Abrir o tubo de creme dental.
4. Apertar o tubo sobre a escova aplicando uma pequena quantidade de creme sobre a mesma.
5. Fechar o tubo.
6. Colocar a escova na boca e movimentá-la para a cima e para baixo em pequenos círculos por um determinado tempo (repetir esta operação até que os dentes estejam limpos)
7. Enxaguar a boca.
8. Limpar e guardar a escova.

Esse algoritmo é bem genérico e pouco específico. Interessante notar que cada linha tem um verbo no infinitivo, um comando, uma ação. Uma instrução.

Neste contexto algorítmico, uma instrução indica uma ação elementar a ser executada.

As características da Descrição Narrativa (ou representação descritiva) são:

• Uso da linguagem natural (no caso, Português);
• Facilidade para quem conhece a linguagem e as ações a serem executadas;
• Possibilidade de má interpretação, originando ambiguidades e imprecisões;
• Pouca confiabilidade (a imprecisão gera desconfiança);
• Extensão (se escreve muito para dizer pouco).

PARA EXERCITAR: Escrever algoritmos para trocar um pneu, fritar um ovo, trocar uma lâmpada, atravessar uma rua, tomar banho, calcular o dobro de um número, calcular a média do bimestre e descascar batatas.

Fluxogramas

Fluxograma é um diagrama que representa um processo ou um algoritmo passo a passo, descrevendo o fluxo do processo ou do algoritmo. Cada figura geométrica representa uma ação distinta. Esses diagramas ilustram, de forma simples, a sequência operacional do algoritmo (ou processo).

São usados para muito mais coisas do que descrever algoritmos ou processos de software. Alguns usos são:

• Workflow de processos de negócios;
• Diagrama de Fluxo de Dados (DFD) para modelagem e documentação de sistemas;
• Representação da lógica de um programa (ou algoritmo).

Exemplo de um fluxograma simples mostrando como lidar com uma lâmpada que não funciona (fonte: Wikipedia)

Principais figuras (existem dezenas de outras)

Exemplo (cálculo de uma média, dados duas notas)

Vantagens e desvantagens dos fluxogramas:

Vantagens:

• O fluxograma é uma das ferramentas mais conhecidas;
• Figuras dizem mais do que palavras; (rsrsrs)
• Padrão Mundial.

Desvantagens:

• A solução é amarrada a dispositivos físicos;
• Pouca atenção aos dados, não oferecendo recursos para descrevê-los ou representá-los coerentemente;
• Complicação à medida que o algoritmo cresce.

Bom, esse post já ficou muito grande, portanto a terceira forma, o pseudocódigo eu deixarei para o próximo post sobre essa seção de algoritmos!

Até!

E o algoritmo, hein? Afinal, que “bicho” é esse que domina o mundo?

Como o diminuto GPS consegue, tão rápido, em míseros segundos, achar uma rota para nós? Como o número do nosso cartão de crédito é protegido em uma transação virtual? Como as próprias transações virtuais são realizadas? Como conseguimos ouvir música e assistir a um vídeo, em nossos dispositivos eletrônicos de um local a quilômetros de distância de nós?

A resposta para essas e muitíssimas outras perguntas reside em uma palavra: algoritmo.

Mas, afinal, o que é um algoritmo?

Uma resposta genérica, rápida e de âmbito geral seria: “uma sequência de instruções que executadas ordenadamente e passo a passo, resolve um problema”. Aí você responde: com essa definição, então tudo é um algoritmo? Bom, …, quase tudo, mas, nem tudo! rsrsrs

Mas, sim, você executa algoritmos diariamente. Ao acordar, por exemplo, você escova os dentes. O procedimento de escovar os dentes é quase sempre o mesmo: abrir o tubo de creme dental, pegar a escova, apertar o tubo sobre a escova aplicando uma pequena quantidade de creme sobre a mesma, fechar o tubo, colocar a escova na boca e movimentá-la para a cima e para baixo em pequenos círculos por um determinado tempo, etc. Se você pega um ônibus para ir ao trabalho ou à escola também tem um algoritmo para isso e assim sucessivamente.

Mas, “peraí”, calma lá! Não são esses os algoritmos que executam as tarefas descritas no início do texto. Não, não são mesmo. Mas, eles partem do mesmo princípio.

Eu ensino sobre algoritmos há mais de dez anos e os alunos, invariavelmente acham difícil ou tem uma curva de aprendizado pouco suave (ao menos no início). Tratamos, neste blog, e no início do texto, dos algoritmos que podem ser executados em computadores, ou dispositivos de computação. E estes, simplesmente dominam o mundo…

Mas, vamos por partes (como nosso conhecido Jack). Os matemáticos conhecem o conceito de algoritmo (e de computação em geral) há muitos anos. É famoso, por exemplo, o método babilônico (ou algoritmo) para extração da raiz quadrada aproximada de um número (cerca de 2 mil anos antes de Cristo) e o muitíssimo conhecido Algoritmo de Euclides (300 a.C.) para a extração do MDC entre dois números.

Em suma, um algoritmo, de fato, representa um método para realizar uma tarefa. Os algoritmos de computador tem duas características principais (dentre tantas) que o distinguem de serem “métodos computacionais“: 1) Ele é não ambíguo e 2) tem que ter fim! (Um método para calcular o número π, por exemplo, grosso modo, não pode ser considerado um “algoritmo” formal, pois o número pi não tem fim! É um método. É computacional. Mas não tem fim!)

A consequência destas características é o que define, formalmente, algoritmo. O fato das instruções serem não ambíguas leva à corretude (entradas iguais geram saídas iguais), à previsão da saída e a finitude é o que leva uma máquina como o computador a executá-lo.

Normalmente, se exemplifica o conceito de algoritmo relacionando-o a uma receita culinária onde segue-se passos e usa-se ingredientes (dados de entrada) para gerar um prato (saída). É um exemplo comum e sua força reside na simplicidade da comparação.

Tecnicamente, pode-se repetir operações, efetuar cálculos e tomar decisões até que a tarefa seja completada. Diferentes algoritmos podem realizar a mesma tarefa usando instruções diferenciadas que levam mais ou menos tempo, espaço ou esforço computacional. Isso chama-se complexidade computacional e será estudado em outro tópico.

A precisão das instruções é crucial. Nós podemos tolerar algoritmos descritos imprecisamente, mas não o computador! Além de precisas, as instruções devem ser simples. Simples o bastante para uma máquina executar.

Basicamente, eu posso dizer para alguém: “pegue outra rua” quando o trânsito estiver engarrafado, mas não “dizer” o mesmo ao computador. Ele simplesmente não entenderia.

Portanto, chegamos a uma definição que pode-se dizer suficiente (embora informal):

“Algoritmos são sequências de instruções ou regras simples, ordenadas  e que, se executadas passo a passo, a partir do início, resolvem um determinado problema em um tempo finito”.

Formalmente, a corretude de um algoritmo pode ser provada matematicamente e a análise de sua execução também (complexidade). Estas duas últimas tarefas são metas da Análise de Algoritmos. O conceito  de algoritmo foi formalizado em 1936 por Alan Turing (pela máquina de Turing) e Alonzo Church (pelo cálculo lambda). Os dois conceitos formaram as fundações da Ciência da Computação.

O gênio, Alan Turing (1912-1954)

E eles estão em toda parte. Como eu disse anteriormente, dominam o mundo. Estão no carro quando se usa o GPS para se determinar uma rota de viagem (o aparelho executa os chamados algoritmos de “caminho mínimo“). Estão nas compras pela Internet garantindo a segurança de sites (algoritmos criptográficos). Estão por trás das entregas dos produtos determinando em qual ordem os caminhões devem seguir. São a base das rotas aeroviárias ditando o itinerário dos aviões comerciais e de logística. Estão dentro dos sistemas internos de usinas nucleares e servidores de páginas web como esta que você está lendo, enfim, eles estão sendo executados em computadores em todos os lugares, no notebook, em computadores de grande porte, em smartphones, em carros, TV’s, micro-ondas, enfim, em TODOS os lugares!

Não esqueça disso a próxima vez que marcar sua rota no GPS!

Ainda falaremos muito mais de algoritmos…

Até a próxima!

________________

P.S. o termo “algoritmo”, segundo Donald Knuth, provavelmente o maior cientista da computação vivo, é derivado do nome “al-Khowârizmî“, um matemático persa do século IX. A raiz da palavra, seu radical, é praticamente o mesmo de “álgebra”, “algarismo” e “logaritmo”.

😉

Aulas de Fundamentos de Programação e Algoritmos (04, 05 e 06) e Exercício – 50 Algoritmos

Caros alunos de Fundamentos de Programação e Algoritmos. Seguem as aulas 04, 05 e 06 além do exercício maravilhoso dos 50 algoritmos! Para baixar é só clicar.

Fund. de Programação e Algoritmos –  Aula 04
Fund. de Programação e Algoritmos –  Aula 05
Fund. de Programação e Algoritmos –  Aula 06

Exercícios de Algoritmos (50 Algoritmos).

Não esqueçam que as apresentações dos trabalhos começam nesta semana (dia 22/06), portanto, estejam preparados!

Bons estudos!

Aula 03 e lista de exercícios 03 de Fundamentos de Programação e Algoritmos

Caros alunos de Fundamentos de Programação e Algoritmos, segue a lista de exercícios 03 e a aula 03.
Não esqueçam que só a prática leva à perfeição. O sucesso é construído com esforço e dedicação.
Um grande Abraço!

Aulas e Listas de Exercícios de Estrutura de Dados e de Fundamentos de Programação e Algoritmos

Caros alunos. Desculpem pela demora (de 1 dia) para postar as aulas e as listas de exercícios.

A turma de Estrutura de Dados está ainda na Lista de exercícios 01. Para baixá-la clique aqui. Não esqueçam de acrescentar os 10 programas escritos em sala de aula que estão no slide 53 da Aula 01. Para baixar a Aula 01 Completa e Revisada (versão 2.0), clique aqui.

A turma de Fundamentos de Programação e Algoritmos já está na lista de exercícios 02. Para baixá-la, clique aqui. Para baixar o conteúdo completo da Aula 02, clique aqui. Para baixar as Notas da Aula 02 basta clicar aqui.

A data máxima para entrega de ambas as listas é dia 20/04/2012, próxima sexta-feira, portanto, não se atrasem. Aproveitem o fim de semana para resolver todos os exercícios. Qualquer dúvida, basta contatar o professor. Abs e até a próxima semana.

Volta às aulas com Fundamentos de Programação e Algoritmos

Bom, depois de conhecer a turma de Estrutura de Dados, hoje foi a vez da turma 21620112 de Sistemas de Informação, 2º. período da disciplina Fundamentos de Programação e Algoritmos. A aula, a apresentação com os alunos e dos alunos e a passagem do conteúdo foram bem divertidas e interessantes. Turma grande, 56 alunos, porém dinâmica e participativa o que facilita o trabalho do professor. Apresentações, plano de aula, metodologia, avaliação e a primeira aula foram proveitosas e até o último tópico (e isso foi às 22:08). Agradeço a turma pela paciência pelo extrapolamento do horário(e por ficarem até o final) e também pela grande participação e interesse na disciplina. Espero ter deixado claro o quanto esta disciplina é importante para o restante do curso. Teremos pouco tempo, mas tenho certeza que serão ótimos momentos. Um abraço a todos.

Link para o arquivo da Aula 01: clique aqui.

Link para Ementa/plano de curso e conteúdo programático da disciplina: clique aqui.

Link para as notas de aula da Aula 01: clique aqui.

É recomendadíssimo que o arquivo seja baixado, lido estudado e resolvido. Lembrando que as informações estão resumidas e que as explicações em sala foram, sem dúvida, essenciais.

Link para o programa Visualg. Clique aqui.

Mais links sobre algoritmos aqui, aqui e aqui.

P.S.: Todos os emails que me foram passados na lista já devem ter recebido o convite para acesso à pasta compartilhada no DropBox. Quem não recebeu, comenta aqui ou me contacte por outro meio confirmando seu email para que eu possa reenviar o pedido.
Até!

Recursividade – Algoritmo de Euclides recursivo

A recursividade é um recurso extremamente útil e poderoso tanto na matemática quanto na ciência da computação. Na informática, diz respeito a uma função que chama a si própria. Na matemática a um processo que é definido em termos de si mesmo. A melhor definição de recursividade, com os melhores exemplos, aquela que me fez realmente aprender a recursividade originou-se deste livro: Estruturas de dados usando C de Tenenbaum et al.  Maiores informações sobre recursividade podem ser obtidas aqui, aqui e aqui.

O algoritmo de Euclides demonstrado anteriormente tem uma versão recursiva bem elegante. Segue sua versão para o Visualg:

 algoritmo "Euclides recursivo"
// Função : Euclides Recursivo
// Autor :  Ed
// Data : 31/05/2009
// Seção de Declarações
var
a,b: inteiro

funcao mdc_rec (x:inteiro; y:inteiro):inteiro
var
dividendo,divisor: inteiro
inicio
dividendo<-x
divisor<-y
se divisor=0 entao
 retorne dividendo
senao
 retorne mdc_rec(divisor, dividendo%divisor)
fimse

fimfuncao

inicio
//entrada de dados
escreval()
escreval("Algoritmo de Euclides para encontrar o MDC entre 2 números")
escreval()
escreva("Digite o primeiro numero:")
leia (a)
escreva("Digite o segundo numero:")
leia (b)
escreval()
escreva ("O MDC de ", a," e ", b, " é ", mdc_rec(a,b))
escreval()
fimalgoritmo

Algoritmo de Euclides

O algoritmo de Euclides para obtenção do MDC pode ser descrito como uma série de divisões sucessivas, o que dispensa fatoração.

E agora, … Pascal

Bom, meu aluno thiago tem me cobrado pelo post sobre o Pascal. Então… Vamos lá!

A linguagem de Programação estruturada Pascal foi criada em 1968 pelo professor Niklaus Wirth, em Zurique, na Suíça. Wirth concebeu uma linguagem que facilitasse o ensino de programação, desenvolvendo, desde cedo, bons hábitos entre os iniciantes. Wirth designou-a Pascal em homenagem ao filósofo e matemático francês Blaise Pascal, nascido no século 17, que construiu a pascalina – a 1ª calculadora mecânica funcional. Pascal foi incialmente, uma linguagem fortemente tipada e orientada aos dados. Pouco depois, abraçou a OOP com o diateo Object Pascal. (presente até hoje no Delphi). Pascal é tb muito estruturada e própria para o uso educacional, principalmente de Algoritmos e de estruturas de dados.

Na verdade, o Pascal originou uma gama muito grande de linguagens e pode ser considerada uma “família” de linguagens e dialetos. Grande fama da linguagem se deve ao Turbo Pascal da Borland lançado no início da década de 80, mostrando que era possível fazer compiladores bons, rápidos e baratos.

Hoje o pascal está presente além do Delphi em milhares de instituições de ensino como parte do ensino da programação estruturada e estruturas de dados. Se mais delongas, vamos aos links:

Pascal ZIM – Brazuca. Excelente. Grátis. É só conferir.
Free Pascal – Poderoso ambiente de programção Pascal. Open source.
Borland Turbo Pascal 5.5 – Excelente IDE Pascal.
Página da Linguagem Pascal na Wikipedia
Turbo Pascal Programmers Page
Delphi e Kylix
Apostila Pascal

Inté…

Exercicio – 50 Algoritmos

Sem tempo de postar no portal, envio aqui a lista de exercicios das turmas 216062 e 216071B. A data de entrega foi alterada.

Basta clicar aqui .

Abs e bom estudo.

Correção do exercício 14

Na última aula de algoritmos da sala 216071A, com o horário já esgotado, foram cometidos dois pequenos erros no algoritmo relativo ao exercício 14 da leitura de 30 notas de alunos e os cálculos da média geral, maior, menor, etc..

Um deles é com a contagem final das notas, pois sempre fica faltando uma, geralmente das notas menores do que a média. Fiz então outra versão com o comando repita. Daí o problema era com a menor nota que sempre era zero. Fiz uma gambiarra com um comando SE e então ele ficou corretinho. As duas versões, com enquanto e com repita, estão disponíveis para download. Basta clicar AQUI.

Notas de Aula 7, 8 e 9

Disponíveis as notas das aulas 7, 8 e 9. Basta clicar aqui

Abs e até segunda.