Sign In

Courses 2004

Sort by AttachmentsUse SHIFT+ENTER to open the menu (new window).
Title Metodi Probabilistici in Geometria Computazionale
Teacher Marco Pellegrini, IIT-CNR, Pisa
Period January - February
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
Period March 29 - April 23
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.
Indexing and inverted files
Postings Lists
Query languages
Web Search
Search engines Architecture
Crawling: parallel/distributed, focused
Link analysis (Google PageRank)
Question Answering
Information extraction
Named Entity Recognition
Natural Language Processing
Part of Speech tagging
Question analysis and semantic matching

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
Period June
  • 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
Period June 28 - July 9
Assumption: To reduce software development costs and to increase software quality, the documentation of the requirements must be improved

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
Part 1: The requirements problem and the SCR approach
Industrial context for formal methods
The SCR conceptual model
Part 2: The SCR requirements model
Tables used to define functions
Part 3: The SCR tools
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
Period October 4-20
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.

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
Title Process algebra with timing
Teacher Jos Baeten, Department of Mathematics and Computer Science, Eindhoven University of Technology
Period November - December
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
Period December 2004 January 2005
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
Energy efficiency
Dependability and Security
Self Organization and Cooperation
Sensor Networks