Month: noviembre 2010

Sesión correspondiente al día (23/11/2010).

Hoy hemos hecho el examen de PROLOG, esto quiere decir que ponemos fin a esta parte de practicas y a partir de ahora seguiremos con el software MAGRADA, pero eso será a partir de la póxima sesión.

Después del examen Carlos ha dejado tiempo para seguir con las distintas prácticas de PROLOG y ha subido al campus la última fase del juego que es totalmente opcional para aquellos que quieran hacerla y subir nota.

Cuando terminemos hayque pedir una tutoría para mostrar el programa a Carlos.

Y con esto y un bizcocho hasta mañana a las 8.

Hola vamos con más materia de matemáticas discreta que de discrena nada de nada

Sesión correspondiente al día (23/11/2010).

• Relación entre grados y aristas: teorema y grafo corolario

Teorema

1.Sea G = (V, A) un grafo, entonces:

Σ dG(v) = 2card(A)

Recordamos que:

-La cardinalidad es el número de elementos de un conjunto.

–d g (V):número de aristas incidentes con un vértice. Cada bucle cuenta por dos.

Σ ds(v) = Σ de(v) = card(A)

Corolario

El número de vértices de grado impar de un grafo es par.

• Caminos y conexión

Definiciones: Sea G un grafo no dirigido:

1. Una cadena es una sucesión finita W = v0e1v1….ekvk cuyos términos son alternativamente vértices y aristas.

2. La longitud de una cadena es el número de aristas que contiene.

3. Una cadena simple es una cadena con todas sus aristas distintas.

4. Un camino es una cadena con todos sus vértices distintos.

5. Una cadena cerrada es una cadena de longtud no nula en donde el vértice inicial y final coinciden.

6. Un ciclo es una cadena simple cerrada con todos sus vértices distintos.

Estos conceptos son los mismos para grafos dirigidos salvo que las direcciones de los arcos deben concordar con la dirección del camino o cadena.

En el caso dirigido el ciclo recibe el nombre de circuito.

7. Diremos que dos vértices u y v están conectados si existe un camino de u a v y viceversa.

8. Un grafo es conexo si todo par de vértices están conectados.

9. Un grafo dirigido es débilmente conexo si su grafo no dirigido asociado es conexo.

EJEMPLOS

·Cadena

·Longitud: la longitud del grafo anterior sería 2.

·Cadena simple: la siguiente sería una cadena simple.

Tenemos el siguiente grafo:

Vamos a ver las distintas propiedades y ver el tipo de grafo:

a) ¿Es dirigido?

Sí lo es, como vemos tiene arcos.

b) ¿Es simple?

Sí porque no hay ningún vértice con dos arcos de la misma dirección.

c) ¿Completo?

No es completo ya que no todos los vértices están conectados con todos.

d) ¿Bipartido?

No es bipartido pues no podemos hacer dos conjuntos en los cuales no hayan uniones entre vértices.

e) Grados

Vértice	de(v) (entrantes)	ds(v) (salientes)
V1	1	1
V2	2	3
V3	1	2
V4	1	2
V5	4	1
V6	1	1

CONEXIÓN

Conexo: un grafo es conexo si todo par de vértices está conectado.

Débilmente conexo: Cuando un grafo dirigido no es conexo se puede ver si es débilmente conexo, para ello veremos si su grafo no dirigido asociado es conexo. En el caso que lo sea se podrá decir que el grafo es débilmente conexo. El grafo asociado es el mismo grafo pero no dirigido, es decir, pierde los arcos y los sustituye por aristas.

Relación binaria: Sea G=(V,A) no dirigido. En V se define la relación binaria /R: u y v ε V, u Rv, si u y v están conectados.

R= relacionado.

R es una relación de equivalencia–> determinada partición en {V1, V2,…Vv}

A cada subgrafo de G: G[V1], G[V2]…..G[R] determinado por el conjunto de vértices de cada clase de equivalencia de la relación R se le llama componente conexa del grafo G.

Las posibles relaciones son:

Conexón u->v:

1-Reflexiva: uRv
2-Simétrica: uRv, vRu
3- Transitiva: uRv, vRt, uRt

Si un grafo no es conexo, se dividirá en subgrafos que sí lo sean y que a su vez estén conectados.

Se dividirá el grafo en componentes conexas que son los mayores subgrafos conexos de un grafo G.

Cada vértice del grafo sólo puede pertenecer a una componente conexa.

Por hoy ya esta bién mañana más, to-morrow un montón y a vivir que son two days….

Sesión correspondiente al día (16/11/2010).

Hoy hemos continuado con las fases 6 y 7. Carlos no ha avanzado dando conceptos de teoria ya que las practicas son más largas y ha dejado tiempo para que la gente se ponga al día.

Y ya esta todo la semana que viene más.

Hola buenas hoy me toca currar doble ya que he ido dejando esto para más tarde y me he juntado con que tengo que hacer 2 entradas hoy y mañana tenemos clase de mates osea que mañana me tocará hacer otra, bueno voy a ver de lo que me acuerdo ayudandome de los apuntes y a ver que sale, espero que bien jejeje.

Sesión correspondiente al día (16/11/2010).

En esta sesión hemos continuado el tema de los grafos.

• Tipos de grafos

·Grafo no dirigido asociado: es un grafo dirigido a un grafo con el mismo conjunto de vértices y en el que se han ognorado las direcciones de los vértices.

·Grafo mixto: contiene tantos arcos como aristas, es decir, contiene ambas cosas.

·Grafo simple:

1-No dirigido= sin bucles y no hay dos aristas que unan el mismo par de vértices.

2-Dirigidos= sin bucles y no hay dos arcos uniendo el mismo par de vértices y con la misma dirección.

Si un grafo no es simple se llama multigrafo.

No es simple ya que tenemos un bucle y dos aristas con la misma dirección uniendo los mismos vértices.

Este sí es simple porque aunque tiene 2 aristas, son de distinta dirección.

·Grafo no dirigido completo: si hay al menos una arista (arco) uniendo cada par de vértices distintos.

Si estos grafos son simples se denominan k_n.

-k_n= grafos completos no dirigidos y simples con “n” vértices.

Ejemplo:

• Contar aristas de un grafo

Vamos vértice a vértice uniendo con los que todavía no están unidos. Al final los sumamos.

Una vez tenemos el número de vértices y de aristas  se hace lo siguiente: (vértices * aristas)/2 = aristas del grafo completo

Para los grafos k_n hacemos |A|= (n*(n-1))/2

• Determinar el número crómatico de un grafo, grafos bipartidos y grafo k_m,n

Se parte el grafo en dos formando un grafo bipartido.

·Grafo bipartido: fromado por dos conjuntos de vértices {V1, V2}

-Los vértices de ambos conjuntos han de estar conectados entre sí pero los de V1 no lo estarán entre ellos y tampoco lo estarán los de V2.

-La unión de ambos dará el conjunto completo.

-Su intersección dará el conjunto vacío.

Ejemplo:

V1={x, t}

V2={z, y}

En este grafo es sencillo distinguir los dos grupos de vértices pero en un grafo más complejo no es tan sencillo. En estos casos debemos seguir el siguiente procedimiento:

1-Elegimos un vértice cualquiera.

2-Ponemos una etiquieta a ese vértice y una distinta para los vértices conectados a él, esta etiquieta es distinta al vértice elegido pero común para los vértices conectados a él.

Ejemplo:

En este caso hemos empezado etiquetando el vértice “2″ con un 2 y los vértices adyacentes con un “1″, después el vértice que no es adyacente lo hemos vuelto a etiquetar con un “2″ y sus adyacentes con un “1″.

Una vez hecho esto tendremos un conjunto formado por los vértices con la etiquieta “1″ y otro formado por la etiquieta “2″.

V1={0, 1, 3, 4, 6, 7}

V2={2, 5}

Ahora se sabe cuántos colores son necesarios para pintar este grafo. Con dos colores será suficiente ya que la única condición para pintarlos es que no hayan dos grafos adyacentes pintados iguales y gracias a esta distinción de conjuntos se puede cumplir dicha condición.

Para los grafos dirigidos se hará con su grafo asociado (para comprobar si es bipartido).

También se puede tener grafos bipartidos completos si cada vértice de V1 está unido con vada vértice de V2.

·k_m,n: grafo no dirigido bipartido completo y simple con card(V1)=m, card(V2)=n.

Subgrafo y grafo generador

·Subgrafo: si tenemos un grafo G= (V, A) y un grafo H=(V’, A’). H es subgrafo de G si el número de vértices y aristas de H es menor o igual al de G.

Ejemplo:

También sería un  subgrafo un único vértice (sin aristas) o el propio grafo. Si se cumple que el número de vértices del subgrafo es menor o igual al número de vértices del grafo original y que el número de aristas del subgrafo es menor o igual que el número de aristas del grafo original, entonces se trata de un subgrafo.

·Grafo generador: un subgrafo es generador si V(G)=V(H).

Todo grafo tiene un subgrafo generador simple.

Si el grafo G tiene el mismo número de vértices que el grafo H, entonces H es un subgrafo generador simple, siempre respetando el número de aristas para que sea un subgrafo, es decir, que el número de aristas de H sea menor o igual que el número de aristas de G.

H1 es un subgrafo ya que cumple todo lo comentado y además es generador porque tiene el mismo número de vértices que G1. También es simple.

• Grado de un vértice de un grafo no dirigido y de un grafo dirigido

·Grado de un vértice de un grafo no dirigido:

d_G(v): número de aristas incidentes con él (número de aristas que lo tienen como extremo). Cada bucle se cuenta dos veces.

Γ(v): conjunto de vértices adyacentes a V.

·Grado de un vértice de un grafo dirigido: Se cuentan arcos de entrada y salida y el grado total es la suma de ambos.

Y hasta aqui vimos ahora voy con lo de la siguiente semana!!!

Sesión correspondiente al día (09/11/2010).

En la sesión de hoy hemos empezado la fase 6 de la aplicación, para poder realizarla Carlos nos ha explicado lo que es un bucle repeat-until.

REPEAT

Es un predicado que siempre tiene éxito y, además, obliga a PROLOG a reevaluar a partir de donde está, en adelante. Esto significa que, si alguno de los objetivos siguientes a repeat fracasa, es seguro que, como mínimo, PROLOG continuará la ejecución a partir del repeat.

Objetivos, éxito, fracaso y reevaluación

El mecanismo de proceso de PROLOG está basado en objetivos. Cada nueva cláusula que PROLOG encuentra en su proceso de ejecución es para él un objetivo que debe tratar de cumplir.

Por ejemplo si ponemos:

?-ubicacion(jugador).

El objetivo será encontrar el hecho ubicacion(jugador), que podrá tener éxito o fracaso, dependiendo de si lo encuentra o no lo encuentra respectivamente.

El propósito de la reevaluación es el de encontrar una solución distinta a la que ya se haya encontrado en las anteriores evaluaciones del objetivo. De esta forma, lo que hace PROLOG no es otra cosa que navegar entre todas las posibilidades de solución de nuestra Base de Conocimientos, hasta encontrar alguna que satisfaga (que haga tener éxito) a los dos objetivos a la vez. Esto mismo es aplicable a más de 2 objetivos.

Hasta la próxima….

Entrada de la sesion correspondiente a (09/11/2010)

• Deducción natural: a partir de unas premisas y una conclusión había que averiguar si esa conclusión era cierta. Esto se deducía haciendo suposiciones y utilizando las reglas de inferencia.

Ejemplos:

• PRIMERO

Premisas: ja → v , v→ma Conclusión: ja →ma

-1 ja → v

-2 v →ma

3 ja Suponemos que ja es cierta

4 v De lo anterior se deduce v , se utiliza la regla MP en las proposiciones 1 y 3

5 ma MP de 2,4

6 ja →ma Se hace la TD de 3-5

De 3 a 5, hay una subdeducción que debe ir en un corchete, yo la he puesto en negrita.

• SEGUNDO

Premisas: at→ so v in, in →¬ju   Conclusión: at→ (¬so→ ¬ju)

-1 at→ so v in

-2 in →¬ju

3 at

4 ¬so

5 so v in   MP 1,3

6 in           SD 4,5

7 ¬ju        MP 2,6

8 ¬so→ ¬ju      TD 4,7

9 at→ (¬so→ ¬ju)

• TERCERO ( Utilización la reducción al absurdo)

Premisas: A → C ^P , V, P → ¬V     Conclusión:   ¬A

Consiste en comenzar la deducción suponiendo como cierto lo contrario de la conclusión, en este caso: A

-1 A → C ^P

-2 V

-3 P → ¬V

4  A

5 C ^P        MP 1,4

6 P               EC 5

7 ¬V            MP 3,6

8 V^¬V     IC 2,7

9 ¬A             IN (Abs) 4-8

• Matemática discreta

– Fundamentos de grafos

Un grafo es una estructura discreta formada por vértices y aristas. Según se conecten los vértices tenemos distintos tipos de grafos: dirigidos y no dirigidos.

No dirigidos – Ambos sentidos son correctos o posibles.

Dirigidos – Se indican los sentidos posibles.

No dirigido: tiene un par (V, A) donde:

V= {V₁,…V_n} conjunto de vértices

A= {e₁,…e_m} es una familia de pares no ordenados de vértices, que llamaremos aristas, cada e_k ={V_i, V_j} con V_i, V_j pertenecientes a V.

Los vértices V_i, V_j son extremos de la arista e_k .

Familia quiere decir que puede haber más de una arista uniendo el mismo par de vértices.

Ejemplo de grafo no dirigido:

Dirigido: Si las aristas tienen una dirección o sentido son grafos dirigidos.

V= {V₁,…V_n} conjunto de vértices

A= {e₁,…e_m} es una familia de pares ordenados de vértices, que llamaremos arcos, cada e_k ={V_i, V_j} con V_i, V_j pertenecientes a V.

Los vértices V_i, V_j son extremos de la arista e_k .

Ejemplo de grafo dirigido:

En este caso el orden de los vértices en los arcos no es indiferente, hay que poner primero el vértice saliente y después el entrante.

Los extremos de una arista pueden tener vértices incidentes, adyacentes o formando un bucle.

Los extremos de una arista (arco) son incidentes.

Los vértices conectados por una misma arista (arco) son adyacentes.

Un vértice unido consigo mismo es un bucle.

La próxima sesión más cosas….

Sesión correspondiente al mismo dia de teria (02/11/2010).

Hoy hemos seguido con el proyecto y Carlos no ha avanzado en la teoría. De esta manera la gente atrasada se puede poner al dia y preguntar dudas.

Hasta la próxima….

Entrada de la sesion correspondiente a (01/11/2010)

En esta sesión vimos lo siguiente:

• Regla de resolución proposicional para descubrir si un razonamiento es o no correcto

Continuando con lo visto en la anterior sesión se explicará como se debe aplicar la regla de resolución proposicional para ver si un razonamiento es correcto o no.

Una vez se tenga la forma clausal de la fórmula  se debe buscar contradicciones de literales, es decir, una cláusla X y una cláusula Y que tengan “literal” y “¬literal” respectivamente. Una vez se sabe esto se procede a ir eliminando estos literales contradictorios de tal forma que al final se obtenga una cláusula resolvente, con esta cláusula se sabe si el razonamiento es correcto o si no lo es.

A continuación vimos una serie de ejemplos que los podemos encontrar en los apuntes de clase

• Demostración por deducción natural

El objetivo es demostrar la validez de un razonamiento, es decir de comprobar que una conclusión “Q” se obtiene de un conjunto de premisas Pi mediante la aplicación de un conjunto de reglas de inferencia del sistema a dicho conjunto de premisas.

El objetivo de este tipo de deducción es el de obtener, de forma sistemática, todas las conclusiones que se deducen de un conjunto de premisas usando reglas de inferencia para determinar la validez del razonamiento.

– Subdeducciones

Uno de los aspectos cruciales de la deducción natural son las subdeducciones. En cualquier paso de nuestra deducción podemos introducir un supuesto provisional que debe ser cancelado en alguna línea posterior. Desde el supuesto hasta la cancelación tendremos una subdeducción. Para poder finalizar una demostración deberemos haber cancelado todos los supuestos que hayamos hecho.Los supuestos provisionales son una herramienta muy potente ya que nos permiten suponer lo que nosotros queramos. Pero para poder finalizar una demostración deberemos haber cancelado todos los supuestos que hayamos hecho. Por tanto, la cancelación de supuestos provisionales se convierte en una pieza clave de las deducciones naturales.

Cuando un supuesto es cancelado las fórmulas interiores son inaccesibles. La utilización de subdeducciones nos permite “modularizar” nuestras deducciones, planteándonos subobjetivos más sencillos que el objetivo final y que en su conjunto nos lleven a la conclusión que buscamos. Una vez realizada una subdeducción, esta podría considerarse como una regla derivada y utilizarse a partir de ese momento. Estas reglas derivadas permiten ir incrementando nuestro sistema de reglas.

–Componentes de una deducción

En una deducción tenemos una secuencia finita de fórmulas tales que cada una de ellas puede ser:

1.- Supuesto inicial o premisa.

2.- Supuesto provisional

3.- Una fórmula que se deriva lógicamente de otra (s) por inferencia inmediata.

1.- Supuestos iniciales o premisas: son fórmulas que se consideran hipotéticamente dadas desde el principio de la deducción. Los argumentos pueden tener un número finito de premisas. También hay deducciones que están exentas de premisas como es el caso de las demostraciones.

2.- Subdeducciones: son líneas que se introducen provisionalmente en el transcurso de la prueba y deberán ser canceladas antes del establecimiento de la conclusión. Es importante que se entienda bien el proceso de cancelación para que pueda ser usado adecuadamente, ya que si no tenemos cuidado podemos demostrar conclusiones que no se siguen de las premisas dadas.

3.- Líneas que proceden de otra(s) anterior(es) por aplicación de una regla de inferencia: a estas líneas las llamamos consecuencias lógicas inmediatas de otra(s) anterior(es). Llamamos inferencia inmediata a la obtención de una fórmula a partir de otra(s) por la aplicación de una sola regla de inferencia.

Las reglas de inferencia son unas fórmulas ya definidas y las podéis encontrar aquí:

Hoja de las reglas de inferencia

Seguidamente a esto vimos numerosos ejemplos que los podemos encontrar en los apuntes de clase de cada uno.

Para terminar la sesion falta comentar:

Demostración por el método directo:

Se utiliza para demostrar la verdad de una fórmula condicional. Para ello se asume que es cierto el antecedente. El método se aplica cuando se quiere deducir una fórmula condicional X → Y. Proceso deductivo del método directo:

1. Se añade a las líneas de deducción una premisa auxiliar que será la fórmula X.
2. Esta premisa X abre una subdeducción dentro de la deducción en la que se encuentra.
3. A partir de ella se construye una argumentación en la cual podemos utilizar fórmulas anteriores que aparezcan en la deducción y reglas de inferencia hasta obtener la fórmula Y.
4. En este punto se concluye la prueba y queda establecida la validez de X → Y.

Demostración por el método de reducción al absurdo:

En una demostración aparece una contradicción cuando se deduce una fórmula y su negada. El método de reducción al absurdo se fundamenta en la estrategia que consiste en suponer explícitamente la negación de la proposición a demostrar, a partir de esta hipótesis, se trata de generar una contradicción. Si aparece dicha contradicción, es que la suposición es errónea.

Y hasta aqui poudo contar, la siguiente sesion más.