Algoritmos e Estruturas de Dados I
- Introdução
Profa. Mercedes Gonzales
Márquez
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.
Algoritmos - Conceito



Sequência de passos que visa atingir um objetivo
bem definido.
Um algoritmo é um conjunto finito de regras que
fornece uma sequencia precisa de operações para
resolver um problema específico.
Descrição de um conjunto de comandos que,
obedecidos, resultam numa sucessão finita de
ações.
Algoritmos - Características





Finitude: algoritmos devem terminar após um
número finito de passos;
Definição: cada passo deve ser precisamente
definido
Entradas: devem ter zero ou mais entradas
Saídas: devem ter uma ou mais saídas;
Efetividade: todas as operações devem ser
simples de modo que possam ser executadas
em um tempo limitado.
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.
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 respectivamente. 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 – Considere cinco rãs estão
posicionadas em seis casas da seguinte maneira:
rã 1

rã 2
rã 3
rã 4
rã 5
Faça um algoritmo que mostre como as rãs podem chegar
a seguinte posição final:
rã 5
rã 4
rã 3
rã 2
rã 1
Algoritmos - exemplo 4
As rãs foram treinadas para trocar de casas, mas sempre
obedecendo as seguintes regras:
- elas podem pular para a casa vizinha (frente ou trás), se
ela estiver vazia;
- elas podem pular sobre a rã vizinha para uma casa livre
(frente ou trás).
Algoritmos - exemplo 4
Algoritmos - exemplo 5

Algoritmo – um algoritmo que inclua decisões, como o
que fazer em um domingo. Um possível algoritmo
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.
Algoritmos – Método de Construção






entender o problema;
definir os dados de entrada;
definir o processamento;
definir os dados de saída;
construir o algoritmo usando descrição
narrativa, fluxograma ou pseudocódigo;
realizar testes.
Algoritmos - Dificuldades



Difícil para iniciantes saber o que o computador
pode ou não fazer
Criação de algoritmos é um processo não
automático e tem muito de arte
Pode haver mais de uma solução para um
problema.
Algoritmos – exemplo 1

Calcular a área de um retângulo.

Dados de entrada


Processamento (cálculo)


base e altura
Área do retângulo = base x altura
Dados de saída

Área do retângulo
Algoritmos – exemplo 2

Calcular a média ponderada de um aluno e verificar a
sua aprovação em relação a uma média pré-definida
para aprovação. n notas e n pesos devem ser
considerados.

Dados de entrada


notas e pesos correspondentes, média para aprovação
Processamento (cálculo)
Média do aluno =
[(N1 x P1) + (N2 x P2) + ... + (Nn x Pn)] / (P1 + P2 + ... + Pn)

Se média do aluno for maior ou igual à média para aprovação,
aluno aprovado. Caso contrário, aluno reprovado.


Dados de saída

Média do aluno, aprovação
Algoritmos – exemplo 3

Escreva os termos da sequência de Fibonacci inferiores
a L.

Dados de entrada


Processamento (cálculo)





O número L
Atribua 1 ao primeiro termo. Se 1 for menor que L escreva-o.
Atribua 1 ao segundo termo. Se 1 for for menor que L escreva-o.
Some primeiro e segundo termo e escreva.
enquanto a soma for menor que L, atualize o primeiro e segundo
termo e repita o último passo
Dados de saída

Todos os termos inferiores a L.
Algoritmos - Representação



Linguagem natural ou descrição narrativa:
Algoritmos expressos diretamente em
linguagem natural como as receitas.
Fluxograma: representação gráfica
Pseudo-código (pseudo-linguagem):
linguagem intermediária entre linguagem
natural e linguagem de programação.
Algoritmos - Representação

Descrição narrativa



Escrever, usando linguagem natural, os passos a serem
seguidos para a solução.
Vantagens – a linguagem natural já é bastante conhecida.
Não é necessário aprender nenhum conceito novo.
Desvantagens – possibilidades de várias interpretações,
gerando dificuldade na codificação.
Algoritmos – Representação

Exemplo 1 – Descrição narrativa

Passo 1 – Ingressar largura do retângulo

Passo 2 – Ingressar altura do retângulo

Passo 3 – Multiplicar a largura pela altura

Passo 4 – Mostrar o resultado da multiplicação
Algoritmos – Representação

Exemplo 2 – Descrição narrativa

Passo 1 – Ingressar pesos Pi e notas Ni

Passo 2 – Ingressar media referência MF

Passo 3 – Calcular a média ponderada usando

MA =
[(N1 x P1) + (N2 x P2) + ... + (Nn x Pn)] / (P1 + P2 + ... + Pn)
᳸
Passo 4 – Se MA>=MF COND=Aprovado senão
COND=Reprovado
Passo 5 – Mostrar MA e COND
Algoritmos - Representação

Fluxograma



Descrição dos passos para a resolução do problema
utilizando símbolos gráficos definidos previamente.
Vantagens – entendimento mais fácil do que a leitura de
textos.
Desvantagens – necessidade de aprender a simbologia.
Poucos detalhes, dificultando a codificação.
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
Tomada de decisão
Algoritmos - Representação

Exemplo 1 – Fluxograma
Início
b, h
A=b*h
A
Fim
Algoritmos - Representação

Exemplo 2 – Fluxograma
Início
n,pi,Ni,MR
MA =
[(N1 x P1) + (N2 x P2) + ... + (Nn x Pn)] / (P1 + P2 + ... + Pn)
Cond=R
F
MA>=MR
V
Cond=A
A
Fim
MA, Cond
Algoritmos - Representação

Exemplo 2 – Fluxograma – Maior detalhe
Início
Cont=1
n, MR
P(cont),N(cont)
Cont=cont+1
V
Cont<=n
F
MA = [(N(1) x P(1) + N(2) x P(2) + ... + (N(n) x P(n)] / (P1 + P2 + ... + Pn)
Cond=R
F
MA>=MR
MA, Cond
V
Cond=A
Fim
Algoritmos - Representação

Exemplo 3 – Fluxograma –
Início
L
T1=1, T2=1
F
T1<L
V
T1,T2
Fib=T1+T2
Fib<L
V
Fib
T1=T2
T2=Fib
F
Fim
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.

Desvantagens – necessidade de aprender o
pseudocódigo.
Algoritmos - Representação

Exemplo 1 – Pseudocódigo
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
Algoritmos - Representação
Exemplo 2 – Pseudocódigo
ALGORITMO

Inicio
escreva “Informe o número de notas”
leia n
escreva “Informe Média de referência”
Leia MF
Contador<-1
Somaproduto<-0, somapesos<-0
Enquanto contador<=n
escreva “Informe nota(contador)”
leia n(contador)
escreva “Informe peso(contador)”
leia p(contador)
somaproduto<- p(contador)*n(contador)+somaproduto
somapesos<- p(contador)+somapesos
contador<-contador+1
Algoritmos - Representação

Exemplo 2 – Pseudocódigo
MA<-somaproduto/somapesos
Se MA>=MF então
Cond<-“Aprovado“
Senão
Cond<-“Reprovado“
escreva MA, Cond
Fim
Algoritmos - Representação

Exemplo 3 – Pseudocódigo
ALGORITMO
Início
Leia L
T1<-1, T2<-1
Se (T1<L) então
escreva (T1,T2)
Fib<-T1+T2
Enquanto (Fib<L) faça
escreva Fib
T1<-T2
T2<-Fib
Fib<-T1+T2
Fim enquanto
Fim se
Fim
Algoritmos - Representação
Exemplo 4 – Faça um algoritmo para calcular
as raízes de uma equação do segundo grau da
forma ax2+bx+c=0.
-
As raízes podem ser calculadas pelas
fórmulas
x1=[-b+(b2-4ac)(1/2)]/(2a) e
x2=[-b-(b2-4ac)(1/2)]/(2a)
-
Não podemos somente aplicar a fórmulas.
Temos que considerar Por exemplo o que
fazer se o valor do coeficiente a for igual
a zero? Um possível algoritmo é o seguinte:
Algoritmos – Representação
Exemplo 4. Descrição Narrativa
Passo 1. Obter os coeficientes a, b e c
Passo 2. Se o coeficiente a for igual a zero
informar que esta não é uma equação do segundo grau e
terminar o algoritmo.
Caso contrário calcule delta=b2-4ac
Passo 3. Se o valor de delta for negativo
informar que a equação não tem raízes reais e terminar o algoritmo.
Caso contrário calcule a raiz quadrada de delta e guarde o
resultado como raiz
Passo 4. Calcule x1=(-b + raiz)/(2a)
Passo 5.Calcule x2=(-b - raiz)/(2a)
Passo 6. Mostrar x1 e x2
Algoritmos – Representação
Exemplo 4. Passe a solução apresentada na
representação narrativa para a descrição por
fluxograma e por pseudocódigo.
Algoritmos – Representação
Exemplo 5. Considere o seguinte problema. Um
escritório de previsão do tempo armazena diariamente
a temperatura de uma determinada região. A tarefa é
descobrir qual é a menor temperatura registrada nos
arquivos do escritório. Lembrar que temperaturas
podem ser negativas ou positivas.
Um possível algoritmo seria o seguinte:
Algoritmos – Representação
Exemplo 5. Descrição Narrativa
Passo 1. Pegue a primeira temperatura registrada.
Passo 2. Anote esta temperatura como a menor de todas
as temperaturas.
Passo 3. Enquanto ainda houver registros de
temperaturas, execute repetidamente e em ordem todas as
instruções numeradas abaixo:
Passo 4. Pegue a próxima temperatura.
Passo 5. Se esta temperatura for menor que àquela
registrada no momento como a menor então
jogue fora a anteriormente registrada e anote a nova
temperatura como a menor de todas.
Passo 6. Leia a temperatura que está anotada como a
menor. Esta é a temperatura que estávamos procurando.
Algoritmos – Representação
Exemplo 5. Passe a solução apresentada na
representação narrativa para a descrição por
fluxograma e por pseudocódigo.