Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — FGV 2023

Algoritmos e Estrutura de DadosAlgoritmos
Código
fg060681
Banca
FGV
Órgão
CGE-SC
Ano
2023
Nível
Superior
Cargo
Auditor do Estado - Ciências da Computação - Manhã (Conhecimentos Básicos)
Considere o algoritmo K-Means. Suponha os seguintes pontos: x1=(1,2,5); x2=(3,4,2); x3=(9,5,3); x4=(7,6,1); x5=(2,3,5); x6=(8,7,2). Escolha x1 e x4 como centros iniciais.Assinale a opção que apresenta corretamente os pontos em que seriam formados os grupos após a primeira iteração e quais seriam os novos centros.
  1. AGrupo 1: {x1, x3, x5}, Grupo 2: {x2, x4, x6}. Centros: c1= (4,3,4), c2 = (6,5,1).
  2. BGrupo 1: {x1, x2}, Grupo 2: {x3, x4}, Grupo 3: {x5, x6}. Centros: c1=(2,3,3), c2 = (8,5,2) , c3 = (5,5,3).
  3. CGrupo 1: {x1, x2, x5}, Grupo 2: {x3, x4, x6}. Centros: c1= (2,3,4), c2 = (8,6,2).
  4. DGrupo 1: {x1, x2, x3}, Grupo 2: {x4, x5, x6}. Centros: c1= (4,3,3), c2 = (5,5,2).
  5. EGrupo 1: {x2, x3, x5}, Grupo 2: {x1, x4, x6}. Centros: c1= (4,4,3), c2 = (5,5,2).
Revelar gabarito e comentário

GabaritoC — Grupo 1: {x1, x2, x5}, Grupo 2: {x3, x4, x6}. Centros: c1= (2,3,4), c2 = (8,6,2).

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Algoritmo K-Means – Primeira Iteração

Gabarito: letra C. Após a primeira iteração, os pontos são agrupados em: Grupo 1 = {x1, x2, x5} e Grupo 2 = {x3, x4, x6}, com novos centros c1 = (2,3,4) e c2 = (8,6,2), exatamente como descrito na alternativa C.

O K-Means agrupa pontos atribuindo cada um ao centro mais próximo (distância euclidiana) e depois recalcula os centros como a média dos pontos do grupo. Com centros iniciais x1=(1,2,5) e x4=(7,6,1), calculam-se as distâncias:

  • Grupo 1 (centro c1): x1 (dist 0), x2 (dist ≈4,12), x5 (dist ≈1,41) – todos mais próximos de c1 do que de c2.

  • Grupo 2 (centro c2): x3 (dist 3), x4 (dist 0), x6 (dist ≈1,73) – todos mais próximos de c2.

Novos centros:

  • c1 = média de x1, x2, x5 = ((1+3+2)/3, (2+4+3)/3, (5+2+5)/3) = (2, 3, 4)

  • c2 = média de x3, x4, x6 = ((9+7+8)/3, (5+6+7)/3, (3+1+2)/3) = (8, 6, 2)

Alternativa A — ❌ Incorreta

Grupo 1 contém x1, x3, x5 (x3 deveria estar no grupo 2) e Grupo 2 contém x2, x4, x6 (x2 deveria estar no grupo 1). Centros (4,3,4) e (6,5,1) não correspondem às médias corretas.

Alternativa B — ❌ Incorreta

Forma três grupos, mas o K-Meams com dois centros iniciais só pode gerar dois grupos na primeira iteração. Além disso, os centros listados não batem.

Alternativa C — ✅ Correta ⟵ GABARITO

Grupos e centros estão exatamente conforme o cálculo: Grupo 1 {x1,x2,x5}, Grupo 2 {x3,x4,x6}, c1=(2,3,4), c2=(8,6,2).

Alternativa D — ❌ Incorreta

Grupo 1 contém x1,x2,x3 (x3 deveria estar no grupo 2) e Grupo 2 contém x4,x5,x6 (x5 deveria estar no grupo 1). Centros (4,3,3) e (5,5,2) não correspondem.

Alternativa E — ❌ Incorreta

Grupo 1 contém x2,x3,x5 (x2 e x5 trocados com x1 e x4) e Grupo 2 contém x1,x4,x6. Centros (4,4,3) e (5,5,2) incorretos.

PEGA ESSA DICA!

Em questões de K-Means, sempre calcule as distâncias euclidianas entre cada ponto e os centros atuais, atribua ao centro mais próximo e depois recalcule a média aritmética por coordenada para obter os novos centros. Conferir a consistência dos agrupamentos com as distâncias evita erros.

Gabarito: letra C

Link permanente: /questoes/fg060681