Universidade Federal do Espírito Santo
Programação II
Professora: Norminda Luiza
Lógica
Podemos relacionar a lógica com a
“correção do pensamento”, pois uma de
suas preocupações é determinar quais
operações são válidas e quais não são
fazendo análises das formas e leis do
pensamento.
Poderíamos dizer também que é a arte de bem
pensar, que é a ciência das formas do
pensamento. Visto que a forma mais complexa
do pensamento é o raciocínio, a lógica estuda a
“correção do pensamento”.
Lógica
Todo mamífero é um animal.
Todo cavalo é um mamífero.
Portanto, todo cavalo é um animal.
Esse exemplo ilustra silogismos, que no estudo da Lógica
Proposicional (ou cálculo sentencial) representam um
argumento composto de duas premissas e uma conclusão;
e está estabelecendo uma relação, que pode ser válida ou
não.
Esse é um dos objetivos da lógica, o estudo de técnicas de
formalização, dedução e análise que permitam vefiricar a
validade de argumentos.
Lógica de Programação
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 racionalidade e o
desenvolvimento de técnicas que cooperam para
a produção de soluções logicamente válidas e
coerentes, que resolvam com qualidade os
problemas que se deseja programar.
Para representar mais fielmente o raciocínio da
Lógica
de
Programação,
utilizamos
os
Algoritmos.
Algoritmo
É a descrição de um conjunto de comandos
que, obedecidos, resultam numa sucessão
finita de ações.
Ação é um acontecimento que, a partir de um
estado inicial, após um período de tempo
finito, produz um estado final previsível e
bem definido.
Geralmente, um algoritmo se destina a resolver
um
problema:
fixa
um
padrão
de
comportamento a ser seguido, uma norma de
execução a ser trilhada, para se atingir, como
resultado final, a solução de um problema.
Algoritmo
Um algoritmo pode ser definido como uma
sequência de passos que visam a atingir um
objetivo bem definido
Para especificar uma sequência de passos, é
necessário utilizar ordem, ou seja, “pensar com ordem”,
portanto precisamos utilizar lógica.
Ao elaborar um algoritmo, devemos especificar
ações claras e precisas, que a partir de um
estado inicial, após um período de tempo finito,
produz um estado final previsível e bem
definido.
Algoritmo
Por que é importante construir um algoritmo?
• Representar mais fielmente o raciocínio envolvido na
Lógica de Programação.
• Pode ser traduzida
programação.
para
qualquer
Exemplo (utilizando um português coloquial)
Algoritmo 1.1 - Troca de lâmpada
pegar uma escada;
posicionar a escada embaixo da lâmpada;
buscar uma lâmpada nova;
subir na escada;
retirar a lâmpada velha;
colocar a lâmpada nova.
linguagem
de
Algoritmo
Algoritmo 1.2 - Troca de lâmpada com teste
pegar uma escada;
posicionar a escada embaixo da lâmpada;
buscar uma lâmpada nova;
acionar o interruptor;
se a lâmpada não acender, então
subir na escada;
retirar a lâmpada queimada;
colocar a lâmpada nova.
Algoritmo
Algoritmo 1.3 - Troca de lâmpada com teste no início
acionar o interruptor;
se a lâmpada não acender, então
pegar uma escada;
posicionar a escada embaixo da lâmpada;
buscar uma lâmpada nova;
subir na escada;
retirar a lâmpada queimada;
colocar a lâmpada nova.
Algoritmo
Algoritmo 1.4 - Troca de lâmpada com teste e repetição indefinida
acionar o interruptor;
subir na escada;
retirar a lâmpada queimada;
colocar a lâmpada nova.
se a lâmpada não acender, então
retirar a lâmpada queimada;
colocar a lâmpada nova.
se a lâmpada não acender, então
retirar a lâmpada queimada;
colocar a lâmpada nova.
se a lâmpada não acender, então
retirar a lâmpada queimada;
colocar a lâmpada nova. … até quando?
Algoritmo
Algoritmo 1.5 - Troca de lâmpada com teste e condição de parada
acionar o interruptor;
se a lâmpada não acender, então
pegar uma escada;
posicionar a escada embaixo da lâmpada;
buscar uma lâmpada nova;
subir na escada;
retirar a lâmpada queimada;
colocar uma lâmpada nova;
Enquanto a lâmpada não acender, faça
retirar a lâmpada queimada;
colocar uma lâmpada nova;
Algoritmo
Um homem precisa atravessar um rio com um barco que
possui capacidade de transportar apenas ele mesmo e
mais uma de suas três cargas, que são: um lobo, um bode
e um maço de alfafas. O que o homem deve fazer para
conseguir atravessar o rio sem perder suas cargas?
Informações:
um barco
um homem
um lobo
um bode
um maço de alfafa
Ação:
atravessar o rio sem perder as cargas
Algoritmo
Resultado:
todas as cargas na outra margem do rio
algoritmo:
– atravessar homem e bode
– voltar homem
– atravessar homem e lobo
– voltar homem e bode
– atravessar homem e alfafa
– voltar homem
– atravessar homem e bode
fim algoritmo
Algoritmo
Elabore um algoritmo que mova três discos de
uma Torre de Hanói, que consiste em três hastes
(a-b-c), uma das quais serve de suporte para três
discos de tamanhos diferentes (1-2-3), os menores
sobre os maiores. Pode-se mover um disco de
cada vez para qualquer haste, contanto que nunca
seja colocado um disco maior sobre o menor. O
objetivo é transferir os três discos para outra
haste.
Informações:
Algoritmo
3 discos
3 hastes
Ações:
movimentar um disco de cada vez de forma que fiquem ordenado
Resultado:
discos transferidos o ordenados para outra haste
algoritmo
- mover o disco 1 para a haste b
- mover o disco 2 para a haste c
- mover o disco 1 para a haste c
- mover o disco 3 para a haste b
- mover o disco 1 para a haste a
- mover o disco 2 para a haste b
- mover o disco 1 para a haste b
fim algoritmo
Torre de Hanói
Torre de Hanói
Algoritmo
Escrever os termos da sequência de Fibonacci
inferiores a um valor numérico L.
A Sequência de Fibonacci se define como tendo os dois
primeiros termos iguais a 1 e cada termo seguinte é
igual a soma dos dois termos imediatamente anteriores.
L = 50
1 1
2
3
5
8
L = 13
1 1
2
3
5
8
13
21
34
L=1
Algoritmo
Escreva os termos de Fibonacci inferiores a L
fim algoritmo
Algoritmo - Refinamentos sucessivos
Um algoritmo é considerado completo se for do
entendimento do seu destinatário.
Num algoritmo, um comando que não for do
entendimento do destinatário terá de ser desdobrado
em novos comandos, que constituirão um
refinamento do comando inicial.
Ref. Escreva os termos de Fibonacci inferiores a L
Receba o valor de L.
Processe os 2 primeiros termos.
Processe os termos restantes.
fim ref.
Algoritmo - Refinamentos sucessivos
• Um algoritmo e seus refinamentos são formados
por comandos, que determinam as ações a serem
executadas pelo seu destinatário e por estruturas
de controle que determinam a ordem em que os
comandos devem ser executados, se devem ser
executados ou não e quando devem ser repetidos.
• No refinamento anterior vigora a mais simples das
estruturas de controle: a estrutura sequêncial.
• Se um comando de um refinamento for um tanto
vago, ele poderá por sua vez, ser desdobrado em
novos comandos, produzindo-se o refinamento de
um refinamento, e assim sucessivamente.
Algoritmo - Refinamentos sucessivos
Ref. Processe os 2 primeiros termos
Atribua o valor 1 ao primeiro termo
Se ele for menor que L
então escreva-o
fim se
Atribua o valor 1 ao segundo termo
Se ele for menor que L
então escreva-o
fim se
fim ref.
• Neste refinamento aparece uma segunda estrutura de
controle: a estrutura condicional
Algoritmo - Refinamentos sucessivos
Ref. Processe os termos restantes
Repita
Calcule novo termo somando os 2 anteriores
Se novo termo for maior ou igual a L
então interrompa
fim se
Escreva novo termo
fim repita
fim ref.
• Neste refinamento aparece uma terceira estrutura de
controle: a estrutura de repetição
• Após esses refinamentos sucessivos, o algoritmo pode
ser considerado completo, a menos que o destinatário não
saiba fazer a adição de dois termos ou não seja capaz de
entender diretamente algum comando.
Algoritmo
Algoritmo {Escrita dos termos de Fibonacci inferiores a L}
Receba o valor de L.
{Processamento dos 2 primeiros termos}
Atribua o valor 1 ao primeiro termo
Se ele for menor que L
então escreva-o
fim se
Atribua o valor 1 ao segundo termo
Se ele for menor que L
então escreva-o
fim se
{Processamento dos termos restantes.}
Repita
Calcule novo termo somando os 2 anteriores
Se novo termo for maior ou igual a L
então interrompa
fim se
Escreva novo termo
fim repita
fim algoritmo
Algoritmos Estruturados
• São técnicas que permitem sistematizar e ajudar o
desenvolvimento de algoritmos para a resolução
de grandes e complexos problemas nos
computadores: são as técnicas de
desenvolvimento estruturado de algoritmos.
• Objetivos:
– facilitar o desenvolvimento dos algoritmos;
– facilitar o seu entendimento pelos humanos;
– antecipar a comprovação da sua correção;
– facilitar a sua manutenção e a sua modificação;
– permitir que o seu desenvolvimento possa ser
empreendido simultaneamente por uma equipe de
pessoas.
Algoritmos Estruturados
• Para atingir estes objetivos, o desenvolvimento
estruturado preconiza que:
– os algoritmos sejam desenvolvidos por refinamentos
sucessivos. Este desenvolvimento também se
denomina “construção hierárquica de algoritmos” e
“desenvolvimento de cima para baixo” (em inglês, topdown);
– os sucessivos refinamento são módulos, que delimitam
poucas funções e são o mais independente possível,
isto é, conservam poucos vínculos com outros módulos;
– nos módulos deve ser usado um número limitado de
diferentes comandos e de diferentes estruturas de
controle.
Linguagens de Programação
• Para armazenar um algoritmo na memória de um computador
e para que ele possa, em seguida, comandar as operações a
serem executadas, é necessário que ele seja programado,
isto é, que seja transcrito para uma linguagem que o
computador possa “entender”, direta ou indiretamente.
• Os computadores só podem executar diretamente os
algoritmos expressos em linguagem de máquina, que é um
conjunto de instruções capazes de ativar diretamente os
dispositivos eletrônicos do computador.
• Compilador: é um programa que traduz o algoritmo escrito na
linguagem escolhida para a linguagem de máquina
• Interpretador: é um programa que interpreta cada comando
do programa e executa uma série de instruções que a ele
correspondem.