Biblioteca Digital | FCEN-UBA

Biblioteca Digital ¿Por qué?
Objetivos
Impactos
Estadísticas
Documentos
Presentaciones
Notas
Autores y derechos
¿Por qué depositar?
¿Cómo depositar?
Autorización
Depositar y publicar
Editoriales
Publicar mi tesis Formulario Tesis Posgrado
Formulario Tesis Grado
Normativa
Res. CD 2053/05
Res. CD 2533/09
Res. CD 0272/13
Res. CD 2793/15

Colecciones Tesis Doctorales
Fotografías
Publicaciones
Archivo
Libros
Reportes Técnicos

Tesis > TEMA

Computación [ 80 tesis ]

Teoría de la Computabilidad [ 2 tesis ]

Mizrahi, Michel Jonathan. "Algoritmos y complejidad para algunos problemas de dominación" (2014-11-21) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
Los problemas de dominación forman un área de investigación en crecimiento, debido a la cantidad de aplicaciones que pueden modelar, entre las cuales podemos nombrar redes sociales, sistemas distribuidos, redes biológicas, problemas de localización de instalaciones, etc. En esta tesis estudiamos los siguientes problemas de dominación (i) el conjunto dominante mínimo, (ii) dominación romana, (iii) dominación eficiente por vértices, (iv) dominación eficiente por aristas (también conocida como matching inducido dominante), (v) dominación perfecta por vértices (vi) dominación perfecta por aristas, y (vii) subgrafo cordal máximo inducido sin vertices propiamente dominados (también conocido como eliminación de vértices para formar clusters). Para el problema (i) determinamos su complejidad para clases de grafos donde se prohiben subgrafos inducidos con a lo sumo cuatro vértices. Estudiamos los problemas (i) y (ii) para varias subclases de grafos P5-free, dando algoritmos eficientes, robustos y simples en ambos casos. Algoritmos de complejidad lineal para grafos arco-circulares fueron presentados para los problemas (iv), (v), (vi) usando algoritmos existentes para el problema (iii). Damos tres algoritmos de tiempo exponencial para resolver el problema (iv) en grafos generales. Además, para el problema (iv), presentamos algoritmos de complejidad O(n) restringidos a grafos cordales, dualmente-cordales, biconvexos, y claw-free. Estudiamos cuatro variantes del problema (vii) y presentamos algoritmos eficientes para todos ellos cuando nos restringimos a grafos de intervalos propios, grafos de intervalos, grafos arco-circulares, grafos de permutación, y grafos trapezoide. Por otro lado, probamos que las cuatro variantes son NP-Dificil para grafos bipartitos. Finalmente, mostramos que dos variantes son NP-Dificil para grafos split, mientras que las otras dos variantes se pueden resolver en tiempo polinomial.

Abstract:
Domination is a growing research area in graph theory, with a vast number of applications across different disciplines, which include social networks, distributed computing, biological networks, facility location problems, etc. In this thesis we studied the following domination problems (i) minimum dominating set problem (ii) Roman domination (iii) efficient vertex domination (iv) efficient edge domination (also known as dominating induced matching or DIM) (v) perfect vertex domination (vi) perfect edge domination (vii) maximum induced chordal subgraph without properly dominated vertices (also known as cluster vertex deletion). For problem (i) we determined its complexity for graph classes defined by forbidding as induced subgraphs all graphs with at most four vertices. We studied problems (i) and (ii) for some subclasses of P5-free graphs, giving efficient, robust and simple algorithms for both of them. Linear time algorithms restricted to circular-arc graphs were presented for problems (iv), (v), (vi) using existent linear algorithms from problem (iii). We described three exact exponential time algorithms solving problem (iv) for general graphs. Also, for problem (iv), O(n) time algorithms were given restricted to chordal, dually-chordal, bi-convex and claw-free graphs. We studied four variants of problem (vii) and presented efficient algorithms for all variants whenever the graphs were proper-interval graphs, interval graphs, circular-arc graphs, permutation graphs and trapezoid graphs. On the other hand we proved that the four variants are NP-Hard for bipartite graphs. Finally we showed that two of the variants are NP-Hard for split graphs while the other two variants are polynomially solvable.

Steren, Gabriela. "Dos temas en reescritura: combinadores para cálculos con patrones e isomorfismo de Curry-Howard para la Lógica de Pruebas" (2014-12-15) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
Pattern matching es una herramienta fundamental de la programación funcional. Permite describir conjuntos de datos que tienen una misma forma (a través de una expresión llamada patrón"). Esta facilidad ha comenzado a adoptarse también en otros paradigmas, y ha demostrado su utilidad para analizar datos en diversos formatos, como por ejemplo datos semiestructurados. Los cálculos de patrones son lenguajes minimales basados en cálculo lambda en los que se introducen formas sofisticadas de pattern matching para estudiar sus fundamentos formales. La primera parte de esta tesis propone una contribución a este campo, desarrollando una lógica combinatoria para λP, un cálculo de patrones donde cualquier término puede ser un patrón. La lógica combinatoria carece de variables ligadas. Nos encontramos ante dos desafíos. Por un lado, tratar con las variables ligadas en los patrones, ya que una abstracción es un patrón válido en λP. Para esto contamos con la guía de la lógica combinatoria estándar. El segundo desafío consiste en computar, en un escenario combinatorio, la contraparte de la sustitución obtenida ante un matching exitoso. Esto requiere la introducción de reglas capaces de descomponer las aplicaciones. Proponemos una lógica combinatoria que logra este propósito, y estudiamos sus propiedades salientes y extensiones, incluyendo una presentación tipada y la representación de estructuras de datos. La segunda parte de esta tesis se centra en la interpretación computacional de la Lógica de Pruebas, o LP, via el isomorfismo de Curry-Howard. LP, dada a conocer por Artemov en 1995, es un refinamiento de la lógica modal en la cual la modalidad 2A es revisitada como ]A, donde t es una expresión que testifica sobre la validez de A. Es aritméticamente correcta y completa, puede realizar todos los teoremas de S4 y posee la capacidad de versar sobre sus propias pruebas (` A implica ` ]A, para algún t). Nuestra contribución principal es una formulación en Deducción Natural con buen comportamiento, desarrollada con el fin de develar las metáforas computacionales que surgen de esta capacidad de reflexión de LP. Esta es la primera formulación en Deducción Natural capaz de capturar a LP en su totalidad. Para esto, adoptamos la Deducción Natural Clásica de Parigot y la unimos al razonamiento hipotético. Como resultado, obtenemos una presentación en Deducción Natural de LP proposicional, para la cual se demuestran ciertas propiedades claves. Luego extendemos nuestro análisis al caso de primer orden, presentando FOHLP, una extensión de primer orden de HLP. Nuestro punto de partida es una reciente formulación de primer orden de LP, llamada FOLP, que goza de corrección aritmética y tiene una semántica de demostrabilidad exacta (la completitud es inalcanzable dado que no es finitamente axiomatizable). Presentamos una formulación en Deducción Natural llamada FOHLP, traducciones desde y hacia FOLP, una asignación de términos (cálculo lambda) y una prueba de terminación del proceso de normalización de derivaciones.

Abstract:
Pattern matching is a basic building block on which functional programming depends, where the computation mechanism is based on finding a correspondence between the argument of a function and an expression called pattern". It has also found its way into other programming paradigms and has proved convenient for querying data in different formats, such as semistructured data. In recognition of this, a recent effort is observed in which pattern matching is studied in its purest form, namely by means of pattern calculi. These are lambda calculi with sophisticated forms of pattern matching. The first part of this two part thesis proposes to contribute to this effort by developing a combinatory logic for one such pattern calculus, namely λP. We seek to mimic the computational process of λP where arguments can be matched against arbitrary terms, without the use of variables. Two challenges must be met. On the one hand, dealing with bound variables in patterns. Indeed, an abstraction is a valid pattern in λP. Here the standard combinatory logic will provide guidance. The second is computing the counterpart, in the combinatory setting, of the substitution that is obtained in a successful match. This requires devising rules that pull applications apart, so to speak. We propose a combinatory logic that serves this purpose and study its salient properties and extensions including typed presentations and modeling data structures. In the second part, we are concerned with the computational interpretation of a particular modal logic, the Logic of Proofs or LP, via the Curry-Howard isomorphism. LP, introduced by Artemov in 1995, is a refinement of modal logic in which the modality 2A is revisited as ]A where t is an expression that bears witness to the validity of A. It enjoys arithmetical soundness and completeness, can realize all S4 theorems and is capable of re ecting its own proofs (` A implies ` ]A, for some t). Esta es la primera formulación en Deducción Natural capaz de capturar a LP en su totalidad. Our main contribution is a well-behaved Natural Deduction presentation, developed with the aim of unveiling the computational metaphors which arise from the re ective capabilities of LP. This is the first Natural Deduction formulation capable of proving all LP-theorems. For that, we adopt Parigot's Classical Natural Deduction and merge it with a hypothetical reasoning which guide the construction of the inference schemes. As an outcome we obtain a Natural Deduction presentation of propositional LP for which a number of key properties are shown to hold. We then extend our analysis to the first-order case, introducing FOHLP, a first-order extension of HLP. Our point of departure is a recent first-order formulation of LP, called FOLP, which enjoys arithmetical soundness and has an exact provability semantics (completeness is unattainable given that a complete FOLP is not finitely axiomatizable). We provide a Natural Deduction presentation dubbed FOHLP, mappings to and from FOLP, a term assignment (λ-calculus) and a proof of termination of normalisation of derivations.

http://digital.bl.fcen.uba.ar

Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34