Imagina un conjunto de rectángulos 2D de diferentes tamaños; asumamos por el bien de
La simplicidad de que no hay dos rectángulos en este conjunto tiene exactamente del mismo tamaño.
Aquí hay un conjunto de muestra:
Diremos que la caja X encaja dentro de la caja Y si pudiéramos encerrar físicamente a X
dentro de Y; en otras palabras, si las dimensiones de Y son mayores que las de X. En esto
Ejemplo:
- La casilla A puede caber dentro de la caja B, pero no al revés
- E puede caber dentro de todas las demás cajas, pero ninguna otra caja puede caber dentro de ella
- A, B, D, E puede caber dentro de C, que no puede caber en ninguna de las otras casillas
- D no puede caber dentro de A o B; ni A ni B pueden encajar dentro de D
Como veremos pronto, en este caso "encaja" es una orden parcial en un conjunto de
Cajas rectangulares 2D, porque aunque podemos ordenar algunas de las cajas
entre sí, algunos otros pares de cajas no tienen un orden relativo entre
ellos mismos (por ejemplo, A y D).
Si todos los pares de cajas en este conjunto tenían un orden relativo, por ejemplo, considere
el conjunto sin el recuadro D: podríamos definir un pedido total en el conjunto. Otro
ejemplo de esto es un conjunto de cuadrados 2D (en lugar de rectángulos); tan largo
Como todos los cuadrados del conjunto tienen tamaños únicos, siempre podemos definir un
orden total en ellos porque para cualquier par de cuadrados, ya sea el primero puede caber
la segunda, o viceversa.
Definición matemática de las relaciones
Para desarrollar un enfoque matemáticamente sólido para ordenar, tendremos que sumergir nuestra
pies en la teoría de conjuntos y relaciones . Solo estaremos hablando de binario.
relaciones aquí.
Dado un conjunto A, una relación en A es un conjunto de pares con elementos tomados de A.
Un poco más riguroso, dado que es el conjunto que contiene todos
posibles pares ordenados tomados de A (a.k.a. el cartesiano producto de A), luego
R es una relación en A si es un subconjunto de, o.
Por ejemplo, dado el conjunto, entonces:
Tenga en cuenta que definimos explícitamente los pares a ser ordenados lo que significa que (1, 2)
y (2,1) son dos elementos distintos en este conjunto.
Por definición, cualquier subconjunto de es una relación en A. Por ejemplo
. En
programación, a menudo usamos el término predicado para expresar una idea similar. UNA
predicado es una función con un resultado binario, y la correspondencia a
Las relaciones son triviales, solo decimos que todos los pares que pertenecen a la relación
Satisfacer el predicado, y viceversa. Si definimos un predicado R (x, y) para
sea verdadero si y solo si x == y obtendríamos la relación anterior.
Una notación de método abreviado que hará que las definiciones sean más claras: decimos cuándo
. En nuestro conjunto de ejemplos 1R1, 2R2 y 3R3. Esta
la notación es un poco incómoda, pero es el estándar aceptado en matemáticas; por lo tanto estoy
usándolo por coherencia con otras fuentes.
Además, se vuelve más agradable cuando R es un operador. Si redefinimos R como == es
se vuelve más natural: 1 == 1 2 == 2 3 == 3 . La relación de igualdad es
una relación perfectamente válida en un conjunto – sus elementos son todos los pares donde ambos
los miembros tienen el mismo valor.
Propiedades de las relaciones
Hay una serie de propiedades útiles que podrían tener las relaciones. Aquí están
sólo unos pocos que necesitaremos para el resto del artículo; para una lista más larga,
consulte la página de Wikipedia .
Reflexiva : cada elemento del conjunto está relacionado con sí mismo, o
. La relación == que se muestra arriba es
reflexivo.
Irreflexivo : ningún elemento del conjunto está relacionado con sí mismo, o
. Por ejemplo, si definimos la < menos que
relación con los números, es irreflexivo ya que ningún número es menor que sí mismo.
En nuestro ejemplo de cajas, la relación "encaja" es irreflexiva porque ninguna caja puede
encaja dentro de sí mismo.
Transitivo : intuitivamente, "si x encaja dentro de y e e encaja dentro de z, entonces x
encaja dentro de z ". matemáticamente
.
La relación < en los números es obviamente transitiva.
Simétrica : si x está relacionada con y, entonces y está relacionada con x. Esto puede sonar
obvio con el significado coloquial de "relacionado", pero no en el matemático
sentido. La mayoría de las relaciones con las que tratamos no son simétricas. La definicion es
. Por ejemplo, la relación ==
es simétrico, pero < no es simétrico.
Antisimétrico : si x está relacionado con y, entonces y es no relacionado con x a menos que
xey son el mismo elemento; matemáticamente
.
Por ejemplo, la relación (menor o igual) es antisimétrica;
Si y también entonces debe ser que X e Y son
el mismo numero. La relación < también es antisimétrica, aunque en el vacío
sentido porque no podremos encontrar ningún par x e y para satisfacer a la izquierda
lado de la definición; en lógica, esto se llama vacuamente .
Orden parcial
Hay dos tipos de órdenes parciales que podemos definir – débil y fuerte . los
La orden parcial débil es la más común, así que comencemos con eso. Cuando
Estoy diciendo solo "orden parcial", significaré un orden parcial débil.
Un orden parcial débil (también conocido como no estricto ) es una relación en un conjunto Una que es
Reflexivo, transitivo y antisimétrico. La relación en números es
un ejemplo clásico:
- Es reflexivo porque para cualquier número x tenemos
- Es transitivo porque dado y, sabemos que
- Es antisimétrico porque dado y, sabemos
que xey son el mismo número
A orden parcial fuerte (a.k.a. estricta ) es una relación en un conjunto A que es
De carácter irreflexivo, transitivo y antisimétrico. La diferencia entre débil y
órdenes parciales fuertes es la reflexividad. En órdenes parciales débiles,
cada elemento está relacionado consigo mismo; en fuertes órdenes parciales, ningún elemento es
Relacionado consigo mismo. El operador <en números es un ejemplo de estricto
Orden parcial, ya que satisface todas las propiedades; mientras es
reflexivo, <es irreflexivo.
Nuestras cajas rectantulares con la relación de "ajustes" son un buen ejemplo para distinguir
entre los dos. Solo podemos definir una orden parcial fuerte porque
una caja no puede caber dentro de sí misma.
Otro buen ejemplo es una rutina matutina. El conjunto de ropa para vestir.
es {ropa interior, pantalones, chaqueta, camisa, calcetín izquierdo, calcetín derecho, zapato izquierdo, derecho
zapato}, y la relación es "tiene que ser usada antes". El siguiente dibujo
codifica la relación:
Este tipo de dibujo se llama un Diagrama de Hasse que es útil gráficamente
representar conjuntos parcialmente ordenados; La flecha representa la relación. por
Por ejemplo, la flecha de "pantalones" a "zapato izquierdo" codifica que los pantalones deben estar
usado antes del zapato izquierdo.
Tenga en cuenta que esta relación es irreflexiva, porque no tiene sentido decir que
"Los pantalones deben ser usados antes de usar pantalones". Por lo tanto, la relación define.
un orden fuerte parcial en el set.
De manera similar al ejemplo de cajas rectangulares, el orden parcial aquí nos permite ordenar
sólo algunos de los elementos en el conjunto w.r.t. El uno al otro. Algunos elementos como
los calcetines y una camisa no tienen un pedido definido.
Pedido total
Un pedido total es un pedido parcial que tiene una propiedad adicional: dos en total
Los elementos del conjunto deben estar relacionados. Matemáticamente:
Mientras que una orden parcial nos permite ordenar algunos elementos en un conjunto w.r.t. El uno al otro,
el orden total requiere que podamos ordenar todos los elementos en un conjunto. En el
Ejemplo de cajas, no podemos definir un orden total para cajas rectangulares (hay
no la relación "encaja" entre las casillas A y D, no importa de qué manera lo intentemos).
Nosotros podemos definir un orden total entre casillas cuadradas, sin embargo, siempre que su
los tamaños son únicos.
Tampoco podemos definir un orden total para el diagrama de preparación que se muestra arriba,
porque no podemos decir "los calcetines izquierdos deben usarse antes de las camisas" o
"las camisas deben usarse antes de los calcetines izquierdos".
Ejemplos de programación
Los pedidos parciales y totales frecuentemente aparecen en la programación, especialmente cuando
pensando en cosas Ordenar una matriz usualmente implica encontrar algunos
orden total en sus elementos. Romper el empate es importante, pero no siempre
posible. Si no hay manera de distinguir dos elementos, no podemos
matemáticamente llegar a un orden total, pero todavía podemos ordenar (y tenemos
un orden parcial débil). Aquí es donde la distinción entre regular y estable
viene .
A veces estamos clasificando estructuras no lineales, como los gráficos de dependencia en el
Ejemplo de vestir desde arriba. En estos casos un orden total es imposible, pero nosotros
tiene un pedido parcial que puede ser útil para encontrar un pedido de vendaje "válido" – un
Secuencia lineal de pasos de aderezo que no violarían ninguna restricción. Esta
se puede hacer con clasificación topológica
que encuentra una "linealización" válida del gráfico de dependencia.
No comments:
Post a Comment