Algoritmos Essenciais: Análise, Busca e Ordenação

Classificado em Computação

Escrito em em português com um tamanho de 25,82 KB

Importância e Aplicabilidade da Técnica de Força Bruta

A força bruta é aplicável a uma ampla variedade de problemas. Para alguns problemas importantes, a técnica fornece algoritmos razoáveis independentemente do tamanho do problema, como é o caso, por exemplo, da ordenação, busca sequencial e multiplicação de matrizes.

Técnica de Backtracking: Descrição e Aplicabilidade

É um método para realizar busca exaustiva, isto é, avaliar todas as possíveis soluções de um problema. É geralmente aplicado a problemas de otimização.

Exercícios de Aplicação do Método Húngaro

Nos exercícios 3, 4, 5 e 6, aplique o método húngaro para resolver os problemas que estão sendo propostos. (Exemplo extraído de Anton & Rores, 2001, p.xx-xx)

17

4

10

15

5

8

18

7

11

13

0

6

10

0

3

11

0

4

53bMlcTfjhzBiO+OKsMu74SYofHggAOw==

2

0

2

0

1

0

0

0

0

Projeto de Algoritmos por Divisão e Conquista: Os Três Passos

O projeto de algoritmos por divisão e conquista envolve 3 passos em cada nível da recursão. Quais passos são estes?

  1. Dividir: o problema em um determinado número de subproblemas.

  2. Conquistar: os subproblemas resolvendo-os recursivamente, se os tamanhos destes não forem suficientemente pequenos ou diretamente caso contrário.

  3. Combinar: os subproblemas resolvidos de modo a produzir a solução do problema original.

Complexidade dos Métodos de Ordenação

Fale sobre a complexidade dos métodos Selection Sort, Insertion Sort, Bubble Sort, Merge Sort, Quick Sort e Heap Sort (árvore binária).

  1. Bubble Sort: O(n2) e no caso de vetor já ordenado O(n);
  2. Quick Sort: O(n log n) e no pior caso O(n2)
  3. Merge Sort: O(n log n)
  4. Selection Sort: O(n2)
  5. Insertion Sort: O(n2) e se o arquivo estiver ordenado em ordem crescente O(n)
  6. Heap Sort: O(n log n)

Eficiência de Algoritmos de Ordenação para Vetores Ordenados

Se os elementos do vetor estiverem ordenados em ordem crescente, qual algoritmo é mais eficiente: ordenação por seleção (Selection Sort) ou por inserção (Insertion Sort)? Justifique fazendo a simulação dos 2 algoritmos para um vetor ordenado de dimensão 6 (vetor A = {5,10,20,30,40,50}).

Simulação: Selection Sort

{5,10,20,30,40,50} (5)

  1. {5,10,20,30,40,50} (4)
  2. {5,10,20,30,40,50} (3)
  3. {5,10,20,30,40,50} (2)
  4. {5,10,20,30,40,50} (1) -> 15 comparações (n * (n - 1)/2)

Simulação: Insertion Sort

  1. {5,10,20,30,40,50} (1)
  2. {5,10,20,30,40,50} (1)
  3. {5,10,20,30,40,50} (1)
  4. {5,10,20,30,40,50} (1)
  5. {5,10,20,30,40,50} (1) -> 5 comparações (n – 1) -> mais eficiente

Simulação do Algoritmo Merge Sort

Simule o algoritmo Merge Sort sobre o vetor:

(a) A = {21,40,60,67,09,16,44,56}

21   40   60   67   09   16   44   56

21 40                60 67               09 16                44 56

21 40 60 67                  09 16 44 56

09 16 21 40 44 56 60 67

(b) B = {68,05,12,11,36,77,35,28}.

68   05   12   11   36   77   35   28

05 68                11 12               36 77                28 35

05 11 12 68                  28 35 36 77

05 11 12 28 35 36 68 77

Pesquisa Binária: Número Máximo de Comparações

No processo de pesquisa binária em um vetor ordenado, os números máximos de comparações necessários para se determinar se um elemento faz parte de vetores com tamanhos 50, 1000 e 300 são, respectivamente, iguais a:

  1. 5, 100 e 300
  2. 6, 10 e 9
  3. 8, 31 e 18
  4. 10, 100 e 30
  5. 25, 500 e 150

Análise do Algoritmo Merge Sort (PXCOMP 2013)

Considere o algoritmo a seguir. (PXCOMP 2013)

mergesort(v,i,j)

se (i < j)

  • m = (i+j)/2;
  • mergesort(v,i,m);
  • mergesort(v,m+1,j);
  • mesclar(v,i,m,j);
  • fim;

Sobre o comportamento assintótico do algoritmo de ordenação Merge Sort, assinale a alternativa que apresenta, corretamente, sua complexidade.

  1. O(log n)
  2. O(n log n)
  3. O(n2)
  4. O(n3)
  5. O(2n)

Algoritmos de Ordenação com Complexidade O(n log n) (PXCOMP 2002)

Quais dos algoritmos de ordenação abaixo possuem tempo no pior caso e tempo médio de execuções proporcional a O(n log n)? (PXCOMP 2002)

  1. Bubble Sort e Quick Sort
  2. Quick Sort e Merge Sort
  3. Merge Sort e Bubble Sort
  4. Heap Sort e Selection Sort
  5. Merge Sort e Heap Sort

Número Mínimo de Comparações para Encontrar o Menor Elemento (PXCOMP 2003)

Qual é o número mínimo de comparações necessário para encontrar o menor elemento de um conjunto qualquer não ordenado de n elementos? (PXCOMP 2003)

  1. 1
  2. n - 1
  3. n
  4. n + 1
  5. n log n

Escolha Adequada para um Algoritmo de Ordenação (PXCOMP 2013)

Sobre a escolha adequada para um algoritmo de ordenação, considere as afirmativas a seguir. (PXCOMP 2013)

  1. Quando os cenários de pior caso forem a preocupação, o algoritmo ideal é o Heap Sort.
  2. Quando o vetor apresenta a maioria dos elementos ordenados, o algoritmo ideal é o Insertion Sort.
  3. Quando o interesse for um bom resultado para o caso médio, o algoritmo ideal é o Quick Sort.
  4. Quando o interesse é o melhor caso e o pior caso de mesma complexidade, o algoritmo ideal é o Bubble Sort.

Assinale a alternativa correta.

  1. Somente as afirmativas I e II são corretas.
  2. Somente as afirmativas I e IV são corretas.
  3. Somente as afirmativas III e IV são corretas.
  4. Somente as afirmativas I, II e III são corretas.
  5. Somente as afirmativas II, III e IV são corretas.

Complexidade da Busca Sequencial (PXCOMP 2002)

Considere o algoritmo da busca sequencial de um elemento em um conjunto com n elementos. A expressão que representa o tempo médio de execução desse algoritmo para uma busca bem-sucedida é: (PXCOMP 2002)

  1. O(n2)
  2. O(n(n+1)/2)
  3. O(log2 n)
  4. O((n+1)/2)
  5. O(n log n)

Análise do Algoritmo Super Merge (PXCOMP 2002)

Professor Mac S. Perto propôs o seguinte algoritmo de ordenação, chamado de Super Merge, similar ao Merge Sort: divida o vetor em 4 partes do mesmo tamanho (ao invés de 2, como é feito no Merge Sort). Ordene recursivamente cada uma das partes e depois intercale-as por um procedimento semelhante ao procedimento de intercalação do Merge Sort. Qual das alternativas abaixo é verdadeira? (PXCOMP 2002)

  1. Super Merge não está correto. Não é possível ordenar quebrando o vetor em 4 partes.
  2. Super Merge está correto, mas consome tempo O(Merge Sort).
  3. Super Merge está correto, mas consome tempo maior que O(Merge Sort).
  4. Super Merge está correto, mas consome tempo menor que O(Merge Sort).
  5. Nenhuma das afirmações acima está correta.

Algoritmo de Ordenação Mais Rápido para Variedade de Dados (PXCOMP 2003)

Dentre os algoritmos de ordenação citados abaixo, qual é o que executa mais rápido para uma grande variedade de entrada de dados? (PXCOMP 2003)

  1. Bubble Sort (Bolha)
  2. Shell Sort
  3. Merge Sort
  4. Quick Sort
  5. Heap Sort

Afirmativas sobre o Algoritmo de Pesquisa Binária (PXCOMP 2004)

Considere as seguintes afirmativas sobre o algoritmo de pesquisa binária (O(log2 n)): (PXCOMP 2004)

  1. A entrada deve estar ordenada.
  2. Uma pesquisa com sucesso é feita em tempo logarítmico na média.
  3. Uma pesquisa sem sucesso é feita em tempo logarítmico na média.
  4. O pior caso de qualquer busca é logarítmico.

As afirmativas corretas são:

  1. Somente I e II.
  2. Somente I, II e III.
  3. Somente II e III.
  4. Somente III e IV.
  5. Todas as afirmativas estão corretas.

Algoritmos de Ordenação Estáveis (PXCOMP 2005)

Um algoritmo de ordenação é estável se a ordem relativa dos itens com chaves iguais mantém-se inalterada após a ordenação. Quais dos seguintes algoritmos de ordenação são estáveis? (PXCOMP 2005)

  • Bubble Sort (ordenação por bolha);
  • Insertion Sort (ordenação por inserção);
  • Heap Sort;
  • Quick Sort;

Somente (ii).

  1. Somente (i) e (ii).
  2. Somente (i), (ii) e (iii).
  3. Somente (ii), (iii) e (iv).
  4. Somente (i), (iii) e (iv).

Limitante Inferior para Ordenação por Comparação (PXCOMP 2006)

Seja P o problema de ordenar, usando comparação, n ≥ 1 elementos e C a classe dos algoritmos que resolvem P. O limitante inferior de C é: (PXCOMP 2006)

  1. Ω(1)
  2. Ω(log n)
  3. Ω(n)
  4. Ω(n log n)
  5. Ω(n2)

Algoritmos com Complexidade O(n log n) no Melhor Caso (PXCOMP 2006)

Quais algoritmos de ordenação têm complexidade O(n log n) para o melhor caso, onde n é o número de elementos a ordenar. (PXCOMP 2006)

  1. Insertion Sort e Quick Sort
  2. Quick Sort e Heap Sort
  3. Bubble Sort e Insertion Sort
  4. Heap Sort e Insertion Sort
  5. Quick Sort e Bubble Sort

Análise de Algoritmos de Ordenação (PXCOMP 2007)

Seja V = uma lista qualquer de inteiros distintos que se deseja ordenar em ordem não decrescente. Analise as seguintes afirmativas. (PXCOMP 2007)

  1. Considere o algoritmo Quick Sort. Suponha uma execução do algoritmo sobre V tal que a cada sorteio do pivô, a mediana do (sub)problema em questão é escolhida. Então, a complexidade dessa execução é O(n log n).
  2. Considere o algoritmo Quick Sort. Suponha uma execução do algoritmo sobre V tal que a cada sorteio do pivô, os 2 subproblemas gerados têm tamanho e respectivamente do tamanho do (sub)problema em questão. Então, a complexidade dessa execução é O(n2).
  3. Considere o algoritmo Merge Sort. A complexidade do pior caso do algoritmo é O(n log n) e a complexidade do melhor caso (vetor já está ordenado) é O(n).
  4. Considere o algoritmo Heap Sort. A complexidade do pior caso do algoritmo é O(n log n) e a complexidade do melhor caso (vetor já está ordenado) é O(n).
  5. Se para todo i, Vi é O(n), então a complexidade do algoritmo Bucket Sort é O(n).

A partir dos dados acima, pode-se concluir que estão corretas:

  1. Apenas as afirmativas I e II.
  2. Apenas as afirmativas I, II e III.
  3. Apenas as afirmativas I, III e V.
  4. Apenas as afirmativas III, IV e V.
  5. Apenas as afirmativas I e V.

Assinale a Afirmativa Incorreta (PXCOMP 2008)

Assinale a afirmativa incorreta. (PXCOMP 2008)

  1. Seja A[1,n] um vetor não ordenado de inteiros com um número constante k de valores distintos. Então existe algoritmo de ordenação por contagem que ordena A em tempo linear.
  2. Seja A[1,n] um vetor não ordenado de inteiros com um número constante k de valores distintos, então o limite inferior para um algoritmo de ordenação por comparações para ordenar A é de O(n log n).
  3. Seja A[1,n] um vetor não ordenado de inteiros, cada inteiro com no máximo d dígitos, onde cada dígito assume um valor entre um número constante k de valores distintos. Então o problema de ordenar A tem limite inferior O(n).
  4. Seja A[1,n] um vetor não ordenado de inteiros, cada inteiro com no máximo d dígitos, onde cada dígito assume um valor entre O(n) valores distintos. Então o problema de ordenar A tem limite inferior O(n log n).
  5. Seja A[1,n] um vetor não ordenado de inteiros com um número constante k de valores distintos, então um algoritmo de ordenação por comparações ótimo para ordenar A tem complexidade O(n log n).

Sentenças sobre Busca em Vetores Ordenados (PXCOMP 2008)

Considere as seguintes sentenças: (PXCOMP 2008)

  1. Se um vetor A[1,n], n ≥2, de inteiros é ordenado em ordem não decrescente, então encontrar o i-ésimo maior elemento, 1 ≤ i ≤ n, pode ser feito em tempo constante.
  2. Se um vetor A[1,n], n ≥2, de inteiros é ordenado em ordem não decrescente, o limite inferior para o problema de encontrar o i-ésimo maior elemento, 1 ≤ i ≤ n, com um algoritmo de comparação, é O(n).
  3. Se um vetor A[1,n], n ≥2, de inteiros é ordenado em ordem não decrescente, o limite inferior para o problema de encontrar o i-ésimo maior elemento, 1 ≤ i ≤ n, com um algoritmo de comparação, é O(log n).
  4. Se um vetor A[1,n], n ≥2, de inteiros é ordenado em ordem crescente, então encontrar o (n - 1)-ésimo maior elemento, pode ser feito em tempo constante.
  5. Se um vetor A[1,n], n ≥2, de inteiros é ordenado em ordem crescente, então encontrar o i-ésimo maior elemento, pode ser feito em tempo constante.

A esse respeito, assinale a alternativa correta.

  1. Apenas os itens II e IV são falsos.
  2. Apenas os itens I, III e V são verdadeiros.
  3. Apenas os itens III, IV e V são verdadeiros.
  4. Apenas os itens II e III são falsos.
  5. Apenas os itens II e V são verdadeiros.

Multiplicação de Números: Divisão e Conquista vs. Gauss

Multiplicar X * Y utilizando o método tradicional da divisão e conquista e o método de Gauss:

a) X = 1150 e Y = 2010 → a = 11, b = 50, c = 20, d = 10

Método: Divisão e Conquista

a*c*104 + (a*d+b*c)*102 + b*d

2200000

110000

500

2311500

Método de Gauss

g = (a+b)*(c+d), e = a*c, f = b*d, h = g-e-f

X * Y = e*104 + h*102 + f

  1. X * Y = 11*20*104 + ((11+50)*(20+10) – 11*20 – 50*10)*102 + 50*10

X * Y = 2200000 + (1830-220-500)*100 + 500

X * Y = 2200000 + 111000 + 500

X * Y = 2311500

Karma: 6%
Visitas: 0

Entradas relacionadas:

Etiquetas:
Método Húngaro Quick Sort Insertion Sort Bubble Sort Ordenação Algoritmos Busca Força Bruta Selection Sort Merge Sort Complexidade de Algoritmos Backtracking Divisão e Conquista