Posts filed under ‘Algoritmos’

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

Anúncios

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

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

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

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.

sábado, 14 abril, 2012 at 1:40 am Deixe um comentário

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

quarta-feira, 4 abril, 2012 at 1:21 am 6 comentários

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

quinta-feira, 11 junho, 2009 at 7:34 pm 10 comentários

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

  • 127,428 cliques e contando...

Agenda de posts

dezembro 2017
S T Q Q S S D
« maio    
 123
45678910
11121314151617
18192021222324
25262728293031