IPRJ – PROJETO E ANÁLISE DE ALGORITMOS
LISTA DE EXERCÍCIOS 16
1
) Dentre os diversos algoritmos de ordenação, o Merge Sort básico, isto é, o
algoritmo original sem nenhum aprimoramento extra, é a melhor opção de
algoritmo segundo o critério de melhor caso (quando o vetor já está ordenado).
Verdadeiro ou Falso? Justifique sua resposta.
2
3
) Existem diversas variantes na escolha do pivô do Algoritmo de Partição utilizado
no Quicksort. Uma dessas variantes, obriga que o tempo para o melhor caso do
Quicksort seja O(n log n). Verdadeiro ou Falso? Justifique sua resposta.
) Qual o número de trocas (mudança na posição dos valores) realizadas pelo
algoritmo Quicksort no vetor A = {5, 9, 1, 3, 2, 8, 3, 2}? Considere o uso do
algoritmo Quicksort básico sem nenhum aprimoramento.
4
5
) Seja L um vetor com n elementos, onde cada elemento de L vale A, B ou C. Então, é
possível ordenar L com complexidade de pior caso O(n)? Como?
) O algoritmo Counting Sort utiliza um vetor auxiliar C para armazenar o número de
ocorrências de valores no vetor de entrada. Considerando vetor de entrada A = {2,
1
, 5, 2, 4, 4, 5, 4, 3, 4, 1, 3, 0, 1, 3, 0}, o conteúdo armazenado no vetor C após a
execução do Counting Sort é C = {0, 2, 5, 7, 11, 14}. Verdadeiro ou Falso? Justifique
sua resposta.
6
) Uma grande festa vai acontecer no Reino das Nuvens! Finn e Jake estão no castelo
da Princesa Jujuba planejando qual seria a melhor rota para chegar até a festa. A
figura abaixo ilustra o mapa da Terra de Ooo:
Responda as questões abaixo considerando "F" como o vértice inicial. Vértices
sucessores devem ser dispostos em ordem alfabética.
a) Realize uma busca em largura no grafo e apresente os valores de π e d
gerados pelo algoritmo.
b) Realize uma busca em profundidade no grafo e apresente os valores de π, d
e f gerados pelo algoritmo.
c) Construa as árvores de busca geradas pelos algoritmos de busca em
largura e busca em profundidade.
d) Considerando "K" como vértice objetivo, realize uma busca de caminho
mínimo utilizando o algoritmo de Dijkstra e apresente os valores de π e g
gerados pelo algoritmo. Em seguida apresenta o caminho mínimo
encontrado.
7
8
) Em uma busca em largura, o valor d[u] atribuído a um vértice u é independente da
ordem na qual são dados os vértices em cada lista de adjacências. Verdadeiro ou
Falso? Justifique sua resposta.
) Para instalar o gcc-4.4 é necessário instalar um conjunto de dependências. A figura
abaixo ilustra estas dependências:
a) Utilizando o algoritmo de Kahn, apresente uma ordenação topológica
definindo uma sequência valida para a instalação do gcc-4.4 e suas
dependências. Justifique sua resposta apresentando o conteúdo do vetor I e
da pilha L em todas as iterações do algoritmo.
b) Utilizando
o algoritmo de ordenação topológica com busca em
profundidade, apresente uma ordenação topológica definindo uma
sequência valida para a instalação do gcc-4.4 e suas dependências.
Justifique sua resposta apresentando o conteúdo do vetor d e f e da lista L
no final da execução do algoritmo.
9
) Se existe um caminho de u para v em um grafo orientado F, então qualquer busca
em profundidade deve resultar em d[v] ≤ f[u]. Verdadeiro ou Falso? Justifique sua
resposta.
1
0) Após muitos anos pedalando, Geovane já não têm a mesma disposição para
encarar as diversas subidas de Nova Friburgo. Como sabemos, Nova Friburgo é
extremamente montanhosa. Por razões sentimentais, ele não quer mudar para
uma cidade mais plana. Resolveu, então, que tentaria evitar grandes altitudes em
seus caminhos. Para isso, Geovane obteve com o serviço topográfico da prefeitura
um mapa de Nova Friburgo, em que cada rua do mapa possui a informação da
maior altitude encontrada quando trafegada. Tudo que ele precisa fazer agora é
implementar um programa para determinar rotas que minimizem a altura
percorrida entre pares (origem, destino).
a) Defina e ilustre uma estrutura de dados para armazenar e representar o
mapa fornecido pela prefeitura.
b) Apresente o pseudocódigo de um algoritmo que receba como parâmetro
uma origem e um destino. O algoritmo deve retornar um caminho entre a
origem e o destino que evite passar por grandes altitudes.
1
1
1) Considerando G = {V, A} um grafo direcionado representado por uma matriz de
adjacências. A complexidade do algoritmo de Kosaraju para encontrar os
componentes fortemente conectados de G é O(V2). Verdadeiro ou Falso? Justifique
sua resposta.
2) Considerando os seguintes grafos:
(
a)
(b)
Responda as questões a seguir iniciando os algoritmos pelo vértice "A" e dispondo
os vértices sucessores em ordem alfabética.
a) Utilizando o algoritmo de Kosaraju, apresente os componentes fortemente
conectados de cada um dos grafos na ordem em que eles são encontrados
pelo algoritmo.
b) Utilizando o algoritmo de Tarjan, apresente os componentes fortemente
conectados de cada um dos grafos na ordem em que eles são encontrados
pelo algoritmo.
1
1
3) Dado um grafo orientado representado por uma lista de adjacências, qual a
complexidade do processo de calcular o grau de saída de um vértice? Justifique sua
resposta descrevendo o processo.
4) A transposta de um grafo orientado G = (V, A) é o grafo GT = (V, AT), onde AT={(v,u)
∈
V×V|(u,v) ∈ A}. Desse modo, GT é G com todas as suas arestas invertidas.
a) Considerando que G é representado por uma lista de adjacências, descreva
um algoritmo para calcular GT a partir de G. Em seguida, análise a
complexidade do algoritmo proposto.
b) Considerando que G é representado por uma matriz de adjacências,
descreva um algoritmo para calcular GT a partir de G. Em seguida, análise a
complexidade do algoritmo proposto.
1
5) Um grafo orientado G=(V, A) é dito "semiconectado" se, para todos os pares de
vértices u, v ∈ V, temos u ⇝ v ou v ⇝ u. Forneça um algoritmo eficiente para
determinar se G é ou não "semiconectado". Análise a complexidade do algoritmo
proposto.