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 a Probabilidade e a Estatística, hein?

Na faculdade eu sempre olhei muito enviesado para a Probabilidade e a Estatística, mas isso devia-se, claro, à ignorância em relação ao pensamento estatístico. Como Leonard Mlodinow nos ensina no excelente “O Andar do Bêbado: como o acaso determina nossas vidas“, e eu cito: “a mente humana foi construída para identificar uma causa definida para cada acontecimento, podendo assim ter bastante dificuldade em aceitar a influência de fatores aleatórios ou não relacionados”. É isso! Temos extrema dificuldade em entender o pensamento aleatório, probabilístico e, por consequência, o estatístico. Mas, como escrito no mesmo livro (citando o economista Armen Alchian), “os processos aleatórios são fundamentais na natureza, e onipresentes em nossa vida cotidiana; e ainda assim, a maioria das pessoas, não os compreende”.

Mas, é óbvio que isso precisa mudar. Nós, Cientistas da Computação e amantes da tecnologia e da Tecnologia da Informação em geral, não somos “a maioria das pessoas”. Precisamos mudar a nossa lógica determinística, afinal, a ciência inteira (e a Computação não fica de fora) é dominada inteiramente pela Estatística e pelo pensamento estocástico.

“O desenho de nossas vidas, como a chama da vela, é continuamente conduzido em novas direções por diversos eventos aleatórios que, juntamente com nossas reações a eles, determinam nosso destino. Como resultado, a vida é ao mesmo tempo difícil de prever e difícil de interpretar” – Leonard Mlodinow em “O Andar do Bêbado: como o acaso determina nossas vidas”

Portanto, começamos esse estudo, muitas vezes com resultados contra-intuitivos. Mas temos uma ferramenta de grande valia: o computador e as linguagens de programação. Portanto, vamos começar com um experimento básico: a probabilidade da moeda lançada.

Para isso, fiz um script em Python (2.7.11) para simular o lançamento de uma moeda e, em seguida, computar as probabilidades dos lançamentos. Os resultados são interessantes. Quanto mais o número de lançamentos aumenta mais as frequências aproximam-se do número previsto (50% para cada uma das faces).

Aqui está o código:

# -*- coding: UTF-8 -*-
"""
Função:
    Exemplo de lançamento de moeda
Autor:
    Professor Ed - Data: 29/05/2016 -
Observações:  ?
"""
def gera_matriz_lancamentos(matriz, tamanho):
    import random
    matriz_faces = []
    print 'Gerando...'
    for x in range(tamanho):
        num = random.randint(1,2) #1 = cara, 2 = coroa
        matriz.append (num)

        if num==1:
            matriz_faces.append('Cara')
        else:
            matriz_faces.append('Coroa')

    print matriz_faces

def calcula_probabilidades(matriz, tamanho):
    soma_cara = 0
    soma_coroa = 0

    for i in range(len(matriz)):
        if matriz[i]==1:
            soma_cara = soma_cara+1
        elif matriz[i]==2:
            soma_coroa = soma_coroa + 1

    probabilidade_cara = float(soma_cara)/float(tamanho)*100
    probabilidade_coroa = float(soma_coroa)/float(tamanho)*100    

    print 'Foram lancadas ' + str(soma_cara) + ' caras e ' + str(soma_coroa) + ' coroas'

    probabilidades = []
    probabilidades.append(probabilidade_cara)
    probabilidades.append(probabilidade_coroa)    

    return probabilidades

matriz=[]
tamanho = int(raw_input('Digite o tamanho da matriz de lancamentos: '))
gera_matriz_lancamentos(matriz, tamanho)
#print 'Um para cara e 2 para coroa'
#print matriz
vetor_probabilidades = []
vetor_probabilidades = calcula_probabilidades(matriz, tamanho)
print 'As probabilidades sao: %f%% e %f%%' % (vetor_probabilidades[0], vetor_probabilidades[1])

Nem sempre, como os números gerados pelo computador são (pseudo)aleatórios (falaremos disto depois), as frequências são próximas a 50% (variando bastante entre as execuções do programa), mas, em geral, sempre que a quantidade de lançamentos é imensa (acima de 10.000), as probabilidades aproximam-se do limite esperado.

Lembrando, sempre, que se lançarmos uma moeda um milhão de vezes não deveríamos esperar um placar exato (50% caras e 50% coroas). A teoria das probabilidades nos fornece uma medida do tamanho da diferença (chamada de erro) que pode existir neste experimento de um processo aleatório. Se ma moeda for lançada, digamos, N vezes, haverá um distanciamento (erro) de aproximadamente 1/2 N “caras”, este erro, de fato, pode ser para um lado ou para o outro. Ou seja, espera-se que, em “moedas honestas“, o erro seja da ordem da raiz quadrada de N.

Assim, digamos que de cada 1.000.000 lançamentos de uma moeda honesta, o número de caras se encontrará, provavelmente entre 499.000 e 501.000 (já que 1.000 é a raiz quadrada de N). Para moedas viciadas, espera-se que o erro seja consistentemente maior que a raiz quadrada de N.

Um exemplo da execução do programa com duas instâncias exatamente iguais, mas com valores gerados diferentes. (mais ou menos como acontece na realidade).

Abaixo, um exemplo de uma instância com 100.000 lançamentos provando que as frequências, de fato, aproximam-se das probabilidades previstas (inclusive se considerado o erro):

Segundo a Lei dos Grandes Números, a média aritmética dos resultados da realização da mesma experiência repetidas vezes tende a se aproximar do valor esperado à medida que mais tentativas se sucederem. E, claro, se todos os eventos tiverem igual probabilidade o valor esperado é a média aritmética. (Lembrando, claro, que o valor em si, não pode ser “esperado” no sentido geral, o que leva à uma falácia). Ou seja, quanto mais tentativas são realizadas, mais a probabilidade da média aritmética dos resultados observados se aproximam da probabilidade real.

A Probabilidade é descrita por todos, alunos, professores e estudantes, como difícil. Em minha opinião, ela dá a impressão de ser difícil porque muitas vezes, desafia nosso senso comum (que, normalmente, tende sempre à falácia do apostador, ou de Monte Carlo), ainda mais quando dispomos do conhecimento da lei dos grandes números. Estratégias como “o dobro ou nada” nadam de braçadas no inconsciente coletivo com esta falácia.

O teorema de Bayes (que é um corolário da Lei da Probabilidade Total) explica direitinho o porque da falácia do apostador ser, bem, …, uma falácia. Sendo a moeda honesta, os resultados em diferentes lançamentos são estatisticamente independentes e a probabilidade de ter cara em um único lançamento é exatamente ¹⁄₂.

É isso aí. Nos próximos posts vamos falar um pouco mais sobre os significados e como calcular essas probabilidades, sempre tentando um enfoque prático com a ajuda dessa ferramenta magnífica que é o computador!
Até!

P.S.: Assim que meu repositório for clonado certinho (tive uns problemas com o Git local) eu coloco o link para o programa prontinho no Github.
Pronto! Já apanhei resolvi o problema do Git e você pode baixar o arquivo-fonte clicando aqui.
P.S.1: Acabei não resistindo e fazendo o teste para 1.000.000 de lançamentos. O resultado está aqui embaixo. Confira: