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.
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
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)
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
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.
* 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
|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:
15 - 16 February
Sala Riunioni W: 9-11
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.
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
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.
Sala Seminari Est
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.
|Materials: Web site|
1st Semester a.a. 2010-11