Sign In
 
 
 

Courses 2001

Sort by AttachmentsUse SHIFT+ENTER to open the menu (new window).
SyllabusFilter
Title Diffusione dell'informazione in grafi statici e dinamici
Teacher Prof. Pierluigi Crescenzi
Year 2013
Period
Syllabus

Rumor spreading is a well-known gossip-based distributed algorithm for disseminating information in large networks. According to the synchronous push version of this algorithm, an arbitrary source node is initially informed, and, at each time step (a.k.a., round), an informed node u chooses one of its neighbors v uniformly at random, and this node becomes informed at the next time step. In the symmetric pull version of the algorithm, at each time step, a not informed node u randomly chooses one of its neighbors v; if v is informed, then u becomes informed at the next time step. Finally, the push-and-pull version is a combination of the two previous versions, in which, at each time step, each informed node executes a "push operation", and each not informed node executes a "pull operation". Rumor spreading was first introduced in the context of replicated databases, as a solution to the problem of distributing updates and driving replicas towards consistency. Successively, it has been proposed in several other application areas, such as failure detection in distributed systems, peer-sampling, adaptive machine discovery, and distributed averaging in sensor networks. Apart from its applications, rumor spreading has also been deeply analyzed from a theoretical and mathematical point of view. In particular, the completion time of rumor spreading, that is, the number of steps required in order to have all nodes informed, has been investigated in the case of several different network topologies, such as complete graphs, hypercubes, random graphs, and preferential attachment graphs. Besides obtaining bounds on the completion time of  rumor spreading, most of these works also derive deep connections between the completion time itself and some classic measures of graph spectral theory, such as, for example, the conductance of a graph. The techniques and the arguments adopted in these studies strongly rely on the fact that the underlying graph is "static" and does not change over time. It is then natural to ask ourselves what is the speed of rumor spreading in the case of "dynamic" networks, where nodes and edges can appear and disappear over time (several emerging networking technologies such as ad hoc wireless, sensor, mobile networks, and peer-to-peer networks are indeed inherently dynamic). In this dynamic environment, even in the case of the simplest communication protocol that implements the broadcast operation, that is, the flooding protocol (according to which a source node is initially informed, and, whenever  an uninformed node has an informed neighbor, it becomes informed itself at the next time step), it has been shown that evolving graphs can exhibit communication properties which are much stronger than static networks. In this course, we will first review several results concerning the completion time of rumor spreading in the case of static networks. We will then present some results concerning the completion time of the flooding protocol, which have been obtained in the case of some interesting graph evolution models. Finally, we will present very recent results concerning the completion time of the push version of rumor spreading in the case of dynamic graphs.

 
Title Iterative rounding
Teacher Prof. Fabrizio Grandoni
Year 2013
Period
Syllabus

PREREQUISITES:
Attendees are expected to be familiar with elementary notions of linear algebra, probability theory and, possibly, complexity theory and linear programming. However, all the needed definitions and lemmas will be recalled during the seminars.

ABSTRACT:
IIterative Rounding is a recent, and very powerful tool to design
approximation algorithms. The basic idea is as follows. One solves a
(carefully chosen) linear programming relaxation of the considered
NP-hard  problem. Then one rounds some variable in the fractional
solution (which corresponds to fixing part of the solution under
construction) according to proper rounding rules. The problem is then
simplified, and the process is iterated on the residual problem until
a solution to the original problem is obtained. Alternatively or in
combination to rounding, one can also relax (i.e. drop) one
constraint. This leads to "slightly" infeasible solutions. In these
seminars we will describe a representative sample of the most relevant
results obtained via iterative rounding in the literature.

The seminars will be tentatively organized as follows. In the first
week, we will introduce approximation algorithms, and present a few
foundamental results and techniques in the area. The second week will
be devoted to approximation algorithms based on linear programming. We
will first introduce linear programming, and then present some
LP-based techniques in approximation algorithms. The final part of the
week will be devoted to iterative rounding.

 

Sala Seminari W

April 8-12  and  May 6-10
Mon: 16 - 18
Tue, Wed, Thu, Fri: 9 - 11


Title Security at work
Teacher Prof. Luca Viganò
Year 2013
Period
Syllabus

In the Internet of Services (IoS), systems and applications are no longer the result of programming components in the traditional meaning but are built by composing services that are distributed over the network and reconfigured and consumed dynamically in a demand-driven, flexible way. However, composing services leads to new, subtle and dangerous, vulnerabilities due to interference between component services and policies, the shared communication layer, and application functionality.
I will present the AVANTSSAR Platform and the SPaCIoS Tool, two integrated toolsets for the formal specification and automated validation of trust and security of applications in the IoS at design time and run time, respectively. Both toolsets have been applied as a proof of concept on a set of security problem cases drawn from industrial and open-source IoS application scenarios, thereby paving the way to transferring project results successfully to industrial practice and to standardization bodies and open-source communities.
I will present also a number of particular results that have been obtained in the AVANTSSAR and SPaCIoS projects, such as previously unknown attacks, compositionality results, novel attacker models and techniques for efficient security verification and testing.

 

 

May 27 -- June 5
Sala Seminari Ovest 11-13
(additional 4h t.b.a.)

 
Title Elaborazione del Linguaggio Naturale
Teacher Prof. Giuseppe Attardi
Year 2013
Period
Syllabus
 

Title Apprendimento Automatico: Reti Neurali e Metodi Avanzati
Teacher Prof. Alessio Micheli
Year 2013
Period
Syllabus
 
Title Analisi delle reti sociali
Teacher Prof. Dino Pedreschi
Year 2013
Period
Syllabus

Title Semantica e teoria dei tipi
Teacher Prof. Ugo Montanari
Year 2013
Period
Syllabus
 
Title Open Source Libraries and Tools for Computer Graphics
Teacher VCL Group ISTI
Year 2013
Period
Syllabus

General purpose computation:
Eigen  (<http://eigen.tuxfamily.org/>http://eigen.tuxfamily.org/ ;- speaker Gael Guennebaud )
ViennaCL (<http://viennacl.sourceforge.net/>http://viennacl.sourceforge.net/ ;- speaker Florian Rudolf)
OpenSlam-  g2o (<http://openslam.org/g2o.html>http://openslam.org/g2o.html ;- speaker Giorgio Grisetti)

3D Geometry
VCGLib  ( <http://vcg.sf.net/>http://vcg.sf.net/ ;- speaker Fabio Ganovelli o Paolo Cignoni)
PCL (<http://pointclouds.org/>http://pointclouds.org/ ;- speaker lexandru Ichim o Federico Tombari)

3D graphics for the web
Spidergl (<http://www.spidergl.org/>http://www.spidergl.org/  ;- speaker Marco Di Benedetto)


Title Reti mobili: reti ad hoc e di sensori
Teacher Stefano Chessa
Year 2013
Period
Syllabus

The course aims at providing knowledge on mobile ad hoc, mesh, and sensor
networks, by describing their organizations models and architectures, and by
presenting the main design and implementation issues. The course presents
the main issues at the MAC, network, transport, and application layers. In
particular it gives emphasis to the issues in routing, energy management,
topology control, and data management. It also presents some specific
applications for wireless sensor networks, such as localization and
tracking, and the problem of integration of wireless sensor networks in
context aware systems or in other networks. Finally the course presents some
standards, such as 802.11X, 802.15.x, Bluetooth and Zigbee, and gives some
examples of commercial platforms for wireless sensor networks.

 
Title Processes inspired by the functioning of living cells: Natural Computing approach
Teacher Prof. Dr. G. Rozenberg
Year 2013
Period
Syllabus

Natural Computing is an interdisciplinary research field that investigates human-designed computing inspired by nature as well as computation taking place in nature, i.e., it investigates models, computational techniques, and computational technologies inspired by nature as well as it investigates phenomena/processes taking place in nature in terms of information processing.

One of research areas from the second strand of research is  a computational understanding of the functioning of the living cell. We view this functioning in terms of formal processes resulting from interactions between (a huge number of) individual reactions. These interactions are driven by two mechanisms,  facilitation and inhibition: reactions may (through their products) facilitate or inhibit each other.

We present a formal framework for the investigation of these interactions.  We motivate this framework by explicitly stating a number of assumptions that hold for  processes resulting from these interactions, and we point out that these assumptions are very different from the ones underlying traditional models of computation. We discuss some basic properties of these processes, and demonstrate how
to capture and analyse, in our formal framework, some notions related to cell biology and biochemistry.

Research topics in this framework are motivated by biological considerations as well as by the need to understand the underlying computations. The models we discuss turned out to be novel and attractive from the theory of computation point of view. This is extensively discussed throughout the course.
 
The course is of a tutorial style and self-contained. In particular, no prior knowledge of biochemistry or cell biology is required.
 
The course is suited for master and PhD students as well as researchers and faculty members. It is of interest to computer scientists and mathematicians interested in formal models of computation as well as to bioinformaticians, biochemists, and biologists interested in foundational/formal understanding of biological processes.
 
The presented  framework was developed jointly with A.Ehrenfeucht from University of Colorado at Boulder.
 

May 20, 21, 22, 23  -- 10-13

Aula Magari, Pian dei Mantellini, 44, Siena.


Title Interactions, automata, and names
Teacher Emilio Tuosto
Year 2012
Period
Syllabus
Abstract:
Motivation/Overview: Automata are fundamental tools for research in computer science, logic, and mathematics. Notably, automata-based models have been introduced to capture aspects of modern concurrent and distributed systems. Also, automata have been used to investigate languages with richer structure than classical formal languages, more precisely, languages over infinite alphabets.Currently, researchers are studying unyfing models of those apparently complementary lines of research.
These lectures will review a few models of automata with names and/or automata over infinite alphabets.  Besides the theoretical aspects the course will also touch on the use of automata-based verification of concurrent systems.

Objectives: After successful completion of the course, participants
will
- undestand the current developments in the theory of automata with names
- acquire notions of nominal computations
- be able to apply automata-based techniques for modelling abstract computations
 
Title Combinatoria Enumerativa e Applicazioni all'Analisi degli Algoritmi
Teacher Simone Rinaldi e Andrea Frosini
Year 2012
Period
Syllabus

Introduction to Enumerative Combinatorics: how to count; bijective methods;
permutations; special numbers; generating functions; methods for
enumeration: inclusion/exclusion principle, Schueztemberger methodololgy,
ECO method; asymptotics.

Introduction to Discrete Tomography. How to model discrete finite objects,
and the concept of projection. The problems of consistency, uniqueness and
reconstruction in DT; main results. Different concepts of projection: recent
results and open problems.


Title Logica Matematica
Teacher Montagna
Year 2012
Period
Syllabus

Logica proposizionale. Semantica e calcoli a sequenti, completezza. Forme normali. Risoluzione proposizionale, completezza. Caso Horn. Cenni di teoria della complessità. Horn e 2-CNF-SAT sono in P, CNF-SAT è NP-completo.

Logica del primo ordine. Semantica di Tarski. Calcolo dei sequenti. Completezza. Teorema di Herbrand. Unificazione, risoluzione al primo ordine,  e sua completezza.

Macchine di Turing. Funzioni parziali ricorsive. Il problema dell'arresto. Definibilità degli insiemi r.e. nei numeri naturali. Indecidibilità dell'artmetica e della logica del primo ordine. Il Programma di Hilbert e il suo fallimento (Teoremi di Goedel).

Logiche non classiche (cenni). Logica intuizionista, semantica di Kripke. Logiche fuzzy e applicazioni a: (a) Gioco di Ulam con bugie; (b) probabilità; (c) controllo fuzzy (il tutto solo accennato).

Alcune lezioni saranno tenute dal Prof. Sorbi.

--- inizio previsto: 10 aprile

 
Title Fixed Points in Computer Science
Teacher Zoltan Esik, Dept. of Computer Science University of Szeged
Year 2012
Period
Syllabus
Fixed point operations are commonly used to describe the semantics of recursion. Most fixed point operations (metric fixed points, least or greatest fixed points, initial fixed points) in computer science satisfy the same equational properties that define iteration theories.
The equational axioms of iteration theories may be separated into two groups, the Conway identities and the group identities associated with the finite (simple) groups. In addition to equational axiomatizations, we will also cover axiomatizations by universal Horn sentences. A major result is that, in the ordered setting, the fixed point inequation together with the parameter inequation and the fixed point induction rule are complete for the equational theory. Moreover, by adding the operation of one-sided residuation, it is possible to obtain finite equational axiomatizations.
Fixed point operations are central to computer science. They occur in automata and language theory, programming semantics and programming logic, concurrency, computability and complexity, to mention a few areas.
We will  present applications of the theory of fixed points to these fields.

Title Modelli matematici in Biologia
Teacher Dott. Angelo Di Garbo, ricercatore presso l’Istituto di Biofisica del CNR di Pisa
Year 2012
Period
Syllabus

SCOPO: fornire agli studenti gli strumenti di base per lo studio teorico di sistemi biologici.

Sistemi dinamici discreti e continui. Stati stazionari e stabilita’. Soluzioni periodiche. Teoria delle biforcazioni. Teoria del caos deterministico.

Modelli discreti di popolazioni con singola specie: analisi dell’equilibrio e comportamento caotico.

Modelli continui di popolazioni con singola specie.

Dinamica di popolazioni con piu’ specie interagenti: modello di Lotka-Volterra.

Modelli matematici del sistema immunitario, di malattie infettive e di crescita tumorale.

Modelli neurali: Hodgkin-Huxley, FitzHugh-Nagumo, Integrate & Fire.

Dinamica degli enzimi e modelli in biologia molecolare. Dinamica del calcio cellulare.

Equazione di Fisher. Teoria lineare e nonlineare del DNA. Formazione di patterns. Instabilita’ di Turing. Modelli di crescita tumorale.

Cenni sull’analisi non lineare di segnali biologici: serie temporali, teorema di Takens, determinazione dei parametri di ricostruzione dello spazio delle fasi. Stima di invarianti dinamici.

 

Libri consigliati:
- J.D. Murray, Mathematical Biology, Springer-Verlag (1989);
- Materiale fornito dal docente.

 
Title Web Mining and Social Network Analysis
Teacher Dino Pedreschi - Università di Pisa, Knowledge Discovery and Data Mining Lab
Year 2012
Period
Syllabus
Corso della laurea magistrale - undergraduate course
 
Goals
 
Over the past decade there has been a growing public fascination with the complex "connectedness" of modern society. This connectedness is found in many contexts: in the rapid growth of the Internet and the Web, in the ease with which global communication now takes place, and in the ability of news and information as well as epidemics and financial crises to spread around the world with surprising speed and intensity. These are phenomena that involve networks and the aggregate behavior of groups of people; they are based on the links that connect us and the ways in which each of our decisions can have subtle consequences for the outcomes of everyone else.
 
This course is an introduction to the analysis of complex networks, with a special focus on social networks and the Web - its structure and function, and how it can be exploited to search for information. Drawing on ideas from computing and information science, applied mathematics, economics and sociology, the course describes the emerging field of study that is growing at the interface of all these areas, addressing fundamental questions about how the social, economic, and technological worlds are connected.
 
Syllabus
 
1) Graph theory and social networks
Graphs
Social, information, biological and technological networks Strong and weak ties Networks in their surrounding context
 
2) The World Wide Web
The structure of the Web
Link analysis and Web search
Web mining e sponsored search markets
 
3) Network dynamics
Information cascades
Power laws and rich-get-richer phenomena The small-world phenomenon
Epidemics
 
Textbooks
 
David Easley, Jon Kleinberg: Networks, Crowds, and Markets. http://www.cs.cornell.edu/home/kleinber/networks-book/
 
Reading:
M. E. J. Newman: The structure and function of complex networks, SIAM
Review, Vol. 45, p. 167-256, 2003.
A.-L. Barabasi. Linked. PLUME, Penguin Group, 2002.
Duncan J. Watts. Six Degrees: The Science of a Connected Age. Norton, New York, 2003.

Title Internet: Structure, Statistical Analysis and Dynamic Evolution
Teacher Luciano Lenzini, Dipartimento Ingegneria dell'Informazione, Università di Pisa
Year 2012
Period
Syllabus
Abstract:
Many large natural, social, and technological systems can be successfully described within a unified formalism that combines elements of graph theory and statistical physics. This formalism has been developed in the last few years, and has already become the so-called science of complex networks.
This course provides an introduction to the Internet in terms of it being a complex network.
Two main aspects are addressed: measurement systems and modeling the temporal evolution.
 
The course is thus structured into two parts covering:

Internet as a Graph and Measurement Issues
This part introduces the basic concepts that allow the Internet to be described as a graph, and outlines how to measure topological information. It covers the goals of various kinds of Internet measurements, the challenges in measuring the Internet, the methods and tools that have been developed to carry out such measurements, and the results that have been obtained to date in this field .

Modeling the Internet Dynamic
Most of the networks observed in nature and technology have a scale-free nature, characterized by the presence of power-law distributions. This part reviews this class of scale-free network models (Barabasi-Albert Models) which until a few years ago were used to model the temporal evolution of the Internet.
However, recent Internet measurements have proved that Internet growth can no longer be modeled by the Barabasi-Albert model. This part of the course will conclude by showing how international research is attempting to recover from this model.
 
Bibliography relevant for the course:
- G. Caldarelli, "Scale-Free Networks: Complex Webs in Nature and Technology", Oxford University Press (2007)
- S.N.  Dorogovtsev and J.F.F.  Mendes.  "Evolution of Networks", Oxford University Press (2003)
- R.  Pastor-Satorras and A.  Vespignani, "Evolution and Structure of the Internet", Cambridge University Press (2004)
 
Sala Seminari Ovest: NEW SCHEDULE

Mercoledi 18 aprile, ore 9-11, aula Seminari Est


Giovedi 19 aprile, ore 9-11, aula Seminari Est


Lunedi 23 aprile, ore 9-11, aula Seminari Est


Martedi 24 aprile, ore 9-11, aula Seminari Est


Mercoledi 2 maggio, ore 9-11, aula Seminari Est


Giovedi 3 maggio, ore 9-11, aula Seminari Est


Venerdi 4 maggio, ore 9-11, aula Seminari Ovest

 
 
Title STT - Semantica e Teoria dei Tipi
Teacher Ugo Montanari
Year 2012
Period
Syllabus
Corso della laurea magistrale - undergraduate course
 
Finalità del Corso
Verranno presentate alcune proprietà fondamentali dei modelli di calcolo, come la semantica operazionale ed astratta, la struttura dei tipi, l'ordine superiore, la concorrenza, l'interazione. Verranno utilizzate la semantica algebrica e la teoria elementare dei tipi, ma non vi sono prerequisiti eccetto una conoscenza elementare dell'algebra e della logica.
 
Programma del Corso
Il lambda calcolo con tipi semplici
L'isomorfismo di Curry-Howard
Il PCF e il suo modello cpo, con applicazione ai linguaggi di programmazione funzionali Elementi di tipi ricorsivi e polimorfi, con applicazione ai linguaggi di programmazione orientati agli oggetti Le categorie come algebre parziali Categorie monoidali, cartesiane e cartesiane chiuse (CCC) Le CCC come modelli del lambda calcolo con tipi semplici Specifiche algebriche, categorie di modelli e aggiunzioni La semantica operazionale come costruzione universale Le reti di Petri e i loro modelli monoidali (strettamente) simmetrici I sistemi di riscrittura etichettati (LTS) come coalgebre I sistemi LTS composizionali come bialgebre Il Calculus for Communicating Processes (CCS) e il Pi-calcolo di Milner e i loro modelli bialgebrici.
 
Materiali Didattico:
John Mitchell, "Foundations for Programming Languages", MIT Press,
1996. Capitoli:
2.5,4,5,7.2,9,10,11.
Note manoscritte.
 
Orario del Corso: da definire.
Modalita' d'Esame: Da definire.

Attachment
Title Advanced programming models & paradigms for multicore and distributed architectures
Teacher Marco Danelutto
Year 2012
Period
Syllabus
Vedere immagine allegata.
 
Title Advanced Topics in Cloud and P2P Computing
Teacher F.Baiardi (FB), L.Ricci(LR), D.Sgandurra(DS)
Year 2012
Period
Syllabus

The course is focused on the methodologies that aim to improve security and safety in the complex virtual networks underlying cloud or p2p computing. In this context, we will present virtualization technology as an enabling technology, policies and mechanisms to solve the challenging security problems posed by cloud computing. The second part of the course introduces the epidemic approach as a tool to improve the safety of p2p systemand it presents both the underlying mathematical models and a set of applications exploitingthis paradigm.

 
Topics 
Cloud Computing: Taxonomy and Enabling Technologies       2 h.    FB  
    
Attacks and Countermeasures
    cloud cartography                                     2 h.    FB
    proof of retrievability                               2 h.    FB
    xss /xsrf                                             2 h.    FB
    introspection, attestation, trusted computing         2 h.    DS
    homomorphic encryption                                2 h.    FB
 
P2P Computing: epidemics Protocols
    Discrete Time Markov Chains: Definition, Convergence, Solving Markov Chains,  2 h. LR
    Random Walks on Graphs: Applications: Web Search, P2P Search, Encounter-times in Mobile Networks 2 h. LR
 Epidemic on Networks: SI and SIR model, Fluid Models, Applications: P2P search, Virus spread, Advertising. 2 h. LR:
 Gossip Algorithms: Random Peer Sampling, Overlay Construction, Security in P2P overlays 2 h. LR.


Examination:     In depth examination of a subject related to the course topics

Title Apprendimento Automatico: Reti Neurali e Metodi Avanzati
Teacher Alessio Micheli
Year 2012
Period
Syllabus
Corso della laurea magistrale - undergraduate course (6CFU)
 
 
Title A framework for processes inspired by the functioning of living cells: Natural Computing Approach
Teacher Grzegorz Rozenberg
Year 2012
Period
Syllabus

Title Theory and Application of Timed Automata Model Checking
Teacher Prof. Frits Vaandrager, Radboud University Nijmegen
Year 2011
Period
Syllabus
Motivation/Overview: As our daily lives depend increasingly on digital systems, the reliability of these systems becomes a concern of overwhelming importance, and as the complexity of the systems grows, their reliability can no longer be sufficiently
controlled by traditional approaches of testing and simulation. It becomes essential to build mathematical models of these systems, and to use (algorithmic) verification methods to analyse these models. During recent years there has been enormous
progress in the area of model checking. In this course, an overview will be presented of model checking tools&techniques for timed automata, a framework that is particularly useful for the specification and analysis of embedded systems. The
application of these techniques will be illustrated on industrial sized examples taken from the areas of embedded real-time systems, distributed algorithms and protocols.
Participants learn how to make models and how to analyse them using state-of-the-art techniques and tools.
Objectives: After successful completion of the
course, participants are able to:
  • recognize situations in which the applications of timed automata model checking
    techniques for specification and analysis may be useful,
  • explain the modelling framework and basic theory of timed automata,
  • model (critical parts of) embedded systems as networks of timed automata,
  • formalize desired properties of these systems in terms of automata or temporal logic,

Period: 2-14 May

May 2:       9 - 12

May 3-6:    9 - 11

May 9-11:   9 - 11

 
Title Proof theory with applications to computation and deduction
Teacher Prof. Dale Miller, Ècole Polytechnique, LIX
Year 2011
Period
Syllabus
The first week (the first 10 hours) will cover material taken from my lecture notes titled "Proof Search and Computation" (draft dated February 2010 or later). The goals of this first week are
  1. introduce the students to the basics of the sequent calculus,
  2. provide some formal results covering the proof-search approach to computation,
  3. present the basics of linear logic and how it can be used to make the logic
    programming paradigm more expressive.

The second week (the second 10 hours) will expand the role of the sequent calculus from the specification of logic programming computations to the more general settings of model checking and induction.

Period: 12-24 September  --  daily 9-11 -- Sala Riunioni Ovest


Title Ambient Intelligence, Media, and Sensing
Teacher Nicu Sebe, University of Trento
Year 2011
Period
Syllabus

I. Synopsis
This course will focus on three main areas:
(1) multimodal interaction: visual (body, gaze, gesture) and audio (emotion) analysis;
(2) image databases, indexing, and retrieval: context modeling, cultural issues, and machine learning for user-centric approaches;
(3) multimedia data: conceptual analysis at different levels (feature, cognitive, and affective).

II. Motivation
Computer Vision plays a fundamental role in many new types of interfaces and application areas (multimodal and attentive interfaces, applications such as surveillance, medicine, art, etc.) in which humans play a central role. This implies that building Computer Vision systems (e.g., for human-computer interaction, etc.) lies at the crossroads of many research areas (psychology, artificial intelligence, pattern recognition, multimedia, etc.). Although many existing intelligent systems were designed with human uses in mind, many of them are far from being user friendly or are rooted on real-world human-needs (few Computer Vision systems can be considered "Human-Centered"). What are the current trends in computing and what can the scientific/engineering community do to effect a change for the better?

On one hand, the fact that computers are quickly becoming integrated into everyday objects (ubiquitous and pervasive computing) implies that effective natural humancomputer
interaction is becoming critical (in many applications, users need to be able to interact naturally with computers the way face-to-face human-human interaction takes place). On the other hand, the wide range of applications that use multimedia, and the amount of multimedia content currently available, imply that building successful computer vision and multimedia applications requires a deep understanding of multimedia content. The success of human-centered vision systems, therefore, depends highly on two joint aspects:

  1. the way humans interact naturally with such systems (using speech and body language) to express emotion, mood, attitude, and attention, and
  2. the human factors that pertain to multimedia data (human subjectivity, levels of interpretation).

This course takes a holistic approach toward developing human-centered vision systems. The aim is to identify the important research issues, and to ascertain potentially fruitful future research directions in relation to the two aspects above. In
particular, the course will introduce key concepts, discuss technical approaches, and open issues in three areas:

  1. multimodal interaction: visual (body, gaze, gesture) and audio (emotion) analysis;
  2. image databases, indexing, and retrieval: context modeling, cultural issues, and
    machine learning for user-centric approaches;
  3. multimedia data: conceptual analysis at different levels (feature, cognitive, and affective).

The focus of the course, therefore, is on technical analysis and interaction techniques formulated from the perspective of key human factors in a user-centered approach to developing Human-Centered Vision Systems.

III. Benefits & List of Topics
This course will enable the understanding of key concepts, state-of-the-art techniques, and open issues in:

  • Media sensing and processing, sensor data management, mining, and data streams, basic signal processing
  • Vision for multimodal interaction: overview of techniques and state of the art in
    body tracking, gaze detection, and gesture recognition.
  • Multimodal emotion recognition for affective retrieval and in affective interfaces: approaches to multimedia content analysis and interaction that use speech and facial
    expression recognition.
  • Machine learning: adaptive multimodal interfaces and learning of visual concepts from user input for automatic detection and recognition (detection of scenes, objects,
    or events of interest).
  • Multimodal fusion: technical approaches and issues in combining multiple media (e.g., audio-visual) for multimodal interaction and multimedia analysis.
  • Multimedia indexing: an overview of how humans perceive, index, organize, and search multimedia content. Discussion of studies in art, psychology, library sciences,
    and the development of conceptual frameworks for computational frameworks.
  • Human issues: the role of memory, subjectivity, culture, context, and examples of technical approaches to multimedia analysis and interaction that consider these
    factors.
  • Applications: traditional and emerging application areas will be described with specific examples in smart conference room research, arts, interaction for people with
    disabilities, entertainment, and others.

IV. Materials
This course will be specifically designed for a broad audience -- while the focus of the course will be technical, the aim is to give the students a broad view of research and important topics for developing Human-Centered Vision Systems. Materials will
include overviews of technical approaches for Vision-Based Human-Computer Interaction, Human-centered Computing, Artificial intelligence, etc.

 

Period: 16 May      ---     16.30 -- 18.30 Sala Seminari Ovest

            17-20 May and 30 May - 3 June      ---     10 -- 12 Sala Seminari Ovest

 
Title Structured parallel programming
Teacher Marco Danelutto
Year 2011
Period
Syllabus
Da definire

Title From Mobility Data Management to Privacy-aware Analysis and Locationbased Services
Teacher Yannis Theodoridis, Nikos Pelekis (U. Piraeus)
Year 2011
Period
Syllabus

Description:
A flood of data pertinent to moving objects is available today, and will be more in the near future, particularly due to the automated collection of telecom data from mobile phones and other location-aware devices. Such wealth of data, referenced both in space and time, may enable novel classes of applications and services of high societal and economic impact, provided that the discovery of consumable and concise knowledge out of these raw data is made possible. Recent research activities have developed theory, techniques and systems for geographic (particularly, mobility) data management and analysis as well as services that take advance of this data, the socalled Location-based Services (LBS).

In this course, we will present the required infrastructure, Moving Object Database (MOD) engines, as well as methods and
techniques for efficient management, analysis, and mining of mobility data, towards advanced location-aware applications and services. The theoretical lectures will be accompanied and synchronised with exercises and hands-on experience lab modules on a robust and widely cited MOD engine.

Course Outline (proposed: 15 hrs theory + 5 hrs labs)

  • Introduction
  • the background (2 + 0 hrs): GIS and Spatial DBMS; An overview of LBS
  • Mobility database management (3 + 3 hrs): Models and systems for MODs; MOD indexing and querying
  • Mobility data analysis (3 + 2 hrs): OLAP and KDD techniques for MODs
  • Location-based services (2 + 0 hrs): Location- vs. trajectory- aware LBS
  • Privacy aspects on mobility data management (3 + 0 hrs): Privacy-preserving LBS and KDD
  • Outlook (2 + 0 hrs): Open research issues; project proposals
 
Title Geospatial Visual Analytics
Teacher Gennady and Natalia Andrienko, Fraunhofer FIAIS, Bonn, Germany
Year 2011
Period
Syllabus

The course introduces Visual Analytics – a new research discipline defined as the science of analytical reasoning facilitated by interactive visual interfaces. Visual analytics combines automated analysis techniques with interactive visualizations so that to extend the perceptual and cognitive abilities of humans and enable them to extract useful information and derive knowledge from large and complex data and to solve complex problems. Particularly, data and problems involving geospatial components and time are inherently complex and therefore call for visual analytics approaches.
We present a system of exploratory data analysis tools and methods, including interactive maps, statistical graphics and multiple coordinated displays, data transformations applicable to spatial and temporal data, and appropriate computational techniques such as cluster analysis and aggregation. We consider analytical questions related to spatial time series and to spatially
distributed events, describe general types of patterns that can be found in such data, and suggest appropriate visual analytics methods.

We discuss in more detail the problems of analyzing data about movement of various discrete objects in geographical space. We consider three types of movement data: data describing movements of a single entity during a long time period, data
about simultaneous movements of multiple unrelated entities, and data about simultaneous movements of multiple related entities. The pertinent analysis tasks significantly differ for these types of data. For each type of data, we briefly introduce the visual analytics techniques and tools we have developed in the recent years.


Title Correctness by Construction with SPARK
Teacher Carlo Montangero
Year 2011
Period
Syllabus

Preliminary program:
Language issues: restrictions for verification feasibility.
Verification I: information flow control.
Verification II: design by contract.
Verification III: data abstraction and refinement.
Tool support

 

Goals:
The purpose of the course is to present state-of-the-art techniques and tools to develop secure, safe, and modular programs. SPARK is a real language - a sub/superset of Ada - and an environment that supports automatic verification to large extent. Verification is based on the classical pre-post conditions approach. The course will provide adequate introduction to the tools.
Program:
Language issues: restrictions for verification feasibility.
Verification I: information flow control. Tool support.
Verification II: design by contract. Tool support.
Verification III: data abstraction and refinement. Tool support.
Materials:
J. Barnes. High Integrity Software. Addison Wesley. 2006. ISBN 978-0-321-13616-9.

Assessment: either a project in SPARK or a seminar on competitive techniques.
 

 
 
Title Resiliency in cloud e overlay
Teacher F.Baiardi, L.Ricci, D.Sgandurra
Year 2011
Period
Syllabus

Il corso è focalizzato sulle metodologie che permettono di aumentare sicurezza ed affidabilità in reti virtuali complesse quali quelle che sono alla base delle strategie utilizzate da sistemi cloud o P2P. In questa ottica vengono presentate tecnologie di virtualizzazione, meccanismi e politiche per affrontare e risolvere i nuovi problemi di sicurezza ed affidabilità posti da questi sistemi. Infine sono discusse le metodologie e gli algoritmi per la diffusione affidabile di informazioni su reti virtuali.




The course is focused on the methodologies that aims to improve security and safety in complex virtual networks such as those underlying cloud or p2p computing. In perspective, we will present virtualization technology as an enabling technology, policies and mechanisms to solve the challenging security problems posed by cloud computing and a set of algorithms to improve the safety of p2p system together with the mathematical model to evaluate the advantages of their adoption



Docenti



F.Baiardi (FB)


L.Ricci,  (LR)


D.Sgandurra, (DS)




Argomenti



Sistemi Cloud: definizioni di base, proprietà e tecnologie abilitanti       2 ore    FB        


Modello dei guasti e delle minacce     2 ore    FB


Attacchi e contromisure


    cloud cartography                           2 ore    FB


    proof of retrievability                       2 ore    FB


    xss e xsrf                                        2 ore    FB


    introspezione, attestazione             2 ore    DS


    homomorphic encryption                2 ore    FB


Epidemic Protocols


                   algoritmi di gossip: peer sampling, security                  2  ore       LR              


    modelli matematici per algoritmi epidemici            2 ore     LR


                   applicazioni                                              2 ore     LR



Topics  



Cloud Computer: Taxonomy and Enabling Technologies        2 h.    FB        


Threat Modelling                                                                      2 h.    FB


Attacks and Countermeasures


    cloud cartography                         2 h.    FB


    proof of retrievability                     2 h.    FB


    xss /xsrf                                        2 h.    FB


    introspection, attestation, trusted computing        2 h.    DS


    homomorphic encryption                                      2 h.    FB


Epidemic Protocols


                   gossip algorithms: peer sampling, security           2 h.     LR              


    mathematical models for epdemic algorithmi                       2 h.     LR


                   applicazioni                                                            2 h.     LR




Periodo:     Settembre/Ottobre 2011


Esame:     seminario su argomenti presentati nel corso


Title High Performance Computing and Enabling Platforms, 6 CFU, in inglese, primo semestre
Teacher Marco Vanneschi
Year 2011
Period
Syllabus
Abstract: This course deals with two strictly interrelated issues:
1. fundamental concepts and techniques in parallel computation structuring and
design, including parallelization methodologies and paradigms, parallel programming
models and their implementation, and related cost models;
2. architectures of high-performance computing systems, including shared memory
multiprocessors, distributed memory multicomputers, clusters, and others.
Both issues are studied in terms of structural models, static and dynamic support to
computation and programming models, performance evaluation, capability for
building complex and heterogeneous applications and/or enabling platforms, also
through examples of application cases. Technological features and trends are studied,
in particular multi-/many-core technology and high-performance networks
 
Title Distributed Systems: Paradigms and Models
Teacher Marco Danelutto
Year 2011
Period
Syllabus
9 CFU, nel secondo semestre

Title Apprendimento Automatico: Reti Neurali e Metodi Avanzati
Teacher Alessio Micheli
Year 2011
Period
Syllabus
Crediti: 6, Semestre: 2
È un corso avanzato di Machine Learning, per il design di modelli innovativi e
metodologico per applicazioni in aree interdisciplinari
 
Title Elaborazione del Linguaggio Naturale
Teacher Giuseppe Attardi
Year 2011
Period
Syllabus
secondo semestre

Title Reti Mobili: Reti ad hoc e di sensori
Teacher Stefano Chessa
Year 2011
Period
Syllabus
II semestre
 
Title STT - Semantica e Teoria dei Tipi
Teacher Ugo Montanari
Year 2011
Period
Syllabus
Modelli di Calcolo di Sistemi Funzionali, Concorrenti e Interattivi
 
Finalita' del Corso
===================
Verranno presentate alcune proprietà
fondamentali dei modelli di calcolo, come la
semantica operazionale ed astratta, la struttura
dei tipi, l'ordine superiore, la concorrenza,
l'interazione. Verranno utilizzate la semantica
algebrica e la teoria elementare dei tipi, ma
non vi sono prerequisiti eccetto una conoscenza
elementare dell'algebra e della logica.

Programma del Corso
===================
Il lambda calcolo con tipi semplici
L'isomorfismo di Curry-Howard
Il PCF e il suo modello cpo, con applicazione ai
linguaggi di programmazione funzionali
Elementi di tipi ricorsivi e polimorfi, con
applicazione ai linguaggi di programmazione
orientati agli oggetti
Le categorie come algebre parziali
Categorie monoidali, cartesiane e cartesiane chiuse (CCC)
Le CCC come modelli del lambda calcolo con tipi semplici
Specifiche algebriche, categorie di modelli e aggiunzioni
La semantica operazionale come costruzione universale
Le reti di Petri e i loro modelli monoidali (strettamente) simmetrici
I sistemi di riscrittura etichettati (LTS) come coalgebre
I sistemi LTS composizionali come bialgebre
Il Calculus for Communicating Processes (CCS) e
il Pi-calcolo di Milner e i loro modelli
bialgebrici.

Materiali Didattico:
====================
John Mitchell, "Foundations for Programming
Languages", MIT Press, 1996. Capitoli:
2.5,4,5,7.2,9,10,11.
Note manoscritte.

Orario del Corso
================
mercoledi' 11.00-13.00 in Aula Mancini
venerdi' 11.00-13.00 in Aula Mancini.

Modalita' d'Esame
=================
Da definire.


Title Alternative formulations for Integer Linear Programming Problems
Teacher Luis Gouveia
Year 2010
Period
Syllabus

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.

 
Title Proofs, complexity, and approximation
Teacher Pierluigi Crescenzi
Year 2010
Period
Syllabus

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


Title New Semantic Tools in logic programming
Teacher James Lipton
Year 2010
Period
Syllabus

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.
 

 
Title Classical and Quantitative Program Analysis
Teacher Herbert Wiklicky
Year 2010
Period
Syllabus

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.
 


Title Process algebras for quantitative analysis
Teacher Jane Hillston, Stephen Gilmore
Year 2010
Period
Syllabus

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

 
Title Statistical Machine Translation
Teacher Niladri Chatterjee
Year 2010
Period
Syllabus

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


Title Formal modelling and analysis of interactive systems
Teacher Antonio Cerone
Year 2010
Period
Syllabus

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.

 
Title Semantica e teoria dei tipi (course of "Laurea Magistrale" (master degree))
Teacher Ugo Montanari
Year 2010
Period
Syllabus

Title Distributed Systems: Paradigms and Models (course of "Laurea Magistrale" (master degree))
Teacher Marco Danelutto
Year 2010
Period
Syllabus
 
Title Bioinformatica (course of "Laurea Magistrale" (master degree))
Teacher Nadia Pisanti
Year 2010
Period
Syllabus

Title Calculus of Computation: Decision procedures with applications to analyzing and developing robust software.
Teacher Zohar Manna http://theory.stanford.edu/~zm/
Year 2009
Period 20th September - 8th October --- All lectures will be at 11-13 in Sala Seminari W
Syllabus

Foundation: Logic review. Propositional and first-order logic; induction.
Verification: Methods for proving correctness of sequential programs using first-order reasoning; need for decision procedures.
Decision procedures: Algorithms that decide the validity of logical formulas for common theories including SAT, equality, arithmetic, recursive data structures, and arrays. Combination theories and combination of decision procedures.

 
Title Privacy and anonymity in location- and movement-aware data analysis
Teacher Fosca Giannotti, Dino Pedreschi, Franco Turini KDD Lab Università di Pisa and ISTI-CNR, Pisa, Italy
Year 2009
Period June 15-July 17 --- all lectures will be in Sala Seminari W
Syllabus

The course shall focus on the issue of privacy and anonymity in location-aware and movement-aware data, presenting an original account of the newly emerging and active research areas of:
* privacy and anonymity in location-based services: models of location-privacy that support anonymity of mobile users during real-time service;
* privacy and anonymity in mobility data analysis: models of privacy and anonymity threats for mobility data publishing and mobility data mining, and related privacy-preserving techniques for secure mobility data publishing and secure mobility data mining.


Title Web search (in two parts)
Teacher S. Muthukrishnan http://www.cs.rutgers.edu/~muthu/                       and           Aristides Gionis http://research.yahoo.com/bouncer_user/34
Year 2009
Period 1st part: June - 2nd part Winter
Syllabus

Theory of Sponsored Search Auctions
S. Muthukrishnan, Google Inc.

Web search engines are becoming an increasingly important advertising medium. When a user poses a query, in addition to search results, the search engine also returns a few advertisements. On most major search engines, the choice and assignment of ads to positions is determined by an auction among all advertisers who placed a bid on some keyword that matches the query. The user might click on one or more of the ads, in which case (in the pay-per-click model) the advertiser receiving the click pays the search engine a price determined by the auction. While economic and game theory provide a well-developed framework for understanding auctions in general, the particular instance of sponsored search auctions presents new challenges.
In traditional auctions, the auctioneer and the buyers are the only active players, with the commodity being inert. Here, the value of the commodity itself is determined by the behavior of search engine users which introduces complications. Further, different advertisers and users have widely different goals and behavior, so simple utility models may not capture the hybrid mix of these players in the auction.
Also, the game consists of not just a single auction, or even several repeated auctions, but rather a portfolio of auctions that are run corresponding to the entire ensemble of user queries. In presence of budgets, a study of such a portfolio of auctions becomes challenging. Finally, the scale of this operation with billions of events a day brings focus on computational challenges, more so than in most auction scenarios.
This course will cover the theory behind the auction for a single user query. This part of the course will discuss classical auction theory, the new concepts and techniques developed to understand the current sponsored search auctions, and discuss some open issues as we attempt to generalize these auctions. In the second part, we take a more global view and discuss auctions for the ensemble of user queries. Many optimization issues are involved, and the tutorial will discuss the basic theory here. Finally, we will discuss some new directions and open problems.


Topics in web mining and next-generation search
Aris Gionis, Yahoo! Research.

In the classic paradigm of Internet, there is a clear distinction between the users who publish content and those users who search for information. Evolving from this classic paradigm, the Internet is becoming a medium for establishing social connections, publishing information in a cooperative manner, making economic transactions, sharing experiences, and being entertained. In this new social environment the borders between information producers and information consumers are becoming increasingly fuzzy. Searching for information in this new environment creates a new information-search paradigm that offers more capabilities and allows users to find high quality information tailored to their needs. On the other hand, the volume and heterogeneity of the available data makes the search problem considerably more challenging.
Another very important and rich source of web data, which complement content data, are access logs. Dealing with access logs can be a very challenging task due to the extremely large volume of the data and the presence of noise. On the other hand, access logs are very valuable because they record direct information about the interests of users and their feedback in the system. Thus, mining access logs can provide very useful cues about user behavior, it can help extracting latent knowledge such as folksonomies, and it may be used to improve web applications.
In this course we will present selected topics and discuss recent research papers in the above areas of web mining, namely mining query logs and user-generated content.

 
Title Structural Operational Semantics
Teacher Simone Tini, Università dell'Insubria
Year 2009
Period July 6-16 -- all lectures are in Sala Seminari W, 11-13
Syllabus

Description: Structural Operational Semantics (SOS) provides a framework to give an operational semantics to programming and specification languages. In particular, concurrent process calculi are usually equipped with an SOS. The idea of SOS is to generate Labeled Transition Systems (LTSs) from Transition System Specifications (TSSs), namely sets of Transition Rules of the form premises/conclusion, which describe how moves of a process can be inferred from moves of its subprocesses.

Contents:
1. Preliminaries.
* Labeled Transition Systems,
* Behavioral Equivalences and Preorders,
* Term Algebras,
* Transition System Specifications.

2. The meaning of Transition System Specifications. Associating an LTS with a TSS is not immediate if "negative premises" appear in the transition rules. Several approaches have been proposed.
* Model-Theoretic Approach,
* Proof-Theoretic Approach,
* Stratification-Based Approach.

3. Conservative Extensions. When a language equipped with an SOS is extended with new features, are we sure that all processes specified with the original language keep the same behavior? The notion of Conservative Extension is an answer to this question.
* Operational Conservative Extension,
* Applications to Axiomatizations,
* Applications to Rewriting.

4. Congruence Formats. Instead of proving a result for a given language, one can attempt to establish results holding for classes of languages. The idea behind the notion of "format" is that the languages are classified on the basis of the syntactic form of the transition rules.
* Panth Format for bisimulation,
* Ntree Format,
* De Simone Format and De Simone Languages,
* GSOS Format,
* RBB Safe Format for weak bisimulation,
* Precongruence Formats for Behavioral Preorders.

5. Non classic SOS. Applications of SOS theory to probabilistic languages and to the non interference security property are showed.
* Rule Formats for Non-Interference.
* Rule Formats for Probabilistic Languages.


Title Fondamenti di Logica
Teacher Simone Martini
Year 2009
Period May-June
Syllabus
Sistemi in deduzione naturale e a sequenti per la logica classica e intuizionista. Relazioni tra i due.
- Teoria della dimostrazione: eliminazione del taglio e/o normalizzazione. Consequenze.

Qualche argomento a scelta tra i seguenti:
- Lambda-calcolo tipizzato e la corrispondenza di Curry-Howard. Normalizzazione forte; Confluenza.
- Logica lineare: sequenti, reti di dimostrazioni. Cenni alla semantica Logiche leggere e relazioni con la complessita' computazionale implicita
- Logiche modali classiche: semantica, modelli di Kripke, relazione di accessibilita'.

Il docente e` disponibile a trattare i classici teoremi limitativi (Goedel, Church, Tarski), nel caso in cui l'uditorio ne avesse necessita`.
 
Title Biological Sequence Analysis
Teacher Esko Ukkonen University of Helsinki http://www.cs.helsinki.fi/u/ukkonen/
Year 2009
Period Sept. 28 -- Oct. 8
Syllabus

Computational analysis of biological sequences (DNA, RNA, protein sequences) is in the core of bioinformatics. The course will give an introduction to the computational toolbox in the area. The emphasis will be on algorithms, and the approach is a mixture of probabilistic and combinatorial techniques. In addition to the classic algorithms for pairwise and multiple alignments and for database searches also some novel topics on high-throughput sequencing, gene regulatory motifs and haplotypes will be covered.

Contents (tentative)
Introduction
- biological sequences
- probabilistic models of sequences
Pairwise alignment - motivation
- scoring schemes: BLOSUM etc
- global alignment: Needleman-Wunsch algorithm
- local alignment: Smith-Waterman algorithm
- significance of alignment scores: Karlin-Altschul statistics
Similarity searches in databases
- basic dynamic programming
- heuristic improvements: Blast
- index-based approach: dynamic programming over suffix tree
The fragment assembly problem
- the classic three-step algorithm
- practical improvements
- implications of the new high-throughput sequencing technologies
Multiple alignment
- scoring schemes
- basic solution by dynamic programming
- some heuristic improvements
Hidden Markov Models (HMMs) for sequence families
- HMM definition and basic techniques (Viterbi, Forward)
- building multiple alignments
- HMM learning using EM algorithm
Sequence motifs for transcription factor binding
- families of motifs
- suffix-tree techniques for substring motifs
- position weight matrix (PWM)
- learning PWMs with EM from high-throughput data
Fast search methods for PWMs
- significance thresholding
- naive algorithm
- more advanced algorithms
Gene regulatory motifs
- gene regulatory elements in DNA
- predicting putative elements: the EEL algorithm
The haplotyping problem (if time allows)
- genotypes and haplotypes
- HMM approach to haplotyping


Title Packing and cutting problems
Teacher Valerio De Carvalho
Year 2009
Period
Syllabus
April 20 - 24
 
Title Teoria dell'Informazione (undergraduate course)
Teacher Francesco Romani
Year 2009
Period 2nd academic semester
Syllabus

Title Tecniche di specifica e dimostrazione (undergraduate course)
Teacher Ugo Montanari
Year 2009
Period 2nd academic semester
Syllabus
 
Title Topics in Integer Programming
Teacher J.M. Valério de Carvalho http://pessoais.dps.uminho.pt/vc/
Year 2009
Period Period to be defined
Syllabus

Title Privacy nell'analisi dei dati (Privacy and anonymity in mobility data mining and location-based services)
Teacher Dino Pedreschi, Franco Turini e Fosca Giannotti, Pisa KDD Laboratory, Universita' di Pisa e ISTI-CNR
Year 2008
Period Second semester
Syllabus
Argomenti:
 
The technologies of mobile communications and ubiquitous computing pervade our society, and wireless networks sense the movement of people and vehicles, generating large volumes of mobility data. This is a scenario of great opportunities and risks: on one side, mining this data can produce useful knowledge, supporting sustainable mobility and intelligent transportation systems; on the other side, individual privacy is at risk, as the mobility data contain sensitive personal information. A new multidisciplinary research area is emerging at this crossroads of mobility, data mining, and privacy.
This course precisely addresses the problem of privacy and anonymity of location and mobility data, on the basis of the experience gathered in a large-scale European research initiative, the GeoPKDD project – Geographic Privacy-aware Knowledge Discovery and Delivery http://www.geopkdd.eu – which is coordinated by the instructors.
In its introductory part, the course will introduce:
  • the advocated scenario of location-aware and movement-aware data, services and analytical opportunities;
  • the privacy and anonymity threats and the privacy-preserving and anonymity- preserving techniques developed in the general case of relational data for supporting safe data publishing and data mining.

On this basis, the course shall focus on the issue of privacy and anonymity in location-aware and movement-aware data, presenting an original account of the newly emerging and active research areas of:

  • privacy and anonymity in location-based services: models of location-privacy that support anonymity of mobile users during real-time service;
  • privacy and anonymity in mobility data analysis: models of privacy and anonymity threats for mobility data publishing and mobility data mining, and related privacy-preserving techniques for secure mobility data publishing and secure mobility data mining.
Riferimento:
Fosca Giannotti, Dino Pedreschi (Eds.) Mobility, Data Mining and Privacy, Springer, publication December 2007 ISBN 978-3-540-75176-2
http://www.springer.com/978-3-540-75176-2
 
 
Title Bayesian Data Analysis
Teacher Ercan Kuruoglu, ISTI-CNR, Pisa
Year 2008
Period May 5-30
Syllabus
Argomenti:
 
Bayesian data analysis methods have become increasingly important in many fields such as economics, bioinformatics, computer science in the last decade. In particular, the Bayesian approach has received an ever increasing momentum in the field of signal processing, and classical statistical signal processing has been revolutionised into Bayesian signal processing. This change has been reflected immediately to applications such as image segmentation, audio restoration and machine vision with great success. This course aims to equip interested graduate students with the necessary theoretical background and the technical tools and also to present them various applications where Bayesian data analysis had and would have important potentials. Latest developments in the Bayesian field such as particle filters will also be presented which are hoped to lead to new research ideas in the classroom.
  • Introduction to Bayesian Estimation Theory
    • History,
    • Bayes theorem,
    • Classical versus Bayesian interpretation of probability,
    • Bayesian philosophy
  • Posterior distribution
    • Point estimation based on posterior
  • Prior distribution
    • Non-informative priors
    • Jeffrey's prior
    • Conjugate priors
  • Single parameter models, multiparameter models
    Hierarchical models
  • Sampling
    • Why sampling?
    • Reverse sampling
    • Rejection sampling
    • Importance sampling
    • Monte Carlo sampling
  • A review of Markov chain theory
    • Markov processes
    • Stationary distribution
    • Ergodicity
    • Irreducibility
  • Markov chain Monte Carlo
    • Relation with statistical mechanics
    • Metropolis method
    • Metropolis-Hastings
    • Gibbs sampling
    • Relation with simulated annealing
    • Reversible jump MCMC
    • Advanced topics: convergence, multiple MCMC, etc
  • Sequential Monte Carlo
    • Filtering non-stationary signals (Kalman filter and its extensions)
    • Unscented Kalman filter
    • Particle filter
  • Applications (2 hours)
    • Telecommunications , Image Processing, Bioinformatics , Computer vision , etc

 


Title Mathematical Models and Algorithms for the Web
Teacher Paolo Ferragina e Fabrizio Luccio, Dipartimento di Informatica, Università di Pisa
Year 2008
Period March, April
Syllabus
Argomenti:
Modern information retrieval and data mining applications for the Web need to carefully cope with the specialties and size of Web structure and content in order to be efficient and scalable. In this course we will address these two issues discussing, on the one hand, the mathematical laws governing network growth and, on the other hand, the design of efficient algorithms that store and search huge amount of data.
In the first part, we will study the mechanisms according to which a network can grow under random and/or hand-directed rules, going from the classical "random graph process" to the "preferential linking" behavior of the Web. Mathematical analisys will be validated by experimental evidence. In particular, models of random and intentional networks attacks will be examined.
In the second part, we will address the new algorithmic challanges posed by the processing of large datasets and by the architectural features of the memory hierarchy of current computers. These issues force algorithmic designers and engineers to address simultaneously data compression (fitting more data in the faster/smaller memory levels) and cache-friendly data access (exploiting the accessing features of memory levels). We will survey basic and sophisticated techniques useful to cope with this new scenario.
 
 
Title Virtual Machines
Teacher Antonio Cisternino, Vincenzo Gervasi, Dipartimento di Informatica, Università di Pisa
Year 2008
Period February 25 - March 7
Syllabus
  • Introduzione alle virtual machines JVM e CLR
  • Specifica di una virtual machine
    • Modello con Abstract State Machines della JVM
    • Modello con semantica operazionale (Gordon e Syme)
    • Lo standard CLI
  • Type system
    • Inheritance model
    • Bounded parametric polymorphism
    • Interoperability
  • Implementazione di una virtual machine: il CLR
    • Rotor (JIT, Garbage Collector, Generics)
    • Mono (differenze con Rotor)
    • Struttura dei binari (dati e metadati)
  • Compilare per una virtual machine
    • Compilatori JVM e CLR
    • ILX e i linguaggi funzionali
    • I linguaggi dinamici
  • Runtime Code Generation
    • Manipolare il bytecode
    • Generazione di codice al volo
    • Annotated C# e Code Bricks

Title Advances in medical applications of Artificial Intelligence
Teacher Paolo Lisboa, John Moores University - Liverpool
Year 2008
Period February 7-14
Syllabus
  • 1-5. Generic principles of neural networks in medical applications
    • Introduction to the concept of neural networks.
    • Concept of self-organisation - SOM, overview of GTM; examples from Magnetic Resonance Spectroscopy (MRS).
    • Automatic adaptive learning - ART model. Simple example from MRS.
    • MLP with regularisation. Examples from medical classification - Cushing's data.
    • Bayesian regularisation framework. Examples from medical classification – Parkinson's.
    • Basic structure of the SVM.

References [1, 2, 3, 4, 6, 7, 8, 9, 10, 13]

  • 6-7. Survival analysis and prognostic modelling for oncology
    • PLANN
    • PLANN-ARD
    • PLANNCR-ARD
    • Examples from breast cancer prognosis and, hopefully, also applied to GIMEMA data.

References [11, 14]

  • 38 Automatic rule extraction from data
    • OSRE model.
    • Examples from MRS, breast cancer and other medical data including some bioinformatics.

References [5, 12]

  • 9-10 Clustering and visualisation for bioinformatics
    • Optimisation of k-means models.
    • Direct visualisation of clusters in 3-D.
    • Example from Ferrara bioinformatics dataset

Reference [15]

Riferimenti:
 
  1. Ripley, B.D. "Can Statistical Theory Help Us to Use Neural Networks Better?" Proc. Interface 97, 29th Symposium on the Interface: Computer Science and Statistics, 1997. http://www.stats.ox.ac.uk/~northrop/teaching/PAN/Interface97.pdf
  2. Lampinen, J. and Kostiainen, T."Overtraining and model selection with the self-organising map" Proc. IJCNN'99, Washington, DC, USA. http://citeseer.ist.psu.edu/420998.html
  3. Lisboa. P.J.G., Vellido, A. and Wong, H."Bias Reduction in Skewed Binary Classification with Bayesian Neural Networks" Neural Networks, 13, 407-410, 2000.
  4. Huang, Y., Lisboa, P.J.G. and El-Deredy, W."Tumour grading from Magnetic Resonance Spectroscopy: a comparison of feature extraction with variable selection" Statistics in Medicine, 22, 1, 147-164, 2003.
  5. Etchells, T.A. and Lisboa, P.J.G."Rule extraction from neural networks: a practical and efficient approach" IEEE Transactions on Neural Networks, 17 (2):374-384, 2006.
  6. Vellido, A. and Lisboa, P.J.G."Handling outliers in brain tumour MRS data analysis through robust topographic mapping" Journal of Computers in Biology and Medicine, 36 (10): 1049-1063, 2006.
  7. Barton, G.J., Lees, A., Lisboa, P.J.G. and Attfield, S."Visualisation of gait data with Kohonen self organising neural maps" Gait and Posture, 24, 1: 46-53, 2006.
  8. Lisboa, P.J.G. and Taktak, A.F.G."The use of artificial neural networks in decision support in cancer: A Systematic Review", Neural Networks, 19: 408-415, 2006.
  9. Barton, G.J., Lees, A., Lisboa, P.J.G. and Attfield, S."Gait Quality Assessment Using Self-Organising Artificial Neural Networks", Gait and Posture, 25, 3: 274-379, 2007.
  10. Fisher, A.C., El-Deredy, W., Hagan, R.P., Brown, M.C. and Lisboa, P.J.G."Removal of eye movement artefacts from single channel recordings of retinal evoked potentials using dynamical embedding and independent component analysis" Medical and Biological Engineering and Computing 45, 1:69-77, 2007.
  11. Taktak, A., Antolini, L., Aung, M.H., Boracchi, P., Campbell, I., Damato, B., Ifeachor, E.C, Lama, N., Lisboa, P.J.G, Setzkorn, C., Stalbovskaya, V. and Biganzoli, E.M."Double-blind evaluation and benchmarking of prognostic models in a multi-centre study" accepted for Computers in Medicine and Biology.
  12. Aung, M.S.H, Lisboa, P.J.G., Etchells, T.A., Testa, A.C., Van Calster, B., Van Huffel, S., Valentin, L. and Timmerman, D."Comparing Analytical Decision Support Models Through Boolean Rule Extraction: A Case Study of Ovarian Tumour Malignancy" accepted for Lecture Notes in Computer Science.
  13. Vellido, A., and Lisboa, P.J.G."Neural Networks and other Machine Leaning Methods in Cancer Research" accepted for Lecture Notes in Computer Science 4507-0996.
  14. Jarman, I.H., Etchells, T.A. and Lisboa, P.J.G."A Data-based Decision Support System for Breast Cancer Prognosis" accepted for Artificial Intelligence in Medicine.
  15. Lisboa, P.J.G., Ellis, I.O., Green, A.R., Ambrogi, F."Cluster-based visualization with scatter matrices" submitted to Pattern Recognition Letters.
 
Title Privacy and Security in Wireless ad Hoc Network
Teacher Roberto di Pietro, Dipartimento di Matematica, Universita' Roma Tre
Year 2008
Period May 5-16 (first lesson: May 5 16.00-18.00)
Syllabus
Schedule:
5/5 Lu: 16-18 aula riunioni OVEST
6/5 Ma: 16-18 aula riunioni OVEST
7/5 Me: 9-11 aula riunioni OVEST
7/5 Me: 16-18 aula riunioni OVEST
8/5 Gi: 16-18 aula riunioni OVEST
12/5 Lu: 16-18 aula seminari EST
13/5 Ma: 16-19 aula seminari EST
14/5 Me: 16-19 aula seminari EST
15/5 Gi: 16-18 aula seminari EST

Mobile ad hoc networks (MANETs) and Wireless Sensor Networks (WSN) are able to provide fast and efficient network deployment capabilities in a wide variety of scenarios where a fixed networking infrastructure is not possible. Unfortunately, many proposed security solutions contain strong assumptions or they didn’t well adapt to the characteristics of MANETs or WSNs. In this course we will review some of the security issues and solutions for MANET and WSN. Further, we will also address privacy issues in a two rising research areas, where the call for innovative solutions is demanding, that is Radio Frequency IDentifiers and vehicular ad hoc networking (VANET). The organization of the course is thought to raise also active participation of the attendees; at the end of each lecture, one hour is dedicated to discuss research issues/ideas that could foster cooperation among participants.
  • Introduction to security issues in mobile, resource constrained devices. (2h)
  • Confidentiality Issues in WSN (3h + 1 hour discussion)
  • Replicated Nodes Detection in WSN (3h + 1 hour discussion)
  • Authentication for resource constrained devices (3h + 1 hour discussion)
  • Privacy issues in RFID and VANETS (2h + 1 hour discussion, 2h + 1 hour discussion)

 


Title An introduction to dynamical systems (a comparative study of discrete and continuous dynamical systems and of their stability)
Teacher Frederico de Oliveira-Pinto, Universidade Indipendente, Lisboa, Portugal
Year 2008
Period June 23 - July 11
Syllabus
Discrete systems:
  • Introduction
  • Recurrence and difference equations
  • General solutions of discrete systems
  • Equilibrium values
  • Dynamical stability
  • Examples of linear systems with exponential growth and known general solutions
  • Analytical solutions of discrete linear versus continuos linear growth models
  • Quadratic dynamical systems
  • Discrete quadratic versus logistic systems
  • Closed-form solutions for discrete quadratic and discrete cubic dynamical systems with "chaotic" behaviour
  • Study of theis intrinsic instability
Continuous systems:
  • Volterra-type predator-prey systems
  • Military fighting models
Schedule:
  • 23 June -- 4 July, everyday: 15-17 Sala Seminari EST
  • 7 July -- 11 July, everyday: 15-17
    Riferimenti:
    1. G. Fulford et al. - "Modelling with differential and difference equations", Cambridge University Prees, 1997.
    2. R.A.Holmgren - "A first course in Discrete Dynamical Systems", (2 Ed), Springer, 1996.
    3. F. Oliveira-Pinto and M. Adibpour - "Analitical solutions of one-dimensional Discrete Dynamical Systems with "chaotic" behaviour", Non-linear Dynamics, 1 (1990) p 121 - 129.
    4. F. Oliveira-Pinto and B.W. Conolly - "Applicable Mathematics of non-physical phenomena", Ellis Horwood, Chicherter, a Division of J. Wiley and Sons, 1982.
    5. J.T. Sandefur - "Discrete Dynamical Systems, Theory and Applications", Claredon Press, Oxford, 1990.
  •  
    Title The rCOS Method for Component-Based and Model Driven Development
    Teacher Zhiming Liu, UNU-IIST, Macao
    Year 2008
    Period June 30 - July 11
    Syllabus
    Model driven development is a most promising approach to separation of concerns in design of complex software systems. It employs a UML-like multi-view and multi-notational language for describing the models of the system at different stages in the development. It also supports component-based design and allows developers to design systems at a higher level of abstraction using models or specifications of components. They will be produced and integrated at a later implementation, assembly and deployment stage.
    However, a major challenge in the practice of model-based software development is to ensure correctness and dependability of the software product. To deal with this challenge, we need a common semantics for the multi-view modeling approach, and a method for verification and reasoning about models of different views, correct refinement of models, and consistently relating the models of different views. Tool support for such a method needs to integrate sophisticated visual and editing tools for model construction, transformers for correctness preserving model transformations, checkers and provers for verification of properties of models. The method, techniques and tools have to be incorporated into existing software development processes and environment.
    In this course, we introduce a method, called rCOS, that we recently developed for Refinement and Verification in Component-Based Model Driven Development. The outline of the content of the course is:
    • Introduction: the state of the art in practical software engineering, the current status of formal methods, the motivation and theme of rCOS
    • Unifying Theories of Programming (UTP) in a Nutshell: the semantic foundation of rCOS
    • The theory of rCOS a). component-based modelling and refinement: interfaces, contracts, components, composition (connectors), coordination and glue. b). object-oriented modelling and refinement: classes, objects, references, polymorphism, subtyping, dynamic binding, oo refinement
    • Development process and case study
    • Tool support: UML profile for rCOS, model transformations and model verification and analysis
    Schedule: Every day: 11-13 in Sala SEMINARI EST

    Exam: select one of
    • Group project: each group of two or three can work on their own identified project by using the rCOS method. It can be an object-oriented system, a component-based project, a project that needs both component-based and object-oriented modelling and design.
    • Seminar: Relate rCOS to your own research interest
    Course materials:
    1) Slides will be given before or at the lectures
    2) Downloadable publications about rCOS at http://rcos.iist.unu.edu

    Title Natural Language parsing and translation
    Teacher Marcello Federico, Fondazione Bruno Kessler - Trento
    Year 2008
    Period May 7-19 (first lesson: May 7, 15.00 - 17.00)
    Syllabus
    Machine Translation (MT) is one of the oldest and still far from being solved challenges taken on by computer science. The course will start by briefly reviewing the history, approaches, progress, and difficulties of MT. The central topic of the course will be the statistical MT approach introduced in the early 90's at IBM. In particular, the following topics will be covered: statistical framework of MT, word alignment models, log-linear models, training and search algorithms, speech and text translation, performance evaluation. Alternative MT approaches will be discusses, and current research trends in the field will be presented.
     
    Title Formal Methods for Interacting Systems
    Teacher Antonio Cerone, UNU-IIST, Macao
    Year 2007
    Period January-February
    Syllabus
    Argomenti: Task analysis. Task Models. Interface Generation. Cognitive Models. Task Failure and Behavioural Patterns. Cognitive Architectures. Security and Usability. Reverse Engineering with Matrix Algebra.
     

    Title Computational Combinatorial Optimization
    Teacher Claude Lemarechal, INRIA Montbonnot, Bordeaux, Francia
    Year 2007
    Period May
    Syllabus
    Riferimento:
    C. Lemarechal, Lagrangian relaxation
    In: Computational Combinatorial Optimization
    Eds. Junger and D. Naddef
    Springer, Heidelberg, 2001
    pp. 112-156

     
     
    Title Model Checking
    Teacher Enrico Tronci, Dipartimento di Informatica, Università di Roma "La Sapienza"
    Year 2006
    Period February 2-24
    Syllabus
    Argomenti:
    1. Sistemi Ibridi: HyTech (3h)
    2. Algoritmi di Model Checking Esplicito: Murphi, SPIN. (3h).
    3. Model Checking Simbolico:
      • OBDDs (2h)
      • CTL (2h)
      • mu-calculus via OBDDs (2h)
      • SMV, VIS (2h)
    4. Bounded Model Checking: bmc, SAT, zchaff (2h)
    5. Probabilistic Model Checking: PRISM, FHP-Murphi (2h)
    6. Software Model Checking: Survey (2h), CMC (2h).
    7. Counterexample Guided Abstraction Refinement (2h).

    Title Interpretazione astratta per l'analisi e la verifica di linguaggi dichiarativi
    Teacher Prof. Giorgio Levi, Dipartimento di Informatica, Università di Pisa
    Year 2006
    Period April 4-27
    Syllabus
    Argomenti:
     
    1. Introduzione all'interpretazione astratta
    2. Inferenza dei tipi via interpretazione astratta
    3. Programmazione logica: semantica e analisi
    4. Verifica via interpretazione astratta
    5. Operatori di raffinamento
     
    Title Categorical structures for system modelling
    Teacher Jose Luiz Fiadeiro, Professor of Software Science and Engineering, Department of Computer Science - University of Leicester
    Year 2006
    Period May
    Syllabus
    The focus of this series of lectures is the support that category theory can bring to the modelling of complex software systems. It consists of an introduction to basic and more advanced categorical concepts and techniques using examples drawn from concurrency theory, algebraic specification (namely institutions) and software architecture (the language CommUnity). Our ambition is to show how category theory can provide a unifying, truly 'universal' approach to the handling of different levels of complexity that arise in the development of large and interaction-intensive systems. The course will be supported by the book "Categories for Software Engineering", Springer 20 (http://www.fiadeiro.org/jose/CATBook/)

    Title Logica per l’informatica
    Teacher Andrea Masini, Dipartimento di Informatica, Università di Verona
    Year 2006
    Period First two weeks of May
    Syllabus
    Argomenti:
     
    • Logica Classica del I ordine:
      1. Sintassi e semantica;
      2. problemi di formalizzazione;
      3. deduzione naturale;
      4. correttezza e completezza;
    • 2) Logica Intuizionista:
      1. semantica;
      2. deduzione naturale;
      3. interpretazione BHK e teorie dei tipi;
    • Cenni ad altri sistemi deduttivi: sequenti, tableaux.
     
    Title Computational Models based on Rewriting
    Teacher Andrea Corradini, Fabio Gadducci, Dipartimento di Informatica, Università di Pisa
    Year 2006
    Period After mid May
    Syllabus
    Argomenti:
    Several computational models describe the evolution of systems using some rewriting mechanism: a set of rules is given, and a system moves from one state to the next one by applying a rule.
    Depending on the structure of the states, such formalisms are presented with different names (Chomsky grammars, Petri nets, term rewriting systems, graph grammars,...) and a rich body of literature has been developed for each of them.
    The goal of the course is to introduce the basics of several of such computational models in a uniform way, stressing their similarities and highlighting their differences. Moving from simpler to more complex models, basic notions of universal algebra and of category theory will be introduced, as they will provide a more adequate language as well as useful proof techniques.
    For the various formalisms introduced, the main application fields will be briefly surveyed.
    A preliminary list of topics (to be further refined during the first lessons) includes:
    • Abstract rewriting systems: relational presentation, basic definitions (residuation and equivalence), termination, confluence
    • Term rewriting systems: algebraic presentation (terms, substitutions, unification) and equational reasoning (equational logic), basic definitions and results (validity and decidability), confluence (critical pairs, completion), permutation equivalence, proof terms
    • Petri Nets: multiset-presentation, basic definitions and results, termination, reachability, parallelism, processes
    • Graph rewriting systems: categorical presentation, basic definitions and results, parallelism, processes
      Applications: basic overview on the use of rewrite systems for the specification of concurrent and distributed systems
    • Verification: basic overview on the analysis techniques so far available for rewrite systems, and their use in applied case studies
      Tools: basic overview on the available tools (as the Java applets collected on http://www.informatik.uni-hamburg.de/TGI/PetriNets/tools/java/)

     


    Title Il lambda calcolo parametrico: un meta-modello di computazione
    Teacher Simona Ronchi della Rocca, Dipartimento di Informatica, Università degli Studi di Torino
    Year 2006
    Period First half of June
    Syllabus
    Argomenti:
    Il lambda calcolo parametrico è un calcolo paradigmatico, che può sussumere (oltre ad altri calcoli) sia il lambda calcolo classico che il lambda calcolo per valore di Plotkin. Può quindi essere studiato come modello per studiare in modo uniforme la semantica (operazionale e denotazionale) di diversi modelli di computazione.
    Programma di massima:
    • La sintassi
    • Le proprieta' fondamentali: confluenza e standardizzazione
    • Solvability e separability
    • Le macchine di valutazione e la semantica operazionale
    • Alcune relazioni interessanti tra call-by-name e call-by-value
    • La semantica denotazionale
    • I tipi intersezione e i filtri modelli
    • Costruzione di filtri modelli
    • Il problema della full-abstraction.

    Riferimento:
    S. Ronchi Della Rocca, L.Paolini, "The Parametric Lambda Calculus: a meta-model for Computation, Texts in Computer Science, Springer, 2004

     
    Title Machine Learning oriented Natural Language Processing
    Teacher Prof. Kiril Ribarov, Charles University, Praga
    Year 2005
    Period March 30 - April 8
    Syllabus
    The course will include:
    • general machine learning procedures
    • comparative, more or less successful application of learning algorithms for NLP
    • characteristics of natural languages, qualitative and quantitative
    • Introduction of large span annotation, example the Prague Dependency Treebank
    • Morphology and Parsing
    • Several innovative approaches in NLP

     


    Title Semantic Foundations for Computer and Network Security
    Teacher Prof. Roberto Gorrieri, Università di Bologna
    Year 2005
    Period April 18-29
    Syllabus
    The course (20 hours) will be divided into two parts. In the first part, some notions about process algebras and Petri nets are presented in order to provide formal models for concurrent communicating systems. In the second part, such formalisms are used to study security properties of computer systems (information flow security) and network protocols (e.g., secrecy, authentication, integrity). The focus will be on the theory of non-interference, which is presented in full detail, as well as its extension to timed and probabilistic systems.
     
    Title Parallel Computing in Combinatorial Optimization
    Teacher Prof. Bernard Gendron, University of Montreal
    Year 2005
    Period June 9-30
    Syllabus
    Objectives:
    At the end of this course, the student will be familiar with the current research on the design of parallel algorithms and software tools for solving combinatorial optimization problems. Both heuristic and exact methods will be reviewed, including tabu search, simulated annealing, variable neighbourhood search, genetic algorithms, ant systems, branch-and-bound algorithms, and constraint programming methods. The implementation of these algorithms on various parallel and distributed computing systems will be studied, including shared-memory systems, message-passing environments, networks of heterogeneous workstations and grid computing environments. We will consider classical problems, such as the Traveling Salesman Problem (TSP), the Vehicle Routing Problem (VRP) and the Quadratic Assignment Problem (QAP), as well as difficult network design problems arising from applications in the fields of transportation and telecommunications.
    Periodo:
    The course will take place during 3 weeks (between June 9 and June 30, 2005). We plan to have two lessons of three hours each every week, except for the last week, where we could need an additional three hours (depending on the number of students registered) to allow each student to give a talk on a research paper.
     

    Title Categories and Computer Science
    Teacher Prof. Robert Walters, Università dell'Insubria
    Year 2005
    Period June
    Syllabus
    Argomenti:
    The course will cover a number of advanced topics in Category Theory, each topic illustrated with examples from Computer Science. The topics covered will include:
    • Distributive and extensive categories
      Distributive law and the relation between parallel and sequential; hierarchy; well-behaved sums; the Fam construction; further exactness properties; adhesive categories and graph rewriting; elementary topoi; cartesian closed categories and higher order.
    • Monoidal categories
      Symmetry and Yang-Baxter equations; sums and monoid morphisms; generic algebras (Frobenius, separable) in monoidal categories; syntax of cobordisms, finite functions, cospans of graphs; algebras of automata.
    • Categories with feedback and trace
      Compact closed categories; the geometry of the tensor calculus; feedback and the universal property of automata; categories for discrete and continuous linear system theory; well-supported compact closed; span and cospan categories; classical problems of concurrency; partita doppia; coordination languages; traced monoidal categories and the Int construction.
    • Enriched categories
      Free V-categories and the Kleene theorem; colimits in V-cat; Cospan(V-cat) and the behaviour of processes; quantales; Cauchy completeness.
    • Bicategories
      Bicategories of relations, spans, profunctors; adjoint arrows in bicategories, spans and bisimulations; compositional model checking; monoidal bicategories and braiding; asynchronous circuits.
    • Sheaf Theory
      Sheaves as variable sets; sheaves as enriched categories; presheaves as generalized graphs, data for building categories with structure; famillial representability; Kan extensions.
    • Computational category theory
      Rewriting and distributive laws; Kan extensions and the Todd-Coxeter algorithm; Knuth-Bendix, Groebner bases.
     
    Title Systems biology: modeling, analysis and simulation
    Teacher Prof. Corrado Priami, Università di Trento
    Year 2005
    Period Ma 30 - June 11
    Syllabus
    Argomenti:
    The course will show the connection between concurrent languages (through their process algebra semantics) and dynamic behaviour of biological systems. It turns out that the modelling, analysis and simulation techniques of concurrent programs are very suitable to model, analyse and simulate cell behaviour. The neat results of this cross-fertilization between computer science and biology could lead to improve the performance of biological research and could provide hints to further push ahead the development of formal methods in the concurrency field.
     

    Title An Introduction to Dynamical Systems
    Teacher Prof. Frederico Oliveira-Pinto, Universidade Independente, Lisboa
    Year 2005
    Period October 6-21
    Syllabus
    Argomenti:
    A comparative study of discrete and continuous dynamical systems and of their stability.
    Contenuti:
    Discrete systems:
    - Introduction
    - Recurrence & difference equations
    - General solutions of discrete systems
    - Equilibrium values
    - Dynamical stability
    - Examples of linear systems with exponential growth and known general solutions
    - Analytical solutions of discrete linear versus continuous linear growth models
    - Quadratic dynamical systems
    - Discrete quadratic versus logistic systems
    - Closed-form solutions for discrete quadratic and discrete cubic dynamical systems with "chaotic" behaviour
    - Study of their intrinsic instability

    Continuous systems:
    - Volterra-type predator-prey systems
    - Military fighting models

    Bibliography and additional reading:
    1. G. Fulford & altri - "Modelling with differential and difference equations", Cambridge University Press, 1997.
    2. R.A. Holmgren - "A first course in Discrete Dynamical Systems", (2 Ed.), Springer, 1996.
    3. F. Oliveira-Pinto & M. Adibpour - "Analitical solutions of one- dimensional Discrete Dynamical Systems with "chaotic" behaviour", Non-linear Dynamics, 1 (1990) p 121-129.
    4. F.Oliveira-Pinto & B.W. Conolly - "Applicable Mathematics of non-physical phenomena, Ellis Horwood, Chicherter, a Division of I Wiley & Sons, 1982.
    5. IT. Sandefur -"Discrete Dynamical Systems, Theory and Applications, Clarendon Press, Oxford, 1990.

     
     
    Title Metodi Probabilistici in Geometria Computazionale
    Teacher Marco Pellegrini, IIT-CNR, Pisa
    Year 2004
    Period January - February
    Syllabus
    Lo scopo del corso è di introdurre lo studente ad alcune tecniche per il disegno di algoritmi probabilistici efficienti sviluppati nell'ultimo decennio ed alla loro applicazione principalmente nel campo della geometria computazionale. Si studieranno problemi applicativi di tipo planare che coinvolgono poligoni e insiemi di poligoni (mappe planari, diagrammi di Voronoi) all'interno di una teoria più generale di natura combinatorica (Spazi di confugrazioni, Random sampling, epsilon-nets). Si giungerà quindi a dimostrare bounds asintotici sul tempo medio di soluzione di svariati problemi e "tail estimates" sulla deviazione di tali tempi dalla media.

    Title Search Engine and Question Answering
    Teacher Giuseppe Attardi, Dipartimento di Informatica, Pisa
    Year 2004
    Period March 29 - April 23
    Syllabus
    Modelli di Information Retrieval

    Boolean and vector-space retrieval models
    Ranked retrieval
    Text-similarity metrics: TF-IDF (term frequency/inverse document frequency) weighting; cosine similarity
    Performance metrics: precision, recall, F-measure.
    RunTime
    Indexing and inverted files
    Compression
    Postings Lists
    Query languages
    Web Search
    Search engines Architecture
    Crawling: parallel/distributed, focused
    Link analysis (Google PageRank)
    Scaling
    Question Answering
    Information extraction
    Named Entity Recognition
    Natural Language Processing
    Part of Speech tagging
    Question analysis and semantic matching
    Riferimenti:

    R. Baeza-Yates, B. Ribeiro-Nieto, Modern Information Retrieval, Addison Wesley, 2000.
    I.H. Witten, A. Moffat, T.C. Bell, Managing Gigabytes, 2nd Edition, Morgan Kaufmann, 1999.
    C. Manning and Shutze, Foundations of Statistical Natural Language Processing , MIT Press, 1999
     
    Title Concurrent Languages for Probabilistic Asynchronous Communication
    Teacher Catuscia Palamidessi, INRIA Futurs Saclay e LIX École Polytechnique, Parigi
    Year 2004
    Period June
    Syllabus
    • Robin Milner. Communicating and mobile systems: the pi-calculus. Cambridge University Press, 1999.
    • R. Milner, J. Parrow, D. Walker. Modal Logics for Mobile Processes. Theoretical Computer Science 114:149-171, 1993.
    • Catuscia Palamidessi. Comparing the expressive power of the Synchronous and the Asynchronous pi-calculus. Proc. of the 24th ACM Symposium on Principles of Programming Languages (POPL), pages 256-265, ACM, 1997.
    • Benjamin Pierce. Foundational Calculi for Programming Languages. Chapter in the CRC Handbook of Computer Science and Engineering, 1996.
    • Davide Sangiorgi and David Walker. The pi-calculus. A Theory of Mobile Processes. Cambridge University Press, 2001.

    Title Rigorous Requirements for Safety-Critical Systems. Fundamentals and Applications of the SCR (Software Cost Reduction) method
    Teacher Costance L. Heitmeyer, Naval Research Lab, Washington DC, USA
    Year 2004
    Period June 28 - July 9
    Syllabus
    COURSE GOALS
    Assumption: To reduce software development costs and to increase software quality, the documentation of the requirements must be improved
    Goals:

    Understand how SCR techniques can be used to improve requirements documents for complex, critical systems
    Understand principles behind the SCR approach and how these addresses key industrial problems (e.g., cost, ease of use)
    Understand how the SCR formal model and notation are used to improve the quality of a requirements specification
    Understand how a solid formal foundation leverages benefits of automation
    Understand the effects of applying SCR technology in the context of large, safety-critical systems
    COURSE CONTENT:
    Part 1: The requirements problem and the SCR approach
    Industrial context for formal methods
    The SCR conceptual model
    Part 2: The SCR requirements model
    State-based
    Tables used to define functions
    Part 3: The SCR tools
    Specification
    Simulation
    Formal Analysis (consistency checking, model checking, theorem proving)
    Part 4: Industrial experience and technology transfer
    Applying SCR to practical systems
    Technology transfer lessons
     
    Title Principles and Applications of Constraint Programming
    Teacher M.H. van Emden, University of Victoria, Canada
    Year 2004
    Period October 4-20
    Syllabus
    Prerequisiti:
    Although CP provides an attractive alternative to Operations Research and Numerical Analysis, it does not require a background in these areas. All graduate students in computer science will be sufficiently prepared for this course. The same holds for graduate students in other disciplines who have taken programming and computation courses.
    Programma:

    Why Constraint Programming?
    The equations of Ivan Sutherland -- The difficulties of Operations Research and Numerical Analysis -- The power of the relational model -- Applications in AI, Management, Logistics
    What is Constraint Programming?
    Constraint Satisfaction Problems informally -- Constraint Satisfaction Problems formally -- The role of domains -- The need to approximate domains
    Approximation Theory
    The hull function -- Domains for reals and integers
    Contraction Operators
    The fundamental formula -- application to equality and inequality -- application to numerical constraints
    Floating-point arithmetic
    The IEEE standard -- directed rounding
    Interval Arithmetic
    General definition of interval operations -- arithmetic interval operations
    Constraint Satisfaction Problems with Continuous Variables
    Constraint Satisfaction Problems with Integer Variables
    Propagation
    Solving
    Optimization

    Title Process algebra with timing
    Teacher Jos Baeten, Department of Mathematics and Computer Science, Eindhoven University of Technology
    Year 2004
    Period November - December
    Syllabus
    Abstract:
    The course will enable the student to acquire a better understanding of issues that can be relevant to the description and analysis of concurrent, communicating processes if their time-dependent behaviour is important. The course is concerned with algebraic theories that have been developed to be used for describing and analysing concurrent, communicating processes in those cases where their time-dependent behaviour is important. Discussed are four closely related theories that deal with time-dependent behaviour in different ways. The theories are extensions of the theory ACP. The use of the theories is illustrated by means of examples of the description of processes and the analysis of described processes by algebraic calculations. The examples concern among other things protocols and controllers.
    The course is based on the book: Baeten & Middelburg: Process algebra with timing, Springer 2002.
     
    Title Mobile Ad Hoc Networks and Sensor Networks
    Teacher Piero Maestrini, Dipartimento di Informatica & ISTI-CNR, Pisa; Stefano Chessa, Dipartimento di Informatica, Pisa
    Year 2004
    Period December 2004 January 2005
    Syllabus
    Overview:
    Mobile, wireless ad hoc networks are among the fastest growing areas in networking research.They are best suited for applications in environments where fixed infrastructures are unavailable or unfeasible. Examples of such applications are communication in remote or hostile environments,management of emergencies, and disaster recovery. Ad hoc commercial installations are also emerging as a promising application area. Mobile ad hoc networks are an heterogeneous mix of different wireless and mobile devices, ranging from little hand-held devices to laptops. Such devices rely on on-board batteries for energy supply, hence energy efficiency of mobiles is an important issue. Ad hoc networks implement a distributed cooperation environment, based on a peer-to-peer paradigm. Given the limited range of wireless communication the network is generally multihop. For this reason a distributed routing protocol is required in order to provide communication between arbitrary pairs of nodes.
    The course covers the following issues related to Ad Hoc Networking:
    MAC Layer
    Routing
    Clustering
    Energy efficiency
    Dependability and Security
    Self Organization and Cooperation
    Sensor Networks

    Title Some computational aspects of geoinformatics
    Teacher Prof. Mike Worboys, Department of Computer Science, Keele University, England
    Year 2003
    Period Ottobre
    Syllabus
    Much of the early technology for spatial data handling (e.g. spatial indices, object-oriented spatial data models) is now well understood.
    Current preoccupations of computer scientists working with geospatial data will be the subject of these lectures. Topics will include spatial reasoning, qualitative spatial data handling, multi-contextual spatial data models and spatio-temporal information systems.
    1. Spatial reasoning will be approached from a formal perspective, looking at developments of Egenhofer's intersection method and the RCC calculus.
    2. Proper treatment of qualitative data and integration of qualitative with quantitative spatial information is key if useful human computer interfaces with spatial databases are to be developed.
    3. Current and future spatial information systems architectures will be multi-contextual, with data arising from many sources and having users with heterogeneous data models and purposes. The talk will develop a framework in which multiple contexts can be developed.
    4. Much useful geoinformation has dynamic and historic components, so the lectures will conclude by examining some of the recent work, including that of the European Chorochronos project, on spatio-temporal systems.
     
     
    Title Data Mining to Relational Data Mining
    Teacher Saso Dzeroski, Department of Intelligent Systems; Jozef Stefan Institute, Ljubljana, Slovenia; Fosca Giannotti, ISTI-CNR, Pisa; Dino Pedreschi, Dipartimento di Informatica, Univ. Pisa
    Year 2003
    Period February - April
    Syllabus
    The goal of the course is twold. First, it gives an introduction to the basics of data mining, i.e., the computational methods for the analysis of large and complicated data sets, aimed at extracting knowledge from data. Such methods are based on algorithmic and statistical techniques, as well as database and machine learning techniques. Second, the course introduces to multi-relational data mining, i.e., knowledge discovery from multi-relational data, a line of research rooted in inductive logic programming, at the intersection of machine learning and programming languages.

    Title Logica lineare
    Teacher Roberto Di Cosmo, Universite' de Paris VI-VII
    Year 2003
    Period February-April
    Syllabus
    La Logica Lineare è una logica costruttiva in cui la nozione di "risorsa disponibile" rimpiazza la tradizionale nozione di verità. La Logica Lineare, proposta da Girard, si è rivelata essere non solo uno strumento utile per una migliore comprensione dei sistemi logici preesistenti, ma anche uno strumento fondamentale in vari campi dell'informatica, dalla realizzazione di interpreti efficaci per i linguaggi funzionali, alla migliore comprensione dei modelli di calcolo, fino ad applicazioni in programmazione per vincoli. Lo scopo del corso è di dare una rapida introduzione ai concetti ed alle tecniche fondamentali della Logica Lineare.
     
    Title Some Computational Aspects of Geoinformatics
    Teacher Mike Worboys, Department of Spatial Information Science and Engineering University of Maine Orono, USA
    Year 2003
    Period April 2-14
    Syllabus
    Much of the early technology for spatial data handling (e.g. spatial indices, object-oriented spatial data models) is now well understood. Current preoccupations of computer scientists working with geospatial data will be the subject of these lectures. Topics will include spatial reasoning, qualitative spatial data handling, multi-contextual spatial data models and spatio-temporal information systems. 1. Spatial reasoning will be approached from a formal perspective, looking at developments of Egenhofer's intersection method and the RCC calculus. 2. Proper treatment of qualitative data and integration of qualitative with quantitative spatial information is key if useful human computer interfaces with spatial databases are to be developed. 3. Current and future spatial information systems architectures will be multi-contextual, with data arising from many sources and having users with heterogeneous data models and purposes. The talk will develop a framework in which multiple contexts can be developed. 4. Much useful geoinformation has dynamic and historic components, so the lectures will conclude by examining some of the recent work, including that of the European Chorochronos project, on spatio-temporal systems.

    Title Program Verification
    Teacher José Meseguer, University of Illinois at Urbana-Champaign
    Year 2003
    Period June
    Syllabus
    Programs can be either declarative (based on a logical system) or imperative (conventional languages). They can also be either sequential or concurrent. All four combinations are possible. The course will address program verification techniques for programs in this general sense using techniques from equational and rewriting loogic to specify their semantics; and of first-order logic, inductive logic, Hoare logic, and temporal logic, to specify properties. Proving tools supporting mechanized reasoning in all these cases will be used. The logical foundations will also be developed.
     
    Title Rigorous Approaches to Information Security Problems
    Teacher Joshua D. Guttman, MITRE, Bedford, MA 01730-1420, USA
    Year 2003
    Period October - November
    Syllabus
    The purpose of this course is to explain a method my colleagues and I have applied to a wide range of different problems within the general area of information security. The method has three steps. First, one constructs a model abstracting key aspects of the problem domain in terms of a few mathematical ideas. Second, one selects one or a few logical forms of statement, meaningful in the model, as the security goals to be achieved in different circumstances or configurations. Third, a combination of proof techniques and algorithms are needed to determine the security goals achieved in given circumstances, or to construct circumstances in which given security goals are achieved.
    We will apply this general method in three main areas. First, we will apply it to security management. Security management is the problem of using simple mechanisms on a large scale to achieve predictable security goals. We will consider security management problems for filtering routers, for gateways executing the IP security goals, and in the operating system context of Security Enhanced Linux.
    Second, we will apply our method to cryptographic protocols, emphasizing the strand space formalism. Strand spaces give us a systematic way to discover flaws in existing protocols; to prove that they achieve authentication and confidentiality goals; and to design new protocols to meet specific goals.
    Finally, we will examine trust management, which is the use of logical theories by multiple principals to derive access control decisions. We will also explain recent work interrelating trust management theories with cryptographic protocols to ensure that access derivations rely only on recent information.

    Title Constraint Reasoning and Programming
    Teacher Dr. Thom Fruehwirth, Ludwig-Maximilians-University, Munich
    Year 2002
    Period Feb 18 - March 1, 2002
    Syllabus
    We first introduce the basic ideas behind the family of (concurrent)constraint logic programming languages in a calculus-based framework.
    Constraint handling rules will be used to describe the constraint systems and their solver in a single high-level executable notation.
    We will present some of the most common constraint domains, their solvers and applications such as Boolean constraints for circuit design, linear polynomial equations for financial and engineering applications and finite domains for scheduling.
     
    Prologue - 2 hours
         Basic predicate logic and calculus
    Part I - 8 hours
    The family of (concurrent) constraint logic programming languages
         Constraint logic programming (incl. Prolog)
         Concurrent constraint logic programming
         Constraint handling rules
    Part II - 8 hours
    Constraint systems and their solvers
         Rational Trees
         Feature Terms
         Boolean Constraints
         Finite Domains
         Linear polynomial equations
         Non-Linear polynomial equations
    Finale - 2 hours
         Commercial applications, market and companies
         Case study Munich rent advisor on the internet
         Case study Planning wireless telecommunication
     
    Literature
    Th. Fruehwirth and S. Abdennadher, Constraint-Programmierung, Textbook, ISBN 3-540-60670-X, Springer Verlag, Germany, 1997.
     
    K. Marriott and P.J. Stuckey, Programming with Constraints,
    ISBN 0-262-13341-5, MIT Press, USA, 1998.
     
     
    Title Responsive systems
    Teacher Prof. Miroslaw Malek, Humboldt-Universität, Berlin
    Year 2002
    Period Feb 18 - March 8
    Syllabus
    Overview of the course
    Fast growth and proliferation of web applications and embedded systems forces the increased demand for properties such as dependability, timeliness and security. We call the systems responsive if they can deliver correct solutions and actions even in the presence of faults. In this course we focus on dependability  and timeliness but references to security and performance are also included. After introducing the various dependability, timeliness and responsiveness perspectives on system design as well as the methodology we introduce basic concepts, measures and models used in responsive computing and communication. We then describe testing methods, fault diagnosis, fault recovery and fault tolerance techniques that are essential in the dependable systems design and scheduling methods which are the core of real-time systems. We conclude the course with case studies, which demonstrate what techniques have been, used for the dependability and responsiveness enhancement in the real life systems.
     
     
     
    Dependability  and Responsiveness Concepts and Measures
    Dependability  and Responsiveness Models
    Testing Techniques
    Fault Diagnosis Techniques
    Fault Tolerance Techniques
    Dependable Memories and Networks
    Fault-Tolerant Software
    Scheduling Algorithms for Real Time

    Title Models and logics for mobility
    Teacher Models and logics for mobility
    Year 2002
    Period October - December
    Syllabus
    DESCRIPTION OF THE COURSE:
    Cardelli and Caires have proposed a logic to describe spatial as well as temporal properties of mobile systems. On the other hand, recent work on permutation-based models of abstract syntax with name binding operations by Honda, Pitts and others can be adapted to build models of mobile systems like the pi-calculus. The course will present the Cardelli and Caires logic together with models based on permutations and general substitutions.
     
    Period: September 2002
     
     
    Docente: Dr. Silvia Giordano, LCA-EPFL, Lausanne
    Titolo: Mobile ad hoc networking
     
    Abstract: A mobile ad-hoc network (MANET) represents a system of wireless mobile nodes that can freely and dynamically self-organize into arbitrary and temporary network topologies, allowing people and devices to seamlessly internetwork in areas without any pre-existing communication infrastructure. These networks are energy and bandwidth constrained, and designed to operate in a wide variety of environments, from military networks (with hundreds of nodes) to low-power sensor networks (with potentially, thousands of nodes). Many challenges remain to be resolved before MANETs can be widely deployed, however. Major advances are called for in the areas of wireless technologies, location and configuration management, addressing and routing, security and Quality of Service (QOS). 
    This course covers comprehensively the area of ad hoc networking, ranging from physical issues up to applications aspects. In particular, it will cover physical, data link, network and transport layers, as well as application, security, simulation and energy management issues in mobile ad hoc networks. Aim of the course is to study ad hoc protocols and models, with an emphasis on the most recent contributions.
                        
    Part I : Mobile ad hoc networking  - 12 hh
                - MANET and the Internet;
                - Multiple access schemes;
                - Routing in ad hoc networks;
                - Addressing and location;
                - Simulation and prototyping mobile networking protocols;
     
    Part II : Economic and social aspects of mobile ad hoc networking  - 8 hh
               - Security in ad hoc networks;
               - Application layer; 
               - Self-organization and co-operation.
      
            
    Literature: Although ad hoc networking is a "hot topic", at the moment, there are only (few) specialized books, mostly examining routing aspects. More precisely, two books that were recently published by C. Perkins and C.K. Toh contain outdated and selected information, from the perspective of respective authors with narrow specialization. In contrast, this course intends to provide comprehensive coverage. For the reason, the students will be provided with specific journals and conference papers during the course.
     
    Title Introduzione alla complessità computazionale
    Teacher Dr. Bruno Codenotti, CNR-IMC, Pisa
    Year 2001
    Period Gennaio-febbraio. La prima lezione è fissata per il 22/1 alle 17 nella sede dell'IMC.
    Syllabus
    Il docente ha proposto due titoli e programmi tra cui sceglierà in funzione della preparazione e degli interessi dei dottorandi che
    lo seguiranno.
     
    Titolo: Introduzione alla complessità computazionale
    Modelli di calcolo, determinismo e non determinismo
    Classi di complessita’
    Le classi P e NP
    Teoria della NP-completezza
    Classi in spazio
    Classi e algoritmi probabilistici
     
    Testo: Introduzione alla complessità computazionale, A. Bernasconi e B. Codenotti, Springer Verlag (1998)
     
    Titolo: Metodi matematici in complessità computazionale
    Il problema della primalità: determinismo, nondeterminismo e tecniche probabilistiche
    Pseudocasualità e complessità
    Calcolo di forme lineari: limitazioni inferiori
    La trasformata veloce di Fourier
    Circuiti algebrici
     
    Riferimenti:
    - A. Bernasconi, B. Codenotti, Introduzione alla complessità computazionale, Springer Verlag, 1998.
    - A. Bernasconi, B. Codenotti e G. Resta, Metodi matematici in complessita’ computazionale, Springer Verlag, 1999.

    Title Algebraic Semantics of Coordination
    Teacher Prof. José Luiz Lopes Fiadeiro, Technical University of Lisbon
    Year 2001
    Period Aprile
    Syllabus
    We propose an algebraic characterisation of the notion of coordination in the sense of recently proposed languages and computational models that provide a clear separation between the modelling of individual software components and their interaction in the overall software organisation.
    We show how this separation can be formalised in a categorical framework in which the suitability of specification logics, program design languages and mathematical models of behaviour for supporting coordination mechanisms can be discussed. We further show how coordination can be formally related to the notion of superposition, as used for parallel program design, and connectors, as used for architectural design. Finally, we discuss the impact that coordination has on system evolution, namely on the ability for systems to be reconfigured dynamically, and ways of extending object-oriented modelling  languages  like the UML with coordination primitives that support this evolutionary approach.
     
    Title Constraint Reasoning and Programming
    Teacher Dr. Thom Fruehwirth
    Year 2001
    Period 27 Agosto - 9 Settembre oppure 2 settimane in Ottobre
    Syllabus
    Prologue - 2 hours - Basic predicate logic and calculus
     
    Part I - 8 hours - The family of (concurrent) constraint logic programming languages
    ·         Constraint logic programming (incl. Prolog)
    ·         Concurrent constraint logic programming
    ·         Constraint handling rules
    Part II - 8 hours - Constraint systems and their solvers
    ·         Rational Trees
    ·         Feature Terms
    ·         Boolean Constraints
    ·         Finite Domains
    ·         Linear polynomial equations
    ·         Non-Linear polynomial equations
    Finale - 2 hours
    ·         Commercial applications, market and companies
    ·         Case study Munich rent advisor on the internet
    ·         Case study Planning wireless telecommunication
     
    We first introduce the basic ideas behind the family of (concurrent)constraint logic programming languages in a calculus-based framework.
    Constraint handling rules will be used to describe the constraint systems and their solver in a single high-level executable notation.
    We will present some of the most common constraint domains, their solvers and applications such as Boolean constraints for circuit design, linear polynomial equations for financial and engineering applications and finite domains for scheduling.
    Literature
    The course is based on the German textbook "Constraint-Programmierung", and on the English textbook "Programming with Constraints".
     
    ·         Th. Fruehwirth and S. Abdennadher, Constraint-Programmierung, Textbook, ISBN 3-540-60670-X, Springer Verlag, Germany, 1997.
    ·         K. Marriott and P.J. Stuckey, Programming with Constraints, ISBN 0-262-13341-5, MIT Press, USA, 1998.
     

    Title Data Mining and Knowledge Discovery in Databases
    Teacher Prof. Jiawei Han, Simon Fraser University, Canada; Prof. Dino Pedreschi - Dip. Informatica univ. Pisa; Fosca Giannotti - CNUCE/ CNR
    Year 2001
    Period Marzo
    Syllabus

    part1: basic concepts (10 hours):

    This part is aimed at covering  the basics of the knowledge discovery process, and the main  data mining tools and related algorithms employed in this process.

    The goal of this part is to provide a systematization to the many concepts around this area, according the following lines:the process, the methods applied to paradigmatic cases and the support environment.

    Emphasis is placed on the integration of KDD/DM and database query languages, as well as the methodological problems posed by data analysis and knowledge extraction.

    The KDD paradigm is exemplified with three real world experiences form market basket analysis, fraud detection and customer segmentation, including demos with commercially available systems.

    part 2: advanced topics (10 hours):

    This part is aimed at covering the knowledge discovery in advanced databases and information repositories, and some special data mining algorithms.In particular, the course will include new frequent pattern mining algorithms, spatial and multimedia data mining, time series and sequential pattern mining methods, text and Web mining techniques, as well as research issues and future directions.  Emphasis is placed on the algorithms and methodologies for efficient and scalable mining of interesting patterns in sophisticated databases.

     

    Detailed topics  part1:

     

    Motivation and basic concepts (2.5 h)

    The technical and social needs of data analysis and knowledge extraction.

    The process of knowledge discovery in databases.

    Survey of Data mining techniques and algorithms.

    Association rules and experiences in market basket analysis. (2.5 h)

    An in-depth study of association rules is presented, emphasizing on techniques, methodologies of use, demos with real systems, and experiences in building an intelligent system for market basket analysis (extraction of business rules from supermarket sales data).

    Classification with  decision trees and experiences in fraud detection. (2 .5 h)

    An in-depth study of classification using decision trees is presented, emphasizing on techniques, methodologies of use, demos with real systems, and experiences in building an intelligent system for fiscal fraud detection.

    Clustering and experiences in customer segmentation (2.5 h)

    First an application to a case-study in customer segmentation is outlined.Then an in-depth study of main clustering techniques is presented emphasizing on techniques and methodologies of use.

    Scheduling  part1 (10 hours):

    Lecture 1: March 15, 2001 - 14:30 thru 17:00

    Lecture 2: March 16, 2001 - 11:00 thru 13:30

    Lecture 3: March 22, 2001 - 14:30 thru 17:00

    Lecture 4: March 23, 2001 - 11:00 thru 13:30

    Speakers:

    Fosca Giannotti - CNUCE/ CNR,

    Prof. Dino Pedreschi - Dip. Informatica Univ. Pisa

     

    Detailed topics part2:

     

    Scalable methods for mining frequent and sequential patterns (2.5 h)

    An in-depth study of frequent pattern growth methodology and its applications at mining associations, sequential patterns, constraint-based mining, and several other kinds of patterns.

    Mining Spatial, temporal, time-series, and multimedia data (2.5 h)

    Spatial data warehousing and spatial data mining methods, mining temporal and time-series data, mining sequential patterns, partial periodicity, and DNA sequences, mining multimedia data.

    Text mining and Web mining (2.5 h)

    Information retrieval and text mining, keyword association and document classification, Web mining: issues and classification, Web mining, multi-layer Web warehousing, Web log mining.

    Issues on mining advanced databases and the future of data mining (2.5 h)

    Mining other complex types of data, research issues on mining advanced databases, visual data mining, theoretical foundations of data mining, data mining applications: domain-specific data mining and invisible data mining, future of data mining.

    Scheduling of the second part of course (10 hours):

    Lecture 1: March 27, 2001 - 14:30 thru 17:00

    Lecture 2: March 28, 2001 - 11:00 thru 13:30

    Lecture 3: March 29, 2001 - 14:30 thru 17:00

    Lecture 4: March 30, 2001 - 11:00 thru 13:30

    Speaker: Jiawei Han, Simon Fraser University, Canada

     

    List of main references

     

    Jiawei Han, Micheline Kamber. Data Mining: Concepts and Techniques,
    Morgan Kaufmann Publishers, 2000 http://www.mkp.com/books_catalog/catalog.asp?ISBN=1-55860-489-8
    U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy (editors). Advances in Knowledge discovery and data mining. MIT Press, 1996.
    T. Mitchell. Machine learning. Mc-Graw Hill, 1997.
     

    Some recent research papers in SIGMOD, VLDB, ICDE, KDD, etc.

     
    Title Fondamenti dell'Informatica: Semantica II (FS2)
    Teacher Ugo Montanari
    Year 2001
    Period February
    Syllabus
    Finalità del Corso
    Il corso presenta i principi generali di alcuni importanti aspetti comuni a molti linguaggi di programmazione: la struttura dei tipi, l'ordine superiore e la modularita'. Lo sviluppo matematico, basato sul lambda calcolo tipato, sara' motivato da esempi tratti da linguaggi di programmazione funzionali ed orientati ad oggetti.
     
    Programma Dettagliato
     
    Esempi di programmazione con un linguaggio funzionale di ordine superiore, potenza espressiva e limitazioni. (4h)
    Il Lambda Calcolo con tipi semplici. (8h)
    Modelli del Lambda Calcolo tipato. (12h)
    Esempi di programmazione con moduli, packages, generics, templates.(4h)
    Polimorfismo e subtyping. (8h)
    Inferenza di tipi. (4h)
     
    Libro di Testo
    John Mitchell, "Foundations for Programming Languages", MIT Press, 1996. Capitoli: 2.5,4,5,7.2,9,10,11.
     
    Periodo: Il corso avra' inizio il: giovedi' 22 febbraio con il seguente orario:
    giovedi' 11-13 aula C1 polo Fibonacci
    venerdi' 14-16 aula C1 polo Fibonacci
     
    L'orario potra' essere ridiscusso in caso di impossibilità a frequentare dei dottorandi interessati.
     
    La pagina web del corso è: http://www.di.unipi.it/~ugo/FS2.html

    1 - 100 Next