Use uma árvore de decisão para descrever um procedimento ótimo para identificar um pássaro dentre as seis espécies a seguir, usando apenas perguntas “sim ou não”. Explique como você sabe que o seu procedimento é ótimo.
Espécies Fatos
Yellow Warbler Quase todo amarelo, cabeça da mesma cor.
Wilsoiis Warbler Quase todo amarelo, cabeça preta, dorso verde-oliva.
American Goldfinch Quase todo amarelo, cabeça preta, dorso amarelo.
Oak Titmouse Quase todo cinza, com penacho.
Hutton's Vireo Quase todo cinza, dorso verde-oliva, sem penacho.
Blue-gray Gnatcatcher Quase todo cinza, dorso cinza-escuro, sem penacho.

Passo 1

O enunciado pede um procedimento de classificação por meio de perguntas “sim ou não” para distinguir seis espécies de pássaros. O conteúdo envolvido é o de árvores de decisão binárias e noções básicas de informação (bits) para medir quantas perguntas são necessárias em piores casos.

Passo 2

Cada pergunta “sim ou não” fornece no máximo 1 bit de informação. Para escolher uma dentre 6 espécies, precisamos de pelo menos
lceil log2 6rceil = 3
perguntas em qualquer árvore de decisão, pois 2^2=4<6<=8=2^3.

Passo 3

Para maximizar o balanceamento, a primeira pergunta deve dividir o conjunto em dois grupos de tamanho o mais igual possível. Uma escolha natural é:
“O pássaro é quase todo amarelo?”
bul<=t Se “Sim”, restam exatamente 3 espécies amarelas.
bul<=t Se “Não”, restam exatamente 3 espécies acinzentadas.

Passo 4

Ramo “Sim” ( 3 amarelos). Pergunta seguinte:
“A cabeça é preta?”
bul<=t Se “Não”, sobra apenas o Yellow Warbler (toda amarela e cabeça amarela).
bul<=t Se “Sim”, sobra um par Wilson's Warb<=r, American Goldfinch.

Passo 5

Para distinguir essas duas espécies com cabeça preta, perguntamos:
“O dorso é verde-oliva?”
bul<=t Se “Sim”, é Wilson’s Warbler (dorso verde-oliva).
bul<=t Se “Não”, é American Goldfinch (dorso amarelo).

Passo 6

Ramo “Não” à primeira pergunta ( 3 acinzentados). Pergunta seguinte:
“O pássaro tem penacho?”
bul<=t Se “Sim”, é Oak Titmouse (único com penacho).
bul<=t Se “Não”, restam Hutton's Vireo, Blue-gray Gnatcatcher.
Para esse par, fazemos:
“O dorso é verde-oliva?”
bul<=t Se “Sim”, é Hutton’s Vireo.
bul<=t Se “Não”, é Blue-gray Gnatcatcher (dorso cinza-escuro).

Passo 7

Essa árvore tem profundidade máxima 3, igual ao limite inferior lceillog2 6rceil=3. Logo não é possível usar menos perguntas em pior caso, o que prova que o procedimento é ótimo.

Resposta

Árvore de decisão ótima (máximo de 3 perguntas):
1. É quase todo amarelo?
– Sim to 2. A cabeça é preta?
bul<=t Não to Yellow Warbler
bul<=t Sim to 3. O dorso é verde-oliva?
– Sim to Wilson’s Warbler
– Não to American Goldfinch
– Não to 2. O pássaro tem penacho?
bul<=t Sim to Oak Titmouse
bul<=t Não to 3. O dorso é verde-oliva?
– Sim to Hutton’s Vireo
– Não to Blue-gray Gnatcatcher