Algoritmos: Definição, Importância e Exemplos

Prévia do material em texto

Algoritmo
Prof. André da Cunha Ribeiro
Doutor em Engenharia de Sistemas e 
Computação – COPPE/RJ
 
Plano de Ensino
 
Questões “em aberto”!!!
 O que é algoritmo?
 Será que sabemos fazer um algoritmo?
 Qual a sua importância para a computação?
 Qual será a sua origem?
 
O que é um computador?
 Computador: o que computa, calculador, 
calculista.
 Um computador é uma máquina que, a partir de 
uma entrada, realiza um número muito grande de 
cálculos matemáticos e lógicos, gerando uma 
saída.
 Computadores realizam tarefas complexas por 
meio de um número enorme de operações 
simples.
 
O que é um computador?
 A linguagem nativa do computador é 
codificada numericamente, de forma binária:
 Bit: Pode assumir valores 0 ou 1.
 Byte: Agrupamento de 8 bits em uma 
palavra.
 Letras e símbolos são representados por 
números.
 
UM COMPUTADOR SIMPLIFICADO
 
Definição: Algoritmo.
 Um algoritmo é um conjunto 
finito de regras que fornece 
uma sequência de operações 
para resolver um problema 
especifico.
 
Vamos a prática I
 Dispomos de duas vasilhas com capacidades 
de 9 e 4 litros e uma outra vasilha de medida 
desconhecida. 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. 
 Mostre uma sequência de passos, que 
usando as vasilhas de 9 e 4 litros encha a 
terceira vasilha de medida desconhecida 
com seis litros de água. 
 
Uma possível solução é: 
 Encha a vasilha de 9 litros; 
 Usando a vasilha de 9 litros, encha a vasilha de 4 litros; 
 Despeje o que sobrou na vasilha de 9 litros (5 litros) na 
terceira vasilha. Observe que falta um litro para completar os 
seis litros; 
 Esvazie a vasilha de 4 litros; 
 Torne a encher a vasilha de 9 litros; 
 Usando a vasilha de 9 litros encha a vasilha de 4 litros; 
 Esvazie a de 4 litros; 
 Usando o que restou na vasilha de 9 litros (5 litros), encha 
novamente a vasilha de quatro litros; 
 Despeje o que sobrou na vasilha de 9 litros (1 litro) na terceira 
vasilha, que agora tem 6 litros. 
 
Azulejos
 São dados N azulejos de dimensões 10cm x 10cm. 
Com eles, você deve montar um conjunto de quadrados 
(com espessura de um azulejo) de modo a utilizar 
TODOS os azulejos dados. Inicialmente você deve 
montar o maior quadrado possível com os azulejos 
dados; então, com os azulejos que sobraram, você 
deve montar o maior quadrado possível, e assim 
sucessivamente. a) 148
b) 75
c) 290
d) 120
e) 76
f) 347
 
Características importantes:
 Finitude ( ele terá um fim. )
 Definição(temos que definir todos os 
passos)
 Entradas (teve ter zero ou mais entradas)
 Saídas (teve ter uma ou mais saídas)
 Efetividade (Isto significa que todas as 
operações devem ser suficientemente 
básicas de modo que possam ser em 
princípio executadas com precisão em um 
tempo finito usando papel e lápis ) 
 
Etapas de um algoritmo:
ProcessamentoEntrada(dados)
Saída
(informação)
 
Como representar um algoritmo?
 Linguagem Natural
 Os algoritmos são expressos diretamente em linguagem 
natural, como no exemplo anterior.
 Fluxograma Convencional
 Esta é um representação gráfica que emprega formas 
geométricas padronizadas para indicar as diversas ações e 
decisões que devem ser executadas para resolver o 
problema.
 Pseudo-linguagem
 Emprega uma linguagem intermediária entre a linguagem 
natural e uma linguagem de programação para descrever 
os algoritmos.
 
Linguagem Natural.
 Algoritmo de domingo. 
 Acordar. 
 Tomar o café. 
 Se estiver sol vou à praia senão leio o jornal. 
 Almoçar. 
 Ir ao cinema. 
 Fazer uma refeição. 
 Ir dormir. 
 Final do domingo 
 
Fluxograma Convencional.
 Esta forma de representação de algoritmos 
emprega várias formas geométricas para 
descrever cada uma das possíveis ações 
durante a execução do algoritmos. 
 
 
 
Importância para a computação!
 Para resolver um problema no computador é 
necessário que seja primeiramente 
encontrada uma maneira de descrever este 
problema de uma forma clara e precisa. 
 Além disto é preciso definir como os dados 
processados serão armazenados no 
computador. 
 
Informações importantes!
 A noção de algoritmo é central para toda a 
computação. 
 A criação de algoritmos é uma das maiores 
dificuldades dos iniciantes em programação 
em computadores. 
 Não existe um conjunto de regras, ou seja, 
um algoritmo que nos permita criar algoritmos.
 Existem vários algoritmos para o mesmo 
problema.
 
Como calcular o MDC entre dois números?
348 e 156
100 e 30
1128 e 336
120 e 23
 
Algoritmo melhor que a fatoração.
Algoritmo(a, b)
dividendo ← a 
divisor ← b
enquanto resto(dividendo/divisor) ≠ 0 
c ← resto(dividendo/divisor) 
dividendo ← divisor 
divisor ← c 
retornar divisor 
 
Algoritmo de Euclides.
 O algoritmo de Euclides encontrar o 
máximo divisor comum entre dois 
números inteiros diferentes de zero. É 
um dos algoritmos mais antigos 
conhecidos, desde que apareceu na 
obra Elementos de Euclides por volta 
de 300 aC. O algoritmo não requer 
fatoração. 
 
QUAL O MENOR CAMINHO DA CASA 
DO JOÃO ATÉ A ESCOLA ?
 
QUAL O MENOR CAMINHO DA CASA 
DO JOÃO ATÉ A ESCOLA ?
 
QUAL O MENOR CAMINHO DA CASA 
DO JOÃO ATÉ A ESCOLA ?
 
QUAL O MENOR CAMINHO DA CASA 
DO JOÃO ATÉ A ESCOLA ?
 
QUAL O MENOR CAMINHO DA CASA 
DO JOÃO ATÉ A ESCOLA ?
 
QUAL O MENOR CAMINHO DA CASA 
DO JOÃO ATÉ A ESCOLA ?
 
QUAL O MENOR CAMINHO DA CASA 
DO JOÃO ATÉ A ESCOLA ?
 
QUAL O MENOR CAMINHO DA CASA 
DO JOÃO ATÉ A ESCOLA ?
 
QUAL O MENOR CAMINHO DA CASA 
DO JOÃO ATÉ A ESCOLA ?
 
O problema do menor caminho.
O algoritmo que soluciona este problema (e 
até hoje não se encontrou forma melhor) 
foi criado por Edsger Wybe Dijkstra , em 
1952. Dijkstra nasceu em 1930, na cidade 
de Roterdan - Holanda, e morreu em 
2002. Foi um cientista de computação e 
recebeu o Turing Award de 1972 por suas 
contribuições fundamentais na área de 
linguagens de programação.
 
Algoritmo de Dijkstra.
para todo v  V[G] 
d[v]← ∞ 
π[v] ← nulo 
d[s] ← 0 
enquanto Q ≠ ø 
u ← extraia-mín(Q) 
S ← S  {u} 
para cada v adjacente a u 
se d[v] > d[u] + w(u, v) //relaxe (u, v) 
então d[v] ← d[u] + w(u, v) 
π[v] ← u 
 
Exercício
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34