ALGORITMOS - Bem-vindo! « ACME! Cybersecurity Researchangel.acmesecurity.org/~adriano/lc/2009/4-algoritmos-LC-quimica... · •!Quais são as regras e comandos. •!Quais Tipos e

1 - Algoritmos

Prof. Dr. Adriano Mauro Cansian 1

ALGORITMOS

Adriano Mauro Cansian

André Proto

UNESP - São José do Rio Preto

______________________________

© Adriano Mauro Cansian! 2

Introdução (1)

•! Para desenvolver um software: –!representar uma abstração da realidade.

•!Abstração por quê ? –!Porque um software não é algo palpável, “real”.

–!Ele simula uma realidade.

•!Por exemplo: quando se usa o MSN, o software está criando uma realidade de que todas as pessoas estão se comunicando ali, ou seja, dentro do MSN.

1 - Algoritmos



Introdução (2)

•! Então, tecnicamente, para fazer um software temos que: –!Representar uma realidade.

–!Selecionar de dados que estejam relacionados com o problema a ser resolvido

–!Processar os dados.

–!Obter os dos resultados esperados.

(Lembrar da figura do microondas)

O Que são “dados” afinal?

•! Tudo que o software vai processar e devolver. –!Exemplo: quando anexo uma foto a um Email,

o programa tem que saber como representar aqueles dados da foto dentro da mensagem de Email.

•!Depois, do outro lado, o software tem que saber representar novamente os dados, para mostrar a foto.


1 - Algoritmos



Dados & Operações

•! Para resolução de um problema: –!escolher uma abstração da realidade.

•!Decidir o que é relevante para o problema.

–!informação: é um conjunto de dados. –!comportamento: é um conjunto de operações.

•! A forma como se representa informação e suas

operações estão ligadas


Como representar dados

•! Como representar dados? –!depende do que se vai fazer.

•!não é uma tarefa muito trivial.

•!não existe uma única solução.

•!não existe receita.

–!a solução de um problema no computador é um modelo.

–!a construção do modelo pode ter muitos níveis de detalhe. Mais complexo = mais detalhes.

1 - Algoritmos



Como fazer as operações?

•! A decisão é influenciada pelo problema. •! Muitas questões dependentes da tecnologia que

vai usar. –!Por exemplo: Windows no PC ou Celular Iphone ?.

•! Programador ! focaliza o problema

–!Decisões de nível mais baixo: deixadas para os projetistas do equipamento computacional.

–!Programador usa linguagens que se concentrar nas características do problema: alto nível.


Algoritmo (1)

•! É um processo sistemático para a resolução de problemas:

–!Dois aspectos básicos no estudo de algoritmos " ”correção” e ”análise”.

–!Correção: exatidão do método empregado.

–!Análise: verificar a eficiência do algoritmo (ver se a “coisa” realmente funciona).

1 - Algoritmos



Algoritmo (2)

•! O algoritmo tem que fornecer uma “saída” a partir de uma “entrada”. –!Ou seja, obter o resultado do problema.

–!Durante o processo, manipula dados gerados a partir de sua entrada.

Lembrar que não se deve pensar apenas em dados de entrada e saída matemáticos. Um movimento de mouse é um dado de entrada.


Algoritmo (3)

•! Um algoritmo é projetado em termos de “Tipos de Dados”.

•! O que é um “tipo de dados” ?

•! É tudo que o computador vai “ler”, “escrever” e processar.

–!Pode ser um número digital no teclado, ou pode ser um sensor de infravermelho de um robô para detectar um obstáculo.

•! Veremos mais sobre ler e escrever mais adiante.

1 - Algoritmos


Algoritmo (4)

•! Para implementar um algoritmo em uma Linguagem de programação?

•! Temos que saber: –!Como representá-lo nesta linguagem.

•! Quais são as regras e comandos.

•!Quais Tipos e Operações suportadas pelo computador.

–!Como representar os dados. •!Usando-se “Estruturas de Dados”.



Algoritmos & Estruturas de Dados

•! Resolução de um Problema –!Algoritmo

•!Representação dos passos para resolver um problema.

–!Estrutura de Dados •!Representação da informação, ou seja, dos dados

que serão tratados.

1 - Algoritmos


Algoritmos


Algoritmos - conceitos (1)

•! A palavra algoritmo, à primeira vista, parece-nos estranha.

•! Embora possua designação desconhecida, fazemos uso constantemente de algoritmos em nosso cotidiano

•! Algoritmos freqüentemente encontrados:

–! instruções para se utilizar um aparelho eletrodoméstico;

–! uma receita para preparo de algum prato;

–! guia de preenchimento para declaração do imposto de renda;

–! a regra para determinação de máximos e mínimos de funções por derivadas sucessivas;

–! a maneira como as contas de água, luz e telefone são calculadas mensalmente;

1 - Algoritmos



Algoritmos - conceitos (2)

–! “Um conjunto finito de regras que provê uma seqüência de operações para resolver um tipo de problema específico.” [KNUTH]

–! “Seqüência ordenada, e não ambígua, de passos que levam à solução de um dado problema.” [TREMBLAY]

–! “Processo de cálculo, ou de resolução de um grupo de problemas semelhantes, em que se estipulam, com generalidade e sem restrições, as regras formais para a obtenção do resultado ou da solução do problema.” [AURÉLIO]


Por que precisamos de algoritmos? (1)

–!“A noção de algoritmo é básica para toda a programação de computadores”.

•! [KNUTH - Professor da Universidade de Stanford, autor da coleção “The art of computer programming”]

1 - Algoritmos



Por que precisamos de algoritmos? (2)

•! A importância do algoritmo está no fato de termos que especificar uma seqüência de

passos lógicos, para que o computador possa executar uma tarefa qualquer.

•! O computador não tem vontade própria.

•! Faz apenas o que mandamos. –!Com um algoritmo, podemos conceber uma

solução para um dado problema, independente de uma linguagem computacional específica.


Algoritmo (1) •! Um texto contendo comandos (instruções)

–!Devem ser executados na ordem especificada.

–!Corresponde a representação concreta.

–!Execução: o algoritmo é um evento dinâmico ! ele evolui no tempo.

–!Ele “roda”.

1 - Algoritmos



Algoritmo (2)

•! Uma dificuldade na concepção e no entendimento de algoritmos é o relacionamento dos aspectos estático e dinâmico.

–! como entender as estruturas dinâmicas das possíveis

execuções do algoritmo a partir da estrutura estática.

–!É o que veremos mais adiante como “rastreio”.


Algoritmo (3)

•! Deve utilizar Estruturas Básicas de controle –!Formas naturais de pensar, e adequadas à

construção de algoritmos inteligíveis.

–!Sempre em “alto nível”.

–!Por exemplo:

SE ......... ENTÃO .......... SENÃO ........

1 - Algoritmos



Algoritmo (5)

•! Em todo evento deve haver um comportamento, com estados iniciais e efeitos resultantes. –!Cada vez que acontecer um padrão de

comportamento, o evento ocorre.

–!Exemplo: se digitar “1” então ligar o alarme.


Algoritmo (6)

•! .Possui um caráter imperativo.

•! Deve-se dar “ordens” no algoritmo: –!Uma ação no algoritmo: um comando, ou ordem

(“faça” / “execute” / “some” / “imprima”).

–!É uma ordem executável para conseguir um certo efeito desejado.

1 - Algoritmos


Características dos algoritmos

Características e formas de representação


Características dos algoritmos

•! Todo algoritmo deve apresentar algumas características básicas: 1.! Não dar margem à dupla interpretação (não ser

ambíguo); 2.! Ter capacidade de receber dado(s) de entrada; 3.! Poder gerar informações de saída; 4.! Ser efetivo, ou seja todas as etapas

especificadas no algoritmo devem ser alcançáveis em um tempo finito;

5.! Ter fim.

1 - Algoritmos



Formas de apresentação

•! Algoritmos podem ser representados, dentre outras maneiras, por: –!DESCRIÇÃO NARRATIVA

–!FLUXOGRAMA

–!LINGUAGEM ALGORÍTMICA

(Pseudo-linguagem, parecida com a linguagem de programação que iremos usar)


Descrição narrativa (1)

•! Faz-se uso da língua nativa para descrever algoritmos.

•! Exemplo: Receita de Bolo •! Providencie manteiga, ovos, 2 Kg de farinha, leite, etc. •! Misture os ingredientes; •! Despeje a mistura na fôrma de bolo;

•! Leve a fôrma ao forno; •! Espere 20 minutos; •! Retire a fôrma do forno;

•! Deixe esfriar; •! Prove.

1 - Algoritmos



Descrição narrativa (2)

•! Vantagens: •!A língua nativa é bastante conhecida por nós;

•!Desvantagens: –!Imprecisão;

–!Pouca confiabilidade •!Por causa da imprecisão;

–!Extenso •!Normalmente, escreve-se muito, para dizer

pouca coisa.


Fluxograma (1)

•!Utilização de símbolos gráficos para representar algoritmos.

•!No fluxograma existem símbolos padronizados para início, entrada de dados, cálculos, saída de dados, fim, dentre outros.

1 - Algoritmos



Fluxograma (2)

Início

Leia NUM

DOBRO ! NUM*2

Escreva DOBRO

Fim

Início do algoritmo

Entrada do número

Cálculo do dobro do número

Apresentação do resultado

Fim do algoritmo


Fluxograma (3)

•! Vantagens: –!Uma das ferramentas mais conhecidas; –!Figuras dizem muito mais que palavras; –!Padrão mundial (não depende da língua).

•! Desvantagens: –!Pouca atenção aos dados, não oferecendo

recursos para descrevê-los ou representá-los; –!Complica-se à medida que o algoritmo cresce.

1 - Algoritmos


Linguagem algorítmica


Linguagem Algorítmica (1)

•! Consiste na definição de uma pseudo-linguagem de programação para representar algoritmos;

•! Comandos e instruções são em português ou inglês. •! Exemplo:

Algoritmo CALCULA_DOBRO •! início

•! Leia NUM

•! DOBRO ! 2 * NUM

•! Escreva DOBRO

•! fim

1 - Algoritmos



Linguagem Algorítmica (2) •! Vantagens:

–! Independência da solução. •! Trata-se de solução lógica apenas.

•! Não interessa quem vai executar.

–! Usa o português como linguagem de base;

–! Pode-se definir quais e como os dados vão estar estruturados;

–! Passagem quase imediata do algoritmo para uma linguagem de programação qualquer.

•! Desvantagens: –! Exige a definição de uma linguagem não real para trabalho;

–! Não padronizado.

Um ambiente para escrever algoritmos

Funcionamento de nosso computador de processamento algorítmico

1 - Algoritmos



Um ambiente para escrever algoritmos Unidade Central de Processamento

(2) Unidade Lógica e Aritmética

(3) Unidade de Controle

(1) Dispositivo de entrada

(5) Dispositivo de saída

(4) Memória Principal

Trajeto de dados

Trajeto de sinais de controle


Componentes (1)

•! (1) Dispositivo de entrada –! Na maioria das vezes o teclado, mas pode ser um mouse, disco,

scanner, leitor de código de barras, dentre outros:

–! É o meio pelo qual os dados serão introduzidos em nosso computador;

•! (2) Unidade Lógica e Aritmética (ULA): –! Parte responsável pelas operações matemáticas e avaliações

lógicas;

•! (3) Unidade de Controle (UC): –! Exerce controle sobre as demais partes do nosso computador;

–! É uma verdadeira gerente que distribui tarefas às outras unidades;

1 - Algoritmos



Componentes (2)

•! (4) Memória: –!Guarda o algoritmo a ser executado e os dados a

serem utilizados.

–!Todo dado fornecido ao computador, bem como o resultado de suas operações, ficam (temporariamente) guardados na memória;

•! (5) Dispositivo de Saída –!Vídeo, impressora, discos, CD, e outros: –!É o meio que se dispõe para apresentação dos

resultados obtidos.


Funcionamento (1)

•! Todos os computadores, independentemente dos seus tamanhos, são conceitualmente semelhantes ao esquema da figura anterior –! Há algumas diferenças, mas não trataremos aqui.

•! Resumidamente, podemos afirmar que existem 4 (quatro) operações básicas que qualquer computador deve executar: –! operações de entrada e saída

–! operações aritméticas –! operações lógicas e relacionais

–! movimentação de dados entre os vários componentes

•! Vejamos cada uma delas…

1 - Algoritmos



Funcionamento (2)

•! Operações de entrada e saída: –!Ler dados do teclado e escrever dados na tela

são exemplos destas operações. –!Elas servem para introduzir dados na memória

do nosso computador, e exibir dados que já estejam lá armazenados;

•! Operações aritméticas: –!São utilizadas na realização de operações

matemáticas, tais como adição, subtração, multiplicação e divisão.


Funcionamento (3)

•! Operações lógicas e relacionais: –! Têm aplicabilidade em comparações, testes de condições

lógicas –! Por exemplo: 2 > 6 ? X > Y ?

•! Movimentação de dados entre os vários componentes: –! As operações aritméticas são executadas na Unidade

Lógica e Aritmética, necessitando da transferência dos dados para essa unidade, e da volta do resultado final para ser guardado na memória.

1 - Algoritmos



Resolvendo um problema manualmente

•! Suponha que desejamos resolver o seguinte problema: –! A partir de dois números, que serão informados,

calcular a adição dos mesmos.

•! Seria bem provável que fosse utilizados os passos a seguir:

a.! saber quais são os números; b.! calcular a soma dos números; c.! responder à questão com o valor do resultado.


Resolvendo o problema em nosso computador

•! Vejamos como seria resolvido esse mesmo problema em termos das operações básicas citadas anteriormente: –! a) operação de entrada de dados dos números ;

–! b1) movimento do valor dos números entre a memória e a ULA;

–! b2) operação aritmética de somar os 2 números;

–! b3) movimentação do resultado da ULA para guardar na memória;

–! c) operação de saída do resultado, que está guardado na memória, para o dispositivo de saída desejado.

1 - Algoritmos


Escrita de algoritmos


Escrita de algoritmos

•!Resumidamente, pode-se dizer que escrever algoritmos ou, em última análise, programar, consiste em: –! “Dividir qualquer problema em muitos

pequenos passos, usando uma ou mais das operações básicas possíveis”.

1 - Algoritmos



Passos, comandos e linguagem (1)

•! Passos que compõem o algoritmo são denominados de comandos.

•! Lembrando: Os comandos de uma linguagem de programação podem ser: –!De “Linguagens de baixo nível”. –!De “Linguagens de alto nível”.


Passos, comandos e linguagem (2)

•! A seqüência de operações básicas anteriores, para resolver o problema de adicionar dois números, está em uma linguagem de baixo nível para o nosso computador “hipotético”.

•! Em uma linguagem de alto nível teríamos uma seqüência de comandos assim:

•!Leia X,Y

•!SOMA " X + Y

•!Escreva SOMA

1 - Algoritmos


Estruturas Básicas da Construção de Algoritmos


Estruturas básicas

•! Existem 3 estruturas básicas de controle, nas quais se baseiam os algoritmos: –!Sequenciação, decisão e repetição.

•!Detalharemos cada uma delas, a seguir:

1 - Algoritmos



Seqüenciação (1)

•! Os comandos do algoritmo fazem parte de uma seqüência, onde é importante a ordem na qual se encontram, pois serão executados um de cada vez, estritamente, de acordo com essa ordem.

•! De uma forma genérica, poderíamos expressar uma seqüência da seguinte maneira:

Comando-1 Comando-2 Comando-3

: Comando-n


Seqüenciação (2)

•! Tem-se uma sequencia de comandos na qual os comandos serão executados na ordem em que aparecem.

•! O comando na posição (x) só será executado após a execução do de ordem (x-1), ou seja, o anterior.

•! Assim: o 3o só será executado após o 2o, e assim por diante.

•! Todo algoritmo é uma seqüência. •! A sequenciação é aplicada quando a solução do

problema pode ser decomposta em passos individuais.

1 - Algoritmos



Decisão ou seleção (1)

•! Essa estrutura também é conhecida por estrutura condicional. •! A execução de um ou mais comandos depende da veracidade de uma

condição ser verificada. •! Vejamos o funcionamento:

Se <condição> Então

<comando-1> Senão

<comando-2>

•! Ou seja, SE a <condição> for verdadeira (então) será executado o <comando-1> e, em caso contrário (senão), teremos a execução de <comando-2>.


Decisão ou seleção (2)

•! A decisão deve ser sempre usada quando há a necessidade de testar alguma condição e, em função desta condição, tomar uma atitude (realizar uma ação).

•! Em nosso dia-a-dia, estamos sempre tomando decisões, vejamos um exemplo:

•! Se tiver dinheiro suficiente, então vou jantar no Sal e Brasa;

Caso contrário (senão), vou comer um sanduba no Chalé;

1 - Algoritmos



Repetição ou iteração (1)

•! Estrutura também é conhecida por “looping” ou laço.

•! A repetição permite que tarefas individuais sejam repetidas um número determinado de vezes, ou tantas vezes quanto uma condição lógica seja satisfeita.

•! Vejamos alguns exemplos: a)! Vou atirar pedras na vidraça até quebrá-la; b)! Baterei cinco pênaltis; c)! Enquanto tiver saúde e dinheiro, vou viajar de carro.


Repetição ou iteração (2)

•! No exemplo (a), vai-se repetir a ação de atirar pedras na janela até que seja satisfeita a condição de quebrar a janela.

•! No exemplo (b), haverá a repetição da atitude de bater um pênalti um número determinado de vezes (condição = cinco).

•! No exemplo (c), a condição que me permitirá continuar viajando de carro é ter dinheiro e saúde.

1 - Algoritmos



Conclusão das estruturas básicas

•! A utilização combinada dessas 3

estruturas descritas vai permitir expressar, usando qualquer que seja a linguagem (ferramenta), a solução para uma gama muito grande de problemas.

•! Todas as linguagens de programação oferecem representantes dessas

estruturas.


Refinamentos sucessivos (1)

•! Um algoritmo é considerado completo se todos os seus comandos forem do

entendimento do seu executor.

•! Um comando que não for do entendimento do executor terá que ser desdobrado em novos comandos, que constituirão um refinamento do comando inicial. –!E assim sucessivamente, até que os comandos

sejam entendidos pelo destinatário.

1 - Algoritmos




•! Por exemplo, o algoritmo para calcular a média aritmética de dois números, pode ser escrito da seguinte forma:

Algoritmo CALCULA_MÉDIA Início

Receba os dois números Calcule a média dos dois números

Exiba o resultado

Fim



•! Podemos desdobrar o comando “Calcule a média dos dois números” em:

Soma os dois números

Divida o resultado por 2

•! Após esse refinamento, o algoritmo pode ser considerado completo, a menos que o destinatário não saiba fazer as operações de adição e divisão, ou não seja capaz de entender diretamente algum comando.

1 - Algoritmos




•! O algoritmo estando completo, podemos reescrevê-lo, inserindo o refinamento na posição do comando que foi refinado.

Algoritmo CALCULA_MÉDIA

Início Avise o que o programa faz.

Solicite os números ao usuário. Receba (leia) os dois números.

Some os dois números.

Divida o resultado por 2. Exiba o resultado.

Fim


Conclusão sobre refinamentos sucessivos

•! Reescrever um algoritmo completo, com os refinamentos sucessivos inseridos nos seus devidos lugares, permite ter uma visão global de como o algoritmo deve ser executado.

•! À medida que o algoritmo passa a ser maior e mais complexo, esta visão global torna-se menos clara e, neste caso, um algoritmo apresentado com os refinamentos sucessivos separados oferece uma melhor abordagem para quem precisar entendê-lo.

1 - Algoritmos



Resumo

•! Até aqui vimos:

–!Definições de algoritmos.

–!Características e modelos descritivos dos algoritmos.

–!Linguagem algorítmica.

–!Ambiente, funcionamento e escrita dos algoritmos.

–!Estruturas básicas: seqüenciação, decisão, seleção e repetição

–!Refinamentos sucessivos.

Documents

ALGORITMOS - Bem-vindo! « ACME! Cybersecurity Researchangel.acmesecurity.org/~adriano/lc/2009/4-algoritmos-LC-quimica... · •!Quais são as regras e comandos. •!Quais Tipos e