Aula 03 - Algoritmos

Prévia do material em texto

INE 5201 
LÓGICA DE PROGRAMAÇÃO – ALGORITMOS 
- Conceito de algoritmo 
- Pseudo-código para representar algoritmos 
Aula 03 
2. Algoritmos 
Algoritmo 
INE 5201 – Introdução à algoritmos 
O nome algoritmo vem do nome do matemático 
persa Abu Abdullah Muhammad bin Musa al-
Khwarizmi (780 – 850). 
 
Entre outras coisas ele desenvolveu uma solução 
sistemática para funções lineares e quadráticas. 
 
A palavra 'algarismo' também é derivada de seu 
nome, devido a seu trabalho relacionado a notação 
posicional do sistema de numeração decimal. 
2. Algoritmos 
Algoritmo 
INE 5201 – Introdução à algoritmos 
No século XVIII na Europa, a tradução do nome de al-Khwarizmi deu 
origem à palavra algoritmo. 
O primeiro caso de um algoritmo escrito para um computador foi um 
programa de Ada Byron para a máquina analítica de Charles Babbage. 
 
 
 
 
 
No século XX, as pesquisas de Alan Turing e Alonzo Church 
formalizaram o que é um algoritmo. 
A partir disto foi possível definir quais tipos de problemas um 
algoritmo pode resolver. 
2. Algoritmos 
Algoritmo 
INE 5201 – Introdução à algoritmos 
Algoritmos são formas de codificar procedimentos 
estereotipados. 
 
Para descrever procedimentos estes têm de ser codificados 
de uma forma legível e organizada. 
2. Algoritmos 
Resolução de problemas com o uso do computador; 
 
Necessidade de descrever de forma clara e precisa o 
problema; 
 
Descrever uma sequência de passos que conduzam à sua 
resolução; 
 
 A criação de algoritmos para resolver problemas é uma 
das maiores dificuldades e motivação na programação. 
INE 5201 – Introdução à algoritmos 
2. Algoritmos 
Algoritmo 
INE 5201 – Introdução à algoritmos 
Para organização e descrição de algoritmos usamos 3 estruturas de 
controle: 
 
O bloco ou sequência de comandos: descreve uma sequência de ações 
que devem ser executadas uma após a outra. 
 
A estrutura condicional: usada para descrever uma situação onde 
temos de decidir entre duas formas de agir em função de uma 
situação que poderá ocorrer. 
 
A estrutura de repetição: usada para descrever uma situação onde 
temos de repetir um determinado número de vezes alguma ação até 
que uma situação seja atingida. 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
O teorema da programação estruturada ( Corrado Böhm and 
Giuseppe Jacopini, 1966) é resultado da teoria das linguagens de 
programação. 
 
Ela define que cada rotina computável pode ser implementada em 
uma linguagem que combine os sub-programas em apenas três 
maneiras específicas: 
 
1. Executar um subprograma, depois outro sub-programa (seqüência) 
 
2. Executar um ou dois subprogramas de acordo com o valor de uma 
variável booleana (condição) 
 
3. Executar um subprograma até que uma variável booleana seja 
verdadeira (iteração) 
2. Algoritmos 
Desenho de algoritmos/programas 
• Algoritmo: descrição de uma metodologia que 
conduz à resolução de um problema; 
 
• Programação: codificação precisa desse 
algoritmo, segundo uma linguagem de 
programação; 
INE 5201 – Introdução à algoritmos 
2. Algoritmos 
Desenho de algoritmos/programas 
 
 
 
1. Análise do problema; 
2. Concepção do algoritmo; 
3. Tradução do algoritmo para linguagem de 
programação. 
INE 5201 – Introdução à algoritmos 
PROBLEMA ALGORITMO PROGRAMA 
2. Algoritmos 
Passos para construção de algoritmos 
1. Compreender o problema; 
2. Identificar os dados de entrada; 
3. Identificar os dados de saída; 
4. Determinar o que é preciso para transformar dados de entrada 
em dados de saída: 
1. Usar uma estratégia (ex: divisão e conquista) 
2. Observar regras e limitações 
3. Identificar todas as ações a realizar 
4. Eliminar ambiguidades 
5. Construir o algoritmo; 
6. Testar o algoritmo; 
7. Executar o algoritmo; 
INE 5201 – Introdução à algoritmos 
2. Algoritmos 
Problema: Trocar um pneu 
furado!! 
 
INE 5201 – Introdução à algoritmos 
2. Algoritmos 
2.1 Formas de representação de um algoritmo 
 
2.1.1 Algoritmo: Descrição narrativa 
 
Ex: Trocar um pneu 
 1. Afrouxar ligeiramente os parafusos 
 2. Suspender o carro 
 3. Retirar os parafusos 
 4. Retirar o pneu furado 
 5. Colocar o pneu reserva 
 6. Apertar os parafusos 
 7. Abaixar o carro 
 8. Apertar os parafusos 
INE 5201 – Introdução à algoritmos 
2. Algoritmos (narrativa) 
Ex: Trocar um pneu 
 
 
 1. Afrouxar ligeiramente os parafusos 
 2. Suspender o carro 
 3. Retirar os parafusos 
 4. Retirar o pneu furado 
 5. Colocar o pneu reserva 
 6. Apertar os parafusos 
 7. Abaixar o carro 
 8. Apertar os parafusos 
 
 
 
INE 5201 – Introdução à algoritmos 
Verificar se existe o pneu 
reserva 
Verificar se existe a chave de 
roda e o macaco 
Verificar o aperto 
2. Algoritmos (narrativa -> formalização) 
2.1.1 Algoritmo: Descrição narrativa – migrando para o pseudocódigo 
 
Ex: Trocar um pneu 
 SE (pneu reserva ≠ 0): 
 SE (chave de roda ≠ 0) E (macaco ≠ 0): 
 Afrouxar os parafusos 
 Suspender o carro 
 Retirar os parafusos 
 Retirar o pneu furado 
 Colocar o pneu reserva 
 Apertar os parafusos 
 Abaixar o carro 
 Apertar os parafusos 
 Verificar o aperto dos parafusos 
 SENÃO: 
 Chame o guincho!!!! 
INE 5201 – Introdução à algoritmos 
2. Algoritmos 
Problema: Trocar um pneu 
furado!! 
 
INE 5201 – Introdução à algoritmos 
Outros detalhes ? 
2. Algoritmos 
Problema: Trocar um pneu 
furado!! 
 
INE 5201 – Introdução à algoritmos 
Especificidade ou generalizado ? 
2. Algoritmos 
Problema: Trocar um pneu 
furado!! 
 
INE 5201 – Introdução à algoritmos 
Proteção quanto à 
entradas não previstas ? 
2. Algoritmos 
2.1.2 Algoritmo: Pseudo-código 
 
Forma de representação de algoritmos. 
 
Se assemelha muito ao modo de como os 
programas são escritos em uma linguagem de 
programação. 
 
INE 5201 – Introdução à algoritmos 
2. Algoritmos 
2.1.2 Algoritmo: Pseudo-código 
 
Esta forma de representação permite que os 
algoritmos possam ser traduzidos quase que 
diretamente para uma linguagem de 
programação. 
INE 5201 – Introdução à algoritmos 
2. Algoritmos 
2.1.2 Algoritmo: Pseudocódigo 
Algoritmo 
<nome_do_algoritmo> 
<declaração das variáveis> 
 Entrada: <variáveis_de_entrada> 
 Saída: <variáveis_de_saída> 
<subalgoritmo> 
Início 
<corpo_do_algoritmo> 
Fim 
INE 5201 – Introdução à algoritmos 
2. Algoritmos 
Problema: Fazer um bolo. 
 
INE 5201 – Introdução à algoritmos 
Farinha de trigo 
Ovos 
Açúcar 
Fermento 
Leite 
Manteiga 
RECEITA 
Receita – descrição de uma sequência de passos ou ações que 
resultam em um produto gastronômico... 
2. Algoritmos (narrativa) 
Problema: Como fazer um bolo ? 
 
INE 5201 – Introdução à algoritmos 
Farinha de trigo 
Ovos 
Açúcar 
Fermento 
Leite 
Manteiga 
INSTRUÇÕES 
Algoritmo: (receita de bolo) 
1. Pegar dois ovos; 
2. Quebrar os dois ovos; 
3. Separar as claras; 
4. Bater duas claras; 
5. Adicionar duas gemas; 
6. Adicionar uma xícara de açúcar; 
7. Bater até a massa fica uniforme; 
8. ... 
 
A ordem em que as 
instruções são executadas 
influi no resultado final. 
2. Algoritmos (narrativa -> formalização) 
INE 5201 – Introdução à algoritmos 
Pegar dois ovos; 
Quebrar os dois ovos; 
Separar as claras; 
Bater duas claras; 
Adicionar duas gemas; 
Adicionar uma xícara de açúcar; 
.... 
Se (houverem dois ovos): 
Senão: 
Comprar ovos 
Algoritmo: (bolo) 
Bloco de comando 
Sequência de instruções 
2. Algoritmos (narrativa -> formalização) 
INE 5201 – Introdução à algoritmos 
Pegar doisovos; 
Quebrar os dois ovos; 
Separar as claras; 
Bater duas claras; 
Adicionar duas gemas; 
Adicionar uma xícara de açúcar, farinha e água; 
Misturar tudo; 
 
 
Colocar a massa em um travessa; 
Assar; 
Se (houverem dois ovos): 
Senão: 
Comprar ovos 
Enquanto (a massa estiver não estiver homogênea): 
Bater a massa durante 1 min; 
2. Algoritmos (formalizar) 
INE 5201 – Introdução à algoritmos 
Operadores 
 
Operadores são símbolos que atuam sobre variáveis e valores. 
 
Operadores aritméticos (+ , - , * , / , %, **): 
 
Operadores de comparação (>, <, ==, >=, <=, !=, is, in): 
 
Operadores lógicos (and, or, not): 
 
Operadores de atribuição (=): 
 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
Álgebra Booleana 
 
Desenvolvida pelo inglês George Boole no século XIX. 
 
É considerada a base de toda a matemática 
computacional. 
 
A álgebra de boole envolve operadores essenciais da 
teoria de conjuntos e lógica. 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
Álgebra Booleana 
 
Álgebra Booleana 
0 1 
true false 
não sim 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
Álgebra Booleana: Operadores Lógicos 
 
AND 
OR 
NOT 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
Álgebra Booleana: Operador Lógico - AND 
 
AND 
#Algoritmo média do aluno 
Leia a primeira nota 
Leia a segunda nota 
Calcule a média 
SE (média < 5,74) AND (média > 2,74): 
 escreva (“Aluno em recuperação”) 
.... 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
Álgebra Booleana: Operador Lógico - OR 
 
#Algoritmo Escolhendo o objeto pela cor 
Leia a cor do objeto 
SE (cor == “vermelho”) OR (cor == “branca” ): 
 escreva (“Pode comprar”) 
.... 
OR 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
Álgebra Booleana: Operador Lógico - NOT 
 
#Algoritmo Qualquer objeto que não seja branco 
Leia a cor do objeto 
SE NOT(cor == “branca”): 
 escreva (“compre”) 
ELSE: 
 escreva(“Não compre”) 
NOT 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
A estrutura condicional: usada para descrever uma situação onde 
temos de decidir entre duas formas de agir em função de uma 
situação que poderá ocorrer. 
SE (condição satisfeita): 
 bloco de comandos 1 
SENÃO: 
 bloco de comandos 2 
Resultado de uma 
comparação. 
Dois possíveis resultados: 
verdadeiro ou falso 
Exemplo: 
SE (saldo < 0): 
 escreva (“ Cliente em débito”) 
SENÃO: 
 escreva(“Saldo positivo”) 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
SE (condição satisfeita): 
 bloco de comandos 1 
SENÃO: 
 bloco de comandos 2 
Exemplo: 
#Algoritmo média do aluno 
Leia(media_final) 
Leia(recuperacao) 
media  (media_final + recuperacao) / 2 
SE (media < 5,75): 
 escreva (“Aluno reprovado”) 
SENÃO: 
 escreva (“Aluno aprovado”) 
Estrutura condicional 
2. Algoritmos 
A seguir um exemplo para o cálculo da média da 
nota de 3 provas para cada um dos alunos 
integrantes na turma: 
 
Processo de construção de um script a partir de 
uma ideia de formalização do algoritmo, desde a 
narrativa formal, passando por pseudocódigo 
até o desenvolvimento de um script python. 
INE 5201 – Introdução à algoritmos 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
1. Lê o nome do aluno 
2. Recebe as notas das três provas 
3. Calcule a média 
4. Se a média for maior ou igual a 6.0 escreva – “Aprovado” 
5. Se a média for menor que 6.0 e for maior que 3.0 escreva – “Recuperação” 
6. Senão escreva - “Reprovado” 
7. Repita o passo 1 para o próximo aluno; 
ALGORITMO – NARRATIVA – Linguagem natural 
# Algoritmo - média 
# Variáveis 
 Entrada: nome_do_aluno, nota_1, nota_2, nota_3 
 Saída: Situação 
#subalgoritmo 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
ALGORITMO – FORMALIZANDO – Tentando formalizar o algoritmo 
1. Leia(nome_aluno) 
2. Leia(nota_1) 
3. Leia(nota_2) 
4. Leia(nota_3) 
5. Média  (nota_1 + nota_2 + nota_3) / 3 
6. Se (Média >= 6.0): 
7. Escreva(“Aprovado”) 
8. Ou Se (Média < 6.0) e (Média > 3.0): 
9. Escreva(“Recuperação”) 
10. Senão : 
11. Escreva (“Reprovado”) 
12. Repita o passo 1 
# Algoritmo - média 
# Variáveis 
 Entrada: nome_do_aluno, nota_1, nota_2, nota_3 
 Saída: Situação 
#subalgoritmo 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
ALGORITMO – PSEUDOCÓDIGO 
1. alunos  escreva(“Digite o número de alunos”) 
2. PARA aluno  1 até alunos: 
3. nome_aluno  escreva(“Digite o nome do aluno”) 
4. nota_1  escreva(“Digite a primeira nota”) 
5. nota_2  escreva(“Digite a segunda nota”) 
6. nota_3  escreva(“Digite a terceira nota”) 
7. media  (nota_1 + nota_2 + nota_3) / 3 
8. SE (media >= 6.0): 
9. escreva(“Aprovado”) 
10. OUSE(Média < 6.0) E (Média > 3.0): 
11. escreva(“Recuperação”) 
12. SENÃO : 
13. escreva (“Reprovado”) 
# Algoritmo - média 
# Variáveis 
 Entrada: nome_do_aluno, nota_1, nota_2, nota_3 
 Saída: Situação 
#subalgoritmo 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
ALGORITMO –> SCRIPT - PYTHON 3 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
A estrutura condicional: usada para descrever uma situação onde 
temos de decidir entre duas formas de agir em função de uma 
situação que poderá ocorrer. 
SE (condição satisfeita): 
 bloco de comandos 1 
SENÃO: 
 bloco de comandos 2 
Resultado de uma 
comparação. 
Dois possíveis resultados: 
verdadeiro ou falso 
Exemplo: 
SE (saldo < 0): 
 escreva (“ Cliente em débito”) 
SENÃO: 
 escreva(“Saldo positivo”) 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
SE (condição satisfeita): 
 bloco de comandos 1 
SENÃO: 
 bloco de comandos 2 
Exemplo: 
#Algoritmo média do aluno 
Leia(primeira_nota) 
Leia(segunda_nota) 
media  (primeira_nota + segunda_nota) / 2 
SE (média < 5,75): 
 escreva (“Aluno reprovado”) 
SENÃO: 
 escreva (“Aluno aprovado”) 
Estrutura condicional 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
A estrutura de repetição: usada para descrever uma situação onde 
temos de repetir um determinado número de vezes alguma ação até 
que uma situação seja atingida. 
PARA i  1 ATÉ 100: 
 bloco de comandos 
 
Repete o bloco até esgotar. 
Ou seja executa o bloco de 
comandos 100 vezes. 
Exemplo: 
PARA i  1 ATÉ 20: 
 escreva(i) 
 a  i + 10*i 
 escreva(a) 
2. Algoritmos 
INE 5201 – Introdução à algoritmos 
A estrutura de repetição: usada para descrever uma situação onde 
temos de repetir um determinado número de vezes alguma ação até 
que uma situação seja atingida. 
ENQUANTO (a < b): 
 bloco de comandos 
 
Repete o bloco de comandos 
até que a condição seja falsa. 
 
Exemplo: 
a  126 
b  55600 
ENQUANTO a < b: 
 a  a + 0.65*a 
 escreva(a)