ALGEBRA LINEAL

Autor: DAZA FERNANDEZ VANESSA.
Año: 2003.
Universidad: POLITÉCNICA DE CATALUÑA.
Centro de lectura: SALA D'ACTES DE LA FME.
Centro de realización: FACULTAT DE MATEMATIQUES I ESTADISTICA SUD.

Resumen: Suposem que un conjunt de n participants vol calcular una determinada funció (pública) de les seves entrades (secretes). De manera genèrica els protocols de computació multipart s'encarreguen de garantir una solució per a aquest tipus de situacions. Proposen protocols segurs on els participants executen conjuntament un protocol de manera distribuïda que els permet obtenir, al final, el resultat de l'avaluació de la funció amb les seves entrades. A més a més es garanteixen alguns aspectes de seguretat, com la privacitat de les entrades dels participants així com l'exactitud del resultat, fins i tot si alguns participants del protocol es comporten de manera deshonesta. A finals dels anys 80 es van presentar les primeres solucions generals a aquest problema que garantien seguretat tot i que certes famílies de participants es comportessin de manera corrupta. Aquestes famílies estaven caracteritzades per un cert llindar t, de manera que la seguretat del protocol estava garantida només si menys de t participants eren corromputs. No va ser fins l'any 2000 que no es va presentar una solució eficient per a resoldre aquest problema, permetent l'estructura més general possible de participants per corrompre. La proposta relacionava la computació multipart amb els esquemes lineals per a compartir secrets. En certa manera utilitzen la linealitat del esquemes lineals per a compartir secrets per a calcular la part lineal de la funció. Però per poder calcular qualsevol funció és necessari poder avaluar la multiplicació de manera distribuïda entre el conjunt de participants. Així és com sorgeix el problema matemàtic de la multiplicació dels esquemes lineals per a compartir secrets. En poques paraules, el problema consisteix en trobar protocols eficients que calculin el producte de dos secrets a partir dels fragments que cada participant té de cadascun dels secrets. Un dels punts clau de la seva proposta és la reducció de la complexitat dels protocols de computació multipart a la dels esquemes per a compartir secrets. Una part d'aquesta tesi està dedicada a aquest problema, més concretament a l'estudi de la transformació dels esquemes lineals per a compartir secrets en esquemes multiplicatius minimitzant la complexitat dels esquemes resultants. Mentre que la recerca dels anys vuitanta en el camp de la computació multipart estava principalment marcada pels resultats existencials, en els últims anys, la recerca en aquest camp de la computació multipart ha experimentat un creixement en una direcció completament diferent. Aquesta nova tendència busca protocols ad-hoc, dissenyats per a resoldre diferents situacions i problemes a partir de suposicions concretes i mecanismes específics. Es perd així generalitat a canvi de guanyar eficiència en les propostes. A aquesta tesi també hem abordat aquesta altra tendència. En particular ens hem centrat en el problema criptogràfic de la distribució de claus, construint protocols de distribució de claus distribuïts en diferents models. Destaquem el fet que totes les nostres propostes presenten un mateix element comú: l'ús dels esquemes lineals per a compartir secrets com a eina bàsica a l'aproximació distribuïda del problema de la distribució de claus.

Autor: Díez Machío Héctor.
Año: 2005.
Universidad: LEÓN.
Centro de lectura: Escuela de Ingeniería Industrial e Informática.
Centro de realización: Escuela de Ingeniería INdustrial e Informática.

Resumen: EL OBJETO DE ESTUDIO DE LA TESIS SON LAS MÁQUINAS. SE ESTUDIAN TRES TIPOS DE MÁQUINAS. LOS SISTEMAS DINÁMICOS LINEALES SOBRE ANILLOS DE ORDEN SUPERIOR, LOS SISTEMAS DINÁMICOS CUÁNTICOS Y LAS MÁQUINAS SECUENCIALES FINITAS (AUTÓMATAS FINITOS). PARA EL PRIMER TIPO DE MÁQUINAS SE ESTUDIAN LOS PROBLEMAS DE CARACTERIZAR LA ACCESIBILIDAD Y LA BÚSQUEDA DE INVARIANTES MEDIANTE EQUIVALENCIA FEEDBACK. LOS RESULTADOS OBTENIDOS GENERALIZAN RESULTADOS CONOCIDOS PARA SISTEMAS DINÁMICOS DE ORDEN UNO. PARA EL SEGUNDO TIPO DE MÁQUINAS, MUCHO MENOS ESTUDIADAS, SE TRATAN EL PROBLEMA DE LA BÚSQUEDA DE FORMA CANÓNICAS. SE PROPONEN SOLUCIONES PARA SISTEMAS IMPERTURBADOS Y PARA SISTEMAS CON ÚNICO CAMPO DE CONTROL EXTERNO. LAS FORMAS CANÓNICAS OBTENIDAS SE UTILIZAN PARA RESOLVER LA ECUACIÓN DINÁMICA DE DICHOS SISTEMAS. PARA EL TERCER TIPO DE MÁQUINAS SE ESTUDIAN SIMULTÁNEAMENTE LAS MÁQUINAS CON COMPORTAMIENTO CLÁSICO Y CUÁNTICO. SE PROPONE UN MODELO DE MÁQUINA SECUENCIAL FINITA Y SE DEMUESTRA QUE DICHO MODELO GENERALIZA LOS MODELOS DE AUTÓMATAS FINITOS DETERMINISTAS, AUTÓMATAS PROBABILÍSTICAS Y LOS MODELOS MÁS IMPORTANTES DE AUTÓMATAS CUÁNTICOS. SE DESCRIBE LA COMPOSICIÓN EN CASCADA Y SE DEMUESTRA QUE EL MODELO ES CONSISTENTE CON DICHA OPERACIÓN. ADEMÁS ESTE MODELO PRESENTA LA NOVEDAD DE PODER TRABAJAR CON COMPOSICIONES DE MÁQUINAS CLÁSICAS Y CUÁNTICAS SIMULTÁNEAMENTE. FINALMENTE SE TRATA EL PROBLEMA DE LA EQUIVALENCIA DE ESTADOS Y SE DEJA ABIERTO EL PROBLEMA DE CALCULAR DE FORMA FINITA CUANDO DOS ESTADOS DE ESTAS MÁQUINAS SON EQUIVALENTES. SE OFRECE UNA CONJETURA PARA DICHO PROBLEMA. EL OBJETO DE ESTUDIO DE LA TESIS SON LAS MÁQUINAS. SE ESTUDIAN TRES TIPOS DE MÁQUINAS. LOS SISTEMAS DINÁMICOS LINEALES SOBRE ANILLOS DE ORDEN SUPERIOR, LOS SISTEMAS DINÁMICOS CUÁNTICOS Y LAS MÁQUINAS SECUENCIALES FINITAS (AUTÓMATAS FINITOS). PARA EL PRIMER TIPO DE MÁQUINAS SE ESTUDIAN LOS PROBLEMAS DE CARACTERIZAR LA ACCESIBILIDAD Y LA BÚSQUEDA DE INVARIANTES MEDIANTE EQUIVALENCIA FEEDBACK. LOS RESULTADOS OBTENIDOS GENERALIZAN RESULTADOS CONOCIDOS PARA SISTEMAS DINÁMICOS DE ORDEN UNO. PARA EL SEGUNDO TIPO DE MÁQUINAS, MUCHO MENOS ESTUDIADAS, SE TRATAN EL PROBLEMA DE LA BÚSQUEDA DE FORMA CANÓNICAS. SE PROPONEN SOLUCIONES PARA SISTEMAS IMPERTURBADOS Y PARA SISTEMAS CON ÚNICO CAMPO DE CONTROL EXTERNO. LAS FORMAS CANÓNICAS OBTENIDAS SE UTILIZAN PARA RESOLVER LA ECUACIÓN DINÁMICA DE DICHOS SISTEMAS. PARA EL TERCER TIPO DE MÁQUINAS SE ESTUDIAN SIMULTÁNEAMENTE LAS MÁQUINAS CON COMPORTAMIENTO CLÁSICO Y CUÁNTICO. SE PROPONE UN MODELO DE MÁQUINA SECUENCIAL FINITA Y SE DEMUESTRA QUE DICHO MODELO GENERALIZA LOS MODELOS DE AUTÓMATAS FINITOS DETERMINISTAS, AUTÓMATAS PROBABILÍSTICAS Y LOS MODELOS MÁS IMPORTANTES DE AUTÓMATAS CUÁNTICOS. SE DESCRIBE LA COMPOSICIÓN EN CASCADA Y SE DEMUESTRA QUE EL MODELO ES CONSISTENTE CON DICHA OPERACIÓN. ADEMÁS ESTE MODELO PRESENTA LA NOVEDAD DE PODER TRABAJAR CON COMPOSICIONES DE MÁQUINAS CLÁSICAS Y CUÁNTICAS SIMULTÁNEAMENTE. FINALMENTE SE TRATA EL PROBLEMA DE LA EQUIVALENCIA DE ESTADOS Y SE DEJA ABIERTO EL PROBLEMA DE CALCULAR DE FORMA FINITA CUANDO DOS ESTADOS DE ESTAS MÁQUINAS SON EQUIVALENTES. SE OFRECE UNA CONJETURA PARA DICHO PROBLEMA.

Autor: CORTÉS UTRILLAS VANESA.
Año: 2006.
Universidad: ZARAGOZA.
Centro de lectura: FACULTAD DE CIENCIAS.
Centro de realización: FACULTAD DE CIENCIAS.

Resumen: Esta memoria se enmarca en el campo del estudio de métodos numéricos adaptados a matrices estructuradas, que muestra una intensa y creciente actividad investigadora. Las clases de matrices estructuradas consideradas tienen relación con propiedades de signo. Algunas de las clases de matrices que más se estudiarán en la memoria son las de las matrices signo-regulares y estrictamente signo-regulares, conteniendo esta última clase tanto las matrices totalmente positivas como las totalmente negativas. Recordemos que una matriz m x n se llama (estrictamente) signo-regular si, para cada k=1,..., mín{m,n}, todos los menores de orden k tienen el mismo signo (estricto). Se estudia el factor de crecimiento de la eliminación de Gauss con distintas estrategias de pivotaje. Algunas de las estrategias de pivotaje consideradas son nuevas e intermedias entre el pivotaje parcial y una estrategia de pivotaje introducida recientemente, el llamado pivotaje "rook" . En contraste con el pivotaje parcial, que no es "backward" estable para la eliminación de Gauss-Jordan, vemos que estas estrategias intermedias sí que lo son. Además mostramos su buen comportamiento para la eliminación de Gauss.Usando el llamado factor de crecimiento medio vemos que estas estrategias intermedias son ya muy competitivas frente al más costoso pivotaje "rook". También analizamos el factor de crecimiento y otros aspectos de las estrategias de pivotaje parcial escalado, así como su económica implementación en el caso de aplicarlas a clases especiales de matrices, como por ejemplo la importante clase de las M-matrices. Además, proponemos una estrategia de pivotaje por filas (llamada dos-determinantal) asociada a la eliminación de Neville para las matrices signo-regulares. Vemos que esta estrategia tiene factor de crecimiento óptimo y se puede aplicar con un coste computacional reducido (inferior al del pivotaje parcial); además, esta estrategia produce los mismos intercambios de filas que las estrategias de pivotaje parcial escalado para la eliminación de Neville. Destaquemos que esta estrategia preserva la signo-regularidad a lo largo del proceso de eliminación. La caracterización que presentamos de las matrices estrictamente signo-regulares mediante la eliminación de Neville con esta nueva estrategia nos permite proporcionar un test robusto que comprueba la estricta signo-regularidad de una matriz cualquiera. Finalmente, consideramos descomposiciones de las matrices estrictamente signo-regulares. Entre las descomposiciones analizadas, podemos mencionar la LDU, la QR, la SVD, la polar y la llamada simétrica-triangular. También damos caracterizaciones de esta clase de matrices a través de algunas de sus factorizaciones. En particular, vemos que, en muchas situaciones, estas caracterizaciones se simplifican considerablemente, como por ejemplo en el caso de las matrices totalmente negativas.