IV. 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

 

V. Razonamiento lógico en las 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.

S₁ = 1 S₁ + 0 S₂ + ε

S₂ = 1 S₂ + 0 S₁

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).

 

VII. Teoría de la codificación

      7.1 Codificación de información binaria

La codificación de caracteres es el método que permite convertir un carácter de un lenguaje natural (alfabeto o silabario) en un símbolo en otro sistema de representación, como un número o una secuencia de pulsos eléctricos en un sistema electrónico, aplicando normas o reglas de codificación.

La codificación de información binaria se trata de convertir caracteres de formato digital o binario ( 1 y 0) a información que puede ser usada por un usuario u otra aplicación de la computadora o externa.

Definen la forma en la que se codifica un carácter dado en un símbolo en otro sistema de representación. Ejemplos de esto son el código Morse, la norma ASCII o la UTF-8, entre otros.

ASCII

Por estar íntimamente ligado al octeto (y por consiguiente a los enteros que van del 0 al 127, el problema que presenta es que no puede codificar más que 128 símbolos diferentes (128 es el número total de diferentes configuraciones que se pueden conseguir con 7 dígitos binarios o digitales (0000000, 0000001, ..., 1111111), usando el octavo dígito de cada octeto (bit o dígito de paridad) para detectar algún error de transmisión). Un cupo de 128 es suficiente para incluir mayúsculas y minúsculas del abecedario inglés, además de cifras, puntuación, y algunos "caracteres de control" (por ejemplo, uno que instruye a una impresora que pase a la hoja siguiente), pero el ASCII no incluye ni los caracteres acentuados ni el comienzo de interrogación que se usa en castellano, ni tantos otros símbolos (matemáticos, letras griegas,...) que son necesarios en muchos contextos.

ASCII Extendido

Debido a las limitaciones del ASCII se definieron varios códigos de caracteres de 8 bits, entre ellos el ASCII extendido. Sin embargo, el problema de estos códigos de 8 bits es que cada uno de ellos se define para un conjunto de lenguas con escrituras semejantes y por tanto no dan una solución unificada a la codificación de todas las lenguas del mundo. Es decir, no son suficientes 8 bits para codificar todos los alfabetos y escrituras del mundo.

Unicode

Como solución a estos problemas, desde 1991 se ha acordado internacionalmente utilizar la norma Unicode, que es una gran tabla, que en la actualidad asigna un código a cada uno de los más de cincuenta mil símbolos, los cuales abarcan todos los alfabetos europeos, ideogramas chinos, japoneses, coreanos, muchas otras formas de escritura, y más de un millar de símbolos especiales.

UTF-8

Es una norma de transmisión utilizada junto con la norma de codificación Unicode. Utilizadas en conjunto, funcionan de la siguiente manera:

• Unicode asigna los enteros del 0 al 127 (un total de 128) a exactamente los mismos caracteres que ASCII
• UTF-8 empaqueta cualquier entero del 0 al 127 en un octeto "a la antigua" pero con el octavo dígito siempre en cero, ya que actualmente el bit de paridad no se utiliza mas para detección de errores
• Además, como la tabla de Unicode es tan grande, la mayoría de sus símbolos están asignados a enteros mayores que 127 (códigos que, en consecuencia, necesitan más que 7 dígitos para su representación binaria). En todos esos casos, UTF-8 envía el comienzo de la representación binaria del código en cuestión en un primer octeto con dígito de paridad = 1
• El receptor de este mensaje, interpreta este dígito en 1 como señal de que lo que está siendo transmitido es un código que no cabe en 7 dígitos binarios; y por tanto determina que el símbolo no lo va a conocer mientras no lea el siguiente octeto, y tal vez el que sigue. En el peor de los casos, quizás se haga necesario leer seis octetos consecutivos para determinar un código alto.

      7.2 Detección de errores

Es una importante práctica para el mantenimiento e integridad de los datos a través de canales ruidosos y medios de almacenamiento poco confiables.

La comunicación entre varias computadoras produce continuamente un movimiento de datos, generalmente por canales no diseñados para este propósito (línea telefónica), y que introducen un ruido externo que produce errores en la transmisión.

Por lo tanto, debemos asegurarnos que si dicho movimiento causa errores, éstos puedan ser detectados.

      7.3 Decodificación de información binaria

ES el proceso contrario a la codificación en este caso tratándose se un sistema binario se trata principalmente de convertir cualquier sistema en un formato digital binario de forma tal que para la computadora sea fácil utilizarla.

      7.4 Corrección de errores

El método para detectar y corregir errores es incluir en los bloques de datos transmitidos bits adicionales denominados redundancia.

Se han desarrollado dos estrategias básicas para manejar los errores:

• Incluir suficiente información redundante en cada bloque de datos para que se puedan detectar y corregir los bits erróneos. Se utilizan códigos de corrección de errores.

• Incluir sólo la información redundante necesaria en cada bloque de datos para detectar los errores. En este caso el número de bits de redundancia es menor. Se utilizan códigos de detección de errores.

Si consideramos un bloque de datos formado por m bits de datos y r de redundancia, la longitud final del bloque será n, donde n = m + r.

Tipo de códigos detectores

Paridad simple (paridad horizontal)

Consiste en añadir un bit de más a la cadena que queremos enviar, y que nos indicará si el número de unos (bits puestos a 1) es par o es impar. Si es par incluiremos este bit con el valor = 0, y si no es así, lo incluiremos con valor = 1.

Ejemplo de generación de un bit de paridad simple:

Queremos enviar la cadena “1110100”:

1º Contamos la cantidad de unos que hay: 4 unos

2º El número de unos es par por tanto añadimos un bit con valor = 0

3º La cadena enviada es 11101000

El receptor ahora, repite la operación de contar la cantidad de “unos” que hay (menos el último bit) y si coincide, es que no ha habido error.

Problemas de este método:

Hay una alta probabilidad de que se cuelen casos en los que ha habido error, pero se ha pasado, como ocurre si se cambian dos números en la transmisión en vez de uno.

Paridad cruzada (paridad horizontal-vertical)

Para mejorar un poco el método anterior, se realiza una paridad que afecte tanto a los bits de cada cadena o palabra como a un conjunto de todos ellos. Siempre se utilizan cadenas relativamente cortas para evitar que se cuelen muchos errores.

Para ver más claro este método, se suelen agrupar los bits en una matriz de N filas por K columnas, luego se realizan todas las paridades horizontales por el método anterior, y por último, se hace las misma operación de calcular el número de unos, pero ahora de cada columna.

La probabilidad de encontrar un solo error es la misma, pero en cambio, la probabilidad de encontrar un número par errores ya no es cero, como en el caso anterior. Aun así, existen todavía una gran cantidad de errores no detectables

Un ejemplo de paridad cruzada (o de código geométrico)

1º Tenemos este código para transmitir: 1100101111010110010111010110

2º Agrupamos el código en cada una de las palabras, formando una matriz de N x K:

1100101

1110101

1001011

1010110

3º Añadimos los bits de paridad horizontal:

1100101 0

1110101 1

1001011 0

1010110 0

4º Añadimos los bits de paridad vertical:

1100101 0

1110101 1

1001011 0

1010110 0

 

0001101 1

 

Una vez creada la matriz, podemos enviar ésta por filas, o por columnas. Enviando las palabras por columnas aumentamos la posibilidad de corregir una palabra que haya sufrido un error de ráfaga (errores que afectan a varios bits consecutivos, debidos a causas generalmente electrónicas, como chispazos, y que harían que se perdiera toda una palabra completa)

Códigos de redundancia cíclica también llamados CRC

Intentando mejorar los códigos que sólo controlan la paridad de bit, aparecen los códigos cíclicos. Estos códigos utilizan la aritmética modular para detectar una mayor cantidad de errores. Y para facilitar los cálculos se trabaja (aunque solo teóricamente con polinomios).

La finalidad de este método es crear una parte de redundancia la cual se añade al final del código a transmitir (como en los métodos de paridad) que siendo la más pequeña posible, detecte el mayor número de errores que sea posible.

Pero además de esto, debe ser un método sistemático, es decir, que con un mismo código a transmitir, (y un mismo polinomio generador) se genere siempre el mismo código final.

El polinomio generador: es un polinomio elegido previamente, y que tiene como propiedad minimizar la redundancia. Suele tener una longitud de 16 bits, para mensajes de 128 bytes, lo que índica que la eficiencia es buena. Ya que solo incrementa la longitud en un aproximado 1,6%

(16bits / (128bytes * 8bitsporbyte)) * 100 = 1,5625

Un ejemplo de polinomio generador usado normalmente en las redes WAN es: g(x) = x¹⁶ + x¹² + x⁵ + 1

Los cálculos que realiza el equipo transmisor para calcular su CRC son:

1. Añade tantos ceros por la derecha al mensaje original como el grado del polinomio generador
2. Divide el mensaje con los ceros incluidos entre el polinomio generador
3. El resto que se obtiene en la división se suma al mensaje con los ceros incluidos
4. Se envía el resultado obtenido

Estas operaciones generalmente son incorporadas en el hardware para que pueda ser calculado con mayor rapidez, pero en la teoría se utilizan los polinomios para facilitar los cálculos.

Ejemplo de obtención del CRC:

Datos:

Mensaje codificado en binario: 1101010

Polinomio generador: x⁴ + x + 1

Operaciones:

1º Obtener el polinomio equivalente al mensaje: x⁶ + x⁵ + x³ + x

2º Multiplicar el mensaje por x4 (añadir 4 ceros por la derecha): x¹⁰ + x⁹ + x⁷ + x⁴

3º Dividir en binario el mensaje por el polinomio generador y sacar el resto: x² + 1

4º Restar el mensaje con el resto (en binario también): x¹⁰ + x⁹ + x⁷ + x⁴ + x³ + x¹ + 1

5º Transmitir el mensaje

El equipo receptor debe comprobar el código CRC para comprobar si se han producido o no errores.

Ejemplo de los cálculos del receptor:

1º Mediante el protocolo correspondiente acuerdan el polinomio generador

2º Divide el código recibido entre el polinomio generador

3º comprueba el resto de dicha operación

 3.1 Si el resto es cero, no se han producido errores

 3.2 Procesar el mensaje

 3.1 Si el resto es distinto de cero, significa que se han producido errores

 3.2 Reenviar el mensaje

 3.2 Intentar corregir los errores mediante los códigos correctores

En resumen, este método requiere de un polinomio generador, que elegido correctamente, puede llegar a detectar gran cantidad de errores:

• Errores simples: todos
• Errores dobles: todos
• Errores en las posiciones impares de los bits: todos
• Errores en ráfagas con una longitud menor que el grado del polinomio generador: todos
• Otras ráfagas: un porcentaje elevado, y cercano al 100%

Suma de comprobación

Es un método sencillo pero eficiente sólo con cadenas de palabras de una longitud pequeña, es por esto que se suele utilizar en cabeceras de tramas importantes u otras cadenas importantes y en combinación con otros métodos.

Funcionalidad: consiste en agrupar el mensaje a transmitir en cadenas de una longitud determinada L no muy grande, de por ejemplo 16 bits. Considerando a cada cadena como un número entero numerado según el sistema de numeración 2^L − 1. A continuación se suma el valor de todas las palabras en las que se divide el mensaje, y se añade el resultado al mensaje a transmitir, pero cambiado de signo.

Con esto, el receptor lo único que tiene que hacer es sumar todas las cadenas, y si el resultado es 0 no hay errores.

Ejemplo:

Mensaje 101001110101

1º Acordar la longitud de cada cadena: 3

2º Acordar el sistema de numeración: 2³ − 1 = 7

3º Dividir el mensaje: 101 001 110 101

4º Corresponder a cada cadena con un entero: 5 1 6 5

5º Sumar todos los valores y añadir el número cambiado de signo: -17

6º Enviar 5 1 6 5 -17 codificado en binario

El receptor:

1º Suma todos los valores si = 0 procesa el mensaje sino se ha producido un error.

Este método al ser más sencillo es óptimo para ser implementado en software ya que se puede alcanzar velocidades de cálculo similares a la implementación en hardware

Distancia de Hamming basada en comprobación

 

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