[ca] Una aproximació exitosa per representar l'estructura sintàctica de les frases en Lingüística Computacional, basada en la teoria desenvolupada per Tesnière, és la d'un arbre de dependències sintàctiques. Parelles de vèrtexs de paraules relacionades sintàcticament s'uneixen per una aresta que porta una etiqueta que indica el tipus de relació sintàctica. Quan abstraiem les paraules i les relacions sintàctiques, eliminant les etiquetes dels vèrtexs i les etiquetes de les arestes que indiquen el tipus de relació sintàctica, obtenim el que es coneix com un arbre linearitzat. Un arbre linearitzat és simplement un arbre arrelat juntament amb un arranjament lineal. I un arranjament lineal d'un graf és una permutació dels vèrtexs del graf, el qual es pot representar dibuixant els vèrtexs en una línia horitzontal i les arestes com a semicercles per sobre d'ella. Hi ha molts problemes computacionals que involucren arranjaments lineals de grafs. Exemples notables són aquells que busquen una disposició que optimitzi la suma de les longituds de les arestes, on la longitud d'una aresta es defineix com el valor absolut de la diferència de les posicions dels extrems de l'aresta en l'arranjament. El problema que minimitza aquesta suma és conegut com el problema de l'Arranjament Lineal mínim (minLA). Quan es maximitza la suma de les longituds de les arestes, el problema es coneix com el problema de l'Arranjament Lineal Màxim (MaxLA). En un intent de proporcionar una teoria de l'ordre de les paraules, els investigadors en llenguatge humà han proposat el conegut principi de minimització de la Distància de Dependències després d'observar i proporcionar evidència a gran escala de la tendència de les llengües a minimitzar la suma total de les longituds de les arestes en els arbres de dependències sintàctiques de les seves frases. Per tal de proporcionar una teoria exhaustiva de l'ordre de les paraules, alguns investigadors en llenguatge també han argumentat que MaxLA es manifesta en les llengües en subestructures dels arbres de dependències sintàctiques isomorfes a un graf estrella. Se sap que tant minLA com MaxLA són NP-Difícils en grafs generals, i només es coneixen algorismes polinòmics per arbres en minLA. En aquesta tesi, aportem algorismes òptims per resoldre diverses variants restringides tant de minLA com de MaxLA. Estudiem aquests dos problemes per a grafs bipartits sota la restricció que els vèrtexs han de ser disposats en dos intervals disjunts segons la partició de vèrtexs a què pertanyen (arranjaments bipartits). També els estudiem per a arbres lliures sota la restricció que les arestes no puguin creuar-se en l'arranjament (arranjaments planars), i per a arbres arrelats sota la restricció que l'arranjament és planar i la arrel no està coberta (arranjaments projectius). En aquesta tesi també s'estudia la formulació no restringida de MaxLA per a arbres lliures. Els nostres esforços han produït solucions en temps polinòmic per a arbres k-lineals (0<= k <= 2) i un algorisme d'aproximació 3/2. A més, proveïm fórmules i algorismes per calcular el valor esperat del cost d'un arranjament bipartit aleatori uniforme de grafs bipartits, i d'arranjaments planars i projectius d'arbres (també aleatoris uniformes), basant-nos en nous coneixements sobre com generar aquests arranjaments uniformement a l'atzar. Tots aquests algorismes, i d'altres també, s'han empaquetat dins la Llibreria d'Arranjaments Lineals (LAL), amb llicència GNU Affero GPL.

[es] Una aproximación exitosa para representar la estructura sintáctica de las frases en Lingüística Computacional, basada en la teoría desarrollada por Tesnière, es la de un árbol de dependencias sintácticas. Parejas de vértices de palabras relacionadas sintácticamente se unen por una arista que lleva una etiqueta que indica el tipo de relación sintáctica. Cuando abstraemos las palabras y las relaciones sintácticas, eliminando las etiquetas de los vértices y las etiquetas de las aristas que indican el tipo de relación sintáctica, obtenemos lo que se conoce como un árbol linearizado. Un árbol linearizado es simplemente un árbol con raíz cuyos vértices se han distribuido en una ordenación lineal. Y una ordenación lineal de los vértices de un grafo es una permutación de los vértices del grafo, la cual se puede representar dibujando los vértices en una línea horizontal y las aristas como semicírculos por encima de ella. Existen muchos problemas computacionales que involucran ordenaciones lineales de grafos. Ejemplos notables son aquellos que buscan una ordenación que optimice la suma de las longitudes de las aristas, donde la longitud de una arista se define como el valor absoluto de la diferencia de las posiciones de los extremos de la arista en la ordenación. El problema que minimiza esta suma es conocido como el problema de la Ordenación Lineal mínima (minLA). Cuando se maximiza la suma de las longitudes de las aristas, el problema se conoce como el problema de la Ordenación Lineal Máxima (MaxLA). En un intento de proporcionar una teoría del orden de las palabras, los investigadores en lenguaje humano han propuesto el conocido principio de minimización de la Distancia de Dependencias después de observar y proporcionar evidencia a gran escala de la tendencia de las lenguas a minimizar la suma total de las longitudes de las aristas en los árboles de dependencias sintácticas de sus frases. A fin de proporcionar una teoría exhaustiva del orden de las palabras, algunos investigadores en lenguaje también han argumentado que MaxLA se manifiesta en las lenguas en subestructuras de los árboles de dependencias sintácticas isomorfas en un grafo estrella. Se sabe que tanto minLA como MaxLA son NP-Difíciles en grafos generales, y sólo se conocen algoritmos polinómicos para árboles en minLA. En esta tesis, aportamos algoritmos óptimos para resolver diversas variantes restringidas tanto de minLA como de MaxLA. Estudiamos estos dos problemas para grafos bipartitos bajo la restricción de que los vértices deben ser dispuestos en dos intervalos disjuntos según la partición de vértices a los que pertenecen (ordenaciones bipartitas). También los estudiamos para árboles libres bajo la restricción de que las aristas no puedan cruzarse en la ordenación (ordenaciones planares), y para árboles arraigados bajo la restricción que la ordenación es planar y la raíz no está cubierta (ordenaciones proyectivas). En esta tesis se estudia también la formulación no restringida de MaxLA para árboles libres. Nuestros esfuerzos han producido soluciones en tiempo polinómico para árboles k-lineales (0 <= k <= 2) y un algoritmo de aproximación 3/2. Además, proveemos fórmulas y algoritmos para calcular el valor esperado del coste de una ordenación bipartita aleatorio uniforme de grafos bipartitos, y de ordenaciones planares y proyectivas de árboles (también aleatorios uniformes), basándonos en nuevos conocimientos sobre cómo generar estas ordenaciones uniformemente al azar. Todos estos algoritmos, y otros también, se han empaquetado en la Librería de Ordenaciones Lineales (LAL), con licencia GNU Affero GPL.