Pregunta de entrevista, probando una red de clasificación

1

Aquí hay una pregunta en la que me topé:

enlace

MinMax2 es un componente con 2 entradas, A y B, y 2 salidas, Máx y Mín. Lo has adivinado, conectas 2 números en las entradas y el componente controla la salida máxima con el mayor de los dos y la salida mínima con el menor de los dos.

Su trabajo es diseñar un componente MinMax4, con 4 entradas y 4 salidas, que clasifique los 4 números utilizando solo componentes MinMax2. Trate de usar la menor cantidad posible de componentes MinMax2.

Aquí está la solución: enlace

Logré resolverlo, pero lo que no respondí con éxito fue: ¿cuántas secuencias de entrada diferentes se necesitan para verificar el comportamiento lógico de MinMax4?

La respuesta obvia es $ 4! $, pero según tengo entendido, hay una solución más mínima.

    
pregunta krolya

1 respuesta

1

La pregunta es ambigua, aunque a veces las preguntas de la entrevista son intencionalmente ambiguas para provocar una discusión de las ambigüedades.

Una forma de verlo es, si está verificando un diseño para una red de clasificación de 4 entradas, cuántas secuencias de entrada se necesitan para asegurarse de que la implementación sea correcta. Si no sabe nada sobre cómo se implementa, entonces necesita probar todas las permutaciones de $ 4! $ De cuatro valores para estar absolutamente seguro de que la implementación es correcta.

Otra forma de verlo es, si fabrica el circuito, cuántas secuencias de entrada necesita aplicar a cada dispositivo durante la prueba para asegurarse de que el circuito se haya fabricado correctamente. En este caso, por lo general, tomaría el diseño como un hecho dado, por lo que no necesita cubrir todas las permutaciones de $ 4! $, Solo necesita suficientes entradas para cubrir los casos interesantes de cada elemento del circuito. Supongo que esta era la intención de la pregunta, y supongo que solo dos casos se consideran interesantes para cada componente de MinMax2 (A > B y A < B). También está el caso A = B, pero se puede argumentar que el comportamiento de MinMax2 es indiferente cuando A = B.

Esto no es realista, ya que en la práctica necesitaría más de dos casos para asegurarse de que todos los transistores y cables dentro del componente MinMax2 se fabricaron correctamente. Pero asumiré que solo estamos tratando de cubrir dos casos para cada MinMax2.

En ese caso, si las entradas son de la A a la D, donde A < B < C < D, entonces solo se necesitan dos entradas para cubrir ambos casos para cada MinMax2: A, C, B, D y D, C, B, A. El primero cubre el caso de "no intercambio" para cada MinMax2, y el segundo cubre el caso de "intercambio" para cada MinMax2.

    
respondido por el Andy

Lea otras preguntas en las etiquetas