ALGORITMOS Oficinas de Desenvolvimento de Software

ALGORITMOSOficinas de Desenvolvimento de Software

Prof. Norton

www.norton.net.brNorton.Glaser@fatec.sp.gov.br

Programação

Inicio as 19:00 Conceitos e definição de algoritmos Vetores e matrizes Recursão Intervalo 20:40 Retorno 21:00 Pesquisa Ordenação

O que é algoritmo ?

Um algoritmo é uma sequência ordenada de instruções para resolver um problema.

Um algoritmo deve possuir as seguintes propriedades: garantia de término, exatidão e efetividade.

“Algoritmo é uma sequência de passos que visa atingir um objetivo bem definido” (FORBELLONE, 1999)

“Algoritmo é a descrição de uma sequência de passos que deve ser seguida para a realização de uma tarefa”

(ASCENCIO, 1999)

O que é algoritmo ?

Um algoritmo e composto por: Problematização Instruções unitarias Sequencia Logica

Um algoritmo pode ser representado por: Uma descrição narrativa Um Fluxograma Um Programa

Variáveis

Variável e um espaço alocado na memoria para o armazenamento de um dado, durante a execução de um programa.

Este valor pode ser modificado durante o processamento do algoritmo

Exemplo:int quantidade = 8;float temperatura = 21.5;

Estruturas de Dados

Os tipos primitivos (inteiro, real, caracter e lógico) não são suficientes para representar todos os tipos de informação.

Particularmente quando temos mais de uma informação relacionada. Ex: Lista dos nomes dos alunos de uma sala, endereço de alguém etc.

Utilizaremos os tipos primitivos para construir outras estruturas de dados mais complexas.

Vetores

Também denominados: Estruturas compostas homogêneas unidimensionais

Permitem a manipulação de um conjunto de informações de um mesmo tipo primitivo

Exemplo: float valores [40];

Onde: 40: Quantidade total de elementos do vetor float: Tipo primitivo base do vetor valores: nome que representa o vetor no programa O índice do vetor inicia-se em 0 (zero) indo até 39 (n – 1)

Vetores Manipulação:

0 1 2 3 4 5 6 7 8 37 38 39

int A = 5;

valores [ 6 ] = 6.5;

6.57.8 5.3

valores

valores [ 1 ] = 7.8;valores [ 3 ] = 5.3;

valores [ A ] = 9.8;valores [ A-1 ] = 9.1;leia ( valores [ A+3 ] ); // supondo que foi informado 4.7

9.89.1 4.7

Vetores - Notas acima da média usando vetor

float notas [10];int NotaAcima;float Soma, Media;Soma = 0;NotaAcima = 0;for(int X =0; X < 10; X++){

cin >> notas[X];Soma=Soma + notas[X];

}Media = Soma / 10;for(int X=0; X<10; X++){

if(notas[X] > Média ){NotaAcima=NotaAcima + 1;

}}cout << NotaAcima;

Matrizes

Também denominadas: Estruturas compostas homogêneas

multidimensionais Permitem a manipulação de um conjunto de

informações de um mesmo tipo primitivo. Exemplo:

int SALA[4][4];

Onde: SALA: Nome da matriz 4: Capacidade da primeira e da segunda dimensão int: Tipo primitivo base da matriz

Matrizes Manipulação:

0 1 2 3int A, B;

SALA [1][2] = 5;

SALA

SALA [2][1]= 6;SALA [0][1] = 7;A = 3;

SALA [A][B]= 8;SALA [A][B-2]= 9;SALA [A-2][B-2]= 10;

0

1

2

3

5

6

7

89

10

11

12

SALA [B][A] =11;SALA [B-2][A] =12;

B = 2;

Matrizes – Temperatura Semanal

float temperatura [7][3];float minima, maxima, media;minima = 99;maxima = -99;media = 0;for(int J =0 ; J<7; J++){

cin >> temperatura[J][0] ; //Temperatura minima do diacin >> temperatura[J][1] ; //Temperatura maxima do diatemperatura[J][2] = (temperatura[J][0] + temperatura[J][1]) /2;if(temperatura[J][0] <= minima) minima = temperatura[J][0];if(temperatura[J][1] >= maxima) maxima = temperatura[J][1];media += temperatura[J][2];

}media = media / 7;cout << minima << maxima << media;

Recursão

Recursividade é o mecanismo de programação no qual uma definição de função ou de outro objeto refere-se ao próprio objeto sendo definido.

São sinônimos: recursividade, recursão, recorrência.

Recursão

Funções Recursivas Recursividade Mutua Recursividade de cauda

Recursão – Funções Recursivas Estratégia para a definição recursiva de uma função:

dividir o problema em problemas menores do mesmo tipo

resolver os problemas menores (dividindo-os em problemas ainda menores, se necessário)

combinar as soluções dos problemas menores para formar a solução final

Ao dividir o problema sucessivamente em problemas menores eventualmente os casos simples são alcançados: não podem ser mais divididos suas soluções são definidas explicitamente

Recursão – Funções Recursivas Em todas as funções recursivas existe:

Um caso base, ou condição de parada, cujo resultado é imediatamente conhecido.

Um passo recursivo em que se tenta resolver um sub problema do problema inicial.

Assim função recursiva é uma função que é definida em termos de si mesma.

Recursão – Fatorial

int fatorial(int n){if(n == 1) return n;return fatorial(n-1) * n;}

Recursão – Potencia de 2

int pot(int base, int exp){if(exp == 0) return 1;return (base * pot(base, exp-1));}

Recursão – Fibonacci

int fibonacci(int n){if(n==1 || n==2) return 1;elsereturn fibonacci(n-1)+fibonacci(n-2);}

Recursão – Recursividade Mutua Recursividade mútua ocorre quando

duas ou mais funções são definidas em termos uma da outra.

Na Recursividade mútua , as subrotinas são conectadas através de uma cadeia de chamadas sucessivas que acaba retornando à primeira que desencadeou.

Para exemplificar a recursividade indireta vamos utilizar um código que verifica se um número é par ou ímpar:

Recursão – Par e Impar

int par(int n){if(n==0) return 1;return impar(n-1);}

int impar(int n){if(n==0) return 0;return par(n-1);}

Recursividade de Cauda

Uma função recursiva apresenta recursividade de cauda se o resultado final da chamada recursiva é o resultado final da própria função.

Se o resultado da chamada recursiva deve ser processado de alguma maneira para produzir o resultado final, então a função não apresenta recursividade de cauda.

A recursão de cauda é uma técnica de recursão que faz menos uso de memória durante o processo de empilhamento, o que a torna mais rápida que a recursão comum.

Recursividade de Cauda

int fatorial_aux(int n, int parcial){if(n==1) return parcial;return fatorial_aux((n-1), parcial*n));}

int fatorial_cauda(int n){return fatorial_aux(n, 1);}

Recursividade de Cauda

O que acontece é uma transcrição direta de um cálculo iterativo: passa-se inicialmente o valor parcial 1 para a função

fatorial_aux() e ela “atualiza” este valor a cada chamada recursiva, multiplicando o cálculo parcial do fatorial por n, n – 1, n – 2, …, até o “caso base”.

Neste ponto, o valor do fatorial já foi calculado e é apenas retornado.

Esta recursão de cauda poderia gastar menos memória ainda se utilizasse passagem por referência dos parâmetros.

Desta forma, cada função recursiva empilhada não criaria um espaço de memória para os parâmetros n e parcial, mas apenas atualizaria estas duas variáveis sem ficar fazendo cópias delas.

Recursão versus Iteração

Recursão Iteração

Estruturas de seleção if, if-else ou switch.

Estruturas de repetição for, while ou do-while

Repetição por chamadas de funções repetidas.

Repetição explícita.

Termina quando um caso base é reconhecido.

Termina quando teste do laço falha.

Pode ocorrer infinitamente Pode ocorrer infinitamente.

Lento Rápido.

Soluções simples e de fácil manutenção

Soluções complicadas e de difícil manutenção.

Recursão versus Iteração

Mesmo diminuindo-se os gastos de memória da recursão através de uma implementação que usa recursão de cauda e passagem de parâmetros por referência, o cálculo iterativo será comumente mais rápido por não fazer repetidas chamadas de funções.

No entanto, a recursão de cauda é importante principalmente em linguagens de programação funcionais, onde não existem estruturas de repetição.

Neste caso, a recursão é a única abordagem disponível e o desempenho pode ser fator crítico, exigindo implementações de recursão de cauda.

Pesquisa

Algoritmos de pesquisa tem o objetivo de encontrar valores em uma estrutura de dados.

Para vetores ou matrizes não ordenadas utilizamos a pesquisa linear.

Para vetores ou matrizes ordenadas podemos utilizar a pesquisa binaria.

Pesquisa Linear

Busca linear ou sequencial e um tipo de pesquisa em vetores ou listas de modo sequencial, elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente.

No melhor caso, o elemento a ser buscado é encontrado logo na primeira tentativa da busca.

No pior caso, o elemento a ser buscado encontra-se na última posição e são feitas N comparações, sendo N o número total de elementos.

Pesquisa Linear - Iterativo

int linearI(int v[], int tamanho, int busca){for(int i=0; i<tamanho; i++){

if(v[i] == busca){return i;

}}return -1;

}

Pesquisa Binaria

A pesquisa ou busca binária é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista.

Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor.

Se o elemento do meio do vetor for a chave, a busca termina com sucesso.

Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor.

E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.

Pesquisa Binaria - Iterativoint binariaI(int v[], int chave, int N){

int inf = 0; //limite inferiorint sup = N-1; //limite superiorint meio;while(inf <= sup){

meio = inf + (sup-inf)/2;if(chave == v[meio]){

return meio;} else {

if(chave < v[meio])sup = meio – 1;

else inf = meio + 1;

}return -1; //não encontrado

}

Ordenação

Ordenação é o ato de se colocar os elementos de uma sequência de informações, ou dados, em uma ordem predefinida.

Os algoritmos que ordenam um conjunto, geralmente representados em um vetor, são chamados de algoritmos de ordenação.

Os algoritmos de ordenação auxiliam os algoritmos de busca.

Ordenação

Métodos Simples Selection sort – Ordenação por seleção Insertion sort - Ordenação por inserção Bubble sort - Ordenação por flutuação

Métodos Sofisticados Quicksort – Ordenação Eficiente

Ordenação por Seleção

Algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida),

Depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.

Ordenação por Seleção

Ordenação por Seleçãovoid selection_sort(int v[], int tam){

int min,aux;for(int i=0; i < (tam-1); i++) {min = i;for(int j = (i+1); j<tam; j++){

if(v[j] < num[min]){min = j;

}}if(i != min){aux = num[i];num[i] = num[min]; num[min] = aux;

}}

}

Ordenação por Seleção

5 3 1 4 2 4 comparações (5 e 3; 3 e 1; 1 e 4; 1 e 2)

1 3 5 4 2 3 comparações (3 e 5; 3 e 4; 3 e 2)

1 2 5 4 3 2 comparações (5 e 4; 4 e 3) 1 2 3 4 5 1 comparação (4 e 5) 1 2 3 4 5 n – 1 iterações realizadas: vetor

ordenado

Ordenação por Inserção

Semelhante ao processo de ordenação de cartas usado por jogadores de baralho. Olhar a sequência de cartas da esquerda para a direita

e ver se alguma está fora da ordem. Ao encontrar uma fora da ordem, procura sua posição

correta nas cartas já olhadas que estão em ordem. Eficiente quando aplicado a um pequeno número de

elementos. Em termos gerais, ele percorre um vetor de elementos

da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados

Ordenação por Inserção

Ordenação por Inserção

void insertSort(int v[], int tam){int eleito, j;for(int i=1; i < tam; i++) {eleito = v[i];j = i-1;while((j>=0) && (eleito < v[j])){v[j+1] = números[j];j--;

}v[j+1] = eleito;}}

Ordenação por Inserção

5 4 3 2 1 1 comparação (5 e 4) 4 5 3 2 1 2 comparações (3 e 5; 3 e 4) 3 4 5 2 1 3 comparações (2 e 5; 2 e 4; 2 e 3) 2 3 4 5 1 4 comparações (1 e 5; 1 e 4; 1 e 3;

1 e 2) 1 2 3 4 5 N vazio e O igual ao tamanho do

vetor: vetor ordenado

Ordenação por Bolha

Dado um vetor de N elementos, inicia a iteração comparando o primeiro elemento com o segundo: se não estiverem em ordem (primeiro maior

que o segundo), eles são trocados; caso contrário, nada acontece. Em seguida, faz-se o mesmo para o segundo e

terceiro elementos. O processo se repete até que, ao final de n – 1

iterações, o maior elemento do vetor será deslocado de sua posição inicial para a última.

Ordenação por bolha

Ordenação por bolha

void bubbleSort(int v[], int tam){int aux;for(int i=tam-1; i >=1; i--) {for(int j=0; j < i; j++) {if(v[j]>v[j+1]){aux = v[j];v[j] = v[j+1];}

}}

}

Ordenação por Bolha

5 4 3 2 1 4 comparações (5 e 4; 5 e 3; 5 e 2; 5 e 1)

4 3 2 1 5 3 comparações (4 e 3; 4 e 2; 4 e 1) 3 2 1 4 5 2 comparações (3 e 2; 3 e 1) 2 1 3 4 5 1 comparação (2 e 1) 1 2 3 4 5 n – 1 iterações realizadas: vetor

ordenado

Ordenação Eficiente - QuickSort O Quicksort adota a estratégia de divisão

e conquista. A estratégia consiste em rearranjar as

chaves de modo que as chaves "menores" precedam as chaves "maiores".

Em seguida o Quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada.

Ordenação Eficiente - QuickSort Os passos são:

1. Escolha um elemento da lista, denominado pivô;

2. Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sublistas não ordenadas. Essa operação é denominada partição;

3. Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;

Ordenação Eficiente - QuickSort A base da recursão

são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte

Ordenação Eficiente - QuickSort

Ordenação Eficiente - QuickSort

void quickSort(int v[], int esquerda, int direita){int i, j, x, y;i = esquerda;j = direita;x = v[(esquerda + direita) / 2];while(i<=j) {

while(valor[i] < x && i < direita) {i++;

}while(valor[j] > x && j > esquerda){j--;

}if(i <=j){y = valor[i];valor[i] = valor[j];valor[j] = y;i++;j--;

}}if(j > esquerda) quickSort(v, esquerda, j);if(i < direita) quickSort(v, i, direita);

}