Combinatorial Optimization is becoming ever more crucial, in these days. From natural sciences to economics, passing through urban centers administration and personnel management, methodologies and algorithms with a strong theoretical background and a consolidated real-word effectiveness is more and more requested, in order to find, quickly, good solutions to complex strategical problems. Resource optimization is, nowadays, a fundamental ground for building the basements of successful projects. From the theoretical point of view, Combinatorial Optimization rests on stable and strong foundations, that allow researchers to face ever more challenging problems. However, from the application point of view, it seems that the rate of theoretical developments cannot cope with that enjoyed by modern hardware technologies, especially with reference to the one of processors industry. In this work we propose new parallel algorithms, designed for exploiting the new parallel architectures available on the market. We found that, exposing the inherent parallelism of some resolution techniques (like Dynamic Programming), the computational benefits are remarkable, lowering the execution times by more than an order of magnitude, and allowing to address instances with dimensions not possible before. We approached four Combinatorial Optimization’s notable problems: Packing Problem, Vehicle Routing Problem, Single Source Shortest Path Problem and a Network Design problem. For each of these problems we propose a collection of effective parallel solution algorithms, either for solving the full problem (Guillotine Cuts and SSSPP) or for enhancing a fundamental part of the solution method (VRP and ND). We endorse our claim by presenting computational results for all problems, either on standard benchmarks from the literature or, when possible, on data from real-world applications, where speed-ups of one order of magnitude are usually attained, not uncommonly scaling up to 40 X factors.

This thesis is the result of a Ph.D. program in Alto Apprendistato carried out at the Dipartimento di Informatica - Scienza e Ingegneria (DISI) of the University of Bologna and at the company devDept Software. With regard to the professional side of my Individual Training Project, I developed technical and scientific skills in 3D geometry of curves and surfaces, CAD, and Finite Element Analysis (FEA). Regarding the academic side, I investigated CAD aspects in the field of Isogeometric Analysis (IGA) on both single and hybrid multipatch physical domains. Simulations are performed in classical FEA systems, which require the conversion of designs, made by CAD systems, into finite element meshes. IGA is a new approach that aims to unify the worlds of CAD and FEA by using the same geometry for analysis as what is used for modeling. That is, the same set of basis functions are adopted both to describe the computational geometry in the CAD tool, and to span the solution space for FEA. The traditional FEA pipeline works on meshes and the most advanced IGA systems work on NURBS or T-spline geometries. Hybrid geometric models (i.e., models in which mesh and NURBS entities coexist), are an emergent way to represent a solid object, but in most CAD systems mesh and NURBS geometries cannot interact with each other, and conversions to a common representation are often needed. In this thesis, we investigate how IGA can be applied on 2D and 3D hybrid models made by both mesh and NURBS entities without requiring laborious and time consuming conversion processes.

Many problems arising in several and different areas of human knowledge share the characteristic of being intractable in real cases. The relevance of the solution of these problems, linked to their domain of action, has given birth to many frameworks of algorithms for solving them. Traditional solution paradigms are represented by exact and heuristic algorithms. In order to overcome limitations of both approaches and obtain better performances, tailored combinations of exact and heuristic methods have been studied, giving birth to a new paradigm for solving hard combinatorial optimization problems, constituted by model-based metaheuristics. In the present thesis, we deepen the issue of model-based metaheuristics, and present some methods, belonging to this class, applied to the solution of combinatorial optimization problems.

In this thesis, it is examined the issue of equivalence between linear terms in higher order languages, that is, in languages which allow to use functions as variables, and where variables which appear in the terms must be used exactly once. The work is developed focusing on the bisimulation method, with the purpose to compare this technique with that which has become the standard for the comparison between the terms of a language, i.e. the context equivalence. The thesis is divided into three parts: in the first one, the introduction of the bisimulation and context equivalence techniques takes place within a deterministic linear and typed language. In the second part, the same techniques are reformulated for a language that, while preserving the linearity, loses the deterministic connotation, allowing the terms to evaluate to a set of values each one having a certain probability to appear in the end of calculation. In the last part, a quantum language is examined, discussing the advantages of quantum computation, which allows to speed-up many of the algorithms of computation. Here one gives the concept of quantum program, which is inextricably linked to the (quantum) register where the qubits used in the computation are stored, entailing a more complex notion of equivalence between terms. The techniques to demonstrate that bisimulation is a congruence are not standard and have been used for the first time by Howe for untyped languages: within the thesis, one shows that bisimulation is a congruence in all considered languages but it coincides with the context equivalence relation only for the deterministic one. Indeed, extending the techniques already used by Howe to the probabilistic and quantum environment, it is shown, as non trivial result, that in probabilistic and quantum linear languages the bisimulation is contained in context equivalence relation.

With an increasing number of people who live in cities, urban mobility becomes one of the most important research fields in the so-called smart city environments. Urban mobility can be defined as the ability of people to move around the city, living and interacting with the space. For these reasons, urban accessibility represents a primary factor to keep into account for social inclusion and for the effective exercise of citizenship. In this thesis, we researched how to use crowdsourcing and participative sensing to effectively and efficiently collect data about aPOIs (accessible Point Of Interests) with the aim of obtaining an updated, trusted and completed accessible map of the urban environment. The data gathered in such a way, was integrated with data retrieved from external open dataset and used in computing personalized accessible urban paths. In order to deeply investigate the issues related to this research, we designed and prototyped mPASS, a context-aware and location-based accessible way-finding system.

Choreographies are a relatively new tool for designing distributed systems from a global viewpoint. Moreover, choreographies are also free from deadlocks and race conditions by design. Recent theoretical results defined proper Endpoint Projection (EPP) functions to compile choreographic specifications into their single components. Since EPPs are behavioural preserving, projected systems also enjoy freedom from deadlocks and races by construction. Aim of this PhD is to formalise non-trivial features of distributed systems with choreographies and to translate our theoretical results into the practice of implemented systems. To this purpose, we provide two main contributions. The first contribution tackles one of the most challenging features of distributed development: programming correct and consistent runtime updates of distributed systems. Our solution is a theoretical model of dynamic choreographies that provides a clear definition of which components and behaviours can be updated. We prove that compiled choreographic specifications are correct and consistent after any update. We also refine our theoretical model to provide a finer control over updates. On this refinement, we develop a framework for programming adaptable distributed systems. The second contribution covers one of the main issues of implementing theoretical results on choreographies: formalising the compilation from choreographies to executable programs. There is a sensible departure between the present choreographic frameworks and their theoretical models because their theories abstract communications with synchronisation on names (a la CCS/π-calculus) yet they compile to Jolie programs, an executable language that uses correlation — a renown technology of Service-Oriented Computing — for message routing. Our solution is a theory of Applied Choreographies (AC) that models correlation-based message passing. We pinpoint the key theoretical problems and formalise the principles that developers should follow to obtain correct implementations. Finally, we prove our approach by defining a correct compiler from AC to the calculus behind the Jolie language.

The continuous technological progress and the constant growing of information flow we observe every day, brought us an urgent need to find a way to defend our data from malicious intruders; cryptography is the field of computer science that deals with security and studies techniques to protect communications from third parties, but in the recent years there has been a crisis in proving the security of cryptographic protocols, due to the exponential increase in the complexity of modeling proofs. In this scenario we study interactions in a typed lambda-calculus properly defined to fit well into the key aspects of a cryptographic proof: interaction, complexity and probability. This calculus, RSLR, is an extension of Hofmann's SLR for probabilistic polynomial time computations and it is perfect to model cryptographic primitives and adversaries. In particular, we characterize notions of context equivalence and context metrics, when defined on linear contexts, by way of traces, making proofs easier. Furthermore we show how to use this techniqe to obtain a proof methodology for computational indistinguishability, a key notion in modern cryptography; finally we give some motivating examples of concrete cryptographic schemes.

In this thesis, the author presents a query language for an RDF (Resource Description Framework) database and discusses its applications in the context of the HELM project (the Hypertextual Electronic Library of Mathematics). This language aims at meeting the main requirements coming from the RDF community. in particular it includes: a human readable textual syntax and a machine-processable XML (Extensible Markup Language) syntax both for queries and for query results, a rigorously exposed formal semantics, a graph-oriented RDF data access model capable of exploring an entire RDF graph (including both RDF Models and RDF Schemata), a full set of Boolean operators to compose the query constraints, fully customizable and highly structured query results having a 4-dimensional geometry, some constructions taken from ordinary programming languages that simplify the formulation of complex queries. The HELM project aims at integrating the modern tools for the automation of formal reasoning with the most recent electronic publishing technologies, in order create and maintain a hypertextual, distributed virtual library of formal mathematical knowledge. In the spirit of the Semantic Web, the documents of this library include RDF metadata describing their structure and content in a machine-understandable form. Using the author's query engine, HELM exploits this information to implement some functionalities allowing the interactive and automatic retrieval of documents on the basis of content-aware requests that take into account the mathematical nature of these documents.

Biological data are inherently interconnected: protein sequences are connected to their annotations, the annotations are structured into ontologies, and so on. While protein-protein interactions are already represented by graphs, in this work I am presenting how a graph structure can be used to enrich the annotation of protein sequences thanks to algorithms that analyze the graph topology. We also describe a novel solution to restrict the data generation needed for building such a graph, thanks to constraints on the data and dynamic programming. The proposed algorithm ideally improves the generation time by a factor of 5. The graph representation is then exploited to build a comprehensive database, thanks to the rising technology of graph databases. While graph databases are widely used for other kind of data, from Twitter tweets to recommendation systems, their application to bioinformatics is new. A graph database is proposed, with a structure that can be easily expanded and queried.

A Smart City is a high-performance urban context, where citizens live independently and are more aware of the surrounding opportunities, thanks to forward-looking development of economy politics, governance, mobility and environment. ICT infrastructures play a key-role in this new research field being also a mean for society to allow new ideas to prosper and new, more efficient approaches to be developed. The aim of this work is to research and develop novel solutions, here called smart services, in order to solve several upcoming problems and known issues in urban areas and more in general in the modern society context. A specific focus is posed on smart governance and on privacy issues which have been arisen in the cellular age.