www.tic2.org/WebTecnica

Conjunto

Reunión de elementos. Si el conjunto es infinito no puede definirse por enumeración, ya que es infinito. Por ello debe definirse por extensión.

Números naturales = (1, 2, 3, 4 ...)

Colores = (Negro, Rojo ...)

Constante

Elemento de un conjunto.

Variable

Es un 'almacen' donde que puede contener cualquier valor de un conjunto. En un programa, define una zona de memoria.

Producto cartesiano

Todos los pares ordenados posibles con los elementos de dos conjuntos.

Ej: Teniendo un conjunto A y otro B, el producto cartesiano AxB =

Mapeo

Correspondencia entre dos conjuntos.

Ejemplo: mapeo del conjunto cartesiano de los conjuntos A (A1, A2 y A3) y B (B1, B2 y B3) con el grupo N

AxB -> N

Los elementos del conjunto N = A1B1, A1B2 ... A3B3

Función

Correspondencia de un elemento de un conjunto (Dominio) a un único elemento de otro conjunto (imagen).

f: A->B ó y = f(x) siendo x Î A, x Î B

Ej: 3 + 5 = 8

Las funciones más importantes en informática son: crear, destruir, obtener propiedad de objeto y modificar propiedad de objeto.

Función compuesta

Función compuesta de otras funciones (en secuencia, no de manera anidada).

Grafo de una función

Es la representación gráfica de dicha función.

Relación

Relación R entre A y B en R = (A,B,P(x,y))

Puede darse entre:

• Elementos de conjuntos distintos.
• Elementos del mismo conjunto.
• Un elemento consigo mismo.

Haciendo un símil con el lenguaje escrito, mediante las conjunciones hacemos relaciones de composición en el lenguaje.

Las relaciones pueden ser de:

• Equivalencia. Permite hacer clasificaciones. Ej: Tener la misma altura. Es una relación:
  • Reflexiva
  • Transitiva
  • Simétrica
• Orden.
  • Tipos
    • Total. Ej: en programas, los concurrentes no lo son.
    • Parcial. Solo están ordenados algunos elementos. Ej: programas concurrentes.
  • Es una relación:
    • Reflexiva
    • Transitiva
    • Simétrica

Proposición

'Frase que afirma algo'.

Ej: Cervantes escribió el Quijote

Añadiendo detrás si dicha proposición es verdadera o falsa obtenemos un predicado.

Predicado

Es una proposición a la que se le añade si es verdera o falsa.

Ej:'Cervantes escribió el Quijote' es verdadero

Algebra

Si sobre un conjunto definimos operaciones (o funciones) y ecuaciones tenemos un álgebra.

Álgebra = elementos + operaciones (suma, resta...) + ecuaciones (reglas, propiedades o leyes)

Álgebra de proposiciones:

• Aserción o enunciado simple: p <el sol brilla>
• Predicado. p<el sol brilla> = Verdadero
• Enunciado compuesto. Son las operaciones entre proposiciones, osea, las operaciones lógicas p<el sol brilla> y q<hace calor> r = p ^ q

Organigramas

Se usan para describir una secuencia de acciones. Hacen énfasis en decisiones y acciones. Usan símbolos básicos, de decisión, etc.

Diagramas de estado

Los estados los definen atributos y las transiciones son definiciones por acciones. Hace énfasis en los estados.

Árboles organizativos

Ponen de manifiesto las relaciones: de orden, etc.

Diagramas PER

Son los que aparecen, por ejemplo, en las aplicaciones de diseño de proyectos. Ej: si en un proyecto de obra los albañiles deben haber terminado la estructura de la casa antes de que entren los fontaneros, debemos sincronizar a ambos para que los últimos no entren antes de que hayan concluido su trabajo los primeros.

Grafos

Han sido simplificados en gráficos.

Ruta

Camino o ruta es la secuencia finita y no vacía de arcos. (Ej: ruta a un archivo).

Nodo terminal

Nodo que no tiene hijos.

Grafo etiquetado

Un grafo etiquetado finito (digrafo) etiquetado se define como la tupla G = <N,A,E,F>, donde:

• N. Conjunto finito de nodos.
• A. Conjunto de pares o arcos ordenados (incluidos en el producto cartesiano, y no mayor que este).
• E. Conjunto finito no vacio de etiquetas (son dirigidas, van en un sentido). Las relaciones pueden ser bidireccionales.
• F. Función (1, 2, 3... h) en E.
  • f(i) es la etiqueta de (ni, nj)

Grafo dual

Aquel en el que pueden cambiarse arcos por nodos y viceversa sin que ocurra nada.

Autómata finito

Defino estados y transiciones. El número de estados es finito. Son similares a los diagramas de estado.

M sobre alfabeto A. M = (S,A,m,si,F), donde:

• S. Conjunto no vacio de estados.
• A. Alfabeto finito de estados.
• m. Mapeo de SxA en S (define la transición).
• si. Estado inicial.
• F. Conjunto de finales.

Redes de Petri

Es una tupla que se compone de R = <P,T,e,s>, donde:

• P. Conjunto finito y no vacio de lugares (nodos).
• T. Conjunto finito y no vacio de transiciones.
• P n T = 0. Es decir, que una transición no puede ser un nodo y viceversa.
• P x T -> N (Arco de entrada a las transiciones).
  
• T x P -> N (Arco de salida a las transiciones).
  

Marcaje de una Red de Petri

<R, M0> El marcaje de la red se compone por uno o más tokens o marcas en los nodos.

El marcado de la red que se ve a la izquierda es:
M = (1, 0, 1) donde M = (P1, P2, P3)

Red simple

Tiene arcos de salida de lugares con valor 1 y de entrada con valor -1.

Red no simple

En una red no simple, una transición está cargada cuando los lugares tengan al menos las marcas que indica su arco.

Red dual

De manera equivalente a como ocurría con los grafos duales, una red dual es aquella en la cual los lugares pueden cambiarse por transiciones y viceversa.

Red inversa

La que se obtiene al cambiar el sentido de las flechas.

Transición cargada

Una transición está cargada cuando todos los lugares de entrada tienen al menos una marca (al menos el valor absoluto del arco).

Regla de disparo

Si la transición de T1 está cargada, la regla de disparo es: de los lugares de entrada les restamos tantas marcas como indica su arco de entrada, y a los lugares de salida les ponemos tantas marcas como indica su arco de salida.

Veamos un ejemplo de red de Petri, y como evoluciona al ir realizando disparos consecutivos. M0 sería el estado inicial, y M2 el final (en el cual se produce un bloqueo).

Bloqueo

Un bloqueo supone que ya no se puede ejecutar otra transición en la red. Pueden ser buscados o no buscados. Ej: la inicialización de una aplicación es deseable que solo se ejecute una vez, así que tras la primera inicialización suele provocarse su bloqueo.

Un bucle infinito también se considera un bloqueo.

Obtener un diagrama de estado/transición a partir de una red de Petri

Concurrencia en Redes de Petri

Veamos un ejemplo de red de Petri en secuencia:

A continuación veamos un ejemplo (que se lee de izquierda a derecha) de red donde existe concurrencia. Se dice que existe concurrencia porque podría dispararse tanto T1 como T2. Da igual el orden en el que se efectúa el disparo, porque el resultado final siempre será el mismo.

Ejemplo: Enviador-Receptor

La red de Petri del ejemplo, modela el envío de un correo electrónico desde un emisor a un receptor. Este ejemplo nos permite ver los distintos estados y analizar si se bloqueará la comunicación.

En el ejemplo se muestra un proceso Enviador, que envía mensajes (marca), a un proceso Receptor. Como la velocidad de operación de estos procesos puede ser distinta, se sincronizan a través de un proceso Buffer. Si las velocidades de disparo son distintas, el más rápido deberá esperar al más lento.

Veamos el ejemplo para entenderlo mejor. A continuación podemos ver:

El emisor, antes de enviar el correo, debe escribirlo. Por otra parte, el receptor, antes de leer un correo ha de recibirlo. Cada lugar puede almacenar, como máximo un token.

Si el emisor escribiera y enviara correos más rápido de lo que el receptor puede recibirlos y leerlos el canal de comunicación se saturaría. Este diagrama no sería muy eficaz, ya que en el punto *1 puede desbordarse. Dichos lugares se llaman unbounded. Los lugares marcados como *2 no lo serían.

Veamos ahora un ejemplo similar al anterior, pero en el que se ha incluido un servidor de correo.Para que el servidor acepte el correo procedente del emisor, debe tener el canal vacío, ya que si está lleno el emisor no puede enviarle otro. El emisor y el receptor trabajan en concurrencia. Sin embargo, el emisor y el servidor de correo trabajan en secuencia, y el receptor con el servidor de correo también.

La sincronización impone una secuenciación. En esta red no hay lugares unbounded.

En el siguiente ejemplo, tanto el canal ocupado como el vacío puede albergar, cada uno, tres tokens, en lugar de un token (como ocurría en los ejemplos anteriores).

Tipos de lenguaje

Los tipos de lenguajes más habituales son:

• Natural. El que usamos para hablar, escribir, etc.
• de requisitos. Utilizado para la especificación de requisitos.
• de especificación. Para realizar especificaciones.
• de diseño. Usado en diseño.
• de pruebas.
• de programación.

Alfabeto o vocabulario

Conjunto finito de símbolos usados en el lenguaje.

Sentencia

Cualquier cadena de longitud finita compuesta de símbolos de un alfabeto.

Lenguaje

Es el conjunto de sentencias creadas a partir de un alfabeto.

Metalenguaje

Lenguaje utilizado para utilizar otro lenguaje.

Ej: XML

BNF

Es un metalenguaje, que se compone de:

Ej: <Oración> :: <Sujeto> <Verbo> <Complementos>

Se leería: Una Oración se define como un Sujeto seguido de un Verbo y seguido de Complementos.

Gramática

La gramática, formulada matemáticamente sería:

G = (Vn, Vt, P, S)

Donde:

• Vn. Variables o no terminales.
• Vt. Terminales. Son los tokens e identificadores. Son palabras reservadas del lenguaje. Ej: en programación suelen ser las palabras IF, THEN, ELSE, etc.
  Ej2: en el lenguaje natural suelen serlo las preposiciones, los artículos, etc.
• S. Símbolos de comienzo.
• P. Producciones. Son relaciones entre varias cadenas de variables y terminales. Ej: frase.

Scanner

Es un programa que analiza el léxico (palabras). Reconoce los delimitadores. Ej: Lex de Unix.