
  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 pickup 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:0017:00
Wed 10/3: 9:0012:00
Thu 11/3: 14:0016:00
Fri 12/3: 9:0011:00




  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  1013
Tue 16.3 & 23.3  1012
Thu 18.3 & 25.3  1013
Fri 19.3 & 26.3  1012
(subject to changes)




  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 higherorder 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 higherorder 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.

2528, 31 May: 15  17.30 Sala Seminari W
1,3,4 June : 15  17.30 Sala Seminari W




  Herbert Wiklicky 
The lectures will give an introduction to static program analysis.
We will first discuss classical dataflow 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.

1021 May  1113
Sala Seminari W




  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:
MonThu: 1517
Fri: 911
15  16 February
Sala Riunioni W: 911




  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
concepts
3. Language Modeling.
Ngram models, Smoothing Techniques, Managing largsescale data
4. Wordbased Models
Word alignment, EM algorithm, Fluency.
5. Higher Order Models and Overview of available Software.
6. PhraseBased Translation
Phrase extraction, Phrase Translation, Loglinear 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 1223
Sala Seminari Est
1113




  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 modelchecking 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 shortterm memory in goalbased tasks and the switching between automaticity and attention, as well as the emergence of cognitive errors and their detection using modelchecking.
Finally the course will show how to formalise task failures, how to use modelchecking to verify the soundness and completeness of a task failure decomposition and how to give a psychological interpretation to the outcome of the modelchecking analysis. 
NOTE: dates may be subject to change after the first lecture.
1. Tuesday 7 December 2010, 9:3012:30
2. Thursday 9 December 2010, 9:0012:00
3. Tuesday 14 December 2010, 9:0012:00
4. Wednesday 15 December 2010, 9:0012:00
5. Thursday 16 December 2010, 9:0012:00
6. Tuesday 21 December 2010, 9:0012:00
7. Wednesday 23 December 2010, 9:3011:30
Possible seminars (one of the examination options)
from Monday 27 to Thursday 30 December. 



  Ugo Montanari 

Materials: Web site 




  Marco Danelutto 
1st Semester a.a. 201011




  Nadia Pisanti 


