MC558 - Prova P1

Enunciado distribuído na sala.

Gabarito:

1. 1. T(n) = n(n+1)(2n-1)/6 = Θ(n³)

   2. f₁ = lg²n, f₂ = (sqrt(2))^{lg n} = sqrt(n), f₃ = n, f₄ = n2ⁿ, f₅ = eⁿ. Esta é a única ordem possível.

2. 2. MB ≤ V

   3. M^tC ≤ E

   4. MB ≥ V

   5. M^tC ≥ E

   6. Existem vetores X e Y de dimensão n × 1 com zeros e uns tais que X + Y = V, M^tX = E e M^tY = E.

3. Arestas da árvore:

   b → e → h → i → f → l, h → k

   Tempos de chegada e saída:

   a: 1/2
   b: 3/16
   c: 17/18
   d: 19/20
   e: 4/15
   f: 7/10
   g: 21/22
   h: 5/14
   i: 6/11
   j: 23/24
   k: 12/13
   l: 8/9
   m: 25/26
   

   Componentes fortemente conexas:

   a, b, c, d, efhikl, g, j, m

4. Arestas da árvore:

   ab, bc, be, cd, cf, eh, ek, dg, dm, fi, fl, gj

   Distâncias:

   a: 0
   b: 1
   c: 2
   d: 3
   e: 2
   f: 3
   g: 4
   h: 3
   i: 4
   j: 5
   k: 3
   l: 4
   m: 4
   

Critérios de correção

Questão 1

1. 1. Resolução da recorrência vale 1,0. Saber a ordem de crescimento vale 0,5.

      Chute certo vale 0,5. Saber calcular a soma vale 0,5.

      Quem fez uma boa prova pode ganhar mais 0,5 ou 1,0.

      Quem fez só algumas contas que fazem sentido recebeu 0,5.

   2. Se trocou os dois últimos, perdeu: -0,5.

      Se não colocou ($\sqrt{2}$)^{lg n} no lugar certo, perdeu: -0.5.

      Inverteu ordem: ok.

2. Vale 0,5 cada item. Aceitamos 1 no lugar de V ou E representando vetores.

3. A floresta DFS vale 1,0 ponto. Os tempos valem 1,0 ponto. As componentes fortemente conexas valem 0,5 ponto.

   Quem pulou algum tempo perdeu: -0,5. Quem esqueceu as componentes pequenas, de um vértice, foi perdoado.

4. A árvore BFS vale 1,5 ponto. As distâncias valem 1,0 ponto.

   Quem errou uma ou duas arestas perdeu: -0,5.

   Quem colocou distâncias nas arestas perdeu: -0,5.

   Quem errou uma distância perdeu: -0,5.

MC558 Home

© 2012 João Meidanis