ALG01 Conceitos

Prévia do material em texto

Algoritmos
ALG01 - CONCEITOS 
BÁSICOS
Algoritmos 
Universidade CEUMA
2
LÓGICA
 É a arte de bem pensar.
 Ciência das formas de pensamento – estuda a
correção do raciocínio (forma mais complexa do
pensamento).
 Visa a ordem da razão - Coloca ordem no
pensamento.
 É a ciência que estuda as leis e critérios de validade
que regem o pensamento e a demonstração, ou
seja, ciência dos princípios formais do raciocínio.
 Pode ser utilizada em diferentes situações no dia-a-
dia.
3
LÓGICA
 Exemplos:
1) Todo mamífero é um animal. (premissa 1)
Todo cavalo é um mamífero. (premissa 2)
Portanto todo cavalo é um animal. (conclusão)
2) A gaveta está fechada. (premissa 1)
A caneta está dentro da gaveta. (premissa 2)
Precisamos primeiro abrir a gaveta, para depois
pegar a caneta. (conclusão)
4
LÓGICA
 Fatores que influenciam a lógica:
– calma
– conhecimento
– vivência
– versatilidade
– experiência
– criatividade
– ponderação
– responsabilidade e etc.
5
LÓGICA
 Aplicação na programação Lógica de Programação
 Isto significa o uso correto das leis do pensamento, da
ordem da razão e de processos de raciocínio e
simbolização formais na programação de computadores,
objetivando a racionalidade e o desenvolvimento de
técnicas que cooperem para a produção de soluções
logicamente válidas e coerentes, que resolvam com
qualidade os problemas que se deseja programar.
 O objetivo principal da Lógica de Programação é a
construção de algoritmos.
6
ALGORITMOS
É o conceito central da lógica de programação. Pois, 
ela consiste basicamente da construção de 
algoritmos.
7
ALGORITMOS
• Estão presentes no dia-a-dia. Ex.:
– Tomar banho;
– Instruções para o uso de um aparelho 
eletrodoméstico;
– Receita de preparo de algum prato;
– Trocar pneu de um carro;
– Sacar dinheiro de um caixa eletrônico;
Como???
8
ALGORITMOS – Conceitos
• “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]
• Um dos princípios da computação é a divisão dos sistemas
computacionais em:
• Hardware – parte física (unidades de entrada, saída e
armazenamento.
• Software – parte lógica (softwares básico e utilitários).
9
ALGORITMOS – Importância
– É necessária fazer a especificação de uma seqüência
de passos lógicos para que o computador possa
executar uma determinada tarefa;
– O computador não possui vontade própria, faz
apenas o que foi programado;
– Com uma ferramenta algorítmica, é possível
conceber uma solução para um dado problema,
independente da linguagem específica e até mesmo
do próprio computador.
10
ALGORITMOS –
Características
– ter fim;
– não dar margem à dupla interpretação (não
ambíguo);
– capacidade de receber dado(s) de entrada do
mundo exterior;
– poder gerar informações de saída para o mundo
externo ao do ambiente do algoritmo;
– ser efetivo (todas as etapas devem ser
alcançáveis em um tempo finito).
ALGORITMOS – Conclusões
- o algoritmo corresponde a uma descrição de um
padrão de comportamento, expresso em termos de
um conjunto finito, ordenado e não ambíguo de
ações, para resolver um problema.
- Para resolver um problema é necessário escolher
uma abstração da realidade, ou seja interpretá-la,
usando para isso a definição de um conjunto de
dados que representa essa situação real.
- A abstração da realidade é a captura do que existe
de mais relevante em uma situação real, tornando
possível a construção de modelos que podem ser
implementados nos computadores, por meio de
uma Linguagem de Programação (LP).
11
12
ALGORITMOS – Conclusões
É o Frajola???
É um gatinho???
É um mamífero???
O que é isto???
É um animal peludo???
É um felino???
Abstração
“a beleza está nos 
olhos de quem a vê”
O resultado de uma operação mental de abstração
depende não tanto do fenômeno observado, mas do
interesse do observador.12
ALGORITMOS – Conclusões
- dados a serem processados pelo computador
representam uma abstração da parte da realidade,
ou seja, representam algumas características
selecionadas das entidades do mundo real,
necessárias para a solução de um determinado
problema.
• Um dos princípios do funcionamento do computador é:
13
14
 Aplicação 01:
Um senhor, bastante gordo, esta numa das margens de 
um rio com uma raposa, uma duzia de galinhas e um 
saco de milho. O senhor pretende atravessar o rio com 
suas cargas, num barco a remo que só comporta o 
senhor e uma das cargas.
 o senhor não pode deixar em uma das margens, 
sozinhos, a raposa e a galinha, nem a galinha e o 
milho.
Como resolver este problema? Como escrever um 
algoritmo que oriente este senhor a realizar o seu 
intento?
Escreva as instruções na sequencia em que elas 
devem ser executada.
ALGORITMOS
15
 Solução:
1. Atravesse as galinhas.
2. Retorne sozinho.
3. Atravesse a raposa.
4. Retorne com as galinhas.
5. Atravesse o milho.
6. Retorne sozinho.
7. Atravesse as galinhas.
Como saber que a primeira instrução deve ser a 
travessia das galinhas?
ALGORITMOS
16
 Para definir qual seria a primeira instrução, existem
apenas três possibilidades. Verifica-se o que aconteceria
ao se escolher determinada instrução:
se o homem atravessasse primeiro o milho, a
raposa devoraria as galinhas;
se o homem atravessasse primeiro a raposa, as
galinhas comeriam o milho;
 se o homem atravesse primeiro as galinhas, a 
raposa não comeria o milho. 
Neste caso, foi utilizada a técnica da exaustão: como o 
número de alternativas era pequeno, todas elas foram 
analisadas uma a uma.
ALGORITMOS
17
 Aplicação 02:
Como obter exatamente 4 litros de agua dispondo de dois 
recipientes com capacidades de 3 litros e 5 litros?
ALGORITMOS
18
 Solução:
1. Encha o recipiente de 3 litros.
2. Transfira o conteúdo do recipiente de 3 litros para o recipiente 
de 5 litros.
3. Encha o recipiente de 3 litros.
4. Com o conteúdo do recipiente de 3 litros, complete o recipiente 
de 5 litros.
5. Esvazie o recipiente de 5 litros.
6. Transfira o conteúdo do recipiente de três litros para o 
recipiente de 5 litros.
7. Encha o recipiente de 3 litros.
8. Transfira o conteúdo do recipiente de 3 litros para o recipiente 
de 5 litros.
 Essa é uma outra técnica que consiste em tentar resolver casos 
particulares da questão ou resolver a questão para dados menores 
do que os dados que foram fixados. Como: 4 = 3 + 1 ou 4 = 5 – 1
Há outras soluções? Existe alguma solução que realize
a mesma tarefa com uma quantidade menor de instruções?
ALGORITMOS
19
ALGORITMOS – Exemplo
– Vamos nos colocar na situação de um cozinheiro que 
para fazer certos pratos, precisa seguir uma receita.
• Exemplo: Receita de Bolo
– Providencie manteiga, ovos, 2 Kg de massa, 
etc.
– Misture os ingredientes
– Unte a fôrma
– 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
– Experimente
20
ALGORITMOS 
– Mas o que um cozinheiro tem a ver com
algoritmo e com programação?
A receita deve ser seguida exatamente da maneira
como se apresenta.
Você poderia imaginar que o cozinheiro pudesse
despejar a mistura na fôrma antes de juntar os
ingredientes? É impossível, concorda? Logo a
seqüência das ações precisaser respeitada para
obtermos um produto final.
21
ALGORITMOS 
Então:
 Na medida em que precisamos especificar
uma seqüência de passos, é necessário
utilizar ordem,ou seja, “pensar com ordem”,
portanto precisamos utilizar lógica.
22
ALGORITMOS 
 Um algoritmo tem por objetivo representar
mais fielmente o raciocínio envolvido na
lógica de programação e, dessa forma,
permitir abstrair de uma série de detalhes
computacionais, que podem ser
acrescentados mais tarde.
 Foco no que é importante: a lógica da
construção de algoritmos.
23
ALGORITMOS - Princípios 
– São formas de resolução de um problema,
através da especificação passo-a-passo de
como resolvê-lo.
– A noção de algoritmo é básica em
computação, mas pode ser aplicada a vários
contextos. Como o exemplo do cozinheiro.
24
ALGORITMOS - Princípios 
– Contexto Administrativo
Verifique preenchimento do formulário
Se (preenchimento correto) então
Arquive o documento
Forneça o protocolo
Se não
Lamente
Peça que o cliente compre outro formulário
Despeça-se educadamente do cliente
25
ALGORITMOS - Princípios 
– Logo, percebe-se que o conceito de algoritmo
associado ‘a área de computação, pode ser
entendido, no seu sentido mais amplo, como
sinônimo de processo, rotina ou procedimento, e
nesse sentido, ele se insere em qualquer
contexto.
– E mais, algoritmos só se aprende:
• construindo algoritmos
• testando algoritmos
26
• A sintaxe: é um conjunto de regras que define a 
forma de uma linguagem, estabelecendo como são 
compostas as suas estruturas básicas (palavras).
• A semântica: descreve o significado de
construções sintáticas válidas. Geralmente uma LP
é descrita informalmente, utilizando-se linguagem
natural (inglês, português, etc).
Sintaxe e Semântica
27
• A sintaxe de uma LP é formada por regras léxicas e 
regras sintáticas:
– As regras léxicas descrevem as combinações
válidas de caracteres que formam os tokens da LP 
palavras reservadas, identificadores, operadores, 
etc). 
– Exemplo de regras léxicas para a linguagem Pascal:
Sintaxe e Semântica
28
– Já as regras sintáticas descrevem como os tokens
podem ser combinados para formar instruções 
válidas (comandos, expressões, subrotinas, etc).
– Exemplo de regras sintáticas para a linguagem 
Pascal:
Sintaxe e Semântica
29
– Narrativa (Textual):
• Faz-se uso do português para descrever
algoritmos.
• Exemplo: Trocar uma lâmpada
Pegue uma escada
Posicione-a embaixo da lâmpada
Busque uma lâmpada nova
Suba na escada
Retire a lâmpada velha
Coloque a lâmpada nova
ALGORITMOS – Representação
30
– Vantagem:
• Fácil utilização e fácil entendimento por utilizar a
própria língua.
– Desvantagem:
• Falta de padronização;
ALGORITMOS – Representação
31
– Fluxograma. Exemplo:
ALGORITMOS – Representação
32
– Fluxograma
• Vantagens:
– Uma das ferramentas mais conhecidas;
– Figuras dizem muito mais que palavras;
– Padrão mundial.
– Aproxima-se mais de uma linguagem de
programação.
• Desvantagens:
– É preciso que todos os envolvidos entendam a
simbologia;
– Pouca atenção aos dados, não oferecendo
recursos para descrevê-los ou representá-los;
– Complica-se à medida que o algoritmo cresce.
ALGORITMOS – Representação
33
– Linguagem Algorítmica
• Consiste na definição de uma pseudolinguagem
de programação, cujos comandos são em
português, para representar algoritmos;
• Exemplo
Algoritmo CALCULA_DOBRO
Início
Leia NUM
DOBRO = 2 * NUM
Escreva DOBRO
Fim
ALGORITMOS – Representação
34
– Linguagem Algorítmica: possui uma estrutura, onde
há áreas delimitadas por marcadores (ou
delimitadores) que sinalizam o que pode ser
realizado.
• Estrutura geral:
Algoritmo Nome do algoritmo
Declaração de constantes, tipos e variáveis 
(dados)
Início
atribuições
seqüências de comandos
estruturas de controle
comandos de E/S
Fim
ALGORITMOS – Representação
35
– Linguagem Algorítmica
• Vantagens:
– Independência física da solução (solução lógica 
apenas);
– Usa o português como 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.
ALGORITMOS – Representação
36
Algoritmo "<nome do algoritmo>"
var
< declaração de variáveis>
inicio
< lista de comandos>
fimalgoritmo
ALGORITMOS – Representação: 
Visual G
37
1.O algoritmo sempre deve possuir um nome.
2.É importante descrever o objetivo do algoritmo.
3.Iniciar o algoritmo com a palavra Início.
4.Descrever a entrada de dados.
5.Para facilitar a leitura e compreensão, utilizar espaços de 
tabulações (identação) nos blocos de instruções.
6.Utilizar somente um verbo por instrução.
7.Utilizar frases (instruções) simples e curtas para facilitar o 
entendimento.
8.Enumerar cada uma das instruções.
9.Inserir comentários explicativos para as instruções, 
principalmente quando estiver programando.
10.Destacar as palavras que indicam ações ou condições a serem 
executadas ou seguidas, como por exempro: Ler, escrever, se, 
enquanto, faça e outras.
11.Descrever a saída de dados.
12.Encerrar o algoritmo com a palavra Fim.
Representação: regras importantes
38
Nome: Média
Objetivo: Calcular a média de um aluno e apresentar a mensagem 
“aprovado” ou “reprovado”.
Entrada de dados: Notas do 1º e 2º bimestre (Nota1 e Nota2)
Saída de dados: Exibir a média e resultado “aprovado” ou 
“reprovado”
Início
1. Ler a nota do primeiro bimestre (Nota1)
2. Ler a nota do segundo bimestre (Nota2)
3. Calcular a média Media = (Nota1 + Nota2)/2
4. Se Media >= 6,0 então
4.1 imprimir “aprovado”
senão
4.2 imprimir “reprovado”
fim se
5. Imprimir o valor da Media
Fim
ALGORITMOS – aplicando as 
regras importantes
39
ALGORITMOS
– ESTRUTURAS CHAVES DA CONSTRUÇÃO DE 
ALGORITMOS
• Existem 3 estruturas básicas de controle nas 
quais se baseiam os algoritmos:
– Sequênciação;
– Decisão;e,
– Repetição.
40
ALGORITMOS – Sequênciação 
– Os comandos do algoritmo fazem parte de uma
sequência;
– é relevante a ordem na qual se encontram os
mesmos;
– serão executados um de cada vez, estritamente, de
acordo com essa ordem.
Comando-1
Comando-2
Comando-3
:
Comando-n
41
ALGORITMOS – Sequênciação 
– Todo algoritmo é uma sequência;
– Tem-se uma sequênciação de n comandos na qual
os comandos serão executados na ordem em que
aparecem;
– o comando de ordem i+1 só será executado após a
execução do de ordem i (o 3º só será executado após
o 2º);
– A sequenciação é aplicada quando a solução do
problema pode ser decomposta em passos
individuais.
42
ALGORITMOS – Decisão 
– Também conhecida por seleção ou estrutura
condicional;
– Há a subordinação da execução de um ou mais
comandos à veracidade de uma condição;
Se <condição> Então
<comando-1>
Senão
<comando-2>
43
ALGORITMOS – Decisão 
– Se a <condição> for verdadeira será executado o
<comando-1>;
– caso contrário, teremos a execução do <comando-2>;
– A decisão deve ser sempre usada quando há a
necessidade de testar alguma condição e em função da
mesma tomar uma atitude;
– No dia-a-dia, estamos sempre tomando decisões.
Exemplos:
• Se tiver dinheiro suficiente, então vou almoçar em um
bom restaurante.
• Caso contrário (senão), vou comer um sanduíche na
lanchonete da esquina.
44
ALGORITMOS – Repetição 
– Também conhecida por “looping” ou laço;
– Permite que tarefas individuais sejamrepetidas um
número determinado de vezes ou tantas vezes
quantas uma condição lógica permita;
– Exemplos:
a) vou atirar pedras na vidraça até quebrá-la;
b) baterei cinco pênaltis;
c) enquanto tiver saúde e dinheiro, vou desfrutar a 
vida.
45
ALGORITMOS – Repetição 
– 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 (cinco).
– No exemplo (c), a condição que me permitirá continuar 
desfrutando a vida é ter dinheiro e saúde.
– A utilização combinada dessas 3 estruturas descritas vai 
permitir expressar, usando qualquer que seja a 
ferramenta, a solução para uma gama muito grande de 
problemas.
– Todas as linguagens de programação oferecem 
representantes dessas estruturas.
46
– Um algoritmo é considerado completo se os seus
comandos forem do entendimento do seu
destinatário;
– Caso um comando não seja do entendimento do
destinatário, ele terá que ser desdobrado em novos
comandos;
– Estes novos comandos constituirão um refinamento
do comando inicial, e assim sucessivamente, até que
os comandos sejam entendidos pelo destinatário.
ALGORITMOS – Refinamentos 
Sucessivos
47
– 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
– Desdobrando o comando “Calcule a média dos dois números”:
Soma os dois números
Divida o resultado por 2
ALGORITMOS – refinamentos 
sucessivos
48
– 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.
Algoritmo CALCULA_MÉDIA
Início
Receba os dois números
Soma os dois números
Divida o resultado por 2
Exiba o resultado
Fim
ALGORITMOS – Refinamentos 
Sucessivos
49
– 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;
– Neste caso, um algoritmo apresentado com os
refinamentos sucessivos separados oferece uma
melhor abordagem para quem precisar entendê-lo.
ALGORITMOS – Refinamentos 
Sucessivos
50
ALGORITMOS – Resolvendo
– Suponha que se queira resolver o seguinte problema:
• a partir de dois números que serão informados, 
calcular a soma dos mesmos.
– Se você fosse encarregado de efetuar essa tarefa, 
seria bem provável que utilizasse os passos a seguir:
1. Identificar as variáveis que afetam o problema. 
Neste caso, são os números;
2. Identificar as relações, regras e validações 
sobre as variáveis. Neste caso, a soma dos 
números;
3. Realizar o processamento necessário;
4. Apresentar o resultado.
51
ALGORITMOS – Exercícios
– Cite alguns algoritmos que podemos encontrar na
vida quotidiana.
– Suponha que temos um robô a nossa disposição.
Esse robô precisa ser ensinado a fazer determinadas
tarefas. Para ensiná-lo, vamos fazer uso do
português para passar-lhe as instruções necessárias
à execução de cada atividade. Escreva os passos
necessários para o robô:
a) encher uma bacia com água;
b) Fazer uma ligação de um telefone fixo;
c) calcular a sua idade daqui a 20 anos;
d) calcular a média de um aluno com 3 notas;
e) Fazer um suco de laranja.