Universidade Federal de Ouro Preto

Instituto de Ciências Exatas e Biológicas

Departamento de Computação

Cálculo Numérico

Primeiro Trabalho Prático

Johnnatan Messias P. Afonso

Professor - José Álvaro Tadeu Ferreira

Ouro Preto5 de maio de 2010

Sumário

1 De�nição do Problema 1

2 Modelagem Matemática 1

3 Solução Numérica 1

4 Obtenção dos Resultados 1

4.1 Primeira Ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24.2 Segunda Ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24.3 Terceira Ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34.4 Quarta Ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34.5 Quinta Ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34.6 O Resultado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

5 Análise dos Resultados 4

6 Bubble Sort 4

Lista de Figuras

1 Tabela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Tabela dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Pontos escolhidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Lista de Programas

1 Algoritmo BubbleSort . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2

1 De�nição do Problema

Realizando testes com o método de ordenação BubbleSort obteve-se o seguinteresultado de tempo, em segundos, para as quantidades de elementos a serem orde-nados:

Figura 1: Tabela

Através dessa tabela de resultados deseja-se obter uma estimativa de tempo paraque o algoritmo ordene 95.000 elementos.

2 Modelagem Matemática

A função é crescente no intervalo x = [25000;150000], logo podemos resolver esseproblema utilizando interpolação polinomial.

3 Solução Numérica

Utilizarei o Método das Diferenças Divididas para estimar o tempo para ordenar95000 (noventa e cinco mil) elementos de um vetor, uma vez que esse método realizamenos operações aritméticas quando comparado ao Método de Lagrange.

4 Obtenção dos Resultados

Figura 2: Tabela dos Resultados

O polinômio interpolador é:

p(x) = y0 + (x−x0)DY0 + (x−x0)(x−x1)D2Y0 + (x−x0)(x−x1)(x−x2)D

3Y0 +(x−x0)(x−x1)(x−x2)(x−x3)D

4Y0 + (x−x0)(x−x1)(x−x2)(x−x3)(x−x4)D5Y0

1

Sabe-se que:

DrYi =Dr−1Yi+1 −Dr−1Yi

Xi+r −Xi

;

{i = 0, 1, 2, ..., n

r = 0, 1, 2, ..., n− r(1)

SendoD0Yi = Yi ; i = 0, 1, 2, ..., n (2)

Então podemos calcular as diferenças divididas de ordem 1, 2, 3, 4 e 5 nesse caso:

4.1 Primeira Ordem

DYi =Yi+1 − Yi

Xi+1 −Xi

, i = 0, 1, 2, ..., n− 1 (3)

DY0 =Y1 − Y0

X1 −X0

= 0, 000773 (4)

DY1 =Y2 − Y1

X2 −X1

= 0, 00147 (5)

DY2 =Y3 − Y2

X3 −X2

= 0, 00213 (6)

DY3 =Y4 − Y3

X4 −X3

= 0, 00252 (7)

DY4 =Y5 − Y4

X5 −X4

= 0, 00358 (8)

4.2 Segunda Ordem

D2Yi =DYi+1 −DYi

Xi+2 −Xi

, i = 0, 1, 2, ..., n− 2 (9)

D2Y0 =DY1 −DY0

X2 −X0

= 0, 000000012 (10)

D2Y1 =DY2 −DY1

X3 −X1

= 0, 000000011 (11)

D2Y2 =DY3 −DY2

X4 −X2

= 0, 000000009 (12)

D2Y3 =DY4 −DY3

X5 −X3

= 0, 000000021 (13)

2

4.3 Terceira Ordem

D3Yi =D2Yi+1 −D2Yi

Xi+3 −Xi

, i = 0, 1, 2, ..., n− 3 (14)

D3Y0 =D2Y1 −D2Y0

X3 −X0

= −1, 3x10−14 (15)

D3Y1 =D2Y2 −D2Y1

X4 −X1

= −2, 5x10−14 (16)

D3Y2 =D2Y3 −D2Y2

X5 −X2

= 1, 714x10−13 (17)

4.4 Quarta Ordem

D4Yi =D3Yi+1 −D3Yi

Xi+4 −Xi

, i = 0, 1, 2, ..., n− 4 (18)

D4Y0 =D3Y1 −D3Y0

X4 −X0

= −1, 26x10−19 (19)

D4Y1 =D3Y2 −D3Y1

X5 −X1

= 1, 785x10−18 (20)

4.5 Quinta Ordem

D5Yi =D4Yi+1 −D4Yi

Xi+5 −Xi

, i = 0, 1, 2, ..., n− 5 (21)

D5Y0 =D4Y1 −D4Y0

X5 −X0

= −1, 528x10−23 (22)

4.6 O Resultado

Para calcular a estimativa de tempo foram escolhidos os pontos:(80000;77,80),(100000;120,40),(120000;170,90).

Figura 3: Pontos escolhidos

3

Portanto:

p(x) = 77, 80+(x−80000)(0, 00213)+(x−80000)(x−100000)(0, 000000009) (23)

p(95000) = 77, 80+(95000−80000)(0, 00213)+(95000−80000)(95000−100000)(0, 000000009)(24)

p(95000) = 109,075 ∼= 109 segundos

5 Análise dos Resultados

O resultado obtido é coerente com o polinômio do problema, uma vez que 95000 ∈[80000; 100000] e ainda, de forma correspondente, 109 ∈ [77, 80; 120, 40].

6 Bubble Sort

BubbleSort é um simples método de ordenação que veri�ca todas as posições dovetor a �m de ordená-lo, comparando todos os elementos.

Para esse trabalho utilizou-se o seguinte algoritmo em C:

void BubbleSort (TArray∗ pA){

int i , j ;TItem aux ;

5 for ( i =0; i<pA−>Size −1; i++){

for ( j =1; j<pA−>Size−i ; j++){

i f (pA−>Pos i t i on s [ j ] . key<pA−>Pos i t i on s [ j −1] . key )10 {

aux = pA−>Pos i t i on s [ j ] ;pA−>Pos i t i on s [ j ]=pA−>Pos i t i on s [ j −1] ;pA−>Pos i t i on s [ j−1]=aux ;

}15 }

}}

Programa 1: Algoritmo BubbleSort

Ainda é possível otimizá-lo bastando-se incluir uma variável "troca"que veri-�que se houve uma troca de posições dos elementos do vetor, diminuindo o temponecessário para a execução do algoritmo bem como o número de comparações.

Possui ordem de complexidade em número de comparações On2, isto é:

O(n) =n−2∑i=0

n− i− 1 =n−2∑i=0

n−n−2∑i=0

i−n−2∑i=0

1 =n2 − n

2(25)

[1]Na prática esse algoritmo não é comumente utilizado para ordenação de uma

grande quantidade de elementos, uma vez que é muito lento para execução, por isso

4

frequentemente, em computação, utiliza-se o método QuickSort. O QuickSort é oalgoritmo de ordenação interna (Memória RAM) mais rápido que se conhece e emseu melhor caso possui ordem de complexidade n log(n), ou seja, O(n log(n)). [2]

Referências

[1] David Menotti. Algoritmos e Estruturas de Dados I: Ordenação I SelectSort,

InsertSort, BubbleSort. 2009.

[2] David Menotti. Algoritmos e Estruturas de Dados I: Ordenação III QuickSort.2009.

5