Teorica - Algoritmos Parte 1

Prévia do material em texto

*
ALGORITMOS
*
ALGORITMOS
INTRODUÇÃO
AUTOMAÇÃO
É o processo em que uma tarefa é desempenhada por máquinas, sejam estes dispositivos mecânicos, eletrônicos (computadores) ou de natureza mista.
*
ALGORITMOS
INTRODUÇÃO
Para que a automação de uma tarefa seja bem-sucedida é necessário que a máquina que passará a realizá-la seja capaz de desempenhar cada uma das etapas constituintes do processo a ser automatizado com eficiência, de modo a garantir a repetibilidade.
REPETIBILIDADE
*
ALGORITMOS
INTRODUÇÃO
É a especificação da seqüência ordenada de passos que deve ser seguida para a realização de uma tarefa, garantindo a sua repetibilidade.
DEFINIÇÃO DE ALGORITMO
*
ALGORITMOS
INTRODUÇÃO
O conceito de algoritmo não foi criado para satisfazer às necessidades da computação. 
Programação de computadores é apenas uma das aplicações de algoritmos.
DEFINIÇÃO
*
ALGORITMOS
INTRODUÇÃO
Embora possua designação desconhecida, fazemos uso constantemente de algoritmos em nosso cotidiano:
instruções para se utilizar um eletrodoméstico;
uma receita para preparo de algum prato;
guia de preenchimento para declaração do 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, etc.
DEFINIÇÃO
*
ALGORITMOS
INTRODUÇÃO
“A noção de algoritmo é básica para toda a programação de computadores”. 
[KNUTH - Professor da Universidade de Stanford, autor da coleção “The art of computer programming”].
Importância de Algoritmos para a Ciência da Computação 
*
ALGORITMOS
INTRODUÇÃO
Importância de Algoritmos para a Ciência da Computação 
“O conceito central da programação e da ciência da computação é o conceito de algoritmo”. 
[WIRTH - Professor da Universidade de Zurique, autor de diversos livros na área e responsável ela criação de linguagens de programação como ALGOL, PASCAL e MODULA-2].
*
ALGORITMOS
INTRODUÇÃO
Importância de Algoritmos para a Ciência da Computação 
A importância do algoritmo está no fato de termos que especificar uma seqüência de passos lógicos para que o computador possa executar uma tarefa qualquer. 
O Computador faz apenas o que o instruímos a fazer. 
*
ALGORITMOS
INTRODUÇÃO
Importância de Algoritmos para a Ciência da Computação 
Com uma ferramenta algorítmica podemos conceber uma solução para um dado problema, independentemente de uma linguagem específica, até mesmo do próprio computador. 
*
ALGORITMOS
INTRODUÇÃO
Características: 
Todo algoritmo deve apresentar algumas características básicas:
 Ter fim.
Em algum momento o algoritmo deve encerrar os passos.
X=0
Repetir as instruções abaixo enquanto (X ≤ 0)
 Inicio da repetição
 escrever na tela do computador o valor de X
 X = X-1
 Fim da repetição
*
ALGORITMOS
INTRODUÇÃO
Características: 
Todo algoritmo deve apresentar algumas características básicas:
A ORDEM dos passos deve ser precisamente determinada.
X=0
Z=X+1
W=X+Y
Y=3
X=0
Z=1
W=?
Erro de lógica
*
ALGORITMOS
INTRODUÇÃO
Características: 
NÃO dar margem à DUPLA INTERPRETAÇÃO 
		 (ambigüidade)
X=0
Se ( X≥ 0) então faça as instruções abaixo
	X=X+2
	escreva o valor de X na tela
Senão, isto é, se (X≤0) faça as instruções abaixo
	X=X-2
	escreva o valor de X na tela
QUAL O VALOR FINAL DE X?
*
ALGORITMOS
INTRODUÇÃO
Características: 
 Capacidade de receber dado(s) de entrada do mundo exterior
Escreva na Tela “Digite a sua idade”
 
Instrução de Leitura de dados (Entrada)
O algoritmo deve permitir que informações sejam inseridas pelo usuário.
*
ALGORITMOS
INTRODUÇÃO
Características: 
 Capacidade de receber dado(s) de entrada do mundo exterior
Escreva na Tela “Digite a sua idade”
 
Instrução de Leitura de dados (Entrada)
O algoritmo deve conter apenas a lógica de processamento das informações.
*
ALGORITMOS
INTRODUÇÃO
Características: 
Gerar informações de saída para o mundo externo ao do ambiente do algoritmo
X=5
Y=57 - 53
Escreva o valor de Y na tela ( saída )
 
Os resultados das operações devem ser apresentados ao usuário.
*
ALGORITMOS
INTRODUÇÃO
Características: 
Gerar informações de saída para o mundo externo ao do ambiente do algoritmo
X=5
Y=53 - 52
Escreva 100
 
Os resultados NÃO DEVEM SER FORNECIDOS PELO USUÁRIO.
X=5
Y=53 - 52
Escreva o valor de Y na tela ( saída )
 
*
ALGORITMOS
INTRODUÇÃO
Características: 
SER EFETIVO 
(todas as etapas especificadas no algoritmo devem ser alcançáveis em um tempo finito). 
Digite um nome
Procurar o nome em uma lista de nomes
Se o nome não for encontrado, encerrar a busca.
O algoritmo sempre deve conter um critério de parada que aborde todas as possibilidades.
*
ALGORITMOS
INTRODUÇÃO
Programa 
É um algoritmo escrito em uma forma compreensível pelo computador 
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
As formas de representação de algoritmos mais conhecidas são: 
Descrição Narrativa;
Fluxograma Convencional;
Pseudocódigo ou Linguagem Estruturada.
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
DESCRIÇÃO NARRATIVA:
	Os algoritmos são expressos diretamente em linguagem natural. 
Misture os ingredientes
Unte a forma com manteiga
Despeje a mistura na forma
Se houver coco ralado então 
despeje sobre a mistura
Leve a forma ao forno
Enquanto não corar
 deixe a forma no forno
Retire a forma do forno
Deixe esfriar e enfeite
Receita de bolo
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
DESCRIÇÃO NARRATIVA:
Troca de um pneu furado 
Afrouxar ligeiramente as porcas
Suspender o carro
Retirar as porcas e o pneu
Colocar o pneu reserva
Apertar as porcas
Abaixar o carro
Dar o aperto final nas porcas
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
DESCRIÇÃO NARRATIVA:
Cálculo da média de um aluno
Obter as notas da primeira e da segunda prova.
Calcular a média aritmética entre as duas
Se a média for maior ou igual a 7	então 
 o aluno foi aprovado
Caso contrário
	 o aluno foi reprovado
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
DESCRIÇÃO NARRATIVA:
O uso de linguagem natural muitas vezes dá oportunidade a más interpretações, ambigüidades e imprecisões
Exemplo: A instrução “afrouxar ligeiramente as porcas” no algoritmo da troca de pneus está sujeita a interpretações diferentes por pessoas distintas. 
Uma instrução mais precisa seria: “afrouxar a porca, girando-a de 30o no sentido anti-horário.
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
DESCRIÇÃO NARRATIVA:
VANTAGENS:
o português é bastante conhecido por nós
DESVANTAGENS:
imprecisão;
pouca confiabilidade 
(a imprecisão acarreta a desconfiança);
extensão 
(normalmente, escreve-se muito para dizer pouca coisa).
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
Diagramas de fluxo fornecem uma representação gráfica de um procedimento passo-a-passo necessário para resolver um problema, isto é, para construir um algoritmo. 
Tal representação torna uma seqüência complexa de eventos fácil para se ver e compreender. 
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
É uma representação gráfica onde formas geométricas diferentes implicam ações (instruções, comandos) distintas.
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
facilita o entendimento das idéias contidas nos algoritmos e justifica sua popularidade.
 É a forma intermediária entre a descrição narrativa e o pseudocódigo.
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
Um fluxograma se resume a um único símbolo inicial, por onde a execução do algoritmo começa, e um ou mais símbolos finais, que são pontos onde a execução do algoritmo se encerra.
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
Partindo do símbolo inicial, hásempre
 um único caminho orientado a ser seguido, representando a existência de uma única seqüência de execução das instruções e um único fim deverá ser atingido.
Fim
Fim
Início
Fim
Fim
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
Início e final do fluxograma
Entrada de dados
Operações de atribuição e chamada	ou retorno de subalgoritmo
Saída de dados
Decisão
Conector
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
VANTAGENS:
Uma das ferramentas mais conhecidas;
Figuras dizem muito mais que palavras;
Padrão mundial
DESVANTAGENS:
Faz com que a solução do problema esteja amarrada a dispositivos físicos;
Pouca atenção aos dados, não oferecendo recursos para descrevê-los ou representá-los;
Complica-se à medida que o algoritmo cresce.
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
Um fluxograma pode ser construído envolvendo maiores ou menores quantidades de detalhes. 
Todos eles podem se reduzir a dois tipos básicos: 
	o diagrama de fluxo orientado para o homem 
	 (mais grosseiro, menos detalhado)
 	 e o diagrama de fluxo orientado para a máquina
 (mais refinado e detalhado). 
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
Diagrama de fluxo orientado para o homem
É considerado bom se ele pode ser entendido por uma pessoa com conhecimento na área onde se enquadra o problema, porém sem experiência de programação de computadores. 
Diagrama de fluxo orientado para a máquina
É considerado bom se o programa praticamente pode ser escrito diretamente sem codificação intermediária, exceto para comandos de entrada e saída e comandos declarativos.
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
TIPOS DAS VARIÁVEIS NÃO SÃO DECLARADOS. 
O USO DE TEXTOS NO FLUXOGRAMA NÃO É OBRIGATÓRIO 
No fluxograma é representada apenas a lógica do programa e as variáveis utilizadas. 
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
Exemplo: Cálculo da média de um aluno
As variáveis nota1, nota2 e media são inteiras ou reais?
 No fluxograma as variáveis não são declaradas.
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
Leitura Complementar:
Diagramas de Nassi-Shneiderman
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
Pseudocódigo:
CARACTERÍSTICAS:
 É rico em detalhes como, por exemplo, a definição dos tipos das variáveis usadas no algoritmo. 
Assemelhar-se à forma em que os programas são escritos e encontra muita aceitação. 
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
FLUXOGRAMA CONVENCIONAL:
VANTAGENS:
Independência física da solução (solução lógica apenas);
Usa a linguagem natural como base;
Permite a definição de quais e como os dados serão estruturados;
DESVANTAGENS:
Exige a definição de uma linguagem não real para trabalho
Não é padronizado universalmente como o fluxograma.
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
Pseudocódigo:
Forma geral da representação
Algoritmo < nome_do_algoritmo>
 declaração_de_variáveis
 subalgoritmos
Início
 corpo_do_algoritmo
Fim do Algoritmo
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
Exemplo: Cálculo da média de um aluno
Pseudocódigo:
Algoritmo media_aluno
Real nota1, nota2, Media
Início
 Escreva ‘Digite as notas do aluno’
 Leia nota1, nota2
 Media = (nota1+nota2)/2
 Se (Media  7 )então 
 	Escreva ‘o aluno foi aprovado’
 Caso contrário
	Escreva ‘o aluno foi reprovado’
 Fim da decisão
Fim do algoritmo
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
Faça um algoritmo para verificar se uma pessoa é maior de idade. (fluxograma e pseudocódigo).
Exercício:
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
Projeto de refinamentos sucessivos 
Top-down design 
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
LEITURA COMPLEMENTAR
Sintaxe:
Se (<expressão>) então
	<instrução>
Fim SE
Semântica:
“Se o valor de expressão for verdadeiro... Então faça 
 <instrução>”
Finalize a estrutura.
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
Exercícios
Faça um algoritmo para verificar se uma pessoa é maior de idade. (fluxograma e pseudocódigo).
2. Faça o pseudocódigo e o fluxograma:
Determine a velocidade média de um veículo que parte de uma cidade A e vai para uma cidade B. O tempo do percurso é de T horas. 
A está no Km KA. 
B está no KB e 
T=H horas.
A
KA
B
KB
T(h)
*
ALGORITMOS
FORMAS DE REPRESENTAÇÃO
Exercícios para Entregar
Considere que uma calculadora comum, de quatro operações, está com as teclas de divisão e multiplicação. 
Escreva algoritmos que resolvam as expressões matemáticas a seguir usando apenas as operações de adição e subtração.
12 * 4
23*11
10÷2
175÷7
28
X*Y
X÷Y