La thèse porte sur la résolution des problèmes de satisfaisabilité booléenne (SAT) dans un cadre massivement parallèle. Le problème SAT est largement utilisé pour résoudre des problèmes combinatoires de première importance comme la vérification formelle de matériels et de logiciels, la bio-informatique, la cryptographie, la planification et l’ordonnancement de tâches. Plusieurs contributions sont apportées dans cette thèse. Elles vont de la conception d’algorithmes basés sur les approches « portfolio » et « diviser pour mieux régner », à l’adaptation de modèles de programmation parallèle, notamment hybride (destinés à des architectures à mémoire partagée et distribuée), à SAT, en passant par l’amélioration des stratégies de résolution. Ce travail de thèse a donné lieu à plusieurs contributions dans des conférences internationales du domaine ainsi qu’à plusieurs outils (open sources) de résolution des problèmes SAT, compétitifs au niveau international. / This thesis deals with propositional satisfiability (SAT) in a massively parallel setting. The SAT problem is widely used for solving several combinatorial problems (e.g. formal verification of hardware and software, bioinformatics, cryptography, planning, scheduling, etc.). The first contribution of this thesis concerns the design of efficient algorithms based on the approaches « portfolio » and « divide and conquer ». Secondly, an adaptation of several parallel programming models including hybrid (parallel and distributed computing) to SAT is proposed. This work has led to several contributions to international conferences and highly competitive distributed SAT solvers.

The wide application of analog and mixed-signal (AMS) designs makes the verification of AMS circuits an important task. However, verification of AMS circuits remains as a significant challenge even though verification techniques for digital circuits design have been successfully applied in the semiconductor industry. In this thesis, we propose two techniques for AMS verification targeting DC and transient verifications, respectively. The proposed techniques leverage a combination of circuit modeling, satisfiability (SAT) and circuit simulation techniques. For DC verification, we first build bounded device models for transistors. The bounded models are conservative approximations to the accurate BSIM3/4 models. Then we formulate a circuit verification problem by gathering the circuit's KCL/KVL equations and the I-V characteristics which are constrained by the bounded models. A nonlinear SAT solver is then recursively applied to the problem formula to locate a candidate region which is guaranteed to enclose the actual DC equilibrium of the original circuit. In the end, a refinement technique is applied to reduce the size of candidate region to a desired resolution. To demonstrate the application of the proposed DC verification technique, we apply it to locate the DC equilibrium points for a set of ring oscillators. The experimental results show that the proposed DC verification technique is efficient in terms of runtime. For transient verification, we perform reachability analysis to verify the dynamic property of a circuit. Our method combines circuit simulation SAT to take advantage of the efficiency of simulation and the soundness of SAT. The novelty of the proposed transient verification lies in the fact that a significant part of the reachable state space is discovered via fast simulation while the full coverage of the reachable state space is guaranteed by the invoking of a few SAT runs. Furthermore, a box merging algorithm is presented to efficiently represent the reachable state space using grid boxes. The proposed technique is used to verify the startup condition of a tunnel diode oscillator and the phase-locking of a phase-locked loop (PLL). The experimental results demonstrate that the proposed transient verification technique can perform reachability analysis for reasonable complex circuits over a great number of time steps.

No description available.

Not available / text

Στην παρούσα εργασία θα αναφερθούμε στο κατωφλικό φαινόμενο που εμφανίζεται στο k-SAT. Κύρια προσφορά της διπλωματικής είναι μια νέα απόδειξη του κάτω φράγματος στην περίπτωση του προβλήματος 2-SAT, όπου εκμεταλλευόμενοι γνωστά θεωρήματα από τη θεωρία τυχαίων γραφημάτων επιτυγχάνουμε μια ευκολότερη απόδειξη. Ξεκινάμε κάνοντας μια γενική παρουσίαση του προβλήματος της ικανοποιησιμότητας. Στο επόμενο κεφάλαιο παρουσιάζουμε κάποιους βασικούς ορισμούς και κάνουμε μια σύντομη αναδρομή στα αποτελέσματα που έχουν προκύψει. Αντικείμενο του τρίτου και τέταρτου κεφαλαίου είναι το 2-SAT όπου παρουσιάζονται αντιστοίχως η απόδειξη που δόθηκε από τον Goerdt[24] και μια νέα απόδειξη για το κάτω φράγμα με χρήση resolution. Στο τελευταίο κεφάλαιο στρέφουμε το ενδιαφέρον μας στην περίπτωση του 3-SAT και εξετάζουμε τις αποδείξεις ενός άνω και ενός κάτω κατωφλίου. / -

No description available.

Low Earth Orbit is over-cluttered with rogue objects that threaten existing technological assets and interfere with allocating new ones. Traditional satellite missions are not efficient enough to collect an appreciable amount of debris due to the high cost of orbit transfers. Many alternate proposals are politically controversial, costly, or dependent on undeveloped technology. This dissertation attempts to solve the problem by introducing a new mission architecture, Space Sweeper, and bespoke hardware, Sling-Sat, that sequentially captures and ejects debris plastically. Resulting momentum exchanges are exploited to aid in subsequent orbit transfers, thus saving fuel. Sling-Sat is a spinning satellite that captures debris at the ends of adjustable-length arms. Arm length controls the angular rate to achieve a desired tangential ejection speed. Timing the release exacts the ejection angle. This process redirects debris to burn up in the atmosphere, or reduce its lifetime, by lowering its perigee. This dissertation establishes feasibility of principles fundamental to the proposed concept. Hardware is conceptualized to accommodate Space Sweeper ’s specialized needs. Mathematical models are built for the purpose of analysis and simulation. A kinematic analysis investigates system demands and long-term behavior resulting from repeated debris interaction. A successful approach to enforce debris capture is established through optimal control techniques. A study of orbital parameters and their response to debris interactions builds an intuition for missions of this nature. Finally, a J2-compliant technique for path optimization is demonstrated. The results strongly support feasibility of the proposed mission.

Thesis (Ph. D.)--University of Pennsylvania, 1937. / Bibliography: p. 49-57.

Thesis (Ph. D.)--University of Texas at Austin, 2006. / Vita. Includes bibliographical references.

Magíster en Ciencias, Mención Computación / El principal objetivo de esta tesis es encontrar casos tratables y buenas técnicas para computar Certain Answers sobre bases de datos de grafos incompletas, en tiempo polinomial. Las bases de datos de grafos surgen naturalmente de la necesidad de almacenar información de redes, tales como Facebook, mapas de rutas o la web. La idea de "incompletitud" viene de la falta de información completa, complejidad con la cual tenemos que trabajar a diario. Sobre estas bases de datos de grafos carentes de información completa, queremos realizar preguntas en la forma de consultas particulares y determinar si la pregunta puede ser contestada de la misma forma en cada posible completación de la base de datos. La respuesta a estas preguntas en cada posible completación de una base de datos de grafos incompleta es llamada Certain Answers. El problema de Certain Answers sobre bases de datos de grafos incompletas ya ha sido estudiado, y es conocido que este problema es en general co-NP completo. En esta tesis convertimos el problema de computar Certain Answers en un problema 3-SAT con su fórmula lógica booleana asociada. Podemos probar que bajo ciertas condiciones esta fórmula lógica tiene un número de variables que nos permite determinar si es satisfacible en tiempo polinomial. Luego, probamos que estas condiciones son exhaustivas: sin cualquiera de ellas el problema se vuelve co-NP completo otra vez. Para analizar más clases tratables del problema de Certain Answers, convertimos el problema Certain Answers en un problema de programación lineal entera. Con esta formulación de programación lineal, encontramos algunos casos tratables, algoritmos y heurísticas para resolverlo. Sin embargo, el principal logro es la nueva formulación en sí, porque nos permite usar las bien conocidas técnicas de programación lineal para encontrar más casos tratables y mejores heurísticas.