La mayoría de los problemas que he visto que involucran el principio del casillero hasta ahora han parecido bastante artificiales. Mientras estudio CompSci, me interesa qué tipo de problemas prácticos y reales se resuelven en CompSci utilizando este principio.
Respuesta
¿Demasiados anuncios?
Algunos problemas pueden ser muestra de que no se pueda resolver usando el principio del palomar. Por ejemplo, la inexistencia de un universal algoritmo de compresión sin pérdida (un algoritmo que siempre comprime una cadena de caracteres dentro de una cadena más corta de caracteres) puede ser demostrado ser imposible por el uso de una caja argumento que muestra que dos cadenas tendría que ser comprimido en la misma representación comprimida, lo que es imposible sin pérdida descomprimir la cadena. El principio del palomar es también la base para el lema de bombeo para regular y el contexto libre de idiomas, que puede ser utilizado para mostrar que ciertos lenguajes no son regulares o de contexto libre. Estas pruebas son un poco más complicado, pero puede ser utilizado para mostrar que los lenguajes de programación no puede ser analizado exclusivamente a través de expresiones regulares y el contexto libre de gramáticas.
El principio del palomar se puede utilizar de una manera más sutil para obtener el $\Omega(n \log n)$ límite inferior en comparación ordena demostrando que si el algoritmo hace menos comparaciones de esto, debe haber algún par de entradas que el algoritmo no sería capaz de distinguir, ya que hay más entradas posibles de configuraciones del algoritmo. Argumentos similares pueden ser utilizados para mostrar otros límites inferiores en otros problemas.
También en el CS de la teoría, la prueba de que la palabra problema lineal acotado autómata (es decir, dado un LBA y una cadena, ¿el LBA aceptar la cuerda?) puede ser demostrado ser decidable utilizando el principio del palomar. Usted acaba de ver el autómata de cierto número de pasos, y si alguna vez entra en un duplicado de la configuración, se debe bucle para siempre. Ya que hay sólo un número finito de configuraciones de la LBA cuando se ejecuta en una determinada cadena de entrada w (decir que hay n posibles configuraciones) este proceso está garantizado para terminar en la mayoría de los n + 1 pasos, ya que después de n + 1 la máquina debe haber detenido o visitó algún estado dos veces y es un bucle infinito.
Espero que esto ayude!
