近年線上教學平台有著很大的發展，不管是國內的均一教學平台，或國外知名的可汗教育平台，都提供各種學科便利學生自主學習。而在高中化學計算的領域中，這些平台上均提供各種教學課程。美中不足的是在線上的練習系統中，往往題目數量少、題目變化少、無詳細解題步驟，這樣將不足以透過題目衡量一個學生在各個主題的學習上有無明顯的進步。 本論文的目的是改善上述問題。我們設計並實做一系統，只要使用者輸入簡單需求，即可自動產生高中化學問題以及伴隨詳細解答，可方便出題者快速產生各式不同主題的高中化學應用題目。我們的系統提供一個Web前端供使用者輸入所需要生成的題目之資訊。系統由此收齊相關參數之後，接著即可依據參數產生符合題目限制條件的化學問題生成模型。此問題模型為一hypergraph，節點代表已知或未知相關化學量，超連結(hyperedge)則代表數個化學量間的相依關係。有了此一以ASP(Answer Set Programming)表達的問題模型之後，系統即可利用ASP求解器(Solver)進行單一或多個題目生成，後續工作則是驗證每一生成題目之可行性並產生解題步驟，最後經由Django整合呈現於Web上。 / In recent years there has been great progress in the development of online learning. Well-known platforms such as international Khan Academic or local Junyi Academy in Taiwan provide courses in various subjects allowing interested students to study in a very convenient and autonomous way. As expected, courses on common subjects such as high school chemistry are offered with rich content by these platforms. However, there are shortcomings in these courses about the problems they provide for the students to practice or test. In addition to rich content, an ideal course should provide abundant problems of all possible topics, with each given detailed solution, so that students can evaluate their achievement of study by practicing or testing themselves with these problems. Unfortunately, no courses on these platforms meet the above requirements. The purpose of this thesis is to improve the above shortcoming by providing a system which can generate automatically word problems on various topics of high school chemistry, together with detailed accompanied solutions. Our system is a web-based application implemented using Django. It provides a front-end enabling the users to enter related information for the word problems they want the system to generate. According to the parameters collected from the front-end, our system will generate a corresponding chemical problem model. The model is a hypergraph with nodes representing known or unknown chemical quantities related to the problem and hyperedges representing relations or dependencies among these quantities. After the model is generated as a logic program of ASP(Answer-set Programming), the system will use an ASP solver to generate one or more candidate problems. Subsequent works are then used to verify the feasibility of each problem and produce a solution for the feasible one. Finally the generated problems as well as solutions are wrapped in the server side and then sent to and presented friendly in the client's browser.

Combinatorial Group Testing (CGT) is a process of identifying faulty interactions (“errors”) within a particular set of items. Error Locating Arrays (ELAs) are combinatorial designs that can be built from Covering Arrays (CAs) to not only cover all errors in a system (each involving up to a certain number of items), but to locate and identify the errors as well. In this thesis, we survey known results for CGT, as well as CAs, ELAs, and some other types of related arrays. More importantly, we give several new results. First, we give a new algorithm that can be used to test a system in which each component (factor) has two options (values), and at most two errors are present. We show that, for systems with at most two errors, our algorithm improves upon a related algorithm by Mart´ınez et al. in terms of both robustness and efficiency. Second, we give the first adaptive CGT algorithm that can identify, among a given set of k items, all faulty interactions involving up to three items. We then compare it, performance-wise, to current-best nonadaptive method that can identify faulty interactions involving up to three items. We also give the first adaptive ELA-building algorithm that can identify all faulty interactions involving up to three items when safe values are known. Both of our new algorithms are generalizations of ones previously given by Mart´ınez et al. for identifying all faulty interactions involving up to two items.

L’utilisation de l’algèbre pour résoudre des problèmes de graphes a conduit au développement de trois branches : théorie spectrale des graphes, géométrie et combinatoire des groupes et études des invariants de graphes. La notion de graphe d’expansions (invariant de graphes) est relativement récente, elle a été développée afin d’étudier la robustesse des réseaux de télécommunication. Il s’avère que la construction de familles infinies de graphes expanseurs est un problème difficile. Cette thèse traite principalement de la construction de nouvelles familles de tels graphes. Les graphes expanseurs possèdent des nombreuses applications en informatique, notamment dans la construction de certains algorithmes, en théorie de la complexité, sur les marches aléatoires (random walk), etc. En informatique théorique, ils sont utilisés pour construire des familles de codes correcteurs d’erreur. Comme nous l’avons déjà vu les familles d’expanseurs sont difficiles à construire. La plupart des constructions s'appuient sur des techniques algébriques complexes, principalement en utilisant des graphes de Cayley et des produit Zig-Zag. Dans cette thèse, nous présentons une nouvelle méthode de construction de familles infinies d’expanseurs en utilisant les G-graphes. Ceux-ci sont en quelque sorte une généralisation des graphes de Cayley. Plusieurs nouvelles familles infinies d’expanseurs sont construites, notamment la première famille d’expanseurs irréguliers. / Applying algebraic and combinatorics techniques to solve graph problems leads to the birthof algebraic and combinatorial graph theory. This thesis deals mainly with a crossroads questbetween the two theories, that is, the problem of constructing infinite families of expandergraphs.From a combinatorial point of view, expander graphs are sparse graphs that have strongconnectivity properties. Expanders constructions have found extensive applications in bothpure and applied mathematics. Although expanders exist in great abundance, yet their explicitconstructions, which are very desirable for applications, are in general a hard task. Mostconstructions use deep algebraic and combinatorial approaches. Following the huge amountof research published in this direction, mainly through Cayley graphs and the Zig-Zagproduct, we choose to investigate this problem from a new perspective; namely by usingG-graphs theory and spectral hypergraph theory as well as some other techniques. G-graphsare like Cayley graphs defined from groups, but they correspond to an alternative construction.The reason that stands behind our choice is first a notable identifiable link between thesetwo classes of graphs that we prove. This relation is employed significantly to get many newresults. Another reason is the general form of G-graphs, that gives us the intuition that theymust have in many cases such as the relatively high connectivity property.The adopted methodology in this thesis leads to the identification of various approaches forconstructing an infinite family of expander graphs. The effectiveness of our techniques isillustrated by presenting new infinite expander families of Cayley and G-graphs on certaingroups. Also, since expanders stand in no single stem of graph theory, this brings us toinvestigate several closely related threads from a new angle. For instance, we obtain newresults concerning the computation of spectra of certain Cayley and G-graphs, and theconstruction of several new infinite classes of integral and Hamiltonian Cayley graphs.

Reproducing the construction of a geoscientific model is a hard task. It requires the availability of all required data and an exact description how the construction was performed. In practice data availability and the exactness of the description is often lacking. As part of this thesis I introduce a conceptual framework how geoscientific model constructions can be described as directed acyclic hypergraphs, how such recorded construction graphs can be used to reconstruct the model, and how repetitive constructions can be used to verify the reproducibility of a geoscientific model construction process. In addition I present a software prototype, implementing these concepts. The prototype is tested with three different case studies, including a geophysical measurement analysis, a subsurface model construction and the calculation of a hydrological balance model.:1. Introduction 1.1. Survey on Reproducibility and Automation for Geoscientific Model Construction 1.2. Motivating Example 1.3. Previous Work 1.4. Problem Description 1.5. Structure of this Thesis 1.6. Results Accomplished by this Thesis 2. Terms, Definitions and Requirements 2.1. Terms and Definitions 2.1.1. Geoscientific model 2.1.2. Reproducibility 2.1.3. Realisation 2.2. Requirements 3. Related Work 3.1. Overview 3.2. Geoscientific Data Storage Systems 3.2.1. PostGIS and Similar Systems 3.2.2. Geoscience in Space and Time (GST) 3.3. Geoscientific Modelling Software 3.3.1. gOcad 3.3.2. GemPy 3.4. Experimentation Management Software 3.4.1. DataLad 3.4.2. Data Version Control (DVC) 3.5. Reproducible Software Builds 3.6. Summarised Releated Work 4. Concept 4.1. Construction Hypergraphs 4.1.1. Reproducibility Based on Construction Hypergraphs 4.1.2. Equality definitions 4.1.3. Design Constraints 4.2. Data Handling 5. Design 5.1. Application Structure 5.1.1. Choice of Application Architecture for GeoHub 5.2. Extension Mechanisms 5.2.1. Overview 5.2.2. A Shared Library Based Extension System 5.2.3. Inter-Process Communication Based Extension System 5.2.4. An Extension System Based on a Scripting Language 5.2.5. An Extension System Based on a WebAssembly Interface 5.2.6. Comparison 5.3. Data Storage 5.3.1. Overview 5.3.2. Stored Data 5.3.3. Potential Solutions 5.3.4. Model Versioning 5.3.5. Transactional security 6. Implementation 6.1. General Application Structure 6.2. Data Storage 6.2.1. Database 6.2.2. User-provided Data-processing Extensions 6.3. Operation Executor 6.3.1. Construction Step Descriptions 6.3.2. Construction Step Scheduling 6.3.3. Construction Step Execution 7. Case Studies 7.1. Overview 7.2. Geophysical Model of the BHMZ block 7.2.1. Provided Data and Initial Situation 7.2.2. Construction Process Description 7.2.3. Reproducibility 7.2.4. Identified Problems and Construction Process Improvements 7.2.5. Recommendations 7.3. Three-Dimensional Subsurface Model of the Kolhberg Region 7.3.1. Provided Data and Initial Situation 7.3.2. Construction Process Description 7.3.3. Reproducibility 7.3.4. Identified Problems and Construction Process Improvements 7.3.5. Recommendations 7.4. Hydrologic Balance Model of a Saxonian Stream 7.4.1. Provided Data and Initial Situation 7.4.2. Construction Process Description 7.4.3. Reproducibility 7.4.4. Identified Problems and Construction Process Improvements 7.4.5. Recommendations 7.5. Lessons Learned 8. Conclusions 8.1. Summary 8.2. Outlook 8.2.1. Parametric Model Construction Process 8.2.2. Pull and Push Nodes 8.2.3. Parallelize Single Construction Steps 8.2.4. Provable Model Construction Process Attestation References Appendix

Le calcul scientifique parallèle est un domaine en plein essor qui permet à la fois d’augmenter la vitesse des longs traitements, de traiter des problèmes de taille plus importante ou encore des problèmes plus précis. Ce domaine permet donc d’aller plus loin dans les calculs scientifiques, d’obtenir des résultats plus pertinents, car plus précis, ou d’étudier des problèmes plus volumineux qu’auparavant. Dans le monde plus particulier de la simulation numérique scientifique, la résolution d’équations aux dérivées partielles (EDP) est un calcul particulièrement demandeur de ressources parallèles. Si les ressources matérielles permettant le calcul parallèle sont de plus en plus présentes et disponibles pour les scientifiques, à l’inverse leur utilisation et la programmation parallèle se démocratisent difficilement. Pour cette raison, des modèles de programmation parallèle, des outils de développement et même des langages de programmation parallèle ont vu le jour et visent à simplifier l’utilisation de ces machines. Il est toutefois difficile, dans ce domaine dit du “parallélisme implicite”, de trouver le niveau d’abstraction idéal pour les scientifiques, tout en réduisant l’effort de programmation. Ce travail de thèse propose tout d’abord un modèle permettant de mettre en oeuvre des solutions de parallélisme implicite pour les simulations numériques et la résolution d’EDP. Ce modèle est appelé “Structured Implicit Parallelism for scientific SIMulations” (SIPSim), et propose une vision au croisement de plusieurs types d’abstraction, en tentant de conserver les avantages de chaque vision. Une première implémentation de ce modèle, sous la forme d’une librairie C++ appelée SkelGIS, est proposée pour les maillages cartésiens à deux dimensions. Par la suite, SkelGIS, et donc l’implémentation du modèle, est étendue à des simulations numériques sur les réseaux (permettant l’application de simulations représentant plusieurs phénomènes physiques). Les performances de ces deux implémentations sont évaluées et analysées sur des cas d’application réels et complexes et démontrent qu’il est possible d’obtenir de bonnes performances en implémentant le modèle SIPSim. / Parallel scientific computations is an expanding domain of computer science which increases the speed of calculations and offers a way to deal with heavier or more accurate calculations. Thus, the interest of scientific computations increases, with more precised results and bigger physical domains to study. In the particular case of scientific numerical simulations, solving partial differential equations (PDEs) is an especially heavy calculation and a perfect applicant to parallel computations. On one hand, it is more and more easy to get an access to very powerfull parallel machines and clusters, but on the other hand parallel programming is hard to democratize, and most scientists are not able to use these machines. As a result, high level programming models, framework, libraries, languages etc. have been proposed to hide technical details of parallel programming. However, in this “implicit parallelism” field, it is difficult to find the good abstraction level while keeping a low programming effort. This thesis proposes a model to write implicit parallelism solutions for numerical simulations such as mesh-based PDEs computations. This model is called “Structured Implicit Parallelism for scientific SIMulations” (SIPSim), and proposes an approach at the crossroads of existing solutions, taking advantage of each one. A first implementation of this model is proposed, as a C++ library called SkelGIS, for two dimensional Cartesian meshes. A second implementation of the model, and an extension of SkelGIS, proposes an implicit parallelism solution for network-simulations (which deals with simulations with multiple physical phenomenons), and is studied in details. A performance analysis of both these implementations is given on real case simulations, and it demonstrates that the SIPSim model can be implemented efficiently.

The NP-complete k-SAT problem - decide wether a given formula is satisfiable - is of fundamental importance in theoretical computer science. In this dissertation we study random 4-SAT formulas with > 116 n^2 clauses. These formulas are almost surly unsatisfiable. Here we show the existence of a polynomial time algorithm that certifies the unsatisfiability. Therefore we study the discrepancy of hypergraphs and multigraphs. We also combine spectral techniques with approximation algorithms to achieve the new result. Our new algorithm is adaptable for Not-All-Equal-4-SAT and the 2-colouring of 4-uniform hypergraphs. We also extends the Hajos construction of non k-colourable graphs to non k-colourable uniform hypergraphs. / Das NP-vollständige Problem k-SAT ist von zentraler Bedeutung in der theoretischen Informatik. In der Dissertation werden zufällige 4-SAT-Formeln mit > n^2 vielen Klauseln studiert. Diese Formeln sind mit hoher Wahrscheinlichkeit unerfüllbar. Hier wird erstmalig die Existenz eines Algorithmus gezeigt, der diese Unerfüllbarkeit effizient verifiziert. Hierfür wird die geringe Diskrepanz von Hypergrpahen und Multigraphen betrachtet. Der Schlüssel zu diesem Algorithmus liegt in der Kombination von spektralen Techniken mit Approximationsalgorithmen der klassischen kombinatorischen Optimierung. Der vorgestellte Algorithmus kann auf den effizienten Nachweis der Unerfüllbarkeit von Not-All-Equal-4-SAT-Formeln und die Nicht-2-Färbbarkeit von 4-uniformen Hypergraphen erweitert werden. Es wird ebenfalls eine Erweiterung der Hajos-Konstruktion nicht k-färbbarer Graphen auf nicht k-färbbare uniforme Hypergraphen angegeben.

<p>Research on graph representation learning (GRL) has made major strides over the past decade, with widespread applications in domains such as e-commerce, personalization, fraud & abuse, life sciences, and social network analysis. Despite its widespread success, fundamental questions on practices employed in modern day GRL have remained unanswered. Unraveling and advancing two such fundamental questions on the practices in modern day GRL forms the overarching theme of my thesis.</p> <p>The first part of my thesis deals with the mathematical foundations of GRL. GRL is used to solve tasks such as node classification, link prediction, clustering, graph classification, and so on, albeit with seemingly different frameworks (e.g. Graph neural networks for node/graph classification, (implicit) matrix factorization for link prediction/ clustering, etc.). The existence of very distinct frameworks for different graph tasks has puzzled researchers and practitioners alike. In my thesis, using group theory, I provide a theoretical blueprint that connects these seemingly different frameworks, bridging methods like matrix factorization and graph neural networks. With this renewed understanding, I then provide guidelines to better realize the full capabilities of these methods in a multitude of tasks.</p> <p>The second part of my thesis deals with cases where modeling real-world objects as a graph is an oversimplified description of the underlying data. Specifically, I look at two such objects (i) modeling hypergraphs (where edges encompass two or more vertices) and (ii) using GRL for predicting protein properties. Towards (i) hypergraphs, I develop a hypergraph neural network which takes advantage of the inherent sparsity of real world hypergraphs, without unduly sacrificing on its ability to distinguish non isomorphic hypergraphs. The designed hypergraph neural network is then leveraged to learn expressive representations of hyperedges for two tasks, namely hyperedge classification and hyperedge expansion. Experiments show that using our network results in improved performance over the current approach of converting the hypergraph into a dyadic graph and using (dyadic) GRL frameworks. Towards (ii) proteins, I introduce the concept of conditional invariances and leverage it to model the inherent flexibility present in proteins. Using conditional invariances, I provide a new framework for GRL which can capture protein-dependent conformations and ensures that all viable conformers of a protein obtain the same representation. Experiments show that endowing existing GRL models with my framework shows noticeable improvements on multiple different protein datasets and tasks.</p>

Classical planning is the problem of nding a sequence of actions that take an agent from an initial state to a desired goal situation, assuming deter- ministic outcomes for actions and perfect information. Satis cing planning seeks to quickly nd low-cost solutions with no guarantees of optimality. The most e ective approach for satis cing planning has proved to be heuristic search using non-admissible heuristics. In this thesis, we introduce several such heuristics that are able to take into account costs on actions, and there- fore try to minimize the more general metric of cost, rather than length, of plans, and investigate their properties and performance. In addition, we show how the problem of planning with soft goals can be compiled into a classical planning problem with costs, a setting in which cost-sensitive heuristics such as those presented here are essential. / La plani caci on cl asica es el problema que consiste en hallar una secuencia de acciones que lleven a un agente desde un estado inicial a un objetivo, asum- iendo resultados determin sticos e informaci on completa. La plani caci on \satis cing" busca encontrar una soluci on de bajo coste, sin garant as de op- timalidad. La b usqueda heur stica guiada por heur sticas no admisibles es el enfoque que ha tenido mas exito. Esta tesis presenta varias heur sticas de ese g enero que consideran costes en las acciones, y por lo tanto encuentran soluciones que minimizan el coste, en lugar de la longitud del plan. Adem as, demostramos que el problema de plani caci on con \soft goals", u objetivos opcionales, se puede reducir a un problema de plani caci on clasica con costes en las acciones, escenario en el que heur sticas sensibles a costes, tal como las aqu presentadas, son esenciales.