Dado que fazemos consultas por conteúdo na Web frequentemente, é importante compreendermos como o conteúdo dos sites é analisado pelos de serviços de busca. Um algoritmo importante nesse cenário é o PageRank.
O grafo da figura abaixo representa um conjunto de páginas Web que apontam para páginas em outros sites. A cada página está associado um valor de ranque computado por um algoritmo do tipo PageRank. Note que, apesar da página C possuir apenas um link de entrada, ela possui um valor de rank alto.



Seja o seguinte trecho extraído de Mueller e Massaron (2018, p. 212):

“A inovação trazida pelo PageRank é [considerar] que um índice invertido de termos não é suficiente para determinar se uma página corresponde à informação de busca do usuário. Palavras correspondentes (ou significados, a correspondência semântica da busca discutida no fim do capítulo) entre uma busca e o texto da página é um pré-requisito, mas não é suficiente, pois hiperlinks são necessários para avaliar se a página oferece conteúdo de qualidade e é confiável.

Quando se trata de sites, distinguir entre links de entrada e de saída é importante, e links internos que se conectam dentro do mesmo site não devem ser considerados. Os links vistos em uma página são de saída quando levam a outra página em outro site. Os links que trazem alguém para sua página vindos de uma página em outro site são links de entrada (backlinks). Como criador da página, você usa links de saída para fornecer informações adicionais ao conteúdo da página. Presumivelmente, você não usa links aleatórios na sua página (ou links que levam a conteúdos inúteis ou ruins) porque isso estragaria sua qualidade. Conforme aponta para bons conteúdos usando links, outros criadores usam links em suas páginas para apontar para à página quando ela for interessante ou de alta qualidade.

É uma cadeia de confiança. Hiperlinks são como aprovações ou recomendações para páginas. Links de entrada mostram que outros criadores confiam em você, e você compartilha parte dessa confiança adicionando links de saída às suas páginas que levam a outras.”

Observando a figura acima, utilize seu conhecimento sobre o PageRank para avaliar a veracidade das seguintes afirmações.

A computação do algoritmo considera o número de links que chegam a cada página.
A influência que uma página transfere para uma página para a qual ela aponta é inversamente proporcional ao número de links que ela utiliza para apontar para outros sites.
Páginas que não apontam para outras não são consideradas pelo PageRank.
Páginas que formam um ciclo não são consideradas pelo PageRank.

I e II são verdadeiras.


Apenas I é verdadeira.


III e IV são verdadeiras.


Apenas II é verdadeira.


Todas são verdadeiras.

1,25 pontos

PERGUNTA 8

Seja o cenário de um governador que seja melhorar o acesso entre um conjunto de cidades de uma região. Como os recursos são escassos, a equipe do governador precisa selecionar um conjunto de estradas nas quais serão investidos recursos. A equipe faz um levantamento do custo para melhorar as estradas entre cada duas cidades. Na figura abaixo, as cidades estão representas pelo conjunto de nós {0, 1, 2, 3, 4, 5} e o valor das arestas corresponde ao custo calculado pela equipe para melhorar a estradas entre os nós correspondentes.



O algoritmo de Prim identifica uma árvore geradora de mínimo custo a partir da escolha inicial de um nó aleatório e, a seguir, selecionando as arestas cujos pesos são os menores desde que não formem um ciclo, até que todos os nós sejam selecionados. No caso de empate no valor de arestas, uma é escolhida arbitrariamente.

Algoritmo de Prim

1. Selecione um nó aleatório

2. Crie conjunto de arestas como um conjunto vazio

3. Repita até que todos os nós estejam representados no conjunto de arestas

Selecione a menor aresta que se conecta aos nós presentes no conjunto de arestas

Inclua a aresta no conjunto de arestas





A figura abaixo ilustra como o algoritmo de Prim identifica uma árvore geradora de mínimo custo a partir da escolha inicial de um nó aleatório (no caso, o nó 0) e, a seguir, selecionando as arestas cujos pesos são os menores desde que não formem um ciclo, até que todos os nós sejam selecionados.



Aplique os conceitos apresentados para avaliar a veracidade das afirmações a seguir.

Um conjunto de arestas que compõem uma árvore geradora de mínimo custo para o grafo é {0-2, 2-1, 2-3, 3-5, 4-5}.

Um conjunto de arestas que compõem uma árvore geradora de mínimo custo para o grafo é {0-2, 2-1, 2-3, 2-5, 4-5}.

Um grafo pode ter mais que uma árvore geradora de mínimo custo.


II e III são verdadeiras.


Todas são verdadeiras.


II é verdadeira.


I é verdadeira.


I e III são verdadeiras.