Embed Size (px)
Citation preview
ALGORITMOSOficinas de Desenvolvimento de Software
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);
}
