algoritmos

Prévia do material em texto

Algoritmos e 
Estrutura de Dados I 
Ciência da Computação 
Prof. José Carlos Toniazzo 
PARE PENSE PERGUNTE 
Algoritmos Seqüenciais 
 O que é um algoritmo? 
 
 
 
 Algoritmo Seqüencial 
 A execução das tarefas é corretamente 
cumprida, se executarmos todos os passos 
(instruções) na seqüência em que elas 
aparecem, da primeira até a última, sem 
omissões e sem repetições. 
 
 
 
 
 
“Um conjunto finito de regras, bem definidas, 
Para a solução de um problema 
em um tempo finito.” 
Definições 
 “Um conjunto finito de regras que provê uma seqüência de 
operações para resolver um tipo de problema específico” 
[KNUTH] 
 
 “Seqüência ordenada, e não ambígua, de passos que levam à 
solução de um dado problema” [TREMBLAY] 
 
 “Processo de cálculo, ou de resolução de um grupo de 
problemas semelhantes, em que se estipulam, com generalidade 
e sem restrições, as regras formais para a obtenção do resultado 
ou da solução do problema” [AURÉLIO] 
 
 A atenção desta disciplina estará voltada à automação de 
tarefas utilizando computadores. 
Características 
 Todo algoritmo deve apresentar algumas 
características básicas: 
 ter fim; 
 não dar margem à dupla interpretação (não ambíguo); 
 capacidade de receber dado(s) de entrada do mundo 
exterior; 
 poder gerar informações de saída para o mundo externo 
ao do ambiente do algoritmo; 
 ser efetivo (todas as etapas especificadas no algoritmo 
devem ser alcançáveis em um tempo finito). 
Nível de Detalhamento 
Nível de Detalhamento 
Exemplo #1 
 Dados três valores positivos, a, b e c, 
determine a sua média aritmética 
 
 Quais as tarefas a serem executadas para a 
solução deste problema? 
Entrada e Saída 
Entrada 
Saída 
Conjunto de 
Regras 
(processamento) 
Obter os valores para a, b e c. 
Calcular a média aritmética. 
Comunicar os resultados. 
Pensando no Problema 
 Começamos com uma afirmação genérica da 
solução do problema e prosseguimos até o 
algoritmo final, aumentando sistematicamente 
o nível de detalhamento. 
Metodologia para o 
desenvolvimento de algoritmos 
 Passo 1: ler cuidadosamente a especificação do 
problema. 
 
 Passo 2: levantar e analisar todas as saídas 
exigidas na especificação do problema. 
 
 Passo 3: levantar e analisar todas as entradas 
citadas na especificação do problema. 
 
 Passo 4: Como, a partir das entradas, chegarei as 
saídas? (processamento) 
Metodologia para o 
desenvolvimento de algoritmos 
 Passo 5: verificar se é necessário gerar 
valores internamente ao algoritmo e levantar 
as variáveis necessárias e os valores iniciais 
de cada uma (comentar) 
 
 Passo 6: levantar e analisar todas as 
operações e transformações necessárias 
para, dadas as entradas e valores gerados 
internamente, produzir as saídas 
especificadas (comentar) 
Metodologia para o 
desenvolvimento de algoritmos 
 Passo 7: testar cada passo do algoritmo, 
verificando se as transformações 
intermediárias executadas estão conduzindo 
aos objetivos desejados. Utilizar, sempre que 
possível, valores de teste que permitam 
prever os resultados. 
 
 Passo 8: fazer uma reavaliação geral, 
elaborando o algoritmo através da integração 
das partes. 
Exercícios 
 Quais os passos/regras necessárias para 
1. Trocar um pneu de carro? 
2. Fazer um bolo de chocolate? 
 
Critérios para Avaliação do 
Algoritmo 
 Pode existir mais de uma solução para o 
mesmo problema 
 
 Exemplo 
 Encontrar todos os números primos... 
 
Critérios para um algoritmo 
 Ter um número finito de passos 
 Ter passo devem estar precisamente definido. 
 Existir um conjunto de zero ou mais entradas, bem 
definidas. 
 Existir uma ou mais saídas. 
 Ter um conjunto de passos que leve a execução de 
uma tarefa útil. 
 Ter uma condição de fim sempre atingida para 
quaisquer entradas e num tempo finito. 
 
Formas de Representação 
 Existem diversas formas de representação de algoritmos, mas 
não há um consenso com relação à melhor delas. 
 
 O critério usado para classificar hierarquicamente estas formas 
está diretamente ligado ao nível de detalhe ou, inversamente, ao 
grau de abstração oferecido. 
 
 Algumas formas de representação de algoritmos tratam os 
problemas apenas em nível lógico, abstraindo-se de detalhes de 
implementação muitas vezes relacionados com alguma 
linguagem de programação específica. Por outro lado, existem 
formas de representação de algoritmos que possuem uma maior 
riqueza de detalhes e muitas vezes acabam por obscurecer a 
idéia principal, o algoritmo, dificultando seu entendimento. 
Formas de Representação 
 Dentre as formas de representação de 
algoritmos mais conhecidas destacam-se: 
 
 Descrição Narrativa; 
 Diagrama de Nassi-Shneiderman – Diagrama de 
Chapin 
 Fluxograma Convencional; 
 Pseudocódigo, também conhecido como 
Linguagem Estruturada ou Portugol. 
Descrição Narrativa 
 Faz-se uso do português para descrever algoritmos. 
 
 EXEMPLO: Receita de Bolo: 
 Providencie manteiga, ovos, 2 Kg de massa, etc. 
 Misture os ingredientes 
 Despeje a mistura na fôrma de bolo 
 Leve a fôrma ao forno 
 Espere 20 minutos 
 Retire a fôrma do forno 
 Deixe esfriar 
 Prove 
 
 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). 
Diagrama de Chapin 
 Também conhecido como diagrama Chapin, esta ferramenta de 
representação oferece grande clareza para a representação de 
sequenciação, seleção e repetição num algoritmo, utilizando-se 
de uma simbologia própria. A idéia básica deste diagrama é 
representar as ações de um algoritmo dentro de um único 
retângulo, subdividido-o em retângulos menores, que 
representam os diferentes blocos de seqüência de ações do 
algoritmo. Seleção e repetição também são representadas de 
forma gráfica, dentro dos retângulos. 
 
 Seqüência 
 Ação-1 
 Ação-2 
 Ação-n 
 
Fluxograma Convencional 
 É uma representação gráfica de algoritmos onde 
formas geométricas diferentes implicam ações 
(instruções, comandos) distintos. Tal propriedade 
facilita o entendimento das idéias contidas nos 
algoritmos e justifica sua popularidade. 
 
 Esta forma é aproximadamente intermediária à 
descrição narrativa e ao pseudocódigo pois é 
menos imprecisa que a primeira e, no entanto, não 
se preocupa com detalhes de implementação do 
programa como o tipo das variáveis usadas. 
Fluxograma Convencional 
Fluxograma Convencional 
Pseudo-Código (Portugol) 
 Poderemos construir um programa em uma 
linguagem estruturada com facilidade se tivermos um 
algoritmo em pseudo-código estruturado 
adequadamente 
 
 Os elementos do pseudo-código são os mesmos das 
linguagens estruturadas. Isto é, depois de 
desenvolver as idéias, a tradução para linguagem de 
programação é um processo simples e mecânico. 
 
 É isto que devemos fazer!!!!! 
Pseudo-Código (Portugol) 
 A forma geral da representação de um algoritmo na 
forma de pseudocódigo é a seguinte: 
 
Algoritmo <nome_do_algoritmo> 
<declaração_de_variáveis> 
<subalgoritmos> 
Início 
 <corpo_do_algoritmo> 
Fim. 
Pseudo-Código (Portugol) 
 Onde: 
 Algoritmo é uma palavra que indica o início da definição de um 
algoritmo em forma de pseudocódigo. 
 <nome_do_algoritmo> é um nome simbólico dado ao algoritmo com a 
finalidade de distinguí-lodos demais. 
 <declaração_de_variáveis> consiste em uma porção opcional onde 
são declaradas as variáveis globais usadas no algoritmo principal e, 
eventualmente, nos subalgoritmos. 
 <subalgoritmos> consiste de uma porção opcional do pseudocódigo 
onde são definidos os subalgoritmos (funções e procedures) 
 Início e Fim são resprectivamente as palavras que delimitam o início e 
o término do conjunto de instruções do corpo do algoritmo. 
 
 Consiste na definição de uma pseudocódigo de programação, cujos 
comandos são em português, para representar algoritmos. 
ESTRUTURAS CHAVES DA 
CONSTRUÇÃO DE ALGORITMOS 
 SEQUENCIAÇÃO 
 Os comandos do algoritmo fazem parte de uma 
seqüência, onde é relevante a ordem na qual se 
encontram os mesmos, pois serão executados 
um de cada vez, estritamente, de acordo com 
essa ordem. De uma forma genérica, poderíamos 
expressar uma seqüência da seguinte maneira: 
 Comando-1 
 Comando-2 
 Comando-n 
Entrada e Saída 
 Um algoritmo pode receber dados através de 
dispositivos como teclado, mouse, discos e 
placas de rede, e pode enviar dados para o 
monitor de vídeo, discos e outros. 
 
 Este tipo de operações em que dados são 
recebidos por um algoritmo ou são enviados 
por um algoritmo para um dispositivo são 
chamados de operações de entrada e saída. 
Resumindo 
Expressões: Aritméticas e 
Lógicas 
 3 + 7 * 2 – 15 
 
 Verdadeiro E Falso ou Verdadeiro 
 3 + 2 < 5 
 
 Pode-se armazenar o resultado em uma 
variável: 
 imposto <- valor * 0,18 
Exemplos 
Operadores Relacionais 
Exemplo: Hipotenusa 
Algoritmo lados_triângulo 
{Este algoritmo calcula o valor dos lados de 
um triângulo retângulo, dados um de seus ângulos 
menores e a hipotenusa} 
variável 
lado_oposto, lado_adjacente: real 
hipotenusa, alfa: real 
leia(alfa) 
leia(hipotenusa) 
lado_oposto <- seno(alfa)*hipotenusa 
lado_adjacente <- cosseno(alfa)*hipotenusa 
escreva(lado_oposto) 
escreva(lado_adjacente) 
fim 
Exemplo: Hipotenusa - 
Identado 
Algoritmo lados_triângulo 
 
Início 
 
 {Este algoritmo calcula o valor dos lados de 
 um triângulo retângulo, dados um de seus ângulos 
 menores e a hipotenusa} 
 
 variável 
 lado_oposto, lado_adjacente: real 
 hipotenusa, alfa: real 
 
 leia(alfa) 
 leia(hipotenusa) 
 
 lado_oposto <- seno(alfa)*hipotenusa 
 lado_adjacente <- cosseno(alfa)*hipotenusa 
 
 escreva(lado_oposto) 
 escreva(lado_adjacente) 
 
fim 
A Importância das Estruturas 
de Dados 
 Algoritmos são responsáveis por definir o 
comportamento de um programa. Ou seja, são 
responsáveis pela lógica de execução do software; 
 
 Estruturas de Dados são espaços onde os dados de 
Entrada, Processamento e Saída ficam 
armazenados em um computador; 
 
 São conceitos que se complementam. Um depende 
do outro para que sejam corretamente utilizados! 
Tipos de Dados 
 Todo dado é de um certo tipo que define sua 
natureza (p. ex., um nome é diferente de um 
valor), identificando seu uso, e define as 
operações que podem ser realizadas com o 
dado 
 
 Por exemplo, podemos somar dois valores 
numéricos, mas não podemos somar um 
número e uma frase. 
Tipos de Dados: Numérico 
 Inteiro: representa um número inteiro. 
 
 Por exemplo -1, 0, 1, e 26 são dados inteiros. 
Dados deste tipo podem ser usados para 
idade em anos, número de filhos etc. 
Tipos de Dados: Numérico 
 No projeto de um algoritmo devemos utilizar o 
tipo numérico mais adequado, ou seja, não 
devemos usar um número real quando um 
número inteiro resolve o problema. 
 
 Cuidado! Dividir dois números inteiros pode 
resultar em um número real... 
Tipos de Dados: Caractere 
 Valores alfanuméricos incluem letras, 
algarismos e símbolos. Por exemplo, '1‘ é um 
caracter se consideramos apenas o símbolo 
'1' e não o valor 1. 
 
 Letras do alfabeto, símbolos... 
 
 Pesquisar sobre: tabela ASCII 
Tipos de Dados: Enumeração 
 Um dado que pode assumir um valor dentre 
os valores de um conjunto é uma enumeração 
ou tipo enumerado. 
 
 Por exemplo, um dado que pode assumir 
qualquer valor dentro do conjunto de frutas 
 
 banana, maça, pêra, uva, jaca 
Tipos de Dados: Variáveis 
 A variável possui, além do nome, um tipo, 
responsável por definir como o dado vai ser 
armazenado e recuperado da memória. 
 
 Em pseudo-código as variáveis são 
declaradas na seção de declarações, antes da 
seção de comandos, na cláusula variável 
 
 variável 
 salário: real 
Tipos de Dados: Variáveis 
Tipos de Dados: Constantes 
 É possível dar nome às constantes utilizadas 
nos algoritmos. 
 
 As constantes identificadas, assim como as 
constantes literais, podem ser atribuídas a 
variáveis. 
 constante 
 pi = 3,1415926 
 salário_mínimo = 420,00 
Porque utilizar Algoritmos? 
Hardware (Baixo Nível) 
01110111111 
Software (Alto Nível) 
Main, if, else, for, int i, printf, etc... 
COMPILAÇÃO 
“Traduzir” do Alto para Baixo Nível 
ALGORITMO: Permite “traduzir” instruções entendidas por 
um Humano para uma máquina 
Programa de Computador Para o Usuário Utilizar 
Word, Excel, Jogos, Sistemas Comerciais... 
Programador, pessoa que abstrai o problema para resolvê-lo 
Equivalência: Algoritmo X 
Programação ( Linguagem C ) 
Portugol Linguagem C 
Início / Fim { / } 
para/faça for 
enquanto while 
se/então/senão if/else 
escreva printf() / puts()... 
leia scanf() / gets()... 
Exercícios 
 Vamos praticar a construção de alguns algoritmos! 
 
 1 – Faça um algoritmo que, a partir da altura e do peso de uma 
pessoa mostre qual seu índice de IMC: 
 A) identifique entrada, processamento e saída; 
 B) identifique as estruturas de dados necessárias para resolver o 
problema; 
 C) escreva o passo a passo do algoritmo utilizando nossa 
linguagem natural; 
 D) escreva o algoritmo utilizando Pseudo-Código; 
 E) escreva o algoritmo utilizando Fluxograma; 
 F) escreva suas conclusões a respeito da resolução do problema