Aspectos Teóricos da Computação Unidade I

COMPORTAMENTO ASSINTÓPTICO DE FUNÇÕES

Tempo de Execução de um Programa: Comportamento Assintóptico de

Funções e Classes de Comportamento Assintóptico

Seja n um parâmetro que caracteriza o tamanho da entrada do algoritmo. Por exemplo, ordenar n

números ou multiplicar duas matrizes quadradas n × n (cada uma com n2 elementos).

Costuma‑se medir um algoritmo em termos de tempo de execução ou o espaço (ou memória)

usado. Para o tempo, podemos considerar o tempo absoluto (em minutos, segundos etc.). Medir o tempo

absoluto não é interessante por depender da máquina.

Em Análise de Algoritmos conta‑se o número de operações consideradas relevantes realizadas pelo

algoritmo e expressa esse número como uma função de n. Essas operações podem ser comparações,

operações aritméticas, movimento de dados etc.

Um caso de particular interesse é quando n tem valor muito grande (n → ∞), denominado

comportamento assintótico.

Notação O

Para se estudar o comportamento assintótico – para n grande – emprega‑se o termo de ordem

superior.

A notação O pode ser formalizada como se segue:

Diz‑se que T(n) = O(f(n)) se existirem inteiro m e constante c, tais que:

T(n) ≤ cf(n) para n > m

Exercício Resolvido 1:

Apresente um estudo comparativo da grandeza das funções:

F(n) = 1;

F(n) = log2(n);

19

ASPECTOS TEÓRICOS DA COMPUTAÇÃO

F(n) = n;

F(n) = n log2(n);

F(n) = n2;

F(n) = n3

F(n) = 2n

F(n)

n 1 log2(n) n n log2(n) n2 n3 2n

1 1 0 1 0 1 1 2

10 1 3.32 10 33 100 1000 1024

100 1 6.64 100 664 10000 1000000 1, 268 x1030

1000 1 9.97 1000 9970 1000000 109 1, 072 x 10301

Exercício Resolvido 2:

Colocar em ordem crescente as seguintes complexidades:

nlog2(n), 310; n3; n1/3

A ordem crescente é:

310; n1/3; nlog2(n); n3

Problemas P e NP

Complexidade Computacional – A Classe P e a Classe NP – Grafos

Eulerianos e Hamiltonianos

Ciclo de Euler:

Dado um grafo G, existe um caminho fechado em G, tal que esse caminho use uma aresta exatamente

uma vez.

Teorema sobre Caminhos de Euler (para um grafo não orientado)

Existe um caminho de Euler em um grafo conexo se e somente se não existam nós ímpares ou

existem exatamente dois nós ímpares. No caso em que não existam dois nós ímpares, o caminho pode

terminar em qualquer nó e terminar aí; no caso de dois nós ímpares, o caminho precisa começar em um

deles e terminar no outro.

20

Unidade II

Lewis e Papadimitrious apresentam a definição de um Grafo Euleriano quando o grafo é orientado:

Um grafo G é Euleriano se e somente se apresenta as seguintes duas propriedades:

a) Para quaisquer pares de nós u e v, nenhum dos quais isolados, existe um caminho de u para v;

b) Todos os nós apresentam número de arestas que nele incidem iguais ao número de arestas não

incidentes.

Ciclo Hamiltoniano

Dado um grafo G, existe um ciclo que passe por todos os nós de G exatamente uma vez.

O único algoritmo conhecido para este problema consiste em examinar todas as permutações

possíveis dos nós e para cada permutação, verificar se trata de um ciclo Hamiltoniano. Trata‑se, portanto,

de um problema O(n!).

Definição da classe P

P é a coleção de todos os conjuntos reconhecíveis por Máquinas de Turing em tempo polinomial.

Definição da classe NP

NP é a coleção de todos os conjuntos reconhecíveis por máquinas de Turing não determinísticas em

tempo polinomial.

Uma máquina de Turing M = (Q, A, g, q0, H) é denominada polinomial se a máquina sempre para,

qualquer que seja a entrada x de comprimento n após p(n) etapas em que p(n) é uma função polinomial

do comprimento n da cadeia de entrada.

Exercício Resolvido 1:

Considere o grafo G = (V, A, g), em que:

V = {1, 2, 3, 4, 5} são os vértices

A = {a, b, c, d, e}

g(a) = 1‑2

g(b) = 2 – 5

g(c) = 1 – 3

21

ASPECTOS TEÓRICOS DA COMPUTAÇÃO

g(d) = 5‑ 5

g(e) = 3‑4

Pede‑se: verificar se existe um caminho