Download INFORMACIÓN SOBRE LA ASIGNATURA ÁLGEBRA APLICADA A

Document related concepts

Criptografía wikipedia, lookup

Cifrado César wikipedia, lookup

Cifrado por transposición wikipedia, lookup

Verificación por redundancia cíclica wikipedia, lookup

Normalización de bases de datos wikipedia, lookup

Transcript
INFORMACIÓN SOBRE LA ASIGNATURA
ÁLGEBRA APLICADA
A quién está dirigida
La asignatura Álgebra aplicada es una optativa del primer ciclo de la licenciatura en
matemáticas que se imparte en el segundo cuatrimestre.
Su carga académica es de 7,5 créditos, lo que se traduce en cinco horas de clase semanal,
tres teóricas y dos prácticas.
No es requisito haber cursado ninguna asignatura en particular con anterioridad y de
hecho se revisan aquellos aspectos de otros cursos especialmente relevantes para esta
asignatura. No obstante y de forma puntual se hará uso de algún resultado de la Teoría de
Grupos y de Galois. No es en absoluto necesario tener conocimientos previos dee informática ni de
programación, en el primer tema se enseña todo lo necesario a este respecto.
Organización de la asignatura
La asignatura tiene una parte teórica y otra práctica. La primera se evalúa mediante un examen
cuya nota representa el 60% de la calificación final y mediante trabajos teóricos a desarrollar,
individualmente y en grupo, en la plataforma moodle, cuya nota representa el 10% de la
calificación. El 30% restante corresponde a las prácticas, aunque para hacer la media se exige
una nota mínima de 4 (sobre 10) en el examen escrito.
Las prácticas se realizan bajo la supervisión del profesor en grupos de dos alumnos.
Consisten en implementar los algoritmos explicados en clase en un lenguaje de programación. También se puede trabajar en un ordenador propio puesto que el sistema informático que se usa es de libre distribución y se facilitará una copia a quien lo desee.
Qué se estudia en la asignatura
El objetivo de esta asignatura es estudiar algunas aplicaciones del álgebra abstracta a
problemas reales relacionados con el tratamiento de la información, tema de enorme interés en
la actualidad. Hay varios aspectos en los que las herramientas proporcionadas por el álgebra
han resultado de una sorprendente utilidad, sólo mencionaremos tres de ellos:
• El diseño de métodos que aseguren que la comunicación de la información se realiza sin
errores (o con el mínimo número de ellos). Por ejemplo, queremos estar seguros en la
medida de lo posible de que la información que se lee en un código de barras o en un CD es
la correcta.
• Encontrar una forma de proteger la información confidencial de quien no esté autorizado
para tener acceso a ella. Este problema es de crucial importancia para hacer seguras las
transacciones bancarias (uso de cajeros, tarjetas de crédito...) y el comercio electrónico.
• Disponer de algoritmos de compresión de la información, especialmente de imágenes que
exigen una gran capacidad de memoria para ser almacenadas. Este problema
tiene interés para facilitar la transmisión de la información gráfica en internet y para el
desarrollo de la tecnología de vídeo digital.
En este curso daremos una introducción a la Teoría de códigos correctores de errores y a la
Criptología, que resuelven los dos primeros puntos.
La idea de los códigos correctores de errores es sencilla: para aumentar la fiabilidad en la
transmisión de la información añadimos a ésta una cierta redundancia. La forma trivial de
hacer esto es simplemente repetir cada unidad de información un cierto número k de veces. Si
k = 3, un mensaje binario 0, 0, 1, 0, 1 quedaría codificado en la forma
0, 0, 0, 0, 0, 0, 1,1,1, 0, 0, 0, 1,1,1.
Así, si el receptor recibe
0, 0,1, 0, 0, 0, 1,1,1, 0, 0, 0, 0, l, 0,
puede estar seguro de que al menos uno de los tres primeros datos y uno de los tres últimos ha
sido erróneo. Incluso más, puede ‘adivinar’ que el primer bloque debería haber sido 0, 0, 0 y
no 0, 0, 1 y el último debería haber sido 0, 0, 0 y no 0, l, 0. Observar que la primera suposición
es correcta, pero no así la segunda. La diferencia está en que en el primer bloque sólo había un
error mientras que en el segundo había dos. Lo que sí es cierto es que siempre que en un
bloque de longitud tres haya un error, sabremos cómo corregirlo correctamente. Se dice que
nuestro código corrige un error. Si el valor de k aumenta es claro que también aumenta la
capacidad de corregir errores del código. Lamentablemente esto no nos sale gratis, se hace a
costa de aumentar el tamaño del mensaje a transmitir (lo que también aumenta el tiempo
necesario para la transmisión) y, a partir de ciertos valores, ya no compensa ganar en
fiabilidad perdiendo tanto tiempo o memoria. El problema que se plantea es encontrar otros
métodos de codificación que den un suficiente margen de seguridad sin aumentar en exceso
el tamaño de la información codificada y es aquí donde el álgebra permite encontrar soluciones
que a simple vista pasarían completamente inadvertidas.
No somos conscientes de hasta qué punto detrás de muchos actos cotidianos se está
manejando información codificada en el sentido anterior. Un sencillo ejemplo lo tenemos en
nuestro número de carnet de identidad, que consta de 8 dígitos y una letra. La, letra no se
incluye para disponer de una cantidad mayor de números (no hay dos DNI que sólo se
diferencien en la letra), sino que se añade para ganar seguridad. De hecho, cualquiera puede
calcular fácilmente la letra que corresponde a su DNI del siguiente modo: se divide el número
entre 23 y se toma el resto de la división, al que se le suma 1. Así resulta un número entre
1 y 23. Ahora, simplemente se busca la letra correspondiente en la sucesión
TRWAGMYFPDXBNJZSQVHLCKE.
Esto significa que si alguien dice que su DNI completo es 34789234G, es seguro que se ha
equivocado (el resto de dividir 34789234 entre 23 es 9, luego su letra es la décima en la
sucesión anterior, esto es, la D y no la G). Este es un ejemplo de un código que detecta un
error, sin embargo no hay forma de saber cuál de los números es el erróneo, por lo tanto no
tiene ninguna capacidad correctora.
La Criptología es una ciencia conocida y usada desde las épocas históricas más antiguas.
Sorprendentemente, durante más de dos mil años sus fundamentos permanecieron inalterados: se
trata de que el emisor y receptor del mensaje establezcan previamente cuál es la clave de cifrado
de forma que sólo ellos dos sepan cómo recuperar el mensaje original a partir del mensaje
encriptado. En realidad, de lo que depende verdaderamente la privacidad de la comunicación es de
que la regla de descifrado sea conocida únicamente por el receptor, y de hecho sería deseable que
sólo él la conociera. El problema es que en un primer momento parece inevitable que el emisor
del mensaje también sepa cuál es dicha regla puesto que él sí conoce la regla de cifrado, de la cual
no parece que haya mayor problema en poder deducir cuál es la clave de descifrado (básicamente,
será proceder en ‘sentido inverso’). Sólo muy recientemente (hace unos 30 años) se descubrieron
sistemas de cifrado con la propiedad de que a partir de la clave de cifrado es imposible en la
práctica descubrir cuál es la clave de descifrado. Esto supuso una revolución en la criptología que
en la actualidad ha abierto la posibilidad, por ejemplo, al comercio a través de internet. Lo más
sorprendente es que estos sistemas criptográficos (llamados de clave pública frente a los sistemas
tradicionales o de clave privada) se basan en problemas de teoría de números estudiados durante
mucho tiempo por los matemáticos sin ser por supuesto conscientes de que mucho después
tendrían un interés práctico de enorme transcendencia.
Más información
Quien desee más información sobre la asignatura puede ponerse en contacto con el profesor
responsable de la misma, Luis Martínez, bien en su despacho, en el teléfono 946012651 o en la
dirección de correo electrónico [email protected]