conceitos fundamentais de algoritmos

Prévia do material em texto

*
*
*
Conceitos Fundamentais de Algoritmos
e Programação para iniciantes
joa@deinfo.ufrpe.br
REFERÊNCIA: Material dos Profs. Reinaldo Gomes (UFRPE) e Robson Fidalgo (UFPE)
www.xiscanoe.org
*
*
*
Algoritmo Textual Informal
Modo de preparo:
Bata a margarina, as gemas e o açúcar até ficar cremoso
Junte o leite, o coco e a farinha e continue batendo
Acrescente o fermento e, por último, as claras em neve
Unte uma forma com manteiga e leve ao forno para assar
Quão cremoso?!?
De uma vez só?!?
Quanto tempo?!?
Quanto tempo?!?
*
*
*
Algoritmo Textual Informal Refinado
Modo de preparo:
Bata a margarina, as gemas e o açúcar por 15 minutos
Junte o leite, o coco e a farinha e continue batendo por mais 15 minutos
Acrescente 20 g de fermento e, por último, as claras em neve
Unte uma forma com manteiga e leve ao forno para assar por 30 minutos
*
*
*
Algoritmo Gráfico-Textual Informal 
Montagem de um Aeromodelo
Material
Cola especial para plásticos
Estilete
Lixas finas
Durex ou fita crepe
Pregador de roupas, elásticos
*
*
*
Algoritmo Gráfico-Textual Informal
Identificação das peças
*
*
*
Algoritmo Gráfico-Textual Informal
Instruções
Leia e entenda as instruções antes de começar a montagem
Lave as peças com água e detergente. Na lavagem serão removidos desmoldantes e sujeiras, que dificultam a colagem e a pintura. Faça isto dentro de uma bacia, para evitar perder peças pequenas, que porventura se soltem
Encontre as peças que devem ser usadas na primeira parte da montagem (figura do slide anterior) 
Lixe as peças com cuidado eliminando as rebarbas
...
*
*
*
Algoritmo Textual Informal 2
Troca de pneu
“Abra o porta-mala e verifique se todos acessórios estão lá. Em caso negativo, feche o porta-malas e peça carona a alguém. Em caso positivo, retire o triângulo, posicione-o a cerca de 30 m do carro, e, depois, retire o estepe e o macaco. Levante o carro... “
*
*
*
Algoritmo Gráfico Informal 
Troca de pneu
*
*
*
Algoritmo Gráfico Semi-formal 
Troca de pneu (Fluxograma)
Não
Sim
*
*
*
Algoritmo Textual Formal 
Troca de pneu
 abre(porta_malas)
 Se acessorio_ok = FALSO
 Então 
 fecha(porta_malas)
 espera_carona()
 Senão
 pega_triangulo()
...
*
*
*
Algoritmo: Problemas Complexos 
Problema da Torre de Hanói
Seja a seguinte situação:
deve-se mover todos os discos do primeiro eixo para o terceiro mantendo-se a ordem original
em cada movimento, pode-se mover apenas um disco
um disco nunca poderá ser sobreposto por outro maior
*
*
*
Algoritmo: Problemas Complexos 
Passo 1:
mova disco menor para terceiro eixo
*
*
*
Algoritmo: Problemas Complexos 
Passo 2:
mova disco médio para segundo eixo
*
*
*
Algoritmo: Problemas Complexos 
Passo 3:
mova disco menor para segundo eixo
*
*
*
Algoritmo: Problemas Complexos 
Passo 4:
mova disco maior para terceiro eixo
*
*
*
Algoritmo: Problemas Complexos 
Passo 5:
mova disco menor para primeiro eixo
*
*
*
Algoritmo: Problemas Complexos 
Passo 6:
mova disco médio para terceiro eixo
*
*
*
Algoritmo: Problemas Complexos 
Passo 7:
mova disco menor para terceiro eixo
*
*
*
Algoritmo: Problemas Complexos 
Seqüência de passos completa:
Passo 1: mova disco menor para terceiro eixo
Passo 2: mova disco médio para segundo eixo
Passo 3: mova disco menor para segundo eixo
Passo 4: mova disco maior para terceiro eixo
Passo 5: mova disco menor para primeiro eixo
Passo 6: mova disco médio para terceiro eixo
Passo 7: mova disco menor para terceiro eixo
*
*
*
Algoritmo: CONCEITO
O que é um ALGORITMO?
OBS.: Não existe um algoritmo para construir algoritmos
a criação de um algoritmo é um exercício de criatividade (conhecimento) e experiência (técnica e prática)
*
*
*
O que é Programação? = ABSTRAÇÃO!
A realidade é complexa e rica em detalhes!
*
*
*
Abstração
Realidade
O que você abstrai dessa realidade?
*
*
*
Abstração
O que é abstração?
*
*
*
Abstração
Abstração
=
Operação mental que observa a realidade e captura apenas os aspectos relevantes para um contexto
*
*
*
*
*
*
*
*
*
*
*
*
MASLOW
*
*
*
Abstração
A tarefa de programar sistemas computacionais envolve o exercício constante da abstração da realidade e sua codificação em uma linguagem de programação
Sistema de Locadora de Veículo
Abstração
+
Programação
*
*
*
Sistema Computacional
O que é um Sistema Computacional?
*
*
*
Sistema Computacional
Sistema 
Computacional
Software
Hardware
Peopleware
*
*
*
Programação de Sistema Computacional
A programação de um sistema computacional pode ser resumida em 3 passos básicos
Entrada
Saída
Dispositivo
de Entrada
Dispositivo de Saída
Memória
UCP
*
*
*
Programação de Sistema Computacional
Exemplo 1 – Exibir a média de dois números
Entrada
Saída
Dispositivo
de Entrada
Dispositivo de Saída
Memória
UCP
6 , 8
(6 + 8) / 2
7
*
*
*
Programação de Sistema Computacional
Exemplo 2 – Exibir se o aluno está aprovado ou reprovado
Entrada
Saída
Dispositivo
de Entrada
Dispositivo de Saída
Memória
UCP
Ana, 5, 3
Se (5+3)/2>=7
 aprovado
Senão
 reprovado
Ana, reprovado
*
*
*
Programação de Sistema Computacional
Tipos de Linguagens de Programação
1 - Totalmente codificadas em binário (0´s e 1´s)
2 - Usa instruções simbólicas para representar os 0´s e 1´s
3 - Voltadas para facilitar o raciocínio humano
Baixo Nível
Alto Nível
(1)
(2)
(3)
Linguagem 
Assembly
(
Mnem
ô
nica
)
LOAD R1, val1 
LOAD R2, val2 
ADD R1, R2 
STORE R1, val2 
Linguagem 
de 
M
á
quina
0010 0001 1110
0010 0010 1111
0001 0001 0010
0011 0001 1111
Linguagem 
de 
Alto N
í
vel
 val2 = val1+val2
*
*
*
Noções de Lógica
Exemplos de aplicação da lógica 
O quarto está fechado e que meu livro está no quarto. Então, preciso primeiro abrir o quarto para pegar o livro
Rosa é mãe de Ana, Paula é filha de Rosa, Júlia é filha de Ana. Então, Júlia é neta de Rosa e sobrinha de Paula
Todo mamífero é animal e todo cavalo é mamífero. Então, todo cavalo é animal
Todo mamífero bebe leite e o homem bebe leite. Então, todo homem é mamífero e animal (mas não é um cavalo)
*
*
*
Atividade 1 (10min)
Resolva os seguintes problemas de lógica
P1 – Uma lesma deve subir um poste de 10m de altura. De dia sobe 2m e à noite desce 1m. Em quantos dias atingirá o topo do poste?
P2 - Três gatos comem três ratos em três minutos. Cem gatos comem cem ratos em quantos minutos?
P3 - O pai do padre é filho do meu pai. O que eu sou do Padre?
P4 - Se um bezerro pesa 75 kg mais meio bezerro, quanto pesa um bezerro inteiro?
*
*
*
Atividade 1 (10min)
Resolva os seguintes problemas de lógica
P5 – Qual o próximo número da seqüência 7,8,10,13,17,?
P6 – Um pai de 80kg e suas 2 filhas (40kg cada), precisam sair de uma ilha com um barco. Porém a capacidade do barco é de 80kg. Como farão para sair da ilha?
P7 – Usando uma jangada, um camponês precisa atravessar uma cabra, um leão e um fardo de capim para a outra margem do rio. A jangada só tem lugar para ele e mais outra coisa. O que ele deve fazer para atravessar o rio com seus pertences intactos? 
*
*
*
RESPOSTAS - Atividade 1
Respostas
R1 - 9(nove) dias. No nono dia a lesma sobe 2(dois) metros, atinge o topo e evidentemente não desce 1 metro
R2 – 3 (três) minutos
R3 – Tio
R4 – 150 (cento e cinqüenta) kg 
R5 – 22
R6 – Vão asduas filhas. Uma delas volta. O pai sai. A outra filha volta. As duas filhas saem juntas.
R7 - Primeiro leve a cabra, volte e pegue o capim; deixe o capim e leve a cabra de volta; deixe a cabra e leve o leão, depois é só voltar e pegar a cabra.
*
*
*
Noções de Lógica
 Em Lógica um conceito importante é o de “Proposição”
Você sabe o que é uma PROPOSIÇÃO?
*
*
*
Noções de Lógica
Proposição: é um enunciado verbal, ao qual deve ser atribuído, sem ambigüidade, um valor lógico verdadeiro (V) ou falso (F). 
Exemplos de proposições: 
Robson Fidalgo é Professor (V) 
3 + 5 = 10 (F) 
5 < 8 (V)
Contra-exemplos de Proposições:
Onde você vai ? 
3 + 5 
Os estudantes jogam vôlei. (quais ?)
*
*
*
Noções de Lógica
Operações Lógicas: são usadas para formar novas proposições a partir de proposições existentes. 
Considerando p e q duas proposições genéricas, pode-se aplicar as seguintes operações lógicas básicas sobre elas
Definindo a prioridade:
Usar parênteses Ex:((p v q)^(~q)) ou
Obedecer (~) > (^) > (v)
Operação
Símbolo
Significado
Negação
~
Não
Conjunção
^
E
Disjunção
v
OU
*
*
*
Noções de Lógica
Exemplos de aplicação das operações lógica
Considere:
p = 7 é primo = (V)
q = 4 é impar = (F)
Então:
4 NÃO é impar = ~q = (~F) = (V)
7 NÃO é primo = ~p = (~V) = (F)
7 é primo E 4 NÃO é impar = p ^ ~q = (V ^ (~F)) = (V ^ V) = (V)
7 é primo E 4 é impar = p ^ q = (V ^ F) = (F)
4 é impar E 7 é primo = q ^ p = (F ^ V) = (F)
4 é impar E 7 NÃO é primo = q ^ ~p = (F ^ (~V)) = (F ^ F) = (F)
*
*
*
Noções de Lógica
Exemplos de aplicação das operações lógica (Cont.)
Considere:
p = 7 é primo = (V)
q = 4 é impar = (F)
Então:
7 é primo OU 4 NÃO é impar = p v ~q = (V v (~F)) = (V v V) = (V)
7 é primo OU 4 é impar = p v q = (V v F) = (V)
4 é impar OU 7 é primo = q v p = (F v V) = (V)
4 é impar OU 7 NÃO é primo = q v ~p = (F v (~V)) = (F v F ) = (F)
*
*
*
Noções de Lógica
Exemplos de aplicação das operações lógica
Resumindo:
Ou seja:
Não (~) troca o valor lógico. Se é F passa a ser V e vice-versa
E (^) só tem valor V quando as duas proposições forem V, basta uma proposição ser F para o resultado ser F
OU (v) só tem valor F quando as duas proposições forem F, basta uma proposição ser V para o resultado ser V
*
*
*
Atividade 2
Considerando p = V e q = F, resolva as seguintes expressões lógicas
~p
~q
p ^ q
p v q
(~p) ^ q
(~p) v q
p ^ (~q)
p v (~q)
(~p) ^ (~q)
(~p) v (~q)
*
*
*
RESPOSTAS - Atividade 2
Considerando p = V e q = F, resolva as seguintes expressões lógicas
~p = F
~q = V
p ^ q = F
p v q = V
(~p) ^ q = F
(~p) v q = F
p ^ (~q) = V
p v (~q) = V
(~p) ^ (~q) = F
(~p) v (~q) = V
*
*
*
Lógica de Programação & Algoritmo
O que é
Programação 
de computadores?
 INSTRUÇÕES
*
*
*
Instruções Delimitadoras
Servem para especificar o início e o fim do algoritmo.
início
 ...
fim
*
*
*
Declaração de Variáveis
Utilizado para especificar os nomes e os respectivos tipos das variáveis necessárias no algoritmo
declare <variáveis>: <tipo>;
onde:
<variáveis> - lista de nomes de variáveis separados por vírgula
<tipo> - inteiro, real, caracter, string, lógico 
*
*
*
Declaração de Variáveis
Exemplos:
declare a,b,c: real;
declare nome: string;
declare sexo: caracter;
declare pratica_esporte: lógico;
*
*
*
Bloco de Comentário
Serve para explicar um determinado trecho do algoritmo, para torna-lo mais claro, facilitando seu entendimento por outras pessoas ou posteriormente.
{ <comentário> }
Exemplo:
{ Isto é um exemplo de comentário }
*
*
*
Instrução de Entrada
Usada para ler dados de entrada do algoritmo.
leia(<variáveis>);
onde:
<variáveis> - conterão os dados lidos.
*
*
*
Instrução de Entrada
Exemplos:
leia(a,b,c);
leia(nome);
leia(sexo);
leia(pratica_esporte);
*
*
*
Instrução de Saída
Usada para mostrar os resultados do processamento dos dados de entrada.
escreva(<resultados>);
onde:
<resultados> - geralmente é o conteúdo de uma ou mais variáveis com a resposta do problema.
*
*
*
Instrução de Saída
Exemplos:
escreva(“O valor de D é: ”, D);
escreva(nome, sexo);
escreva(“Pratica esporte.”);
*
*
*
Instrução de Atribuição
Utilizado para atribuir um determinado valor a uma variável.
<variável> <expressão>;
onde:
<variável> - nome de uma variável
<expressão> - um valor do mesmo tipo da variável ou uma expressão lógica ou aritmética.
*
*
*
Instrução de Atribuição
Exemplos
D B^2-4*A*C;
nome “Paulo”;
Pratica_Esporte TRUE; 
Sexo ‘M’;
*
*
*
Estruturas de Controle
Baseado na lógica estruturada, Bohn e Jacopini provaram que apenas três estruturas são suficientes para explicar a solução de qualquer problema, inclusive tornando-os estruturados e mais legíveis.
*
*
*
Estruturas de Controle
São elas:
Estrutura Seqüencial: os comandos ou instruções vão sendo executados na ordem em que aparecem no algoritmo.
*
*
*
Estruturas de Controle
Estrutura de Repetição: comandos são executados repetidas vezes até que uma condição de parada seja satisfeita
*
*
*
Estruturas de Controle
Estrutura de Seleção: Conforme o resultado de uma expressão lógica, determinados comandos são executados e outros não, caracterizando assim uma seleção de comandos
TRUE
FALSE
*
*
*
Instruções de Seleção
Tipo simples:
se <sentença> então 
		<comandos>;
fim-se
OBS.:
 <comandos> serão executados apenas se <sentença> resultar em TRUE. 
*
*
*
Instruções de Seleção
Exemplo:
se A>0 então 
		B A + 1;
 A 0; 
fim-se
*
*
*
Instruções de Seleção
Tipo composto:
se <sentença> então 
		<comandos1>;
senão
		<comandos2>;
fim-se
OBS.:
 <comandos1> serão executados apenas se <sentença> resultar em TRUE. Em caso contrário, <comandos2> serão executados. 
*
*
*
Instruções de Seleção
Exemplo:
se A>B então 
		B A + 1;
 A 0; 
senão
	 A 0; 
		B A + 1;
fim-se
*
*
*
Instruções de Repetição
Enquanto / Fim-Enquanto
enquanto <sentença> faça
		<comandos>;
fim-enquanto;
OBS.:
 <comandos> serão executados enquanto <sentença> resultar em TRUE. 
*
*
*
Instruções de Repetição
Exemplo: 
enquanto A>0 faça
		leia(B);
 escreva(B);
 A A - 1;
fim-enquanto;
*
*
*
Instruções de Repetição
Repita / Até
repita
		<comandos>;
até <sentença>;
OBS.:
 <comandos> serão executados até que <sentença> resulte em TRUE. 
*
*
*
Instruções de Repetição
Exemplo:
repita
		leia(B);
 escreva(B);
 A A - 1;
até A<1;
*
*
*
Instruções de Repetição
Para / Até / Fim-Para
para <variável> <inicial> até <final> faça
	<comandos>;
fim-para;
OBS.:
 <variável> - contador do tipo inteiro
<inicial> - valor inicial da variável 
<final> - valor final da variável
*
*
*
Instruções de Repetição
Exemplo:
{ Comandos para escrever 10 vezes uma frase na tela do computador }
para i 1 até 10 faça
	escreva(“Último tipo de repetição”);
fim-para;
*
*
*
Estrutura de um Algoritmo
Um algoritmo em Portugol tem a seguinte estrutura:
início
	<declaração de variáveis>
	<inicialização de variáveis>
	<corpo lógico do algoritmo>
fim
*
*
*
Lógica de Programação & Algoritmo
Estruturas básicas de um algoritmo: 
Seqüência – Início/Fim
Define uma estrutura onde as instruções serão executadas na ordem que aparecem. 
Seleção – Se-Então/Senão
Define uma estrutura condicional que dada a sua avaliação (V ou F) determina qual “caminho” do algoritmo será executado
Repetição – Repita, Enquanto ou Para
Define uma estrutura de iteração condicional (V ou F) oucontada (pré-definida) de instruções
*
*
*
Lógica de Programação & Algoritmo
Algoritmo para ligar de um telefone público - Seqüência
Início
Tirar o fone do gancho;
Ouvir o sinal de linha;
Introduzir o cartão;
Teclar o número desejado;
Conversar;
Desligar;
Retirar o cartão;
Fim.
Este algoritmo só usa uma estrutura de seqüência “Início/Fim”
*
*
*
Lógica de Programação & Algoritmo
Algoritmo para ligar de um telefone público – Seleção
	E se o telefone público estiver com defeito?
Início
Tirar o fone do gancho;
Se ouvir o sinal de linha, então
Introduzir o cartão;
Teclar o número desejado;
Conversar;
Desligar;
Retirar o cartão;
Senão 
ir para o próximo telefone;
Fim.
Este algoritmo usa uma estrutura de decisão “Se-então/Senão”
*
*
*
Lógica de Programação & Algoritmo
Algoritmo para ligar de um telefone público – Repetição
E se o próximo telefone público também estiver com defeito?
Início
Repita
Tirar o fone do gancho;
Se ouvir o sinal de linha então
Introduzir o cartão;
Teclar o número desejado;
Conversar;
Desligar;
Retirar o cartão;
Senão 
ir para o próximo telefone;
Até ouvir o sinal de linha 
Fim.
Este algoritmo usa uma estrutura de repetição “Repita/Até”
*
*
*
Lógica de Programação & Algoritmo
Algoritmo para ligar de um telefone público – Repetição
E se o telefone chamado estiver com defeito?
E se o telefone chamado estiver ocupado?
E se acabarem os créditos do cartão telefônico?
E se ...?
Um algoritmo SEMPRE sofre melhorias sucessivas.
(Técnica de refinamentos sucessivos)
*
*
*
Fluxogramas - Exemplo 1
Achar o valor da expressão: D = B2 - 4AC.
Início
Ler A, B, C
D = B^2 - 4*A*C
1
1
Escrever D
Fim
*
*
*
Fluxogramas: Exemplo 2
Achar o maior de dois números A e B.
Início
Ler A, B
A=B
A<B
 A>B
Comparar
A com B
Escrever:
“A e B iguais”
Fim
Escrever:
“A é maior”
Escrever:
“B é maior”
*
*
*
Português Estruturado - Exemplo 1
Achar o valor da expressão: D = B2 - 4AC.
	Ler os valores de A, B e C
	Calcular a expressão D = B2 - 4AC
	Mostrar o resultado desse cálculo
*
*
*
Português Estruturado - Exemplo 2
Achar o maior de dois números A e B.
	Ler dois números A e B
	Comparar A com B
	Mostrar o resultado dessa comparação
*
*
*
Pseudocódigo - Exemplo 1
Achar o valor da expressão: D = B2 - 4AC.
Início
	Declare A,B,C,D; { Declaração de variáveis }
	Leia(A,B,C);
	D B^2 - 4*A*C; { Operação de atribuição }
	Escreva(D);
Fim.
 
*
*
*
Pseudocódigo - Exemplo 2
Achar o maior de dois números A e B.
	 Início
	Declare A,B; { Declaração de variáveis }
	Leia(A,B);
	Se A = B Então Escreva(“A e B iguais”);
	Senão Se A>B Então Escreva(“A é maior”);
		 Senão Escreva(“B é maior”);
		 Fim-Se
	Fim-Se 
Fim.
*
*
*
Atividade 3
Reescreva corretamente o algoritmo abaixo
Algoritmo aprovação
Início
Obter as 2 notas do aluno;
Repita
Se Média do aluno >=7, então
Repita
Informar que o aluno está REPROVADO;
Até Média < 7
Senão Média >= 7
Informar que o aluno está APROVADO;
Até último aluno;
Fim.
*
*
*
RESPOSTA - Atividade 3
Algoritmo aprovação
Início
Repita
Obter as 2 notas do aluno;
Se Média do aluno >=7, então
Informar que o aluno está APROVADO
Senão
Informar que o aluno está REPROVADO;
Até último aluno
Fim
*
*
*
#! /usr/bin/perl -w
my $file = $ARGV[0];
open NEW, $file;
my $numero_g=0;
my $numero_c=0;
my $numero_total=0;
my $um=0;
while (<NEW>) {
 if (/\>/) {
#	if ($um == 2) {
#	 last;
#	}
#	$um++;
	next;
 }
# print $_;
 chomp;
 for ($i=0; $i<length($_); $i++) {
	$numero_total++;
	if (uc(substr($_,$i,1)) eq "C" ) {
	 $numero_c++;
	}
	if (uc(substr($_,$i,1)) eq "G") {
	 $numero_g++;
	}	
 }
}
print "Total de Gs : $numero_g \n";
print "Total de Cs : $numero_c \n";
print "Total de bases : $numero_total \n";
print "Total de GCs (%) : " . (($numero_g + $numero_c) / $numero_total) * 100;
*
*
*
UM EXERCÍCIO
Construa um algoritmo para escolher as duas maiores laranjas de um balaio
*
*
*
Outros exercícios...
1) leia um número inteiro e mostre uma mensagem indicando se este número é par ou ímpar, e se é positivo ou negativo
2) leia quatro números inteiros e encontre a média aritmética simples entre as que correspondem a números pares. Lembre-se que não pode haver divisão por zero
3) leia 4 notas, calcule a média dessas e escreva: Reprovado (média < 5), Recuperação (média >= 5 e < 7) e Aprovado (média >= 7)
*
*
*
mais exercícios...
4) leia a idade de um nadador e exiba sua categoria segundo as regras: A(5 até 7); B(8 até 10); C(11 até 13); D(14 até 18) e E( Idade > 18)
5) leia dois números inteiros, uma operação matemática (+,-,*,/) e faça o calculo destes números segundo a operação lida
6) leia o nome e a idade de três pessoas e informe o nome da pessoa mais velha e o nome da pessoa mais nova. Considere que não existem idades iguais
*
*
*
ainda mais exercícios...
7) leia os números inteiros A e B e informe se A é múltiplo, divisor ou nada de B
8) leia três números e mostre-os em ordem crescente
9) leia uma milhar e informe se esse número é palíndromo. Exemplos de números palíndromos: 9889, 7337 e 2002
10) leia um número inteiro entre 20 e 59 e mostre seu extenso. Exiba um erro se o número estiver fora do intervalo
*
*
*
AMBIENTES/LINGUAGENS DE PROGRAMAÇÃO
*
*
*
AMBIENTES/LINGUAGENS DE PROGRAMAÇÃO
*
*
*
Próximos passos?
Praticar a leitura e entendimento de Algoritmos de sua área de aplicação
Aprender uma Linguagem de Programação para Computadores
Programação!