Introdução à Algoritmos

Prévia do material em texto

Introdução a Algoritmos
Neste tópico abordaremos alguns 
conceitos básicos de algoritmos
 2
O que um computador 
faz?
 Fundamentalmente um computador: 
 Executa cálculos
 Lembra os resultados
 Que cálculos?
 Instruções primitivas
 Criação de nosso próprios métodos de 
cálculo
 3
Isso é tudo que ele faz?
 Um bilhão de cálculos por segundo
 Centenas de gigabytes de 
armazenamento
 Isto é o bastante?
 Busca na web
 Jogar xadrez
 4
Resolução de problemas 
computacionais
 O que é computação?
 O que é conhecimento?
 Conhecimento declarativo
 Fatos
 Conhecimento imperativo
 Método do tipo “como fazer” ou receitas
 5
Conhecimento 
declarativo
 “A raiz quadrada de um número x é 
um número y tal que y*y = x”
 Nós podemos usar isto para 
encontrar a raiz quadrada de uma 
instância particular de x?
 6
Conhecimento 
imperativo
 Aqui está uma “receita” para deduzir a 
raiz quadrada de um número x
 Comece com um palpite, chamado p
 Se p*p é próximo o suficiente a x, pare e 
diga que p é a resposta
 Caso contrário, gere um novo palpite, 
calculando a média de p e x/p
 Usando o novo palpite, repita o processo 
até que cheguemos próximo o suficiente
 7
Um exemplo: encontrar 
a raiz quadrada de 25
p p*p x/p (p + x/p) / 2
3 9 8.333 5.667
5.667 32.111 4.412 5.040
5.039 25.392 4.961 5.000
5.000 25.000
 8
Algoritmos são 
“receitas”
1.Coloque a mistura do creme no fogo
2.Mexa
3.Mergulhe a colher no creme
4.Retire a colher e passe o dedo em 
suas costas
5.Se o rastro ficar limpo, retire o creme 
do fogo e deixe esfriar
6.Caso contrário, repita a partir do 
passo 2
 9
Etapas de um algoritmo
 Um algoritmo é uma sequência de 
passos que transformam dados de 
entrada na saída
Entrada Processamento Saída
 10
Método para a 
construção de algoritmos
 Na elaboração de algoritmos é necessário 
utilizar um método sistemático de programação 
que permita a obtenção de algoritmos 
confiáveis, flexíveis e eficientes
 Uma proposta de metodologia para construção 
de algoritmos estabelece os seguintes passos:
 Análise do problema
 Projeto do algoritmo
 Teste do algoritmo
 Implementação
 Teste do programa
 11
Análise do problema (1/2)
 Nesta fase procuramos nos certificar da 
compreensão correta do problema, 
eliminando possíveis ambiguidades e nos 
assegurando do entendimento completo das 
especificações de entrada e saída
 Escolhemos uma amostra significativa de 
dados, definindo as especificações de entrada
 Determinamos a saída desejada 
correspondente aos dados de entrada, 
definindo as especificações de saída
 12
Análise do problema (2/2)
 A escolha da amostra de entrada 
confirma também a compreensão correta 
do enunciado do problema
 Em seguida estudamos métodos de 
resolução do problema e estabelecemos 
uma estratégia para obter a sua solução 
(processamento)
 13
Exemplo
 Problema: calcular a área de um 
retângulo dadas as medidas de sua 
base e altura.
 Entradas?
 Saída?
 Método de resolução do problema 
(processamento)?
 14
Exercício
 Identifique as entradas, 
processamento e saída no algoritmo 
abaixo:
 Ler o valor do produto
 Ler a quantidade de produtos
 Calcular o valor da compra (valor * 
quantidade)
 Escrever o valor da compra
 15
Variável
 Símbolo que denota um valor qualquer
 Noção semelhante a usada na matemática
 Possui um nome e armazena um valor
 Metáfora: caixa nomeada aonde se pode 
colocar valores
 O valor de variáveis pode mudar durante 
a execução do algoritmo
 Como?
 Por entrada: leia(n1)
 Por atribuição: n1   10←
n1 é uma 
variável
 16
Projeto do algoritmo (1/2)
 A descrição de um algoritmo pode ser feita 
através de um pseudocódigo (linguagem 
algorítmica) ou através de fluxogramas
 No fluxograma cada operação básica 
(instrução) é representada por um desenho
 No pseudocódigo cada operação básica é 
escrita em linguagem semelhante à 
linguagem natural, com algumas regras 
comuns às linguagens de programação
 17
Projeto do algoritmo (2/2)
 Os fluxogramas são preferíveis em alguns 
casos por permitir uma visualização global 
do processo de resolução e de suas partes
 A linguagem algorítmica, por sua vez, 
apresenta outras vantagens:
 é mais fácil escrever do que desenhar
 a codificação em linguagem de 
programação acaba se tornando uma 
“simples” transcrição de palavras-chaves
 18
Fluxograma x 
Pseudocódigo
AreaRetangulo() {
   real base, altura, area
   leia(base, altura)
   area   base * altura←
   escreva(area)
}
base, altura
Fim
Início
area = base * altura
area
 19
Teste do algoritmo
 Selecione alguns valores para as 
entradas e verifique se o algoritmo 
gera as saídas corretas
 Teste de mesa
base altura area
2 4.5 9.0
5 5 25
 20
Implementação
 Chamamos de implementação de um 
algoritmo à sua codificação em uma 
linguagem de programação
 A implementação de um algoritmo está 
intimamente relacionada às características da 
linguagem escolhida e dos tipos de dados nela 
definidos
 Em breve aprenderemos a linguagem C para 
implementação de nossos algoritmos
 21
Teste de programa
 Compile e depois execute seu 
programa utilizando um conjunto de 
dados de entrada e verifique se ele 
produz as saídas esperadas
	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