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