1 - INTRODUÇÃO

Prévia do material em texto

DEQ/6648 – FUNDAMENTOS DA 
ESTRUTURA DA INFORMAÇÃO 
Departamento de Engenharia Química 
Universidade Estadual de Maringá 
Prof. Leonardo Faria Costa 
INTRODUÇÃO 
• Apresentação dos Algoritmos 
• Recursividade 
• Complexidade de Algoritmos 
• Notação O 
• Algoritmos Ótimos 
INTRODUÇÃO 
• Um algoritmo é um processo sistemático para a 
resolução de um problema 
 
• Dois aspectos básicos no Estudo dos algoritmos: 
 
Correção – verificar a exatidão do método empregado 
através de uma prova matemática. 
 
Análise – avaliar a eficiência do algoritmo em termos de 
tempo de execução e memória ocupada. 
INTRODUÇÃO 
• Durante o processo de computação o algoritmo 
manipula dados gerados pela entrada 
• Tipo Abstrato de Dados – quando os dados são 
dispostos e manipulados de uma forma 
homogênea. 
ALGORÍTMO ENTRADA SAÍDA 
Tipo Abstrato de Dados 
• Modelo matemático + Conjunto de operações 
definido sobre este modelo 
 
• Um algoritmo é projetado em termos de tipos 
abstratos de dados 
 
• Na representação do modelo matemático 
emprega-se uma estrutura de dados 
 
• As estruturas diferem uma das outras pela 
disposição ou manipulação de seus dados 
 
Tipo Abstrato de Dados 
• Estrutura de dados <-> conhecimento dos 
algoritmos 
 
• A escolha certa da estrutura adequada para 
cada caso depende do conhecimento de 
algoritmos para manipular a estrutura de 
forma eficiente 
Apresentação dos algoritmos 
• Os algoritmos serão descritos através de uma linguagem 
de estrutura simples de blocos semelhante ao Pascal 
 
• O início e final de cada bloco são determinados pela 
posição da margem esquerda 
 
• Se uma certa linha do algoritmo inicia um bloco, ele se 
estende até a última linha seguinte, cuja margem 
esquerda se localiza mais a direita do que a primeira do 
bloco 
 
 
 
Apresentação dos algoritmos 
• Exemplo: o bloco iniciado por para inclui as três 
linhas seguintes. 
 
• A declaração de atribuição é indicada por := 
 
Exemplo 
Para i: =1,..., [n] faça 
 temp:= S[i] 
 S[i]:= S[n – i + 1] 
 S[n- i + 1]:= temp 
 
Apresentação de algoritmos 
•Variáveis simples, vetores, matrizes e registros - linguagens de 
programação; 
• Elementos de vetores e matrizes são identificados por índices 
entre colchetes: 
 
– A[5]: quinto elemento do vetor A 
– B[i,3]: elemento localizado na linha i e coluna 3 
– T.chave: indica o campo chave do registro T 
 
•Referência a registros podem ser realizadas por meio de ponteiros 
que armazenam endereços com o uso do símbolo ↑. 
Apresentação de algoritimos 
 
• Cada ponteiro é associado a um único tipo de registro, por 
isso o nome do registro pode ser omitido; 
 
•Exemplo: pt↑.info representa o campo info de um registro 
alocado no endereço contido em pt 
 
•A sentença após o símbolo % significa comentário 
APRESENTAÇÃO DE ALGORÍTMOS 
• Comandos de decisão e repetição 
– se... então 
– se... então... senão 
– enquanto... faça 
– para ... faça 
– pare 
 
Exemplo:Inversão de uma sequência 
•Uma sequência de elementos armazenada no vetor S[i], onde 1 ≤ i ≤ n. 
Deseja-se inverter os elementos da sequência no vetor . 
Para i: =1,..., [n] faça 
 temp:= S[i] 
 S[i]:= S[n – i + 1] 
 S[n- i + 1]:= temp 
 
Para s = 1 e n = 20 
O valor que estiver na primeira posição do vetor S é chamado temp S[1]; 
O que estiver na última posição do vetor S (S[20 – 1 + 1]) = S[20] irá para a primeira 
posição de do vetor (S[1] = S[20]) 
O conteúdo dessa posição será temp. 
Recursividade 
• Procedimento recursivo é um tipo especial de 
procedimento que contém em sua descrição, 
uma ou mais chamadas a si mesmo e a chamada 
é dita chamada recursiva. 
• Todo procedimento recursivo deve possuir pelo menos 
uma chamada de um local exterior a ele (chamada 
externa) 
 
 
Exemplo de recursivo - Fatorial 
• Cálculo do fatorial de um inteiro n ≥ 0, n!=n(n-1)! 
 Sabe-se que 0! = 1; 1! = 1 
 
 função fat(i) 
 fat(i) := se i ≤ 1 então 1 
 senão i x fat(i-1) 
 
• Variável fat – representa uma função 
 
Procedimento não recursivo 
• Um procedimento não recursivo é aquele em que 
todas as chamadas são externas. 
 
• Exemplo: cálculo do fatorial (não recursivo) 
 
 fat[0] := 1 
 para j := 1,... , n faça 
 fat[j] := j x fat[j-1] 
 
• A variável fat é um vetor 
Procedimento não recursivo 
• Todo procedimento recursivo corresponde um 
outro não recursivo que executa, exatamente a 
mesma computação. 
 
• Qual procedimento é melhor? 
 Procedimento recursivo apresenta maiores 
vantagens pois são mais concisos do que os 
não recursivos; a verificação da correção pode 
ser mais simples também 
Complexidade do algoritmo 
• Uma característica importante do algoritmo é o seu tempo de execução: 
 
– Método empírico – tempo de execução através da execução 
propriamente dita do algoritmo 
– Método analítico – medir o tempo de execução de forma 
independente do computador utilizado, da linguagem e das 
condições locais de processamento 
 
• Objetivo de usar esses métodos é obter uma expressão matemática para 
avaliar o tempo de um algoritmo que não é uma tarefa simples 
 
Propor simplificações: 
Simplificações 
1) Supor que a quantidade de dados a serem manipulados pelo algoritmo 
seja muito grande; 
• Algoritmos cujas entradas tem uma quantidade reduzida de dados não 
serão considerados, somente o comportamento assintótico será avaliado – a 
expressão matemática fornecerá valores de tempo somente quando a 
quantidade de dados crescer o suficiente 
• Não serão consideradas constantes aditivas ou multiplicativas na expressão 
matemática obtida. 
•A ideia é exprimir o tempo de execução de um algoritmo 
em função da entrada 
Processo de execução de um algoritmo 
– Pode ser dividido em etapas elementares - passos 
 
– Cada passo consiste na execução de um número fixo de operações 
básicas cujos tempos de execução são considerados constantes ; 
 
– A operação básica de maior frequência de execução é chamada 
operação dominante 
– Exemplo: em vários algoritmos para ordenar os elementos de 
uma sequência dada, cada passo corresponde a uma comparação 
entre dois elementos da sequência. 
Processo de execução de um algoritmo 
• Portanto: 
Número de passos = 
Número de execuções 
da operação dominante 
Analisar a complexidade do algoritmo que faz a 
inversão de uma sequência 
• O algoritmo de um único passo possui um tempo de execução 
constante 
Exemplo 1 
Para i: =1,..., [n] faça 
 temp:= S[i] 
 S[i]:= S[n – i + 1] 
 S[n- i + 1]:= temp 
 
 Cada entrada é uma sequência em que se deseja inverter 
 O algoritmo executa exatamente as mesmas operações para sequência 
de mesmo tamanho n; 
 Cada passo corresponde a troca de posição entre dois elementos da 
sequência ou seja, a execução das três instruções de atribuições dentro 
do bloco para do algoritmo; 
 
O número de passos é igual ao número de execuções do bloco para, ou 
seja, é igual a [n], n>1. 
 
 
 
Exemplo 2 
• Dadas duas matrizes A e B, ambas n x n, analisar a 
complexidade do algoritmo para se obter a matriz 
C = A + B e a matriz D = A . B 
 
 
 Algoritmo: Soma de matrizes 
 para i := 1, ... , n faça 
 para j := 1, ... , n faça 
 cij := aij + bij 
 
 
 Algoritmo: Produto de matrizes 
 para i := 1, ... , n faça 
 para j := 1, ... , n faça 
 cij := 0 
 para K := 1, ... , n faça 
 cij := cij + aik . bkj 
 
 
COMPLEXIDADE DE TEMPO 
‒ Variável independente é o parâmetro n 
‒ Cada passo no algoritmo soma é a execução da soma aij + bij; 
no algoritmo produto é a operação aij.bij 
‒ O n° total de passos é o n° total de somas e produto 
respectivamente para cada caso 
‒ Algoritmo soma efetua n² passos; o algoritmo produto 
executa n³ passos 
NOTAÇÃO O 
• Simplificações para obter a expressão que 
representa o número de passos executadospelo algoritmo 
 
– Desprezar as constantes aditivas e multiplicativas 
• 3n será aproximado para n 
– Desprezar os termos de menor grau 
• n2 + n será aproximado por n2 
• 6n3 + 4n – 9 será aproximado por n3 
NOTAÇÃO O - Exemplos 
• f = n2 – 1 
 
• f = 403 
 
• f = 5 + 2.log n + 3.log2 n 
 
• f = 3n + 5.log n + 2 
 
• f = 5 . 2n + 5n10 
NOTAÇÃO O - Exemplos 
• f = n2 – 1 
 
• f = 403 
 
• f = 5 + 2.log n + 3.log2 n 
 
• f = 3n + 5.log n + 2 
 
• f = 5 . 2n + 5n10 
• f = O(n2) 
 
• f = O(1) 
 
• f = O(log2 n) 
 
• f = O(n) 
 
• f = O(2n) 
NOTAÇÃO O - Propriedades 
i. O(g + h) = O(g) + O(h) 
ii. O(k.g) = k . O(g) = O(g) 
As complexidades de cada algoritmo são: 
Algoritmo 1 – inversão de uma sequência – complexidade O(n/2) 
Algoritmo 2 - fatorial (não recursivo) – complexidade O(n) 
Algoritmo 3 – soma de matrizes – complexidade O (n²) 
Algoritmo 4 – produto de matrizes – complexidade O(n³) 
 
NOTAÇÃO W 
Assim como a notação O é útil para descrever limites 
superiores assintóticos, a notação Ω é empregada para 
limites inferiores assintóticos. 
 
• Exemplo: f = n2 – 1, então são válidas as igualdades f = 
W(n2), f = W(n) e f = W(1), mas não vale f = W(n3) 
 
ALGORÍTMOS ÓTIMOS 
• Seja P um problema, um limite inferior para P é uma 
função l, limites inferiores naturais é o tamanho da 
entrada. 
• Se existir um algoritmo A cuja complexidade seja O(l), 
então A é denominado algoritmo ótimo para P 
• Um algoritmo ótimo é aquele que apresenta a menor 
complexidade dentre todos os possíveis algoritmos para 
resolver o mesmo problema 
ALGORÍTMOS ÓTIMOS 
• Algoritmo 1 – inversão de sequência – qualquer possível 
algoritmo para inverter a sequência deverá efetuar sua 
leitura – limite inferior é Ω(n), a complexidade do 
algoritmo é O(n), então o algoritmo é ótimo 
• Algoritmo 3 – soma de matrizes n x n deverá em primeiro 
lugar efetuar sua leitura – limite inferior é Ω(n²) , a 
complexidade do algoritmo para soma de matrizes é 
O(n²), então o algoritmo é ótimo 
ALGORITMOS ÓTIMOS 
• Algoritmo 4 – produto de matrizes – um limite 
inferior para o problema do produto de matrizes é 
Ω(n²). A complexidade do algoritmo que calcula o 
produto de matrizes é O(n³) e são reconhecidos 
algoritmos que efetuam o produto de matrizes 
dentro de uma complexidade inferior a O(n³) – 
algoritmo não é ótimo