Galey Shapley & introducción

Cual de las siguientes cotas de complejidad no corresponde a la de un algoritmo "Bueno"

Un problema que se puede resolver en tiempo polinomial corresponde a

• un problema tratable

• un problema bueno

• un problema polinomial

• un problema de Cobham–Edmonds

La optimalidad de un algoritmo se refiere a

• si su complejidad temporal es la mejor posible dado la naturaleza del mismo

• si su complejidad espacial es la mejor posible dado la naturaleza del mismo

• si obtiene siempre la respuesta correcta

• si se ejecuta en tiempo polinomial

• si su complejidad temporal y espacial es la mejor posible dado la naturaleza del mismo

En el problema de los casamientos estables un matching perfecto corresponde a

• uno donde no hay parejas inestables

• uno donde cada individuo esta en no mas ni menos que en una pareja

• uno donde cada individuo esta a lo sumo en una pareja

• uno donde no hay parejas inestables y todos están en parejas

El algoritmo de Gale Shapley resuelve el problema de parejas estables en

El matching resultante al aplicar Gale Shapley depende del orden en el que se procesan a los solicitantes que aun no tienen pareja

• Verdadero

• Falso

A medida que se ejecuta Gale Shapley

• La pareja de los requeridos tiende a mejorar

• La pareja de los solicitantes tiene a mejorar

• El numero de parejas conformado puede aumentar o disminuir (nunca mantenerse igual)

• Todas las anteriores

• Ninguna de las anteriores

El mejor compañero valido (best valid partner) de un individuo corresponde a

• al primero en su lista de preferencias

• a aquel con el que se queda emparejado luego de aplicar Galey-Shapley

• a aquel de mayor preferencia entre aquel subconjunto de individuos con los que queda emparejado en algún matching estable

• Todos los anteriores

• Ninguno de los anteriores

Utilizando el algoritmo Gale Shapley el matching resultante es

• el mejor posible para los requeridos

• el mejor posible para los solicitantes

• un matching que beneficia tanto a solicitantes como requeridos

Si un solicitante s tiene a un requerido r en su primer lugar de preferencia y ocurre lo mismo en la lista de r con respecto a s, entonces

• Gale Shapley genera la pareja (s,r)

• El requerido r quedará emparejado con su best valid partner al aplicar Gale Shapley

• El solicitante s solo tendrá un único valid partner

• Todas las anteriores

• Ninguna de las anteriores