Universidade Federal de Ouro Preto

Instituto de Ciências Exatas e Biológicas

Departamento de Computação

Cálculo Numérico

Segundo Trabalho Prático

Johnnatan Messias P. AfonsoRafaella Bicalho da Rocha

Professor - José Álvaro Tadeu Ferreira

Ouro Preto21 de junho 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 2

4.1 1a Regra de Simpson . . . . . . . . . . . . . . . . . . . . . . . . . . . 24.2 Aplicação do Teorema do Valor Médio . . . . . . . . . . . . . . . . . 34.3 O Resultado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

5 Análise dos Resultados 3

6 Bubble Sort 3

Lista de Figuras

1 Tabela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Tabela dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . 2

Lista de Programas

1 Algoritmo BubbleSort . . . . . . . . . . . . . . . . . . . . . . . . . . 3

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 tempomédio da execução do algoritmo.

2 Modelagem Matemática

Como a função é contínua no intervalo fechado [a;b] tal que a= 0 e b= 200000,pode-se utilizar o método de integração numérica.

3 Solução Numérica

Foi utilizado o método de integração 1a Regra de Simpson, uma vez que o inter-valo foi dividido em 8 partes de mesmo tamanho de passo 25000.

Para calcular o tempo médio de execução do algoritmo precisaremos aplicar alémda 1a Regra de Simpson, o Teorema do Valor Médio aplicado a Integrais.

Sendo f é uma função contínua em [a,b], e de acordo com o Teorema do ValorMédio aplicado a Integrais, então existe um z(a,b), tal que:

f(z) =1

b− a

∫ b

af(x).dx (1)

1

4 Obtenção dos Resultados

Figura 2: Tabela dos Resultados

4.1 1a Regra de Simpson

∫ 200000

0f(x).dx (2)

Para n = 8:

h =b− a

n(3)

logo h = 25000

Pela 1a Regra de Simpson, temos:

I =h

3(Y0 + 4Y1 + 2Y2 + 4Y3 + 2Y4 + 4Y5 + 2Y6 + 4Y7 + Y8) (4)

Considerando que:

(Y0 + 4Y1 + 2Y2 + 4Y3 + 2Y4 + 4Y5 + 2Y6 + 4Y7 + Y8) =8∑

i=0

Ci.Yi (5)

8∑i=0

Ci.Yi = 5546, 22 (6)

I =25000

3

8∑i=0

Ci.Yi = 46218500 (7)

2

4.2 Aplicação do Teorema do Valor Médio

Pelo Teorema do Valor Médio aplicado a Integrais, temos:

f(z) =1

200000− 0

∫ 200000

0f(x).dx (8)

Onde f(z) é o tempo médio gasto para a execução do algoritmo.

4.3 O Resultado

De acordo com os dados anteriores, temos que:∫ 200000

0f(x).dx = 46218500 (9)

então,

f(z) =1

200000− 0∗ 46218500 (10)

Logo,

f(z) = 231,09 ∼= 231, 1 segundos

5 Análise dos Resultados

O resultado obtido é coerente com o tempo médio previsto para a ordenação detodos os elementos, uma vez que 231, 1 ∈ [0; 694, 78]

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

3

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(11)

[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 issofrequentemente, 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.

4