Problemas De Conteo

Problemas De Conteo

Enumeración

En las matemáticas y teóricas ciencias de la computación, La definición más amplia y más abstracta de una enumeración de un conjunto es una lista exacta de todos sus elementos (Tal vez con la repetición). Las restricciones impuestas en el tipo de lista utilizarse dependen de la rama de las matemáticas y el contexto en el que uno está trabajando. En configuraciones más específicas, esta noción de la enumeración abarca los dos tipos diferentes de anuncio: una donde hay una orden natural y uno donde el orden es más nebuloso. Estos dos tipos de enumeraciones corresponden a un procedimiento de inclusión de todos los miembros del conjunto en algunos definida secuenciaO un recuento de los objetos de un tipo especificado, respectivamente. Si bien los dos tipos de enumeración a menudo se superponen en las situaciones más naturales, pueden asumir significados muy diferentes en contextos determinados.

Enumeración como contar

Formalmente, la definición más inclusiva de una enumeración de un conjunto S es cualquier surjection de una arbitraria índice establecido I en S. En este contexto general, cada sistema S puede ser fácilmente enumerados por la función de la identidad de S sobre sí mismo. Si uno hace no asumir la axioma de elección o una de sus variantes, S no necesita tener ningún buen orden. Incluso si se asume el axioma de elección, S no necesita tener ningún naturales del buen orden.

Esta definición general, por tanto se presta a una idea de contar en el que está interesado en “cuántos” en lugar de “en qué orden.” En la práctica, este sentido amplio de la enumeración se utiliza a menudo para comparar los tamaños relativos o cardinalidades de los diferentes conjuntos. Si se trabaja en Zermelo-Fraenkel, la teoría de conjuntos sin el axioma de elección, uno puede querer imponer la restricción adicional de que una enumeración también debe ser inyectiva (Sin repetición), ya que en esta teoría, la existencia de un surjection de I en S necesidad no implica la existencia de un inyección de S en I.

Enumeración como lista

Cuando una enumeración se utiliza en una lista ordenada contexto, se impone algún tipo de requisito de ordenar la estructura del índice fijado. Mientras que podemos hacer con los requisitos en el orden muy laxa con el fin de permitir la gran generalidad, la más natural y común requisito previo es que el índice se establece bien ordenada. De acuerdo con esta caracterización, una enumeración ordenada se define como un surjection con un dominio bien ordenada. Esta definición es natural en el sentido de que un determinado bien al comprar en el conjunto índice proporciona una manera única a la lista el siguiente elemento dado un recuento parcial.

Enumeración en el contexto contable vs incontables

El uso más común de la enumeración se produce en el contexto en el que los conjuntos infinitos se dividen en aquellos que son contables y los que no lo son. En este caso, una enumeración no es más que una enumeración con ω dominio. Esta definición también puede enunciarse como sigue:

Como sobreyectiva asignación de \mathbb{N} (El números naturales) Para S (Es decir, cada elemento de S es la imagen de al menos un número natural). Esta definición es especialmente adecuado para las cuestiones de computabilidad y primaria la teoría de conjuntos.

También podemos definirlo de forma diferente cuando se trabaja con conjuntos finitos. En este caso, una enumeración se puede definir de la siguiente manera:

Como biyectiva asignación de S a un segmento inicial de los números naturales. Esta definición es especialmente adecuado a las preguntas combinatoria y conjuntos finitos, entonces el segmento inicial es {1,2 ,…,n} Para algunos n que es el cardinalidad de S.

En la primera definición que varía si la asignación se requiere también que se inyectiva (Es decir, cada elemento de S es la imagen de exactamente un número natural), y / o permitir que se parcial (Es decir, la asignación se define sólo para algunos números naturales). En algunas aplicaciones (especialmente las relativas a la computabilidad de la serie S), Estas diferencias son de poca importancia, porque uno se ocupa sólo de la mera existencia de alguna enumeración, y una enumeración de acuerdo con una definición liberal generalmente implica que las enumeraciones satisfacer requisitos más estrictos también existen.

La enumeración de conjuntos finitos obviamente, requiere que, o bien no inyectividad o parcialidad es aceptada, y en contextos en los conjuntos finitos puede aparecer uno o ambos están inevitablemente presentes.

Propiedades

Existe una enumeración de un conjunto (en este sentido) si y sólo si el conjunto es contable.

Si un conjunto es numerable tendrá un incontables infinidad de enumeraciones diferentes, salvo en los casos degenerados del conjunto vacío o (dependiendo de la definición exacta) establece con un elemento. Sin embargo, si se requiere enumeraciones ser inyectiva y sólo permite una forma limitada de la parcialidad de tal manera que si ƒ(n) Se define a continuación, ƒ(m) Debe estar definido para todos los m < n, A continuación, un conjunto finito de N elementos tiene exactamente N! enumeraciones.

Una enumeración e de un conjunto S con dominio \mathbb{N} induce una bien para ≤ en ese conjunto definido por s ≤ t si y sólo si min e−1(s) ≤ min e−1(t). Aunque el orden puede tener poco que ver con el conjunto subyacente, es útil cuando un poco de orden del conjunto es necesario.

Computable enumeración

En la teoría de la computabilidad A menudo se considera enumeraciones contables con el requisito adicional de que la asignación de \mathbb{N} al conjunto enumerados deben ser calculable. El conjunto que se enumeran a continuación, se llama recursivamente enumerable (O computably enumerable en un lenguaje más contemporáneo), en referencia a la utilización de la teoría de la recursividad en formalizaciones de lo que significa para el mapa para ser computables.

En este sentido, un subconjunto de los números naturales es computably enumerable si es el rango de una función computable. En este contexto, enumerables se puede utilizar para decir computably enumerable. Sin embargo, estas definiciones caracterizan a las distintas clases, ya que hay muchas uncountably subconjuntos de los números naturales que se pueden enumerar de una función arbitraria con ω de dominio y sólo las funciones computables cantidad numerable. Un ejemplo específico de un conjunto con una enumeración, pero no una enumeración computable es el complemento de la detener conjunto.

Por otra parte, esta caracterización se muestra un lugar donde el orden de la lista es importante. Existe una enumeración computables del conjunto de la detención, pero no que enumera los elementos en un aumento de pedidos. Si hubiera uno, entonces el conjunto de la detención se decidible, Que es demostrablemente falsa. En general, se recursivamente enumerable es una condición más débil que la de ser un conjunto decidible. [edición] Ordinal enumeración

En la teoría de conjuntos, No es una noción más general de una enumeración de la caracterización que requiere el dominio de la función de un prospecto que se segmento inicial de los números naturales donde el dominio de la función de enumeración puede asumir ninguna ordinal. Bajo esta definición, la enumeración de un conjunto S es cualquier surjection de un ordinal α en S. La versión más restrictiva de la enumeración antes mencionada es el caso especial donde α es un ordinal finito o límite de la ω ordinal primero. Esta versión más generalizada se extiende la definición mencionada para abarcar transfinitos listados.

Bajo esta definición, el primero incontables ordinales ω1 se pueden enumerar de la función de identidad en ω1 para que estas dos nociones no no coinciden. De manera más general, es un teorema de ZF que cualquier bien ordenada conjunto se pueden enumerar en esta caracterización de manera que coincide hasta volver a etiquetar con la enumeración lista generalizada. Si también se supone que el Axioma de elección, Entonces todos los conjuntos se pueden enumerar de manera que coincide hasta volver a etiquetar con la forma más general de las enumeraciones.

Desde teóricos establecidos trabajar con conjuntos infinitos de arbitrariamente grande cardinalidades, La definición por defecto en este grupo de matemáticos de una enumeración de un conjunto tiende a ser cualquier α-secuencia arbitraria exactamente lista de todos sus elementos. En efecto, en el libro de Jech, que es una referencia común para los teóricos de conjunto, una enumeración se define exactamente esto. Por lo tanto, con el fin de evitar la ambigüedad, se puede usar el término finito o numerable numerables para referirse a uno de los tipos correspondientes de distinguidos enumeraciones contables.

Enumeración como combinatoria contar

Hay subáreas floreciendo en muchas ramas de las matemáticas relacionadas con la enumeración (en el sentido de lo finito contar) Los objetos de tipo especial. Por ejemplo, en permutación enumeración y gráfico de enumeración el objetivo es contar permutaciones o gráficos que cumplen con ciertas condiciones estructurales.

Enumeration. (2011, January 3). In Wikipedia, The Free Encyclopedia. Retrieved 15:52, January 12, 2011, from http://en.wikipedia.org/w/index.php?title=Enumeration&oldid=405660297

Problemas de conteo

Principios del conteo

Contar es un proceso de abstracción que nos lleva a otorgar un cardinal como representativo de un conjunto. Gelman y Gallistel fueron los primeros en enunciar en 1978 los cinco principios que, a modo de estadios, ha de ir descubriendo y asimilando el niño hasta que aprende a contar correctamente:

Principio de correspondencia uno a uno o correspondencia biunívoca

Trae consigo la coordinación de dos subprocesos: la partición y la etiquetación. La partición consiste en otorgar la categoría de contado o no contado formando dos grupos entre el conjunto de objetos que se quieren contar. Esto se realiza generalmente señalando el objeto, agrupándolo a un lado o bien a través de la memoria visual.

La etiquetación es el proceso por el que el niño asigna un cardinal a cada elemento del conjunto, que se rige además por el conjunto de orden estable.

Los niños asignan un número a cada objeto desde los dos años, sin embargo cuando no dominan esta habilidad pueden equivocarse por ejemplo dejando sin contar algún objeto o por el contrario contando otros varias veces.

Principio de orden estable

La secuencia de números a utilizar ha de ser estable y estar formada por etiquetas únicas poder repetirse en cualquier momento para poder facilitar su aprendizaje a los niños. De este modo niños de muy corta edad son capaces de detectar muy fácilmente cuándo se produce una asignación completamente aleatoria en el conteo (p.e.: 2, 5, 3, 9, 24…), aunque les cuesta mayor dificultad si esta secuencia respeta un orden de menor a mayor (1, 2, 5, 6, 9, 10…). De este modo cuanto más se aleja la secuencia del orden convencional más fácil resulta detectar el error.

Este principio se consigue en torno a los 3 ó 4 años. En edades anteriores cuando los niños cuentan asignan los número arbitrariamente o empiezan a contar por cualquier número (5, 8, 2…). 425465

Principio de cardinalidad

Se refiere a la adquisición de la noción de que el último númeral del conteo es representativo del conjunto por ser cardinal del mismo. Según Gelman y Gallistel podemos decir que este principio se ha adquirido cuando observamos: que el niño repite el último elemento de la secuencia de conteo, que pone un énfasis especial en el mismo o que lo repite una vez ha finalizado la secuencia.

Según estos autores el niño logra la cardinalidad en torno a los dos años y siete meses y también según aquellos para lograr la cardinalidad es necesario haber adquirido previamente los principios de correspondencia uno a uno y orden estable. Sin embargo otros autores como Fuson ven la adquisición de la cardinalidad como un proceso más gradual en el que existe un estadio intermedio denominado cuotidad en el que el niño es capaz de responder a la pregunta de ¿cuántos elementos hay en…? pero no formulada de otra manera, como sería plantearle equivalencias entre conjuntos, por lo que para ellos este principio estaría completamente logrado en torno a los 5 años de edad.

Principios del conteo. (2008, 28) de abril. Wikipedia, La enciclopedia libre. Fecha de consulta: 03:25, octubre 15, 2008 from http://es.wikipedia.org/w/index.php?title=Principios_del_conteo&oldid=16953545.


Mis sitios nuevos:
Radio MiTecnologico Emprendedores
Politica de Privacidad