Estructuras de objetos discretos para la computación (página 3)

Teoría básica de los semigrupos y grupos                                                             

    4.1 Operaciones binarias sobre un grupo

          4.1.1 Definiciones

Se define como operación binaria un procedimiento entre dos o más variables en base 2 (o también llamado en módulo 2). Desde el punto de vista de la informática, estas operaciones aunque son puramente matemáticas, ocupan un gran rol en el funcionamiento de la computadora. Esta es la razón por la que se encuentran muchas veces en los microprocesadores y más específicamente en las ALU (Unidades Aritmético Lógicas).

          4.1.2 Propiedades de las operaciones binarias

    4.2 Semigrupos

          4.2.1 Definiciones

Un semigrupo es una estructura algebraica de la forma (A,+) donde + es una operación binaria y asociativa. (Si además + es una op. conmutativa, se dice que es un semigrupo conmutativo).

          4.2.2 Teorema de los semigrupos

          4.2.3 Producto y cociente de los semigrupos

    4.3 Grupos

             4.3.1 Definiciones

Un grupo es un magma (un conjunto, con una operación binaria), que satisface ciertos axiomas, detallados abajo. La rama de la matemática que estudia los grupos es llamada teoría de grupos.

          4.3.2 Teoremas de los grupos

      4.3.3 Productos y cocientes de los grupos

ciencias de la computación

    5.1 Proposiciones y operaciones lógicas

También llamadas Operaciones Booleanas en mención al Álgebra de Boole, estas son usualmente:

AND

Resumiendo, el resultado siempre dará 0 a menos que ambas variables valgan 1. (Equivale a la multiplicación)

OR

Resumiendo, el resultado arrojado será siempre 1 si al menos una de las variables tiene por valor 1.

NOT

El not es una inversión del valor como se ve. (Equivale a restar el valor inicial de 1)

A nivel de hardware existen circuitos lógicos que representan cada una de las operaciones como puertas lógicas.

    5.2 Proposiciones condicionales

    5.3 Métodos de demostración

                             5.3.1 Modus Ponens – método de afirmación

(Latín: modo que afirmando afirma) es una regla de inferencia simple:

Si P entonces Q.

P.

Entonces, Q.

Expresado en la notación de operadores lógicos:

donde representa la aserción lógica.

También se puede expresar de la siguiente forma:

             5.3.2 Modus Tollens – método de refutación

 (del latín, modo que negando niega), también llamado razonamiento indirecto. En lógica, es el nombre formal para la prueba indirecta o inferencia contrapositiva. Usualmente se lo abrevia como "MTT".

La tautología Modus Tollens toma las siguientes formas de ley lógica:

Si P, entonces Q.

Q es falso.

Entonces P es falso.

En una notación diferente, utilizando operadores lógicos:

O también:

∴

donde representa la aserción lógica.

Un posible ejemplo es:

Si llueve voy al cine

No fui al cine

Por lo tanto, no llovió

Expresado según la Teoría de conjuntos:

∴

Lo anterior se lee: "P es un subconjunto de Q. x no pertenece a Q. Por lo tanto, x no pertenece a P."

El argumento tiene dos premisas. La primera es el condicional "P implica Q". La segunda premisa indica que Q es falsa. De estas dos premisas se deduce la conclusión de que P debe ser falsa. Si P fuera verdadera, entonces Q lo sería, por la primera premisa, pero no lo es, por la segunda.

El silogismo Modus tollendo tollens llegó a ser algo famoso cuando fue utilizado por Karl Popper en su respuesta al problema de inducción, Falsacionismo.

 5.3.3 Demostración por contradicción

Es un método de demostración (a menudo usado por Aristóteles como un argumento lógico) en el que asumimos una hipótesis y obtenemos un resultado absurdo, por lo que concluimos que la hipótesis de partida ha de ser falsa. Parte de la base del cumplimiento de la ley de exclusión de intermedios: una afirmación que no puede ser falsa, ha de ser consecuentemente verdadera.

VI. Introducción a los autómatas finitos

   6.1 Análisis léxico

Formalmente, un autómata finito (AF) puede ser descrito como una 5-tupla (S,Σ,T,s,A) donde:

• S un conjunto de estados;
• Σ es un alfabeto;
• T es la función de transición: ;
• es el estado inicial;
• es un conjunto de estados de aceptación o finales.

     6.2 Autómatas finitos deterministas

Un AFD o autómata finito determinista es aquel autómata finito cuyo estado de llegada está unívocamente determinado por el estado inicial y el carácter leído por el autómata.

Formalmente, un autómata finito determinista (AFD) es similar a un Autómata de estados finitos, representado con una 5-tupla (S,Σ,T,s,A) donde:

• Σ es un alfabeto;
• S un conjunto de estados;
• T es la función de transición: ;
• es el estado inicial;
• es un conjunto de estados de aceptación o finales.

Al contrario de la definición de autómata finito, este es un caso particular donde no se permiten transiciones lambda (vacías), el dominio de la función T es S (con lo cual no se permiten transiciones desde un estado de un mismo símbolo a varios estados).

A partir de este autómata finito es posible hallar la expresión regular resolviendo un sistema de ecuaciones.

S1 = 1 S1 + 0 S2 + ε

S2 = 1 S2 + 0 S1

Siendo ε la palabra nula. Resolviendo el sistema y haciendo uso de las reducciones apropiadas se obtiene la siguiente expresión regular: 1*(01*01*)*.

Inversamente, dada la expresión regular es posible generar un autómata que reconozca el lenguaje en cuestión utilizando el algoritmo de Thompson, desarrollado por Ken Thompson, uno de los principales creadores de UNIX, junto con Dennis Ritchie.

Un tipo de autómatas finitos deterministas interesantes son los tries.

     6.3 Autómatas finitos no deterministas

Un AFND o autómata finito no determinista es aquel que presenta cero, una o más transiciones por el mismo carácter del alfabeto .

Un autómata finito no determinista también puede o no tener más de un nodo inicial.

Los AFND también se representan formalmente como tuplas de 5 elementos (S,Σ,T,s,A). La única diferencia respecto al AFD es T.

AFD:

AFND: (partes de S)

Debido a que la función de transición lleva a un conjunto de estados, el automáta puede estar en varios estados a la vez (o en ninguno si se trata del conjunto vacío de estados).

Hiper-cubo binario de dimensión cuatro

Si queremos detectar d bit erróneos en una palabra de n bits, podemos añadir a cada palabra de n bits d+1 bits predeterminados al final, de forma que quede una palabra de n+d+1 bits con una distancia mínima de Hamming de d+1. De esta manera, si uno recibe una palabra de n+d+1 bits que no encaja con ninguna palabra del código (con una distancia de Hamming x <= d+1 la palabra no pertenece al código) detecta correctamente si es una palabra errónea. Aún más, d o menos errores nunca se convertirán en una palabra válida debido a que la distancia de Hamming entre cada palabra válida es de al menos d+1, y tales errores conducen solamente a las palabras inválidas que se detectan correctamente. Dado un conjunto de m*n bits, podemos detectar x <= d bits errores correctamente usando el mismo método en todas las palabras de n bits. De hecho, podemos detectar un máximo de m*d errores si todas las palabras de n bits son transmitidas con un máximo de d errores.

Ejemplo:

Palabras a enviar:

1: 000001

2: 000001

3: 000010

 

Codificadas con distancia mínima de Hamming = 2:

000001 0000

000001 0011

000010 1100

 

Si las palabras recibidas tienen una distancia de Hamming < 2

Son palabras incorrectas

 

 

Dankiel

dankiel23_12[arroba]hotmail.com

 

Partes: 1, 2, 3