Ph.D. Program

Basic notions of algorithms and complexity; Divide-and-Conquer; Dynamic Programming; Basic data structures: heaps, hash tables; Greedy; Local Search; Network Flow; All-pairs Shortest Paths; NP-complete problems and intractability; PSPACE

Basics on formal models of (concurrent) computations, operational semantics and (labelled) transition systems, regular expressions, basic process algebras. Preliminary concepts of software verification, typical verification flow, common program analysis techniques, decision procedures. Basic concepts of software modelling and analysis with stochastic processes, discrete-time markov processes, and petri nets.

Basic concepts of software development paradigms, application domains, the software life cycle, design of software systems and modeling, software architectures. The course also provide some basic knowledge of the tools used to generate software programs from models.

How to write a paper. How to give a scientific talk. How to referee a scientific paper.

Basic notions of equilibrium: dominant versus Nash; computational issues of equilibria; performance of equilibria (price of stability and anarchy). Congestion games: congestion games, cost sharing games, load balancing; price of anarchy and stability; PLS-completeness; speed of convergence. Mechanism design and sponsored web search: Matching Markets; VCG mechanism; GSP mechanism.

Introduction to linear programming; the set cover problem; greedy algorithms and local search; rounding data and dynamic programming; deterministic rounding of linear programs; random sampling and randomized rounding of linear programs; the primal-dual method; techniques to prove the hardness of approximation

Graph mining: interpreting the past, understanding the present, imagining the future. A small world: computing and analysing the degrees of separation. A very small world: computing the diameter. Centrality measures: computing betweenness and closeness centrality. Giant components and bow-tie graphs: Kosaraju-Sharir algorithm and its applications. Link prediction: similarity-based techniques and recommendation systems. Temporal graphs.

Basics in probability theory; coupon collector and contention resolution; Yao’s principle and the secretary problem; the probabilistic method; Chernoff bounds; martingales and Azuma's inequality; random graphs; smoothed analysis.

Modelling and Analysis of Probabilistic Systems: Stochastic Process Algebras, Timed Automata, Markov Decision Processes, Queueing Networks. Uncertainty and Learning of quantitative properties. Guidelines on building simulation environments for Cyber-Physical Systems.

Modelling of reactive systems, review of the model checking approach, temporal logics (LTL, CTL, and CTL*), safety and liveness properties of reactive systems, fairness conditions.

The course will discuss the motivation for self-adaptation, the basic principles and system properties of autonomous and self-adaptive systems and how to engineer these kinds of systems. The course will also present concrete systems in the domain of e-Health, smart mobility, robotics, and recent advances in the literature.

This course will explore model-driven Engineering methodologies applied to practical case studies.The course will cover the basic knowledge of modeling, metamodeling, transformations, and code generation.

Software Quality is defined as a field of study and practice that describes the desirable attributes of software products. In this course we explore some of the methodologies to keep track, monitor and improve software quality with specific applications to development and modeling.

General concepts and techniques of software testing. Main concepts of dependability and reliability testing. Most interesting research challenges in software testing.

Ethical algorithm design. Basics of machine learning. Algorithmic privacy. Algorithmic fairness. Explainability of supervised machine learning. Algorithmic robustness.

This course introduces students to data processing in Python. It first builds the necessary toolset by introducing popular Python libraries for data manipulation/visualization (NumPy, Pandas), applied to simple applications. The toolset is then applied to a more complex case study on the classification of benign and malignant breast cancer. The course concludes presenting KNIME, a popular python-integrated workflow-based language for data analysis.

We introduce Multiplicative Weights Update as a meta-algorithm based on the survey by Arora, Hazan, and Kale from '12. As a motivation, we start with the Weighted majority algorithm. We then introduce the Multiplicative Weights Update routine as a general framework and then present several applications of this framework. (1) We show that the framework can be used to approximately solve zero-sum games, this goes back to a result by Freund and Schapire from '99. (2) We outline how the framework yields approximate solutions to packing and covering LPs going back to a result by Plotkin, Shmoys, and Tardos from '95. (3) We discuss the connection of the presented framework to Randomized rounding LP relaxations, a result by Young from '95. (4) We briefly discuss the relation to boosting in learning theory.

Generally speaking, Secretary Problems and Prophet Inequalities are two classes of optimal stopping problems, both of which combine online decision making and stochasticity, and both of which have received a lot of attention in the last two decades.

Consider the following simple problem: you are presented with a sequence of $n$ numbers, one by one, and your objective is to pick the largest one in the sequence. However, you must make your decision in an online fashion: every time a new number is revealed, you have to make an immediate and irrevocable decision of picking it (and thus the procedure ends) or refusing it (you are allowed to see the next number).

Without any limitations on the adversary that is feeding you the input, there is no strategy that guarantees anything better than a 0-approximation. The situation changes when (1) the input is allowed to be adversarial but it is revealed to the algorithm in a random order, or (2) the input is allowed to arrive in an adversarial order but is drawn from a priori known distributions.

Furthermore, the simple problem described above can be generalized to more involved settings, where we need to pick more than one element subject to some constraints.

In this course, we will survey some results, proofs, and techniques, mostly for generalizations of the simple problem described above, under the assumptions (1) and (2). Such generalizations, together with assumptions (1) and (2), are termed Secretary Problems and Prophet Inequalities, respectively.

This course is about theory of distributed computing. We will learn about some of the most studied models of distributed computing, with focus on synchronous and fault-free models.

We start from the basics: we formally define the distributed setting and what is a distributed algorithm, illustrating the formal definition with some simple examples. Then we slowly build up on this, focusing at the beginning on simple networks such as rings, and learning how to solve, in this setting, simple fundamental tasks such as coloring, maximal independent set, and maximal matching.

Next, we will discuss the topic of decidability: given a problem, can we automatically decide what is its asymptotic distributed complexity? We will see that for a large class of problems, on ring networks, this is actually possible.

After that, we switch to more general network topologies, and we will see how to solve some tasks in this setting.

Finally, we will see some impossibility results. In particular, we will see how to prove lower bounds for the distributed complexity of some classical problems.

A basic knowledge about graph theory and big-O notation is assumed.

Parameterized complexity theory aims at a refined analysis of computational problems. An instance of a problem is not only measured by its size, but also by a natural-number parameter that classifies its inner structure. Many intractable problems are `fixed-parameter tractable', which can mean that they are tractable in practice for small-parameter instances.

The course treats Algorithmic aspects (A) and Formal-Methods viewpoints (FM) of parameterized complexity. In (A) we focus on definitions/basic properties, kernelization, dynamic programming with graph-width parameters, and in (FM) on Courcelle's Theorem for obtaining fpt-results by expressing problems as logical formulas, and the W/A-hierarchies of complexity classes based on model checking problems.

The ASM (Abstract State Machines) are a method for the rigorous design and development of software systems. They are an extension of Finite State Machines and allow the modeling of a system in terms of computation automata. To facilitate the use of ASMs and facilitate their use in software engineering processes, ASMETA (Asm METAmodeling) - https://asmeta.github.io/ has been developed, an integrated environment of tools that assist the user during the various specific and analysis activities (validation and verification) of a model. The course is aimed at presenting ASMETA and the features offered. Through simple case studies the development process of a specific ASM in ASMETA is presented starting from the requirements, the different simulation techniques (random and scenario-driven) and animation of models are shown, and the verification of simple temporal properties. We will show also how to obtain C++ code that can be executed for instance on an Arduino.

Topics:

• Introduction to hybrid system falsification: models of hybrid systems, specification languages (Signal Temporal Logic), and stochastic optimization for falsification;

• Advanced falsification techniques: strategies for efficient state space exploration and design of functions for effective falsification guidance, using Monte Carlo Tree Search and Multi-Armed Bandits;

• Handling of constraints in falsification: penalty-based approaches and search-space transformation approaches;

• Confidence measures for falsification.

Many testing and program analysis techniques require sound and up-to-date software specifications to be effectively applied. Unfortunately, specifications are seldom available, and when they are available they are often outdated and cannot be used to test or analyse software programs. This advanced course will present testing, debugging and repairing solutions, with specific emphasis on the ones that can exploit automatically mined specifications. The first part of the course will present several specification mining techniques that can be used to extract different kinds of behavioural models. The second part of the course will present testing, debugging and repairing techniques with some more emphasis on the ones that exploit mined specifications.

ML and AI are increasingly dominating the high-tech industry. Organizations and technology companies are leveraging their big data to create new products or improve their processes to reach the next level in their market. However, ML and AI are not a silver bullet and Software 2.0 is not the end of software developers or software engineering. In this course we will discuss on how ML and AI can be probitably used in software engineering and on how, on the other side, software engineering can help ML and AI to become the key technology for (autonomous) systems of the near future.

Reinforcement Learning (RL) is a Machine Learning paradigm that addresses sequential decision-making problems in which intelligent agents interact with an environment to optimize a utility signal. In the last decade, RL has become a pervasive approach to deal with complex control tasks and has achieved significant results in several fields, including robotics manipulation, finance, self-driving cars, industrial plant automation, and news recommendation. This course aims to provide a self-contained overview of: i) the fundamental theoretical aspects of RL; ii) the essential RL algorithms (classical and modern ones); iii) some applications to real-world scenarios.

Science understands reality by designing models which allow to explain and predict observations of the real world. Simulation is the computation of the implications of a scientific model. Computers have been invented in order to run simulations fast and reliably, thus allowing for the investigation of complex models. In this course we'll confront the fundamental question "What is a good simulation?" and we'll progress toward an answer by introducing key theoretical ideas and by learning how to perform simulations using the Julia programming language.

Description Logics are formal languages for knowledge representations used to define ontologies. The Web Ontology Language (OWL) and its profiles are based on Description Logics. We will present the syntax and the semantics of the main Description Logics, and their computational complexity of reasoning. We will also present selected topics that occupy researchers and practitioners in the field, e.g.: ontology-based data access, concept learning, provenance, etc. We may use Protégé for a hands-on session.