Tutorial Complexidade de Algoritmos

Pesquisa Operacional / Uma Introdução a Complexidade

1

FUNDAÇÃO EDSON QUEIROZ

UNIVERSIDADE DE FORTALEZA

CENTRO DE CIÊNCIAS TECNOLÓGICAS

TÓPICOS ESPECIAIS DE OTIMIZAÇÃO

NOTAS DE AULA

Uma Introdução a Complexidade de Algoritmos

Plácido Rogério Pinheiro

2001


2

Introdução:

O presente trabalho é uma coletânea de textos, construída através de dissertações, livros

e manuais de softwares. Dentre estes podemos destacar a dissertação do Prof. Geraldo Valdisio

Rodrigues Viana do Departamento de Computação da Univ. Federal do Ceará intitulada “Meta-

Heurísticas para Solução de Problemas de Otimização Combinatória”. Outros textos

consultados foram os livros “Discrete Optimization Algoritms with Pascal Programs” de

Maciej M. Syslo et alli e Operations Research, Applications and Algorithms de Wayne L.

Winston. O apoio computacional, foi obtido através do software LINGO, da LINDO

SYSTEMS INC.


3

1. Conceitos Básicos

1.1 Partição de um Conjunto

Seja A um conjunto não vazio. Chama-se partição de A, ao conjunto P com as seguintes propriedades.

i) todos elementos de P são subconjuntos de A não vazios;

ii) os elementos de P são disjuntos e

iii) a união dos elementos de P é igual ao conjunto A.

Exemplo 1.1

A = { 2, 3, 5, 7, 11, 13, 17, 19 }

P = { { 2, 3, 5 } , { 7, 11 } , { 13, 17, 19 } } Onde:

• Número de Elementos de A: | A | = 8

• Número de Elementos de P: | P | = 3

• Número de subconjuntos não vazios de A: | P(A) | = 2 | A | − 1 = 255

• P1 = { 2, 3, 5 }; P2 = { 7, 11 } ; P3 = { 13, 17, 19 }

• P1 I P2 = P1 I P3 = P2 I P3 = φ

• P1 U P2 U P3 = A

1.2 Notação “O”

Essa notação é usada para expressar a complexidade de tempo de execução de um algoritmo, em função

de um valor “n” que correspondente ao tamanho da entrada do problema. Assim, O( f(n) ) indica que o tempo

necessário para obter um resultado do algoritmo é proporcional a f(n).

Essa medida tem por objetivo avaliar a eficiência do algoritmo em termos de sua complexidade,

normalmente considerada no pior caso. O valor de f(n) não tem uma relação exata com o tempo e sim com

sua ordem de grandeza, o que serve de parâmetro de comparação entre diferentes algoritmos; por exemplo,

para valores de “n” suficientemente grandes as funções f1 (n) = n2 , f2 (n) = 2.n2 + 3 e f3 (n) = 3.n2 , têm a

mesma ordem de grandeza, a qual é proporcional a n2 , ou seja, O(n2). Observe na Tabela 2.1 que a medida

que “n” cresce as ordens de grandeza ( potências de 10 ) de f1 , f2 e f3 tornam-se iguais.


4

N f1 (n) = n2 f2 (n) = 2.n2 + 3 f3 (n) = 3.n2

5 25 53 75

10 100 203 300

50 2500 = 0.25x104 5003 ≈ 0.50x104 7500 = 0.75x104

1000 0.10x107 0.20x107 0.30x107

50000 0.25x1010 0.50x1010 0.75x1010

Tabela 2.1 - Função de Complexidade O (n2)

Por definição, se existir uma função g(n) tal que f(n) ≤ c.g(n) , para uma constante c > 0, diremos que

O( f(n) ) = O( g(n) ).

Normalmente a função “g” representa uma família de funções conhecidas como: O(n), O(n2), O(n3),

O(2n), O(n!), O(log2 n), O(n.log2 n), etc. A notação O(1) é usada para indicar uma complexidade constante,

ou seja, independente de “n”; no entanto, isso é bastante incomum.

No exemplo anterior observa-se que: n2 ≤ 3n2 e 2n2 + 3 ≤ 3n2; logo, c=3 e a função g(n) = n2 .

Cuidados devem ser tomados para valores de “c” elevados, pois, é óbvio que f1 = (50!).n e f2 = 3n não tem

realmente a mesma ordem de grandeza; casos como estes devem ter tratamento especial. A Tabela 2.2

permite fazer uma comparação entre funções comumente usadas na medição da complexidade de um

algoritmo para alguns valores de “n”.

Para uma melhor visualização, os valores indicados representam o tempo médio esperado de execução,

expressos em segundos quando não indicado. Foi considerado o tempo de 1 µs para cada ciclo.


5

Complexidade

n=5 n=10 n=50 n=100 N=1000 n=10000

O ( log2n ) 0.0000023

0.0000033

0.0000056 0.0000066 0.0000099 0.000013

O ( n ) 0.000005 0.000010 0.000050 0.000100 0.001000 0.010000

O ( n.log2n ) 0.000011 0.000033 0.000283 0.000684 0.009966 0.132877

O ( n2 ) 0.000025 0.000100 0.002500 0.010000 1 s 1min 40s

O ( n3 ) 0.000125 0.001000 0.125000 1 s 16min 40s 11dias 14h

O ( n5 ) 0.003125 0.100000 5min 13s 2h 47min 32 anos ∞

O ( 2n ) 0.000032 0.001024 35 anos 4x1016 anos

∞ ∞

O ( 3n ) 0.000243 0.059049 2x1010 anos

∞ ∞ ∞

Tabela 2.2 - Funções de Complexidade mais Comuns

De acordo com análise feita na Tabela 2.2 concluímos que para valores de “n” não superiores a 1000 a

complexidade cúbica O(n3) seria a máxima admitida. Para grandes conjuntos de dados ( n ≥ 10000 ) o ideal

seria a complexidade não superior a O(n2). Em geral, O(nm) para m > 3, ou complexidade exponencia l, são

indesejáveis.

Posteriormente, no item 2.7, veremos que os problemas são classificados em função da complexidade

de seus algoritmos. No item 2.5 daremos uma idéia, através de alguns exemplos, como se obtém esta função

de complexidade.

Um outro fator a ser considerado é que, em função da ordem de complexidade, um aumento da

velocidade do computador pode ser irrelevante em relação ao tempo de execução do algoritmo.

Era de se esperar que, se um computador resolve um problema de tamanho “n” num determinado

tempo, um outro, de velocidade 100 vezes maior, deveria resolver neste mesmo tempo um problema similar

de tamanho “100.n”.

Entretanto, conforme podemos observar na Tabela 2.3, isto não ocorre. Veja que para complexidade

O(n3), um aumento de 1000 vezes na velocidade, corresponde a um aumento de 10 vezes no tamanho; ou,

para o mesmo caso, se a complexidade fosse O(10n) o aumento no tamanho seria de apenas 3 unidades (valor

constante).


6

Ordem

de Complexidad

e

Tamanho no Computador

Atual

Computador 100 vezes mais

rápido

Computador 1000 vezes

mais rápido

O ( n ) N1 100.N1 1000.N1

O ( n2 ) N2 10.N2 31,62.N2

O ( n3 ) N3 4,64.N3 10.N3

O ( n5 ) N4 2,51.N4 3,98.N4

O ( 2n ) N5 N5 + 6,64 N5 + 9,97

O ( 3n ) N6 N6 + 4,19 N6 + 6,29

O ( 10n ) N7 N7 + 2 N7 + 3

Tabela 2.3 - Efeito da Velocidade do Computador x Tamanho do Problema num dado tempo2

1.3 Tempo Computacional

O tempo de execução de cada operação aritmética depende da forma de cálculo e da velocidade do

processador. Para as funções, além destes fatores, deve ser consideradas ainda sua forma de implementação e

a linguagem de programação utilizada.

Por isso, temos variação na medição deste tempo para diferentes compiladores e ambientes

computacionais, mas invariavelmente, as operações de soma ( + ) e subtração ( − ) tem tempo quase igual e

bem menor que a multiplicação ( * ) e divisão ( / ). Entre as funções, geralmente a raiz quadrada ( sqrt ) é a

mais rápida, enquanto que as funções: logaritmo ( log ), seno ( sin ), cosseno ( cos ), exponencial ( exp ) e

arcotangente ( arctg ) são intermediárias quando comparadas com a potenciação com expoente não inteiro (

xy , y∈ℜ ) e a função tangente ( tg ) que se apresentam como as menos rápidas.

Para avaliação destas medidas utilizamos o Algoritmo 2.1, onde clock() é uma função que fornece o

tempo atual em segundos e o símbolo Θ substitui um dos operadores ( +, −, * , / , ^ ) na expressão S = X Θ Y

para dois valores arbitrários de X e Y. Quando S = f (X) , f representa uma das funções citadas

anteriormente.

2 Tabela semelhante à contida na referência [GAR79] p.8


7

{Início – A2.1} ler (X,Y) T1 = clock()

{ Computa tempo de: “loop”, “+” e “=” }

enquanto (I ≤ 1000000) faça I = I +1 S = I fim_enquanto T2 = clock() TLOOP = T2 − T1 I = 0

{ Computa tempo da operação Θ (ou f ) }

enquanto (I ≤ 1000000) faça I = I +1 S = X Θ Y { ou S = f (X) } fim_enquanto T1 = clock() T = T1 − T2 − TLOOP imprimir (T) {Fim - A2.1}

Algoritmo 2.1 - Avalia Tempo Computacional de uma Operação ou Função

Obtivemos os resultados apresentados na Tabela 2.4 codificando o algoritmo na linguagem Fortran,

utilizando o Microsoft Fortran Optmizing Compiler Version 5.0 [MIC89] num microcomputador AT486-DX

com co-processador aritmético e 8 MB de RAM3 .

Os valores representados indicam o tempo médio em µs ( 10−6 s ), e a coluna “Unidade” mostra a

relação entre a medição do tempo do operador ou função com a operação básica de adição.

Vale lembrar que a composição destes tempos depende da máquina utilizada e em geral estes valores

encontram-se em manuais específicos fornecidos pelos fabricantes.

3 RAM (Random Access Memory) significa Memória de Acesso Randômico ou Memória Principal


8

Operação / Função

Tempo Médio ( em µs )

Unidade (Tempo

Relativo)

+ 0.5 1 − 0.5 1 * 2.8 6 / 3.0 6

sqrt 7.2 14 log 14.4 29 sin 15.9 32 cos 15.9 32

arctg 16.2 32 exp 20.3 40 ^ 34.52 69 tg 34.84 70

Tabela 2.4 - Tempo Computacional para Operações e Funções

Com estes resultados, é esperado que se um determinado programa que só realiza operações de adição (

+ ) necessita de 1 segundo para sua execução, seria necessário em torno de 69 segundos quando esta

operação fosse trocada pela potenciação ( ^ ).

Sem perda de generalidade, poderíamos computar as operações e funções num dado algoritmo

indistintamente, apesar dos tempos de processamento serem diferentes. Isso é válido porque levamos em

consideração apenas a ordem de grandeza deste tempo em função da complexidade do algoritmo. Por

exemplo, se t1 , t2 e t3 são respectivamente os tempos computacionais para cálculo das funções logaritmo (

log(x) ) e raiz quadrada ( sqrt(x) ) e da operação de multiplicação (*) temos que t1 ≈ 2 t2 ≈ 5 t3.

Ou seja, a grosso modo poderíamos substituir o cálculo de log(x) pelo cálculo de sqrt(x) duas vezes ou

pela computação da operação “*” cinco vezes, isso sem alterar o tempo de execução do processo; de forma

que, se f1 , f2 e f3 são seus respectivos algoritmos teríamos, O( f1 ) = O( 2.f2 ) = O( 5.f3 ) , ou O( f1 ) = O( f2

) = O( f3 ), pois conforme citado anteriormente, O( f ) = O( c.f ), sendo “c” uma constante positiva.

Poder-se-ia também esperar que a expressão:


9

z sin x x y x y= +( ) * ( ^ ) / log( )

seria executada nessa máquina num tempo aproximado de 78.3 µs, conforme mostra a ordem de execução

das operações indicadas na Tabela 2.5 (foi considerado desprezível o tempo de execução do comando de

atribuição).

Passo Operador Operação Realizada Resultado Tempo (µs)

1 ^ x ^ y r1 34.5 2 + x + y r2 0.5 3 Sin sen(x) r3 15.9 4 Log log(r2) r4 14.4 5 * r3 * r1 r5 2.8 6 / r5 / r4 r6 3.0 7 Sqrt sqrt(r6) r7 7.2 8 = z = r7 z 0.0

TOTAL ⇒ 78.3

Tabela 2.5- Cálculo do Tempo Computacional na Avaliação de uma Expressão


10

1.4 Classes de Problemas

1.4.1 Considerações Gerais

Antes de definirmos classes de problemas iremos relembrar que de acordo com os resultados

apresentados na Tabela 2.2, algoritmos de tempo polinomial são preferíveis aos algoritmos de tempo

exponencial. Complexidade de O( nm ), para m > 3, ou O ( xn ), para x > 1 são indesejáveis e os problemas

correspondentes são denominados de intratáveis. Mesmo nas complexidades de O ( c.n2 ), para grandes

valores de c ( c > 106 ), também são consideradas assim.

Existem problemas dificílimos, no sentido de que nenhum algoritmo pode resolvê-los; estes são

denominados indecidíveis, não-computáveis ou fortemente intratáveis.

De uma maneira geral um problema é considerado tratável quando existe um algoritmo de

complexidade polinomial que o resolva, e seria intratável quando todos algoritmos conhecidos para resolvê-

lo possuem complexidade exponencial, ou não polinomial. Uma regra para escolher um algoritmo eficiente é

que a função f(n) que estima seu tempo de execução não ultrapasse os limites desejados.

Por exemplo, sendo “n” o tamanho da entrada do problema, f (n) > 1010 já é motivo de preocupação,

pois máquinas convencionais com unidade de tempo para instruções e operações da ordem de 10−6 segundos,

requereriam um tempo de execução em torno de 3 horas. Se f (n) > 1011 (10 vezes) este tempo já superaria

um dia e se fosse da ordem de 1014 ultrapassaria 3 (três) anos.

1.4.2 Algoritmos Determinísticos e Não-Determinísticos

Chamam-se determinísticos aqueles algoritmos que para uma dada entrada do problema apresentam

apenas uma solução. Caso sejam implementadas operações cujos resultados permitem um número finito de

soluções, então os algoritmos seriam chamados de não-determinísticos.

Existe um modelo abstrato para representação de algoritmos desta natureza, chamado de Máquina de

Turing ( Alan Mathison Turing, 1936 ) cujo detalhamento pode ser encontrado em [CAM94] p. 59-61. São

definidas primitivas que levam ao sucesso (sim) ou fracasso (não) na sinalização do término de um algoritmo

quando aplicados a uma instância genérica do problema, de forma que, se houver uma seqüência de

operações que conduza ao término com sucesso esta será verificada no menor número de passos.

Um algoritmo não-determinístico tem complexidade O ( f(n) ), para instâncias de tamanho “n” para

término com sucesso e O ( 1 ), ou constante, com término com fracasso.


11

A chamada MTND ( Máquina de Turing Não-Determinística ) é uma máquina conceitual que

implementa algoritmos deste tipo que podem ser executados de forma determinística, onde diversas

instâncias escolhidas poderiam ser executadas “simultaneamente”, uma em cada MTD ( Máquina de Turing

Determinística ). Neste caso para término com sucesso seria considerado o resultado da primeira MTD que

encerrasse assim, provocando uma interrupção nas demais. Para detectar um término com fracasso seria

necessário que todas cópias da MTD tivessem esse resultado e que cada vez que ele fosse obtido haveria

interrupção apenas daquele processo.

1.4.3 Classes P e NP

Esta classificação, fundamentada na teoria desenvolvida por Stephen Cook [COO71], pode ser feita

através de algumas conotações.

Em termo da função de complexidade, podemos dizer que problemas com complexidade de tempo

polinomial constituem a classe P, enquanto que aqueles com tempo exponencial pertencem à classe NP.

Outra conotação desta classificação seria que problemas de decisão que admitem algoritmos

determinísticos polinomiais formam a classe P, enquanto que algoritmos não-determinísticos polinomiais

formam a classe NP.

Conjectura-se que P ≠ NP, pois diversos pesquisadores até hoje não conseguiram elaborar algoritmos

polinomiais eficientes para um grande número de problemas (veja a relação de alguns deles no item 2.7.5),

de forma que na Figura 2.23, o conjunto ( NP − P ) seria não vazio. Porém, se alguém conseguir mostrar um

algoritmo polinomial para resolver pelo menos um daqueles problemas, então P = NP, pois todos os outros

problemas poderiam ser transformados ( reduzidos ) àquele. Outra dificuldade para provar que um problema

de decisão π ∉ P, é necessário mostrar uma prova concreta que todo algoritmo possível para resolver π não é

polinomial.

Observe que P ⊆ NP, pois além das considerações feitas no item 2.7.1, tem-se que um algoritmo

determinístico é um caso particular de algoritmo não-determinístico, sendo P, portanto, uma subclasse de

NP.

Por fim indicamos que a classe NP compreende àqueles problemas de decisão π para os quais existe um

algoritmo não-determinístico para justificar a resposta “sim”, que será reconhecida por um algoritmo

polinomial; observando que uma justificativa para a resposta “não” geralmente é exaustiva.


12

1.4.4 Classe NP-Completo e NP-Árduo

Quando existe uma transformação em tempo polinomial de um problema de decisão π1 para outro π2 (

escreve-se: π1 ∝ π2 ), mostra-se [GAR79] que se π2 ∈ P ⇒ π1 ∈ P, ou de forma equivalente, se π1 ∉ P ⇒

π2 ∉ P. Podemos então dizer que π1 é um caso particular de π2 ,ou seja, π2 é pelo menos tão difícil quanto π1.

Observe que esta relação é transitiva, ou seja, se π1 ∝ π2 e π2 ∝ π3 então π1 ∝ π3.

Um problema de decisão π é chamado de NP-Árduo ou NP-Hard se π0 ∝ π para todo π0 ∈ NP, logo

um problema NP-Árduo é pelo menos tão difícil quanto qualquer problema em NP.

A denominação de problemas de decisão como NP-Completo deve-se a Stephen Cook [COO83] que

estabeleceu que o problema SAT (satisfiabilidade), referido no exemplo 2.14, é o mais difícil da classe NP e

todos os outros problemas em NP podem ser reduzidos polinomialmente a ele. Portanto, a classe NP-

Completo contém os problemas de maior dificuldade entre todos em NP.

A Figura 2.23 mostra uma estrutura de problemas NP numa visão simplificada dos problemas de

decisão; os problemas NP-Árduos estão fora desta classificação.

Figura 2.23 - Estrutura de problemas de decisão NP

Uma técnica de prova para problemas NP-Completos consiste em utilizar a chamada redução mestre:

SAT ∝ π , sendo a redução feita em tempo polinomial. Neste caso, o problema de decisão π é pelo menos tão

difícil quanto SAT, logo π também é NP-Completo. Em geral, usando a propriedade transitiva, se várias

reduções da forma: SAT ∝ π1 ∝ π2 ∝ . . . ∝ πm podem ser feitas em tempo polinomial, então πi , ∀ i=1,...,m,

é um problema da classe NP-Completo.

Se n-SAT é uma classificação do problema SAT, onde cada cláusula tem exatamente “n” literais é fácil

verificar que 2-SAT pertence a classe P e para n≥3, n-SAT é NP. Veja o exemplo:


13

Exemplo 2.16 Provar que: SAT ∝ 3–SAT

Passo-1: Substituir cada cláusula da forma: ( para 4 ≤ k ≤ n )

( g1 ∨ g2 ∨ . . . ∨ gk ) por: ( g1 ∨ g2 ∨ h ) ∧ ( g3 ∨ . . . ∨ gk ∨ ~h ),

onde h é um novo literal e (~h) = não-h (negação de h).

Repetir este passo sucessivamente até que todas cláusulas possuam não mais que 3 literais cada uma.

Passo-2: Substituir as cláusulas com 2 literais:

( g1 ∨ g2 ) por: ( g1 ∨ g2 ∨ h ) ∧ ( ~h ∨ ~h ∨ ~h ).

Passo-3: Substituir as cláusulas com 1 literal:

( g1 ) por: ( g1 ∨ h ∨ h ) ∧ ( ~h ∨ ~h ∨ ~h ).

Essas substituições podem ser feitas em tempo polinomial, de forma que qualquer expressão n-SAT

pode ser transformada numa expressão 3-SAT.

Um problema de otimização é NP-Árduo, pois sendo composto de vários problemas de decisão seria

pelo menos tão difícil quanto estes, logo, não poderia ser NP-Completo. Assim, se π0 for um problema de

decisão (PD) associado a um problema de otimização (PO) π, temos:

π0 ∝ π ( PO = PD1 + PD2 + . . . + PDm )

Portanto, se π0 fosse de ordem O ( f(n) ), π seria de ordem O ( m.f(n) ), logo π só poderia ser resolvido

em tempo polinomial se π0 também o fosse, donde se conclui que π0 é NP-Completo e π é NP-Árduo.

Em resumo, se NPA = NP-Árduo e NPC = NP-Completo, então NPA ≥ NPC ≥ NP, onde o sinal “≥ ”

significa “de dificuldade não menor”. Concluímos também que os problemas da classe NPC são os mais

difíceis em NP, para estes não são conhecidos, ou não existem, algoritmos determinísticos, de complexidade

polinomial, para resolvê-los.

1.4.5 Problemas NP-Completos

Garey & Johnson, [GAR79] p. 190-288, apresentam uma extensa lista de problemas de decisão NP-

Completo, pertencentes às áreas de Otimização Combinatória, Teoria dos Números, Construção de

Compiladores, Planejamento de Tarefas, Teoria dos Grafos, Projeto de Redes de Computadores,

Programação Matemática, Conjuntos e Partições, Lógica, Jogos etc. Aqui selecionamos alguns deles:


14

i) Cobertura de Vértices ( Vertex Cover )

Entrada : Grafo G = ( V, E ) e inteiro positivo k ≤ | V |

Questão : ∃ cobertura em G de tamanho ≥ k ?

Redução: 3-SAT [KAR72]

ii) Número Cromático ( Chromatic Number )


Questão : G é k-colorável ?


iii) Clique ( Clique )


Questão : ∃ clique em G de tamanho ≥ k ?

Redução: Cobertura de Vértices [KAR72]

iv) Conjunto Independente de Vértices ( Independent Set )


Questão : ∃ conjunto independente de vértices de tamanho ≥ k ?


v) Subgrafo Bipartido ( Bipartite Subgraph )

Entrada : Grafo G = ( V, E ) e inteiro positivo k ≤ | E |

Questão : ∃ E′ ⊆ E , com | E′ | ≥ k tal que G′ = (V, E′ ) é bipartido ?

Redução: Máximo 2-SAT [GAR76]

vi) Subgrafo Planar ( Planar Subgraph )

Entrada : Grafo G = ( V, E ) e inteiro positivo k ≤ | E |

Questão : ∃ E′ ⊆ E , com | E′ | ≥ k tal que G′ = (V, E′ ) é planar ?

Redução: Ciclo Hamiltoniano [LIU78]


15

vii) Circuito Hamiltoniano ( Hamiltonian Circuit )

Entrada : Grafo direcionado G = ( V, E ).

Questão : G contém um Circuito Hamiltoniano ?


viii) Caminho Hamiltoniano ( Hamiltonian Path )

Entrada : Grafo G = ( V, E ).

Questão : G contém um Caminho Hamiltoniano ?


ix) Isomorfismo de Subgrafos ( Subgraph Isomorphism )

Entrada : Grafos G = ( V1, E1 ) e H = ( V2, E2 ).

Questão : G contém um subgrafo isomorfo à H ?

Um subgrafo G′ = ( V, E ) de G, V ⊆ V1 e E ⊆ E1, é isomorfo a um grafo H, se | V | = | V2 |, | E | = | E2 | e ∃ f : V2 → V {u, v} ∈ E2 ⇔ { f (u) , f (v) } ∈ E.

Redução: Clique [COO71]

x) Caixeiro Viajante ( Traveling Salesman )

Entrada : Conjunto C com “m” cidades; distância d ( ci , cj ) ∈ Z+ para cada par de cidade ci , cj

∈ C; e um inteiro positivo B.

Questão : ∃ uma permutação < ck(1) , ck(2) , ... , ck(m) > tal que:

d c c d c c Bk i k ii

m

k m k( , ) ( , ) ?( ) ( ) ( ) (1)+=

−

∑

+ ≤1

1

1

?

Redução: Circuito Hamiltoniano [KAR72]

xi) Carteiro Chinês ( Chinese Postman )

Entrada : Grafo misto G = (V, A, E), onde A é o conjunto de arestas direcionadas e E o conjunto de arestas não-direcionadas de G; tamanho L(e) de cada aresta e ∈ (A ∪ E); e um inteiro positivo B.

Questão : ∃ um ciclo em G que inclui cada aresta (direcionada ou não) pelo menos uma vez com tamanho total ≤ B ?

Redução: 3-SAT [PAP76]


16

xii) Partição ( Partition )

Entrada : Conjunto finito A e um tamanho s(a) ∈ Z+ para cada a ∈ A.

Questão : ∃ um subconjunto A′⊆ A, tal que: s a s aa A Aa A

( ) ( )'' =∈ −∈ ∑∑ ?

Redução: 3DM (“Matching” em 3-D) [KAR72]

xiii) Soma dos Elementos de um Subconjunto ( Subset Sum )

Entrada : Conjunto finito A; um tamanho s(a) ∈ Z+ para cada a ∈ A e um inteiro positivo B.

Questão : ∃ um subconjunto A′⊆ A, tal que s a Ba A

( )' =∈∑ ?

Redução: Partição [KAR72]

xiv) Produto dos Elementos de um Subconjunto ( Subset Product )

Entrada : Conjunto finito A; um tamanho s(a) ∈ Z+ para cada a ∈ A e um inteiro positivo B.

Questão : ∃ um subconjunto A′⊆ A, tal que s a Ba A

( )'

=∈

∏ ?

Redução: X3C ( Cobertura Exata para conjuntos de cardinalidade 3)

[YAO78]

xv) Empacotamento ( Bin Packing )

Entrada : Conjunto finito U de itens; um tamanho s(u) ∈ Z+ para cada u ∈ U e os inteiros positivos B, capacidade da caixa (bin), e k.

Questão : ∃ uma partição de U (ver definição no item 2.1), tal que a soma de todos itens de cada partição Ui é ≤ k ?


xvi) Escalonamento de Tarefas ( Multiprocessor Scheduling )

Entrada : Conjunto finito T de tarefas; um número m ∈ Z+ de processadores, tamanho L(u) ∈ Z+ para cada u ∈ T e um tempo limite D ∈ Z+.

Questão : ∃ σ: T → Z0+ tal que ∀ u ≥ 0, σ(t) ≤ u ≤ σ(t) + L(t), o número de tarefas t ∈ T é

menor ou igual a “m” e σ(t) + L(t) ≤ D ?



17

xvii) Programação Inteira ( Integer Programming )

Entrada : Conjunto finito X de pares ( x , b), onde x é uma m-tupla de inteiros e “b” um inteiro; uma m-tupla c de inteiros e um inteiro B.

Questão : ∃ uma m-tupla y de inteiros tal que x.y ≤ b para todo ( x , b) ∈ X e tal que c.y ≥ B. Obs.: u.v é o produto escalar do vetor u = ( u1, u2, ... , um ) pelo vetor v = ( v1, v2, ... , vm ), ou seja, u.v = u1.v1 + u2.v2 + ... + um.vm.


xviii) Programação Quadrática ( Quadratic Programming )

Entrada : Conjunto finito X de pares ( x , b), onde x é uma m-tupla de reais e “b” um real; duas m-tuplas c e d de reais e um real B.

Questão : ∃ uma m-tupla y de reais tal que x.y ≤ b para todo ( x , b) ∈ X e tal que

( . . )c y d y Bi i i ii

m 2

1+ ≥

=∑ , onde ci , di , yi são os i-ésimos componentes de c, d e y, respectivamente.

Redução: Partição [SHA74]

xix) Problema da Mochila ( Knapsack Problem )

Entrada : Conjunto finito U de itens; um tamanho s(u) ∈ Z+ para cada u ∈ U e um valor v(u) ∈ Z+ e os inteiros positivos B e K

Questão : ∃ U′⊆ U tal que s u Bu U

( )' ≤∈∑ e v u K

u U( )' ≥

∈∑ ?


xx) Números Compostos ( Composite Numbers )

Entrada : Inteiro positivo N.

Questão : ∃ inteiros positivos, m e n, tais que N = m.n ?


18

1.4.6 Complexidade Computacional do Método Simplex

Introdução

Durante vários anos, o método simplex pareceu bastante eficiente do ponto de vista

computacional. Entretanto várias questões fo ram abordadas tais como:

O Método Simplex tem complexidade polinomial?

Em termos mais amplos podemos abordar as seguintes questões:

♦Como podemos comparar dois diferentes algoritmos para o mesmo problema?

•Qualidade da Solução

•Eficiência Computaciona l

Uma medida muitas vezes usada para dimensionar a eficiência computacional é o

tempo de execução do computador(cpu time). Porém o “cpu time” depende do tipo de

computador, linguagem de programação, habilidade do programador, etc.

Princípio da Invariância

O princípio da invariância diz que duas diferentes implementações do mesmo

algoritmo não diferirão em eficiência computacional por mais que uma constante

mult iplicativa.

Um caminho apropriado para medir a eficiência computacional é contar o número de

operações elementares que são requeridas pelo algoritmo, i .e. , adições, subtrações,

mul t ip licações, divisões, comparações, etc.

Especificamente, nos calculamos o pior- caso “worst- case” do número de

Sejam duas implementações computacionais do mesmo algoritmo, que podem

diferir na languagem de programação e/ou máquina usada. Então tome t1(n) e

t2(n) segundos para o instante de tamanho n, logo existe uma constante c > 0 e

um inteiro N tal que t1(n) ≤ ct2(n) para todo n ≥ N


19

operações elementares, que pode ser bastante diferente de um caso típico encontrado

em aplicações.

Do ponto de vista “macro”, contaríamos o número de iterações que o algoritmo tem

que executar como uma t(n) função de tamanho n do problema se o esforço de

co mputacional por iteração é estável, por exemplo, limit ada por alguma função de n.

Dizemos que um algoritmo toma um tempo de ordem t(n), onde t é uma dada função,

se existem um c > 0 e uma implementação do algoritmo capaz de resolver qualquer

instância do problema de tamanho n em um tempo limitado por ct(n).

Isto é denotado por O(t(n)) e é chamado o tempo de complexidade do algoritmo

Definição: Sejam f:Á → Å + e g:Á → Å+ duas funções, a notação f∈O(g), que se lê: “f é

da ordem de g”, significa que existe uma constante k > 0 e n0 ∈ Á , tal que f(n) ≤ k.g(n) para

todo n > n0 .

Propriedade: Se f:Á → Å+ e g :Á →Å+ são duas funções tais que f(n) ≤ g(n), então

O(f(n))⊂ O(g(n)) para todo n ∈ Á.

Em resumo, tem-se :

O(1) ⊂ O(logn) ⊂ O(n) ) ⊂ O(nlogn) ) ⊂ O ( n2) ) ⊂ O ( kn ) ) ⊂ O(n! )

Algoritmo de Tempo Polinomial

Um algori tmo para o qual o tempo (equivalentemente, o número de operações) é

O(p(n)), onde p(n) é uma função polinomial e n é o “tamanho” do problema é

chamado algoritmo de tempo polinomial.

Algoritmo de Tempo Exponencial

Um algoritmo para o qual o tempo é O(exp(n)), onde exp(n) é uma função

exponencial e n é o tamanho do problema.


20

O algoritmo simplex possui complexidade exponencial

Considere o problema de Klee-Minty(1972):

jxmax ∑n

1=j

j-n10=Z

s .a )n,...,2,1i(100x)x102( 1iij

1i

1j

ji =≤+ −−

=

−∑

xj ≥ 0 (j=1,2,...,n)

Para n = 2 tem-se

máx Z = 10x1 + x2

s .a x1 ≤ 1

20x1 + x2 ≤ 100

x1 ≥ 0, x2 ≥ 0

Graficamente:

(1,0) (5,0) (0,0)

(0,100)

(1,80)

P (0, 100)⇒ z = 100 (sol. ótima) P (0, 0) ⇒ z = 0 P (1, 0) ⇒ z = 10 P (1, 80) ⇒ z = 90


21

Apresentaremos a seguir todas as soluções básicas viáveis para este PPL Fazendo z’ = -z

Mín z’ = -10x1 – x2

s.a x1 + x3 =1

20x1 + x2 + x4 = 100

x1, x2 ≥ 0

Base X1 X2 X3 X4 B

X3 1 0 1 0 1

X4 20 1 0 1 100

- Z’ -10 -1 0 0 0

VB à X3 = 1; X4 = 100; VNB à X1 = X2 = 0; X1 entra e X3 sai

Base X1 X2 X3 X4 B

X1 1 0 1 0 1

X4 0 1 -20 1 80

- Z’ 0 -1 10 0 10


Base X1 X2 X3 X4 B

X1 1 0 1 0 1

X2 0 1 -20 1 80

- Z’ 0 0 -10 1 90


Base X1 X2 X3 X4 B

X3 1 0 1 0 1

X2 20 1 0 1 100

- Z’ 10 0 0 1 100

VB à X3 = 1; X2 = 100; VNB à X1 = X4 = 0


22

Para n = 3 tem-se

Máx Z = 100x1 + 10x2 + x3

s .a x1 ≤ 1

20x1 + x2 ≤ 100

200x1 + 20x2 + x3 ≤ 10000

xi ≥ 0, i = 1,2,3

Quando o simplex é usado para resolver este PPL, toda solução básica viável deve

ser examinada antes da solução ótima ser descoberta. Generalizando este exemplo, Klee &

Minty (1972) construíram (para n = 2, 3,...) um PPL com n decisões variáveis e n

expressões para que o algoritmo s implex examinassem 2n -1 soluções básicas viáveis antes

da solução ótima se descoberta. Assim, existe um PPL com 10 variáveis e 10 expressões

para que o simplex requeira 21 0 - 1= 1023 pivôs para descobrir a solução ótima. Assim

sendo, tão patológico PPL raramente ocorre em aplicações práticas.

Graficamente tem- se:


23

As restrições representam uma distorção no hipercubo n- dimensional

O exemplo de Klee-Minty mostrou que:

Executaremos 2n – 1 iterações para resolver um problema de n variá veis e restrições.

Para n = 70,

2n = 1.2 x 1021 ,


24

Em 1000 iterações por segundo, este problema levará 40 bilhões de anos para resolver. A

idade do universo é estimada em 15 bilhões de anos.

O método simplex:

• No pior caso: n2 2n operações

• No caso médio: n3 operações

Questão: Existe uma variante do método simplex o qual no pior caso a performance é

polinomial?

• Teorema: Existe um algoritmo o performance no “pior caso” é n3 .5 operações.

Documents

Tutorial Complexidade de Algoritmos