


Title

Metodi Probabilistici in Geometria Computazionale

Teacher

Marco Pellegrini, IITCNR, Pisa

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, epsilonnets). 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

Syllabus

Modelli di Information Retrieval
Boolean and vectorspace retrieval models Ranked retrieval Textsimilarity metrics: TFIDF (term frequency/inverse document frequency) weighting; cosine similarity Performance metrics: precision, recall, Fmeasure. 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. BaezaYates, B. RibeiroNieto, 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

Syllabus

 Robin Milner. Communicating and mobile systems: the picalculus. Cambridge University Press, 1999.
 R. Milner, J. Parrow, D. Walker. Modal Logics for Mobile Processes. Theoretical Computer Science 114:149171, 1993.
 Catuscia Palamidessi. Comparing the expressive power of the Synchronous and the Asynchronous picalculus. Proc. of the 24th ACM Symposium on Principles of Programming Languages (POPL), pages 256265, 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 picalculus. A Theory of Mobile Processes. Cambridge University Press, 2001.




Title

Rigorous Requirements for SafetyCritical 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

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, safetycritical 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 Statebased 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

Period

October 420

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

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 timedependent 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 timedependent behaviour is important. Discussed are four closely related theories that deal with timedependent 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 & ISTICNR, Pisa; Stefano Chessa, Dipartimento di Informatica, Pisa

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 handheld devices to laptops. Such devices rely on onboard batteries for energy supply, hence energy efficiency of mobiles is an important issue. Ad hoc networks implement a distributed cooperation environment, based on a peertopeer 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


 


