Para a questão, defina \( G_{n \times n} \) como um grafo não dirigido 2D grid com 4-vizinhança da seguinte forma:

cada vértice é identificado com uma coordenada inteira 2D, de (1,1) até (n,n); há n x n vértices, correspondendo a todos os valores de (1,1) até (n,n); em cada vértice incidem até 4 arestas, a saber, para um vértice (i,j)

(i,j) ↔ (i-1,j)

(i,j) ↔ (i+1,j)

(i,j) ↔ (i ,j-1)

(i,j) ↔ (i ,j+1)

onde as arestas não existem se alguma coordenada é < 1 ou > n. A Figura 1 (a seguir) mostra um exemplo para n = 5

Marque a resposta mais exata e precisa. O número de arestas em \( G_{n \times n} \) é:

Para a questão, considere as seguintes funções de hash em pseudo-código para gerar códigos de hash para strings.

int P( char *s, int tablesize) {
  return s[0] % tablesize;
}

int S( char *s, int tablesize) {
  int sum = 0;
  for (char *p = s; *p; p++)
    sum = (sum + *p) % tablesize;
  return sum;
}

Esta questão se refere a serviços P ou S que permite que usuários enviem strings que são armazenadas em uma tabela hash utilizando, respectivamente, as funções de hash de mesmo nome. Um atacante deseja rapidamente forçar que o tempo de busca de tais strings se torne \( \Theta \) (n) ao invés de O(1), através do envio ao servidor de um conjunto apropriado de strings.

Marque a opção FALSA.

Para a questão, considere as seguintes funções de hash em pseudo-código para gerar códigos de hash para strings.

int P( char *s, int tablesize) {
  return s[0] % tablesize;
}

int S( char *s, int tablesize) {
  int sum = 0;
  for (char *p = s; *p; p++)
    sum = (sum + *p) % tablesize;
  return sum;
}

As alternativas comparam as duas funções em relação à conveniência de serem usadas como função de hash, considerando o tempo de busca médio.

Marque a alternativa FALSA.

Suponha um grafo onde os vértices são cidades, as arestas estradas entre cidades, e o peso das arestas corresponde a distância entre pares de cidades.

É possível, portanto, se for fornecido um valor da velocidade do veículo, usar Dijkstra para encontrar o caminho mais rápido entre 2 cidades, e obter o tempo gasto nesse caminho mínimo. Para isto, basta modificar o custo das arestas para indicar o tempo = distância / velocidade e não a distância.

Qual das seguintes variações do problema exige, para ser resolvida, modificar o algoritmo Dijkstra original, não sendo possível utilizar o Dijstra inalterado, como caixa preta, e apenas modificar o grafo de entrada, inclusive a escolha dos vértices inicial e final?

Marque a alternativa CORRETA.

Sobre o algoritmo de Dijkstra para encontrar caminhos mínimos sobre um grafo \( G=(V,E) \) não-dirigido e com pesos nas arestas. Uma variação comum do algoritmo armazena em cada nó um ponteiro u.p para o seu antecessor no caminho mais curto da raiz até ele. Chame essa variação de DijkstraP.

Defina: o subgrafo S(G) = (V,E’) como um subgrafo de G, cujos vértices são os mesmos de G, mas E’ é um subconjunto de E. Uma aresta (u,v) de E pertence a E’ apenas se, depois de executado DijsktraP, v.p = u;

Marque a alternativa FALSA: