Universidade do Sul de Santa Catarina
UNISUL –2014/ 1
Engenharia Elétrica
Algoritmos
Prof. Paulo Villa
Aula 1
Slides adaptados do
Prof. Frederico Ferlini
Informações da Disciplina
• Página da disciplina
 gse.ufsc.br/~pvilla
 Controle de Frequência
• Email:
 [email protected]
• Monitoria:
Prof. Paulo Villa
 Cleber Itamaro
 [email protected]
 Quintas 15h00 – 18h00
2
Informações da Disciplina
• Avaliação:
 MS = P*0,6 + T*0,4
• P = Prova (27/06/2014)
• T = Trabalho Final a ser desenvolvido na ferramenta VisuAlg
• Prova 2º Chamada (04/07/2014)
• Avaliação Final (11/07/2014)
3
Prof. Paulo Villa
Introdução
4
• O que é um Algoritmo?
 Algoritmo é o caminho para solução de um problema.
 Em geral um problema possui diversos caminhos para
sua solução.
 Logo, podem existir diversos algoritmos para resolver o
mesmo problema.
Prof. Paulo Villa
Introdução
• Representação:
 Existem diversas formas de representação de
algoritmos:
•
•
•
•
Descrição Narrativa
Pseudo-linguagens
Formas gráficas
Próprias linguagens de programação
5
Prof. Paulo Villa
Introdução
6
• Motivação:
 Uma das dificuldades constatadas no aprendizado de
algoritmos (programação) é a passagem de uma língua
natural (materna), de expressão completamente livre,
para uma linguagem repleta de restrições, com sintaxe
não familiar e, em geral, em uma língua estrangeira.
Prof. Paulo Villa
 A passagem para uma linguagem algorítmica, embora
mais restrita que a linguagem natural, mas com sintaxe
conhecida e em português, representa uma passagem
menos traumatizante.
Introdução
7
• Motivação:
 Outro motivo é o ensino do conceito de algoritmos
independente da sintaxe de uma determinada
linguagem de programação
• “;” ou “” ???
• “:=“ ou “=“ ou “<=“ ???
• “<>“ ou “!=“ ou “/=“ ???
 Perda de tempo com problemas de sintaxe e não com o
conceito de Algoritmos
Prof. Paulo Villa
 Evita associação da lógica da solução de problemas com
eventuais detalhes de implementação de uma
determinada linguagem
Introdução
• Aprendizado:
 Algoritmos NÃO se aprendem:
• Copiando algoritmos
• Estudando algoritmos
 Algoritmos SÓ se aprendem:
• Construindo algoritmos
• Testando algoritmos
8
Prof. Paulo Villa
Aula de Hoje
•Slides
Disciplina de Algoritmos UFJF
9
Prof. Paulo Villa
Sumário
• Revisão:





Sistemas Numéricos
Conversão de Base
Bit: unidade atômica de informação (0 ou 1)
Byte: Conjunto de 8 bits
Word: é a quantidade de bits que a CPU processa por
vez (normalmente 16 ou 32 bits)
• Sistemas Computacionais
Prof. Paulo Villa
 HW / SW
 Estrutura básica de um computador digital
• CPU (ULA + CTRL)
• Memória Principal + Secundária
• Interfaces (entrada ou saída)
10
Sumário
11
• Sistemas Computacionais
 Programação
• Linguagem de programação
 Linguagem de Máquina, Baixo Nível ou Alto Nível (de abstração)
• Tradutor (Compilação ou Interpretação)
• Algoritmos
 Definição:
Prof. Paulo Villa
• Um algoritmo é uma sequência finita de instruções bem
definidas e não ambíguas, cada uma das quais pode ser
executada num período de tempo finito, visando a solução de
um problema (também bem definido)
 Como estudar algoritmos
 Conceitos básicos (ação, estado e processo)
início
Sumário
12
Acionar interruptor
• Algoritmos
Lâmpada não acendeu?
 Formas de representação
V
Pegar uma escada
• Descrição Narrativa
• Fluxograma Convencional
• Pseudo-linguagem
Colocar a escada embaixo do soquete
Buscar lâmpada nova
Desligar interruptor
Subir na escada
Retirar lâmpada queimada
Descartar lâmpada queimada
Prof. Paulo Villa
Colocar lâmpada nova
Acionar interruptor
V
Lâmpada nova queimada?
F
fim
F
Exemplo Algoritmo (Sequencial)
• A troca de uma 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
13
Prof. Paulo Villa
Exemplo Algoritmo (de Seleção)
• A troca de uma lâmpada:
•
•
•
•
•
Pegar uma escada
Posicionar a escada embaixo da lâmpada
Buscar uma lâmpada nova
Acionar interruptor
Se a lâmpada não acender, então
 Subir na escada
 Retirar a lâmpada queimada
 Colocar a lâmpada nova
14
Prof. Paulo Villa
15
Exemplo Algoritmo (de Seleção)[otimizado]
• A troca de uma lâmpada:
• Acionar 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
Prof. Paulo Villa
Exemplo Algoritmo (de seleção) [cont.]
• A troca de uma lâmpada:
• Acionar interruptor
• Se a lâmpada não acender, então







Prof. Paulo Villa
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
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
⋮
16
Exemplo Algoritmo (de Repetição)
• A troca de uma lâmpada:
• Acionar interruptor
• Se a lâmpada não acender, então







Prof. Paulo Villa
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
Enquanto a lâmpada não acender, faça
• Retirar a lâmpada queimada
• Colocar a lâmpada nova
17
Exercícios
18
1. Um homem precisa atravessar um rio com um barco
que possui capacidade apenas para carregar ele mesmo
e mais uma de suas três cargas, que são: um lobo, um
bode e um maço de alfafa. O que o homem deve fazer
para conseguir atravessar o rio sem perder suas cargas?
Escreva um algoritmo mostrando a resposta, ou seja,
indicando todas as ações necessárias para efetuar uma
travessia segura.
Prof. Paulo Villa
• Notem que:
 O bode não pode ficar sozinho com o lobo
 A alfafa não pode ficar sozinha com o bode
Exercícios (Torre de Hanói)
19
2. 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 mesmos sobre
maiores. Pode-se mover um disco de cada vez para
qualquer haste, contanto que nunca seja colocado um
disco maior sobre um menor. O objetivo é transferir os
três discos para outra haste.
Prof. Paulo Villa
Exercício (Jesuítas + Canibais)
20
3. Três jesuítas e três canibais precisam atravessar um rio;
para tal, dispõem de um barco com capacidade para
duas pessoas. Por medidas de segurança não se permite
que em alguma margem a quantidade de jesuítas seja
inferior à de canibais. Qual a sequência de passos que
permitiria a travessia com segurança ?
Prof. Paulo Villa
Solução (Barco+Lobo+Bode+Alfafa)
Prof. Paulo Villa
• informações:
um barco
um homem
um lobo
um bode
um maço de alfafa
• ação:
atravessar o rio sem perder as cargas
• resultado:
todas as cargas na outra margem do rio.
• Algoritmo:
início
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
21
Solução (Torre de Hanói)
Prof. Paulo Villa
informações:
3 discos
3 hastes
ações:
movimentar um disco de cada vez de forma que fiquem ordenado
resultado:
discos transferidos e ordenados para outra haste
Algoritmo:
início
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
22
Solução (Torre de Hanói)
23
Prof. Paulo Villa
Solução (Jesuítas + Canibais)
Prof. Paulo Villa
informações:
3 jesuítas
3 canibais
1 barco com capacidade para 2 pessoas
ações:
atravessar o rio com segurança
resultado:
3 jesuítas e 3 canibais na outra margem do rio
Algoritmo:
início
atravessar dois canibais
voltar um canibal
atravessar dois canibais
voltar um canibal
atravessar dois jesuitas
voltar um jesuíta e um canibal
atravessar dois jesuitas
voltar um canibal
atravessar dois canibais
voltar um canibal
atravessar dois canibais
fim
24