Posts filed under ‘Aulas’

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.

1

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.

escova_dentes

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

flow chart diagram

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:

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

Ficheiro:LampFlowchart pt.svg

Principais figuras (existem dezenas de outras)

principais_simbolos_fluxograma

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

fluxograma-media

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é!

quarta-feira, 24 maio, 2017 at 6:03 pm Deixe um comentário

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?

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.

cakeisalie

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.

algoritmo2

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.

alan_turing_photo

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”.

😉

sexta-feira, 25 novembro, 2016 at 7:18 pm 2 comentários

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.

probabilidade-moedaUm 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):

probabilidade-moeda-100mil-lancamentos

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 12.

É 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:

probabilidade-moeda-1000000-lancamentos

quarta-feira, 29 junho, 2016 at 2:49 pm 2 comentários

Popularidade de linguagens – Você conhece o índice Tiobe?

Você conhece ou já ouviu falar do índice Tiobe? Este é um ranking organizado pela empresa Tiobe que tenta mostrar a popularidade das linguagens de programação quando comparada com outras. Ele iniciou em 2001 e é atualizado todos os meses desde então.

Ele leva em consideração o número de resultados de buscas de nomes de linguagens ou equivalentes em inúmeros sites como Google, Wikipedia, YouTube, Yahoo, Bing, Amazon, Blogger, Baidu e WordPress.

Há uma antiga amiga dos estudantes de Estruturas de Dados que, desde o início do ranking, praticamente nunca saiu do top 5. Nem preciso dizer que é a boa e velha filha de Dennis Ritchie, a Linguagem C!

O ranking de Julho de 2013 estava assim (para as 10 primeiras posições):

Position Jul 2013 Position Jul 2012 Delta in Position Programming Language Ratings Jul 2013 Delta Jul 2012 Status
1 1 C 17.628% -0.70%   A
2 2 Java 15.906% -0.18%   A
3 3 Objective-C 10.248% +0.91%   A
4 4 C++ 8.749% -0.37%   A
5 7 PHP 7.186% +2.17%   A
6 5 C# 6.212% -0.46%   A
7 6 (Visual) Basic 4.336% -1.36%   A
8 8 Python 4.035% +0.03%   A
9 9 Perl 2.148% +0.10%   A
10 11 JavaScript 1.844% +0.39%   A

 

Neste agosto de 2013 ela (a Linguagem C) deu uma variada e caiu para 2º lugar por alguns décimos. Confira:

Position Aug 2013 Position Aug 2012 Delta in Position Programming Language Ratings Aug 2013 Delta Aug 2012 Status
1 2 Java 15.978% -0.37%   A
2 1 C 15.974% -2.96%   A
3 4 C++ 9.371% +0.04%   A
4 3 Objective-C 8.082% -1.46%   A
5 6 PHP 6.694% +1.17%   A
6 5 C# 6.117% -0.47%   A
7 7 (Visual) Basic 3.873% -1.46%   A
8 8 Python 3.603% -0.27%   A
9 11 JavaScript 2.093% +0.73%   A
10 10 Ruby 2.067% +0.38%   A

O que confirma a força da linguagem criada há mais de quarenta anos nos laboratórios da Bell para desenvolver o Unix. Maior do que a popularidade é a influência da rainha das linguagens de programação. Praticamente todas as linguagens foram, de alguma forma (umas mais, outras menos) influenciada por C. Praticamente existe uma divisão em A.C. e D.C. (Antes de C e Depois de C) na história das linguagens de programação!

Só por curiosidade, o LangPop coloca a linguagem C como a número 1 em popularidade em suas séries. Confira: http://www.langpop.com/

O que você acha deste índice de popularidade? É confiável? Concorda que C é um marco na história das linguagens de programação? Quais as linguagens que você utiliza? Gosta de C? Sabe C? Comente! 🙂

quarta-feira, 14 agosto, 2013 at 10:10 am Deixe um comentário

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!

terça-feira, 19 junho, 2012 at 1:38 am Deixe um comentário

Aulas de Estruturas de Dados (03, 04, 05 e 06)

Aqui estão disponíveis as aulas 03, 04, 05 e 06 de Estruturas de Dados e seus respectivos exercícios (inseridos nas próprias aulas). As datas de entrega dos exercícios foram comentadas somente em sala de aula. Curtam e estudem. (Lembrando que o material de Estruturas de Dados em C está reduzido pelo pouco tempo disponível devido a troca de professores). Para baixar é só clicar:

Estruturas de Dados – Aula 03
Estruturas de Dados – Aula 04
Estruturas de Dados – Aula 05
Estruturas de Dados – Aula 06

Bons estudos!

terça-feira, 19 junho, 2012 at 1:23 am Deixe um comentário

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!

quarta-feira, 2 maio, 2012 at 12:48 am Deixe um comentário

Posts antigos


Follow Computador de papel: o conteúdo da forma on WordPress.com

Feeds

direto do Twitter

O Computador de Papel

O computador de papel nada mais é do que a tentativa de "humanizar" o computador, trazê-lo para a fantasia lúdica da realidade, fazê-lo compreendido pelos milhares que o usam, mas não o entendem. Nasceu de minhas viagens intelectuais defronte da tela de fósforo um dia em que ele retrucou-me: decifra-me ou te devoro. Para não ser devorado, ousei decifrá-lo. É também onde posto minhas aulas, meus trabalhos, minhas impressões de um pouco de nada sobre coisa nenhuma. É o local onde falo das minhas paixões, entre elas, a música, o cinema, a TI e a ciência. É um espaço de discussão sobre a realidade do computador, sua influência, seus avanços, o exercício do óbvio que é mostrar a sua importância no e para o mundo. Tem o estilo de seu criador, acelerado, com um tom sempre professoral, tresloucado, por vezes verborrágico, insano, nevrálgico, sem arroubos literários, atônito e contemplativo diante da realidade, apaixonado, livre, feito para mostrar que a TI é antes de tudo, feita por gente!

Estatísticas do blog

  • 124,191 cliques e contando...

Agenda de posts

junho 2017
S T Q Q S S D
« maio    
 1234
567891011
12131415161718
19202122232425
2627282930