Técnicas de recuento
Por técnicas de recuento hacemos referencia a cualquier algoritmo que se utiliza para contar, es decir, para hallar el cardinal de un conjunto. Dentro de las técnicas de recuento, merece un especial tratamiento la Combinatoria: variaciones, permutaciones y combinaciones; aunque no nos ocuparemos de ello en este tema puesto que ya han sido tratadas con anterioridad.
En este post vamos a estudiar principalmente dos tipos de problemas y algunas de las técnicas más utilizadas para resolverlos: los problemas de existencia y los de enumeración. Además veremos algunos ejemplos en los que se pueden aplicar.
PROBLEMAS DE EXISTENCIA
En este tipo de problemas nos planteamos si existen o no las ordenaciones o configuraciones consideradas. Para resolver este tipo de problemas utilizamos el estudio de la paridad:
–Estudio de la paridad: Un conjunto puede tener un número par o impar de elementos. Si probamos que tiene un número impar de objetos, podemos afirmar que existe al menos uno, quedando de esta forma probada la existencia. Un ejemplo de los problemas más famosos resueltos por este método es el de los puentes de Königsberg (por Euler 1763). En este problema se pretende pasar una vez por cada uno de los 7 puentes que unen sus islotes, volviendo al punto de partida. Como cada zona tiene un puente de entrada y otro de salida, se deduce que el número total de puentes debe ser par. No obstante, como hay siete puentes, el problema no tiene solución.
PROBLEMAS DE ENUMERACIÓN
En los problemas de enumeración tenemos que determinar el número de configuraciones pedidas. Dentro de este tipo de problemas, existen dos tipos de técnicas, las que tienen por objetivo contar, junto con las que descomponen el problema en uno más sencillo. Algunas de estas técnicas son:
-Principio de adición: Si se puede realizar una tarea de m formas distintas, mientras que otra se puede realizar de n formas; de tal manera que no se pueden realizar de forma simultánea. Entonces, se puede realizar cualquiera de ellas de m+n formas distintas.
-Principio de multiplicación: Si un procedimiento se puede separar en dos etapas, habiendo en una m resultados y en otra n, entonces el procedimiento total se puede realizar de mxn formas distintas.
-Correspondencia uno a uno: Se trata de establecer una correspondencia biyectiva entre el conjunto que se pretende contar, A, y una sección S(n) de los números naturales. De tal forma que: card (A)= card (S(n))=n.
-Principio de distribución: Dentro de este tipo está el “Principio de los cajones” de Dirichlet, también conocido como el “principio del palomar”: Si m palomas ocupan n nidos, con n<m, entonces hay al menos un nido con dos o más palomas en su interior.
OTRAS TÉCNICAS DE RECUENTO
Además de las técnicas mencionadas, existen otras que también pueden ser útiles en ciertos casos.
-Recurrencia: Esta técnica se basa en la idea de que para resolver un problema de tamaño n, podemos resolver primero un problema más pequeño, de tamaño n-1, n-2, etc. Una vez resueltos estos problemas más pequeños, se utilizan sus soluciones para resolver el problema original.
-Divide y vencerás: Esta técnica consiste en dividir el problema en subproblemas más pequeños y manejables, resolver estos subproblemas y luego combinar sus soluciones para resolver el problema original.
-Técnicas de grafos: Los grafos son estructuras que pueden representar relaciones entre objetos. Las técnicas de grafos pueden ser útiles para resolver problemas de recuento que involucran relaciones entre objetos.
-Técnicas de programación dinámica: La programación dinámica es una técnica que se utiliza para resolver problemas de optimización. Consiste en descomponer un problema en subproblemas más pequeños, resolver estos subproblemas y almacenar sus soluciones para su uso en la resolución de subproblemas más grandes.
Estas técnicas son solo algunas de las muchas que existen para resolver problemas de recuento. La elección de la técnica a utilizar depende del problema específico que se esté tratando de resolver.