Sign In


Sort by AttachmentsUse SHIFT+ENTER to open the menu (new window).
Alternative formulations for Integer Linear Programming ProblemsUse SHIFT+ENTER to open the menu (new window).
Luis Gouveia

Alternative formulations for Integer Linear Programming Problems: Part I

- The Asymmetric Travelling Salesman Problem (ATSP)
- Natural versus Extended formulations
- Creating a (compact) and extended formulation as a means of creating (by projection) a (exponential sized) natural formulation
- Strengthening the projected formulation. The Cut/Subtour formulation.
- Aggregated flow versus disaggregated flow formulations.
- Projecting the disaggregated flow formulation
- Separating cut constraints
- Some other problems: the Vehicle Routing Problem, the cumulative TSP and pick-up and delivery problems

Alternative formulations for Integer Linear Programming Problems: Part II

- Reformulation by Discretization
- Replacing two sets of variables (binary and integer) by one set of binary variables with an extra index.
- Time dependent formulations as discretized flow based formulations
- More general costs
- Application to Location problems: Chvatal Gomory Cuts and Modular Cost problems
- Other applications.
- Shortest Path Reformulations
- Constrained Shortest Path Problems modelled as Unconstrained Shortest Path Problems in adequate graphs
- Constrained Shortest path problems "reformulated" as Path Problems
- The case of the hop constrained shortest path problem
- The hop constrained shortest path problem: network flow models with a cardinality constraint versus the shortest path reformulation.

First part
Sala Seminari Est
Mon 8 Feb: 9:00/12:00
Tue 9 Feb: 9:00/12:00
Wed 10 Feb: 9:00/11:00
Thu 11 Feb: 9:00/11:00

Second part: 9 - 12 March
Sala Seminari Est

Tue  9/3: 14:00-17:00
Wed  10/3: 9:00-12:00
Thu  11/3: 14:00-16:00
Fri  12/3: 9:00-11:00


Proofs, complexity, and approximationUse SHIFT+ENTER to open the menu (new window).
Pierluigi Crescenzi

The PCP theorem:

gap problems and connection with the PCP theorem; expander graphs; error correcting codes; constraint graphs; composition lemma; the PCP theorem proof; applications to the theory of approximation algorithms

15 - 26 March: all lectures are in Sala Seminari W

Mon 15.3 & 22.3 -- 10-13
Tue 16.3 & 23.3 -- 10-12
Thu 18.3 & 25.3 -- 10-13
Fri 19.3 & 26.3 -- 10-12

(subject to changes)
New Semantic Tools in logic programmingUse SHIFT+ENTER to open the menu (new window).
James Lipton

This course will cover elements of category theory and categorical logic, as well as Kripke semantics and its relation to categorical semantics with special emphasis  on Logic Programming Applications.

The aim is to give a comprehensive and unified semantic treatment to a variety of logic programming languages and extensions, including several approaches to constraint logic programming, two formulations  of higher-order  logic programming (including constraints), and new approaches to modelling state and moinads in the logic programming context.

The course will provide a quick introduction to the categorical logic tools needed, including the basics of category theory, indexed and monoidal categories, as well as Kripke semantics.

The first week will be taken up with Kripke and Categorical Semantics for first and higher-order logic, and quick review of lambda prolog.

The second week we will look at models for the various logic programming language extensions mentioned above, with soundness and completeness results.

I will assume that the audience has seen some logic programming and the elements of its "classical" model theory based on fixed points. Also, familiarity with the lambda calculus, untyped and simply typed, as well as its elementary semantics would be helpful.

25-28, 31 May: 15 - 17.30  Sala Seminari W
1,3,4 June   : 15 - 17.30  Sala Seminari W

Classical and Quantitative Program AnalysisUse SHIFT+ENTER to open the menu (new window).
Herbert Wiklicky

The lectures will give an introduction to static program analysis.

We will first discuss classical data-flow analysises and their general formalisation as monotone frameworks. We will also discuss the issue of correctness of an analysis. In a second part the aim is to introduce the machinery of abstract interpretation which allows us to immediately construct a safe (and efficient) analysis based on the semantics of the target language. We will then discuss how to move from the original `possibilistic' approach, which determines what could happen when a program is executed, to a `probabilistic' one, where we try to estimate the chances that certain conditions are fulfilled. Finally, we will sketch application areas of this quantitative setting in, for example, computer security.

Related Books:
* Flemming Nielson, Hanne Riis Nielson, Chris Hankin:
         Principles of Program Analysis. Springer 2005.
* Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Monica S. Lam:
         Compilers: Principles, Techniques, and Tools. 2nd ed, Pearson 2006.

10-21 May -- 11-13
Sala Seminari W

Process algebras for quantitative analysisUse SHIFT+ENTER to open the menu (new window).
Jane Hillston, Stephen Gilmore

Basics of stochastic process algebras and Markov processes
Tackling state space explosion
Software support for stochastic process algebras
Service level agreements and response time
Applications in software systems and biological systems

8 - 12 February

Sala Seminari E:

Mon-Thu: 15-17

Fri: 9-11



15 - 16 February

Sala Riunioni W: 9-11


Statistical Machine TranslationUse SHIFT+ENTER to open the menu (new window).
Niladri Chatterjee

Machine Translation (MT) is one of the oldest and still far from solved challenges undertaken by computer science. The course will present an overview of the history, approaches, progress and difficulties of MT. The central topic of the course will be the statistical MT (SMT) approach introduced in the early 90's at IBM.

In particular, the following topics will be covered:
1.  Introduction to NLP and MT.
        The history, difficulties, problem of divergence, different paradigms.
2. Preliminaries.
         Basic knowleedge of text and speech processing, basic statistics/probability
3. Language Modeling.
         N-gram models,  Smoothing Techniques, Managing largse-scale data
4. Word-based Models
          Word alignment, EM algorithm, Fluency.
5. Higher Order Models and Overview of available Software.
6. Phrase-Based Translation
       Phrase extraction, Phrase Translation, Log-linear models, Reordering
7. Decoding
       Search algorithms, Hypothesis expansion, Hypothesis reduction.
8. Discrimininative Training
       Translation as Supervised learning, Feature extraction
9.  Hidden Markov Models. and Maximum Entropy
       Markov Process,  Application to texting Languages, Word Sense Disambiguation
10. Metrics for Evaluating Translation outputs.

April 12-23

Sala Seminari Est


Formal modelling and analysis of interactive systemsUse SHIFT+ENTER to open the menu (new window).
Antonio Cerone

The course will start by illustrating the challenge of taking human errors into account while modelling interactive systems and by investigating the nature and aspects of human error with reference to practical examples.

It will then present how to incorporate human behaviour in the modelling of interactive systems and how to apply model-checking methodologies to the formal analysis of such systems. This part of the course will focus on important cognitive aspects of human behaviour, such has the role of short-term memory in goal-based tasks and the switching between automaticity and attention, as well as the emergence of cognitive errors and their detection using model-checking.

Finally the course will show how to formalise task failures, how to use model-checking to verify the soundness and completeness of a task failure decomposition and how to give a psychological interpretation to the outcome of the model-checking analysis.

NOTE: dates may be subject to change after the first lecture.


1. Tuesday 7 December 2010, 9:30-12:30

2. Thursday 9 December 2010, 9:00-12:00

3. Tuesday 14 December 2010, 9:00-12:00

4. Wednesday 15 December 2010, 9:00-12:00

5. Thursday 16 December 2010, 9:00-12:00

6. Tuesday 21 December 2010, 9:00-12:00

7. Wednesday 23 December 2010, 9:30-11:30


Possible seminars (one of the examination options)

from Monday 27 to Thursday 30 December.

Semantica e teoria dei tipi (course of "Laurea Magistrale" (master degree))Use SHIFT+ENTER to open the menu (new window).
Ugo Montanari
Materials: Web site

2nd semester

Distributed Systems: Paradigms and Models (course of "Laurea Magistrale" (master degree))Use SHIFT+ENTER to open the menu (new window).
Marco Danelutto

1st Semester a.a. 2010-11

Bioinformatica (course of "Laurea Magistrale" (master degree))Use SHIFT+ENTER to open the menu (new window).
Nadia Pisanti

2nd semester