Algoritmos 02 - Construindo Algoritmos

Prévia do material em texto

N575 - Algoritmos e 
Programação de Computadores 
 
Modelo Algorítmico –Construção de Algoritmos 
 
 
Prof. Raphael Torres Santos Carvalho 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
1 
Roteiro 
 Objetivo 
 O que é problema? 
 Lógica 
 Expressando algoritmos 
 Métodos para construção de algoritmos 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
2 
Objetivo 
 Identificar os conceitos básicos e a metodologia para a 
construção de algoritmos. 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
3 
O que é problema? 
Conceito de Problema (Dicionário Michaelis): 
Questão matemática proposta para ser 
resolvida. 
Questão difícil, delicada, suscetível de diversas 
soluções. 
Qualquer coisa de difícil explicação; mistério, 
enigma. 
Dúvida, questão. 
 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
4 
Problema 
Problemas fazem parte do nosso cotidiano. 
Exemplo de problemas cotidianos: 
 Trocar a resistência de um chuveiro. 
 Fazer um bolo. 
 Definir onde almoçar. 
 Calcular a média final 
Sempre que nos deparamos com um problema 
buscamos um procedimento para solucionar o 
mesmo. 
 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
5 
Resolução de um problema 
Resolução de um problema (programa): 
 Compreender o problema 
 Descrever os passos 
 Codificar os passos 
 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
6 
Conceito de lógica 
O que orientou a obtenção dos procedimentos para as 
soluções vislumbradas? A lógica. 
O que é lógica? 
 A lógica é o ramo da Filosofia e da Matemática que estuda os 
métodos e princípios que permitem fazer distinção entre 
raciocínios válidos e não válidos, determinando o processo que 
leva ao conhecimento verdadeiro. 
O uso da lógica é primordial na solução de problemas. 
Com ela é possível alcançar objetivos com eficiência e 
eficácia. 
Ninguém ensina outra pessoa a pensar, mas a 
desenvolver e aperfeiçoar esta técnica, com persistência 
e constância 
 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
7 
Conceito de Algoritmo 
Algoritmo: 
 Sequência finita de passos (instruções) para resolver um 
determinado problema ou realizar um determinada tarefa. 
 Estas tarefas não podem ser redundantes nem subjetivas na 
sua definição, devem ser claras e precisas. 
 Exemplos: 
o Receitas (de comidas típicas, de bebidas) 
o Manual de instalação de equipamentos 
 
Qualquer tarefa que siga determinado padrão pode 
ser descrita por um algoritmo. 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
8 
Premissas e tarefas 
 Para o desenvolvimento de um algoritmo eficiente, é 
necessário obedecermos algumas premissas básicas: 
 Definir ações simples e sem ambiguidade; 
 Organizar as ações de forma ordenada 
 Estabelecer as ações dentro de uma sequência finita de 
passos. 
 Algoritmos são capazes de realizar tarefas como: 
 1. Ler e escrever dados; 
 2. Avaliar expressões algébricas, relacionais e lógicas; 
 3. Tomar decisões com base nos resultados das expressões 
avaliadas; 
 4. Repetir um conjunto de ações de acordo com uma 
condição; 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
9 
Exemplo de Algoritmo 
Preparar uma caipirinha 
1º Algoritmo 
 Entrada de dados: 
o limão 
o açúcar 
o gelo 
o cachaça 
 
 Descrição: 
o Em um recipiente misture o limão, o açúcar , o gelo e a 
cachaça. 
o Servir em um copo com canudinho. 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
10 
Exemplo de algoritmo 
 1º Algoritmo: Execução 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
11 
Exemplo de Algoritmo 
 2º Algoritmo - Caipirinha Cearense Tradicional 
 
 Entrada de dados: 
 01 limão 
 01 colher de sopa de açúcar refinado 
 01 recipiente com gelo picado 
 01 litro de cachaça Ypioca (o que sobrar você bebe depois) 
 faca, coqueteleira, socador, copo baixo, canudinhos. 
 
 Descrição: 
 Lave o limão e corte em fatias. 
 Coloque uma colher de açúcar no recipiente (copo ou coqueteleira). 
 Coloque o limão no recipiente e amasse juntamente com o açúcar com a 
ajuda de um socador. 
 Acrescente o gelo picado e complete com a cachaça. 
 Agite bem e coloque em um copo com um canudo, decorado com uma 
rodela de limão. 
 Nunca acrescente leite condensado à caipirinha. 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
12 
Exemplo de Algoritmo 
 2º Algoritmo: Execução 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
13 
1 
2 
3 
4 5 
6 
7 
Exemplos de algoritmos 
Algoritmo: trocar uma lâmpada 
1. Pegar a lâmpada nova 
2. Pegar a escada 
3. Posicionar a escada embaixo da lâmpada queimada 
4. Subir na escada com a lâmpada nova 
5. Retirar a lâmpada queimada 
6. Colocar a lâmpada nova 
7. Descer da escada 
8. Ligar o interruptor 
9. Guardar a escada 
10. Jogar a lâmpada velha no lixo 
 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
14 
Exemplos de algoritmos 
 Algoritmo: Sacar dinheiro 
1. Ir até o caixa eletrônico 
2. Colocar o cartão 
3. Digitar a senha 
4. Solicitar o saldo 
5. Se o saldo for maior ou igual à quantia desejada, 
sacar a quantia desejada; caso contrário sacar o valor 
do saldo 
6. Retirar dinheiro e cartão 
7. Sair do caixa eletrônico 
 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
15 
Desenvolvimento de algoritmos 
 É importante ressaltar que qualquer tarefa que siga 
determinado padrão pode ser descrita por um algoritmo. 
 Entretanto ao montar um algoritmo, primeiro divide-se o 
problema apresentado em três fases fundamentais: 
 
Entrada Processamento Saída 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
16 
Desenvolvimento de algoritmos 
 ENTRADA: São os dados de entrada do algoritmo 
 PROCESSAMENTO: São os procedimentos utilizados para chegar ao 
resultado final 
 SAÍDA: São os dados já processados 
 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
17 
Representação dos algoritmos 
 No computador: um algoritmo será implementado em uma 
linguagem de computação gerando um programa, o qual visa 
instruir a máquina a executar determinadatarefa. 
 Computador não é dotado da capacidade de tomar decisões com 
base em premissas. 
 Portanto, não podemos instruir um computador com sentenças 
dúbias. 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
18 
Representação dos algoritmos 
Algoritmo é uma sequência, que não permite 
ambiguidade, de passos finitos, passível de ser executada 
com um esforço finito em tempo finito e que acaba para 
qualquer entrada (inclusive erro). 
O algoritmo tem como papel fundamental ser o elo de 
ligação entre dois mundos (real e computacional). 
A atividade de programação tem início com a construção 
do algoritmo. 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
19 
Representação dos algoritmos 
 Linguagem Narrativa 
 Linguagem Gráfica (fluxogramas) 
 Pseudo-linguagem 
 Linguagem de Programação (C, C++, Java, PHP...) 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
20 
Descrição Narrativa 
 Os algoritmos são descritos na linguagem natural como 
utilizada nos exemplos anteriores. 
 Qual a vantagem? 
 Não há a necessidade de aprender nenhum novo conceito. 
 Qual a desvantagem? 
 Em virtude da ambigüidade presente na linguagem natural a 
descrição narrativa é passível de mais de uma interpretação. 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
21 
Descrição Narrativa 
 Exemplo de ambigüidade presente em uma sentença na 
linguagem natural é: 
“O policial escutou o barulho da porta.” 
 
 Esta frase pode ter pelo menos três interpretações: 
 1 - O policial escutou o barulho produzido pela porta. 
 2 - O policial estava junto à porta e escutou o barulho. 
 3 - O policial escutou o barulho que veio através da porta 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
22 
Métodos de Representação dos 
algoritmos 
 Algoritmo sob o enfoque computacional, como já foi 
mencionado, não podemos utilizar uma descrição narrativa 
para representar um algoritmo. 
 Sendo assim, veremos três métodos para representação de 
algoritmos: 
 Linguagem gráfica (fluxograma) 
 Pseudo-linguagem (português estruturado) 
 Linguagem de programação 
 Os métodos tem regras e disponibilizam um conjunto reduzido 
de palavras/símbolos passiveis de serem utilizados (rigidez 
sintática). 
 Objetivo: obter uma consistência semântica para a eliminação 
da ambiguidade intrínseca linguagem natural. 
 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
23 
Fluxograma 
 Diagrama para representação gráfica de um processo. 
 Um conjunto de símbolos unidos por setas que indicam o fluxo do 
processo. 
 Vantagens: 
 Permite visão completa do fluxo do processo 
 Facilidade de entendimento e tradução para outras linguagens 
 Desvantagem: 
 Dependendo da complexidade do problema, pode se tornar 
muito extenso, dificultando o entendimento da representação. 
 Exemplos de símbolos: 
lave o 
limão 
mais 
uma? 
1 
início 
Ação: Decisão: Conectores: 
Início ou Fim: fim 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
24 
Fluxograma 
 Exemplo 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
25 
lave o 
limão 
1 
início 
não 
fim 
corte o limão 
em fatias 
coloque o açúcar 
no recipiente mais 
uma? 
1 
sim 
coloque o limão 
no recipiente 
2 
2 
amasse o limão 
e o açúcar 
coloque gelo picado 
no recipiente 
complete o recipiente 
com cachaça 
misture bem 
os ingredientes 
sirva em um 
copo com canudo 
3 
3 
enfeite o copo 
com limão 
Pseudo-linguagem 
Maneira intermediária entre a linguagem natural e uma 
linguagem de programação de representar um algoritmo. 
Utiliza um conjunto restrito de palavras-chave, em geral 
na língua nativa do programador, que tem equivalentes 
nas linguagens de programação. 
Não requer todo a rigidez sintática necessária numa 
linguagem de programação, permitindo que o aluno se 
detenha na lógica do algoritmos e não no formalismo da 
sua representação. 
Normalmente, são versões ultra reduzidas de linguagens 
de alto nível. 
 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
26 
Pseudo-linguagem 
 Exemplo: 
 
leia (x, y) 
Se x > y então 
escreva (“x é maior”) 
senão 
se y > x então 
escreva (“y é maior”) 
senão 
escreva (“x e y são iguais!) 
fim-se 
fim-se 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
27 
Exercício 
 Calcular a média final dos alunos da cadeira de Algoritmos. Os 
alunos realizarão quatro provas: 1ª NP1, 2ª NP1, 1ª NP2 e 2ª 
NP2. 
 Quais são os dados de entrada? 
 Qual será o processamento a ser utilizado? 
 Quais serão os dados de saída? 
 Implemente o algoritmo para esse problema. 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
28 
Linguagem de Programação C 
/* média de três números */ 
#include <stdio.h> 
#include <stdlib.h> 
 
int main(void) { 
 float a, b, c, m; 
 
 printf("digite três números: "); 
 scanf("%f %f %f", &a, &b, &c); 
 m = (a + b + c) / 3.0; 
 printf("média = %f\n", m); 
 return 0; 
} 
 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
29 
Linguagem de Programação C 
 Evolução 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
30 
Linguagem 
Natural 
Linguagem 
C++ / Java 
Linguagem 
C 
Linguagem 
Assembly 
Linguagem 
de Máquina 
... 
Linguagem Natural: 
 
 Calcule a raiz de 9. 
 
Linguagem de Máquina: 
 
 0100 0011 1100 1000 
 1111 0010 0011 1110 
 0100 0011 1000 0000 
 1100 1001 1110 1000 
 0100 0011 1100 1000 
 1111 0010 0011 1110 
 0100 0011 1000 0000 
 1100 1001 1110 1000 
 0100 0011 1100 1000 
 1111 0010 0011 1110 
 . . . 
Linguagem Assembly: 
 
0000: mov bx, [FFE6] 
0003: and bx, 1 
0006: cmp bx, 0 
0009: je 0000 
000C: mov ax, [FFE4] 
000F: nop 
0010: mov dx, ax 
0013: mov bl, al 
0015: cmp al 
0017: xor ax 
. . . 
Linguagem C/C++: 
 
#include <math.h> 
 int main(void) { 
 double x = 9.0; 
 printf(“%lf”, sqrt(x)); 
} 
Linguagem de Programação 
 São traduzidas em linguagem de máquina (compostas por 0s e 
1s) que podem ser processadas pelo computador 
 Livres de ambigüidades → única interpretação 
 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
31 
Linguagem de Alto Nível 
TRADUTOR 
Linguagem de Baixo Nível 
C, C++, Java, PHP,... 
Compilador 
Interpretador 
Linguagem de Máquina 
Resoluçãode um problema 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
32 
Entendimento 
do Problema 
Algoritmo 
de Solução 
Tradução do Algoritmo 
para uma Linguagem 
de Programação 
Ser Humano 
Tradução para a 
Linguagem de Máquina 
Execução 
do Programa 
Computador 
Dúvidas? 
N
5
7
5
 -
 A
lg
o
ri
tm
o
s 
e 
P
ro
gr
am
aç
ão
 d
e 
C
o
m
p
u
ta
d
o
re
s 
33