Algoritmos e Estruturas de Dados I
- Introdução
Profa. Mercedes
Gonzales Márquez
Algoritmos - Conceito

Descrição ordenada de um conjunto de comandos que,
obedecidos, resultam numa sucessão finita de ações.
Algoritmos – exemplos da vida
quotidiana





Instruções que um professor passa aos seus alunos em
uma academia de ginástica
Uma receita para preparo de um bolo
O guia de preenchimento da declaração de imposto de
renda.
A regra para determinação de máximos e mínimos de
funções por derivadas sucessivas.
A maneira como as contas de água, luz e telefone são
calculadas mensalmente.
Problemas mais complexos
solucionados por algoritmos
• A internet permite que o mundo acesse e obtenha com
rapidez grandes quantidades de informações.
• Algoritmos inteligentes são necessários para gerenciar e
manipular esse grande volume de dados.
• Exemplos de problemas
1. localização de boas rotas pelas quais os dados viajarão
2. uso de um mecanismo de pesquisa para encontrar com rapidez
páginas em que residem informações específicas.
3. A capacidade de manter privativas informações como números de
cartão de crédito, senhas e extratos bancários é essencial no
comercio eletrônico.A criptografia de chave pública e as assinaturas
digitais são tecnologias centrais utilizadas baseadas em algoritmos
numéricos e na teoria dos números.
Algoritmos - exemplo 1

Algoritmo – instruções que um professor passa aos
seus alunos em uma academia de ginástica para
fortalecer braços e pernas.
1) Repetir 10 vezes os quatro passos abaixo:
1.1.Levantar e abaixar braço direito;
1.2.Levantar e abaixar braço esquerdo;
1.3.Levantar e abaixar perna esquerda;
1.4.Levantar e abaixar perna direita.
Algoritmos - exemplo 2

Algoritmo – Fazer um bolo

1) Bater duas claras ;

2) Adicionar duas gemas;

3) Adicionar um xícara de açúcar;

4) Adicionar duas colheres de manteiga;

5) Adicionar uma xícara de leite de coco;

6) Adicionar farinha e fermento;

7) Colocar numa forma e levar ao forno em lume
brando
Algoritmos - exemplo 3

Problema – Dispomos de duas vasilhas com
capacidades de 9 e 4 litros. As vasilhas não tem
nenhum tipo de marcação, de modo que não é possível
ter medidas como metade ou um terço. Faça um
algoritmo que usando as vasilhas de 9 e 4 litros encha
uma terceira vasilha de medida desconhecida com seis
litros de água.
Uma possível solução é:
(1) Encha a vasilha de 9 litros;
Algoritmos - exemplo 3
(2) Usando a vasilha de 9 litros, encha a vasilha de 4 litros;
(3) Despeje o que sobrou na vasilha de 9 litros (5 litros) na
terceira vasilha. Observe que falta um litro para completar
os seis litros;
(4) Esvazie a vasilha de 4 litros;
(5) Torne a encher a vasilha de 9 litros;
(6) Usando a vasilha de 9 litros encha a vasilha de 4 litros;
(7) Esvazie a de 4 litros;
(8) Usando o que restou na vasilha de 9 litros (5 litros),
encha novamente a vasilha de quatro litros;
(9) Despeje o que sobrou na vasilha de 9 litros (1 litro) na
terceira vasilha, que agora tem 6 litros.
Algoritmos - exemplo 4

Problema - Era uma vez um fazendeiro que foi ao
mercado e comprou um lobo, um carneiro, e uma
alface. No caminho para casa, o fazendeiro chegou à
margem de um rio e arrendou um barco. Mas, na
travessia do rio por barco, o agricultor poderia levar
apenas a si mesmo e uma única de suas compras - o
lobo, o carneiro, ou a alface. Se fossem deixados
sozinhos em uma mesma margem, o lobo comeria o
carneiro, e o carneiro comeria a alface. O desafio do
fazendeiro é atravessar a si mesmo e as suas compras
para a margem oposta do rio, deixando cada compra
intacta. Como ele fará isso?
Algoritmos - exemplo 4
1. Atravesse o carneiro.
2. Retorne sozinho.
3. Atravesse o lobo.
4. Retorne com o carneiro.
5. Atravesse o alface.
6. Retorne sozinho.
7. Atravesse o carneiro.
Algoritmos - exemplo 5

Problema - Você tem três moedas, e sabe que uma
delas é mais leve do que as demais. As outras duas
têm o mesmo peso. Determine a moeda mais leve com
uma pesagem em uma balança de dois pratos.
Algoritmos - exemplo 5
1. Escolha duas moedas.
2. Coloque cada uma das moedas escolhidas num dos
pratos da balança.
3. Se a balança ficar equilibrada, forneça como resposta a
moeda não escolhida; caso contrário, forneça como
resposta a moeda do prato que está num nível mais
baixo.
Algoritmos - exemplo 6

Problema - Você tem nove moedas, e sabe que uma
delas é mais leve do que as demais. As outras oito têm
o mesmo peso. Determine a moeda mais leve com
duas pesagens em uma balança de dois pratos..
Algoritmos - exemplo 6
1. Divida as moedas em três grupos de três moedas cada.
2. Escolha dois grupos.
3. Coloque cada grupo num dos pratos da balança.
4. Se a balança ficar equilibrada, fique com o grupo não
escolhido; caso contrário, fique com o grupo do prato
que está num nível mais baixo (grupo mais leve).
5. Escolha duas moedas.
6. Coloque cada uma das moedas escolhidas num dos
pratos da balança.
7. Se a balança ficar equilibrada, forneça como resposta a
moeda não escolhida; caso contrário, forneça como
resposta a moeda do prato que está num nível mais
Algoritmos - exemplo 7

Um algoritmo que inclua decisões, como o que fazer
em um domingo poderia ser o seguinte:
(1) Acordar.
(2) Tomar o café.
(3) Se estiver sol vou à praia senão leio o jornal e
assisto TV
(4) Almoçar.
(5) Ir ao cinema.
(6) Fazer uma refeição e comer
(7) Ir dormir.
Processador de Algoritmos




Um algoritmo deve ser executado por algum agente ou
também chamado processador de algoritmos.
Este agente pode ser uma pessoa munida de certos
equipamentos e utensílios ou uma máquina projetada
para executar automaticamente algumas instruções
básicas.
O algoritmo para a travessia do fazendeiro seria executado
pelo tal senhor, que estava para tal munido do barco e de
remos.
O computador não entenderia a instrução Bater duas
claras nem Tomar o café.
Processador de Algoritmos

Consideremos um algoritmo para extrair o algarismo da
casa das unidades de um inteiro dado. Vejamos como o
algoritmo para resolver esta questão depende do
processador que vai executá-lo.
1. Se o processador for um ser humano que saiba o que
é número inteiro, algarismo e casa das unidades, o
algoritmo teria uma única instrução: Escreva o
algarismo da casa das unidades do inteiro dado.
2. Se o processador for um ser humano que saiba o que
é número inteiro, algarismo e tenha a noção de "mais à
direita", mas não saiba o que é casa das unidades, o
algoritmo não poderia ser mais esse. Escreva o
algarismo "mais à direita" do número dado.
Processador de Algoritmos
3. E se o processador é uma máquina e não sabe o que é
algarismo, casa das unidades, "mais à direita", etc.?
Neste caso, quem está elaborando o algoritmo deveria
conhecer que instruções o processador é capaz de
executar para poder escrever o seu algoritmo. Por
exemplo, se a máquina é capaz de determinar o resto
de uma divisão inteira, o algoritmo poderia ser:
1. Chame de n o inteiro dado;
2. Calcule o resto da divisão de n por 10;
3. Forneça este resto como o algarismo pedido.
Processador de Algoritmos


Já que o processador de nossos algoritmos será o
computador, precisamos entender seu funcionamento
básico.
Conheçamos a seguir alguns conceitos básicos sobre
computador.
Conceitos Básicos


Computadores – máquinas capazes de
solucionar problemas, mas que só agem
quando recebem instruções nos mínimos
detalhes.
A tarefa principal dos computadores é o
processamento de dados, ou seja, receber
dados
(entrada),
realizar
operações
(processamento propriamente dito) e gerar
uma resposta (saída).
Conceitos Básicos
Estrutura de um computador
MEMÓRIA
UNIDADE
DE
ENTRADA
UNIDADE
DE
CONTROLE
UNIDADE
LÓGICA E
ARITMÉTICA
Unidade Central de Processamento (UCP)
UNIDADE
DE
SAIDA
Conceitos básicos



Unidade de entrada – Traduz informação de um
dispositivo de entrada em um código que a UCP
entende (padrões de pulsos elétricos compreensíveis
ao computador).
Unidade de saída – converte os dados processados,
de pulsos elétricos em palavras ou números que podem
ser escritos em vídeos ou outros dispositivos de saída.
Exemplos ue:
– Teclado
– drive de CD / DVD-ROM, pen drive.
Conceitos básicos
– joystick,
– câmera filmadora,
– câmera digital,
– tela sensível ao toque,
– mesa gráfica,
– caneta ótica, etc.
 Exemplos de us
• Vídeo
• Impressora
• drive de CD/DVD-ROM, pen drive
• caixa de som, etc.
Conceitos básicos

Memória – armazena os dados e o próprio programa.
Número finito de localizações que são identificadas por
meio de um único endereço.
Escrita – CPU envia endereço
da posição de memória a ser
escrita e dados a escrever.
Leitura – CPU envia endereço
da posição de memória a ser
lida e recebe dados.
Endereço
Read/Write
CPU
Dados
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
Conceitos básicos


Unidade lógica e aritmética – São executadas
operações matemáticas de adição, multiplicação e
divisão e operações lógicas como conjunção,
disjunção, ou exclusivo e outras.
Unidade de controle – Responsável pelo “tráfico” de
dados. Controla a transferência de dados da memória
para a unidade lógica e aritmética, da entrada para a
memória e da memória para a saída.
Base de uma linguagem de
programação ou de um pseudo-código
(1) comandos que manipulam os dados em memória e
a interação com o usuário (entrada e saída de dados).
(2) as expressões que permitem a realização de
cálculos aritméticos e lógicos.
(3) comandos que modificam o fluxo de execução do
algoritmo.
(1) o comando de atribuição define ou re-define um
valor armazenado no local de armazenamento
indicado por um nome. Usa-se o símbolo ←
Instruções Básicas
Os comandos de entrada e saída são usados para
determinar o momento da entrada de dados para o
algoritmo e a saída dos resultados obtidos para o
usuário. Os comandos são leia e escreva,
respectivamente.
Variáveis – Operadores aritméticoséticos
Símbolo
+
*
/
**
MOD
DIV
Função
Tipos disponíveis
Adição
Inteiro,real
subtração
”
”
”
”
Multiplicação
Divisão real
Exponenciação
Resto da divisão inteira
Inteiro
Quociente da divisão inteira Inteiro
Operadores relacionais
Função
Símbolo
=
<>
>=
<=
Tipos disponíveis
Igual
Todos
Diferente
Todos
Maior ou igual que
Todos
Menor ou igual que
Todos
O resultado obtido de uma relação é sempre um valor lógico.
Exemplos:
(a) A<>B (b) nome=“Maria” (c) B**2-4*A*C<0
Operadores lógicos
Símbolo
Função
e
Conjunção
Tipos
disponíveis
Lógico
Ou
Disjunção
Lógico
Não
Negação
Lógico
Operadores lógicos - e
A conjunção de duas proposições p e q representa-se
por: p e q e é verdadeira se e somente se ambas as
proposições são verdadeiras.
p
V
V
F
F
q
V
F
V
F
peq
V
F
F
F
Operadores lógicos - e
Sejam as seguintes proposições
p: ok, onde ok é uma variável lógica cujo conteúdo é
verdadeiro
q: A=0, onde o valor de A é 3.
r: teste, onde teste é uma variável lógica cujo conteúdo é
falso.
s: B<>1, onde o conteúdo de B é 2
Qual é o valor lógico das conjunções
(a) p e s (b) p e r (c) q e s (d) q e r
Operadores lógicos - ou
A disjunção de duas proposições p e q representa-se por:
p ou q e é verdadeira se e somente se, pelo menos, uma
delas for verdadeira.
p
V
V
F
F
q p ou q
V
V
F
V
V
V
F
F
Operadores lógicos - ou
Para as quatro proposições do exemplo anterior qual
será o valor lógico das disjunções:
(a) p ou s
(b) p ou r
(c) q ou s
(d) q ou r
Operadores lógicos - não
O operador negação (não) atribui o valor lógico falso a
uma proposição com valor verdade, e o valor lógico
verdade a uma proposição com valor falso. Assim
p
não
(p)
V F
F V
Estruturas de Controle de Fluxo de
execução do algoritmo
Estas estruturas de controle de fluxo são:
Sequencial, Condicional e de Repetição.

Estruturas de controle de fluxo
Estrutura Sequencial: Execução dos comandos
em uma sequência linear (na mesma ordem em
que foram escritas). Exemplo*:
escreva (“Informe seu nome:”)
leia (nome)
escreva (“Informe sua idade:”)
leia (idade)
escreva (“Você se chama”, nome, “e possui”,
idade, “anos!”)
Estruturas de controle de fluxo
Estrutura Condicional : É utilizada quando há uma
condição lógica que desviará o fluxo do algoritmo
para um diferente bloco de comandos,
dependendo da condição ser verdadeira ou falsa.
Exemplo:
se (A > B) então
escreva “A é maior”
senão
escreva “O B é maior ou são iguais”
Estruturas de controle de fluxo
Estrutura de Repetição: Execução de uma
sequência de comandos repetidas vezes. O
computador abandona o fluxo natural da
execução (de cima para baixo) e volta a executar
a sequência de ações desejada. Exemplo:
M← 1
enquanto (M < 10) faça
M←M+1
Fim enquanto
escreva M
Algoritmos - Representação



Já que um algoritmo é uma linha de raciocínio,
pode ser descrito de diversas maneiras, de
forma gráfica ou textual.
Até agora foi usada a representação textual,
usando um português coloquial.
A forma gráfica substitui um grande número de
palavras por convenções de desenhos..
Algoritmos - Representação

Fluxograma – símbolos utilizados
Início e fim do algoritmo
Sentido do fluxo de dados
Cálculos e atribuição de valores
Entrada de dados
Saída de dados
Algoritmos - Representação

Pseudocódigo (portugol)

Descrição dos passos a serem seguidos através de
regras definidas previamente.

Vantagens – codificação mais rápida pois as regras
intencionalmente se aproximam da maneira pela
qual o fazem as linguagens de programação.
Algoritmos – Representação por pseudocódigo

Símbolos e palavras utilizadas (convenção nossa)
←
Cálculos e atribuição de valores
leia
Entrada de dados
escreva
Saída de dados
Se … então...
Senão...
F
V
V
Tomada de decisão (1 vez)
Enquanto …
Tomada de decisão (repetidas faça
vezes)
Algoritmos - Representação


Exemplo – Calcular a área de um retângulo.
Representação Gráfica (Fluxograma)
Início
b, h
A=b*h
A
Fim
Algoritmos – Representação por pseudocódigo

Exemplo - Calcular a área de um retângulo.
ALGORITMO
Inicio
escreva “Informe a largura do retângulo”
leia b
escreva “Informe a altura do retângulo”
leia h
a ← b * h
escreva “Área = ”, a
Fim