VA Analise Algoritmos 04

Prévia do material em texto

Aula 4
Estratégias básicas
Análise de Algoritmos
Gisele Alves Santana
Nesta aula, você vai:
§ Conhecer os dois principais tipos de técnicas 
para a otimização de algoritmos
• Refinamento sucessivo;
• Modularização.
Resumo da aula
Aplicações práticas de algoritmos podem ser 
observadas por toda parte. 
Por exemplo, aplicações que funcionam na 
Internet permitem que as pessoas acessem e 
recuperem grandes quantidades de informações. 
Aplicações procuram alocar recursos da melhor 
forma possível, visando maior 
produtividade e menor custo.
Estratégias básicas
Estratégias para a otimização de 
recursos computacionais 
§ Consistem em definir as propriedades e estruturas 
de dados que são implementadas em um algoritmo; 
§ É aconselhado que o algoritmo seja exaustivamente 
testado, simulando diferentes entradas e 
observando as propriedades especificadas.
Estratégias básicas
Problemas de grande porte 
§ Grande motivação está relacionada à otimização 
do tempo de execução e utilização de espaço 
de memória;
§ Complexidade e dificuldade de entendimento de 
como aquele algoritmo realmente funciona, já 
que este geralmente possui um elevando número 
de componentes e um 
alto grau de interação 
entre os mesmos.
Estratégias básicas
Ideia básica
§ Redução da complexidade através do 
desenvolvimento de um programa em 
diferentes fases
• Refinamento sucessivo;
• Decomposição do programa em módulos 
funcionais, utilizando um número limitado de 
estruturas básicas dentre 
de cada módulo.
Estratégias básicas
Conhecida por desenvolvimento top-down.
Princípio: 
§ A resolução de um problema complexo é mais fácil 
se não for necessário considerar todos os aspectos 
deste problema ao mesmo tempo. 
Objetivo principal:
§ Decomposição de um problema de grande porte em 
uma série de subproblemas 
mais simples até chegar 
a um nível onde pode-se 
tentar uma solução.
Refinamento sucessivo
A definição inicial do problema é realizada em um 
nível mais geral (alto nível). 
Depois, o processo avança em etapas. 
Em cada nova etapa, as tarefas são decompostas 
em tarefas mais específicas, até que todos os 
problemas do programa estejam expressos em 
instruções claras e objetivas. 
Refinamento sucessivo
Permite abordar o problema de maneira mais objetiva 
§ Diminui a probabilidade de erros e facilita a sua 
reparação quando os mesmos ocorrerem. 
Existem diversas técnicas que ajudam no 
desenvolvimento de algoritmos facilitando 
seu entendimento para as pessoas. 
Refinamento sucessivo
Exemplo
Refinamento sucessivo
Algoritmo Divisão 
Informar o denominador 
Informar o divisor 
Divisão = Denominador / Divisor
Algoritmo Divisão 
Informar o denominador 
Informar o divisor 
Se o divisor for diferente de zero: Divisão = Denominador / Divisor 
Se o divisor for igual a zero: Divisão não existe 
Técnicas que permitem contornar a complexidade 
de alguns problemas
§ “dividir-para-conquistar”; 
§ Dividir problemas em subproblemas menores; 
§ A partir das soluções obtidas com a resolução dos 
subproblemas, a solução do problema é 
construída como um todo;
§ Se a resolução de um 
subproblema ainda é muito 
complexa, o mesmo pode ser 
dividido em subproblemas ainda 
menores e assim por diante. 
Refinamento sucessivo
Um subprograma precisa ser “chamado” ou 
“invocado” de algum ponto do código do 
programa como um todo do qual faz parte. 
Se durante a execução o fluxo de controle (ordem 
em que os comandos são executados) atingir um 
ponto de invocação, então o fluxo de controle da 
execução passa para o subprograma. 
Subprogramas podem 
ser vistos como funções.
Refinamento sucessivo
Continuando...
Estratégias básicas 
Conjunto de instruções que realizam uma 
tarefa particular. 
São usadas para criar pequenos pedaços de 
códigos separados do programa principal.
Principal finalidade: 
§ Impedir que o programador 
tenha que escrever o mesmo 
código repetidas vezes.
Funções
Sintaxe
Exemplo
Funções
<tipo> <nome>(<parâmetros>)
{
<declarações locais>;
<comandos>;
return 
}
int quadrado (int a)
{
int quad;
quad = a*a;
return quad;
}
Chamando a função
§ Escreve-se o nome da função seguido dos 
parâmetros fornecidos (entre parênteses);
§ Exemplos: 
• quadrado (int x);
• soma ( ).
Funções
Chamando a função
Funções
int soma ( ) //cabeçalho da função
{
int a, b, soma; //variáveis locais
printf (“Digite um numero: \n“); 
scanf(“%d”, &a);
printf (“Digite um numero: \n“); 
scanf(“%d”, &b);
soma = a + b;
printf(“\nSoma = %d“, soma);
}
int main () //programa principal
{
soma ( ); //chamando a função
}
Não se pode utilizar uma função sem antes declará-la. 
O protótipo é uma forma de se escrever uma função 
depois do programa principal (colocado no após a 
inclusão das bibliotecas).
Considerado como declaração de funções. 
Sintaxe: int soma (int a, int b)
Protótipo de funções
#include<iostream.h>
int soma (); // protótipo da função
int main () {
soma ( ); //chamando a função
}
int soma ( ) { // definição da função
Comandos...
}
Sintaxes:
§ return;
§ return expressão;
§ return (expressão).
Exemplo:
Comando return
int Quadrado (int a)
{
return a*a;
}
São utilizados para transmitir informações 
para a função. 
Uma função pode receber qualquer número 
de argumentos. 
Existem funções que não recebem 
nenhum argumento. 
Parâmetros são inseridos 
entre os parênteses após 
o nome da função e 
separados por vírgulas.
Parâmetros
Parâmetros
int celsius (int fahr); // protótipo
int main () {
int c, f;
printf(“\nDigite a temperatura em 
Fanrenheit: “);
scanf(“%d”, &f);
c = celsius ( f ); //chamando a função 
com a passagem da variável f
printf(“\nTemperatura em celsius: %d”, 
c); 
}
int celsius (int fahr) { //função
int c;
c = (fahr – 32) *5/9;
return c; //retorna um valor para o 
programa principal
}
Considere funções trigonométricas, como seno, 
cosseno, etc. 
A função seno, por exemplo, recebe o valor de um 
ângulo e devolve o seno desse ângulo
§ float seno (float angulo).
Quando as variáveis são passadas por valor, a função 
cria novas variáveis do mesmo tipo e copia nelas os 
valores dos parâmetros. 
As funções não têm acesso 
às variáveis da função 
principal (int main). 
Passagem por valor
Algumas vezes é necessário retornar mais de um 
valor e quando isso é necessário, utiliza-se a 
passagem por referência. 
Principal vantagem
§ A função pode acessar as variáveis da 
função principal.
A passagem por referência 
utiliza o operador unário 
de referência (“&”). 
Esse operador cria outro 
nome para uma variável. 
Passagem por referência
Considere as instruções:
§ int n;
§ int & n1 = n.
Operador &n1 = n
§ Indica que n1 é outro nome para n;
§ O operador “&”faz referência ao endereço de 
memória de uma variável;
§ Uma referência não é uma 
cópia da variável, mas a mesma 
variável sob diferentes nomes.
Passagem por referência
São declaradas duas 
variáveis: n e n1.
Finalizando...
Estratégias básicas 
Durante a fase de projeto, a solução do problema total 
vai sendo organizada em soluções de subproblemas
§ Possibilita a divisão do programa em vários módulos 
que possuem funções claramente definidas. 
Essas funções podem ser implementadas 
separadamente por vários programadores 
de uma mesma equipe. 
Modularização
Um dos métodos utilizados para a resolução de 
problemas complexos trata da divisão de um 
grande problema em problemas menores. 
A partir disso, os sub problemas menores 
são resolvidos um de cada vez. 
Modularização
Umalgoritmo pode ser composto por vários 
subalgoritmos
§ Denominados de módulos. 
Um problema complexo pode ser visualizado 
como um conjunto de problemas mais simples.
Módulos 
§ Conceito computacional, 
que aplica a divisão de um 
programa em partes funcionais, 
sendo que estas partes 
se comunicam entre si.
Modularização
O módulo representa uma tarefa relacionada 
ao programa. 
No caso de um conjunto de comandos ou apenas 
um comando que executa uma única função para 
a solução do problema, o mesmo pode ser 
considerado como um módulo funcional
§ Função. 
Modularização
Os algoritmos são executados linha por linha 
(uma linha após a outra). 
Quando funções são implementadas, o algoritmo 
para em determinado ponto, executa essa função, 
mas volta imediatamente após o ponto que parou. 
Nesse caso, a função faz parte do programa 
principal, somente está em uma 
região diferente e é acessada 
através de uma chamada a ela.
Modularização
Um programa pode ser pensado de maneira modular
§ Como um conjunto de blocos a serem 
ligados de alguma forma. 
Como a função realiza uma operação específica, ela 
pode ser considerada como a parte modularizada de 
um programa.
Modularização
Um bom algoritmo deve tentar reduzir a interação 
entre módulos (denominada de acoplamento) e 
aumentar o relacionamento dos elementos de um 
mesmo módulo (denominado de coesão).
Modularização
Modularizar um problema 
§ Dividir o mesmo em pequenas partes, sendo que 
cada uma dessas partes será responsável pela 
realização de uma etapa do problema.
Para auxiliar no desenvolvimento de um algoritmo 
é utilizada a modularização, a qual torna mais fácil 
a resolução de pequenos 
problemas ao invés de 
um problema complexo.
Modularização
Dúvidas?