Courses Offered During the 1996-97
Academic Year
Titolo del Corso: Introduction to Petri Nets and
Timed Testing of Asynchronous Systems
Docente: Walter Vogler, University of Augsburg, Germany
Responsabile: Roberto Gorrieri
Periodo: 10-12 settembre (tre giorni)
Oraio: dalle 14.00 alle 17.00 nelle aule:
giorno aula
-------------------------
10-11 Enriques
12 Vitali
Sede: Dipartimento di Matematica, Univ. di Bologna,
Piazza di Porta San Donato 5, Bologna
Contenuti
In this short course, Petri nets will be introduced - first with their
basic semantics, then with some variants of partial order
semantics. Next, failure semantics and the testing scenario of De
Nicola and Hennessy will be explained; it turns out that failure
semantics describes exactly the system behaviour as far as it is - in
some setting - observable by a testing environment, e.g. the user. In
the second part, I take the opportunity to present some recent ideas
of mine, which vary the idea of testing; the resulting timed testing
takes not only into account which actions are performed, but also the
efficiency of the system. It can be shown that now some form of
partial order semantics is exactly what can be observed. Furthermore,
some interesting results are obtained that compare the worst case
efficiency of some implementations of bounded buffers.
Rensink:
Titolo del Corso: Practical Aspects of Process Algebra
Docente: Arend Rensink, University of Hildesheim, Germany
Periodo: 24-27 settembre + 1-3 ottobre (sette giorni)
Orario:
giorno aula ora
-------------------------------------
24 sett Vitali 14-17
25 sett Bombelli 14-17
26-27 sett Enriques 14-17
1 ott Vitali 14-17
2 ott Bombelli 10-13
3 ott Bombelli 14-17
Sede: Dipartimento di Matematica, Univ. di Bologna,
Piazza di Porta San Donato 5, Bologna
Contenuti
A lot of research has been done in the field of process algebra, but
practical applications are few and far between. In this couse we
discuss some of the things that have been done and can be done using
the process algebraic paradigm. The course is based ISO standard
language LOTOS. Some hands-on experience using a simulator tool will
be part of the course. After introducing the language, we explain how
LOTOS has been used to specify communication services and protocols in
the ISO framework. Furtheremore, we discuss the use of specification
styles in the language. Then we go into the notion of correctness, and
various ways to establish it, i.e., methods of verification. Finally,
we show some slightly larger examples of LOTOS specifications.
This course fixes mainly on the practical use of process algebra, and
largely leaves theoretical issues alone, except where they are needed
to understand the subject; such as in the matter of verification,
which relies on a formal semantics. The course is thus also suitable
for those who have not yet investigated the process algebraic paradigm
before.
Outline
- - the LOTOS language
- Process formalism
- Data formalism
- Simulation tool
- - Services and protocols
- OSI model
- OSI service specifications
- Implementation through protocols
- - Specification styles
- Monolithic
- Property oriented
- State oriented
- Resource oriented
- - Correctness
- Simulation
- Axioms and proof systems
- Correctness preserving transformations
- Testing
- - Larger examples
- Cache-protocol
- Login protocol
- Car engine control
Titolo del Corso: Complexity Theory
Docente: Alessandro Panconesi (Humboldt University)
Responsabile: Ozalp Babaoglu
Periodo: 14--24 Ottobre 1996
Sede: Dipartimento di Scienze dell'Informazione, Universita di Bologna
Orario:
Giorno Aula del Dip. di Matematica
LUN 14 ottobre 11.00-13.00 Aula Vitali
14.30-16.30 Aula Vitali
MER 16 ottobre 11.00-13.00 Seminario 1
15.00-17.00 Aula Tonelli
GIO 17 ottobre 11.00-13.00 Seminario 2
14.30-16.30 Seminario 2
LUN 21 ottobre 11.00-13.00 Seminario 2
14.30-16.30 Seminario 2
MAR 22 ottobre 11.00-13.00 Seminario 2
14.30-16.30 Seminario 2
GIO 24 ottobre 11.00-13.00 Seminario 2
14.30-16.30 Seminario 2
Scopo del Corso
Gli obbiettivi del corso sono due: (a) presentare del materiale che
per la sua importanza \'e opportuno che faccia parte del bagaglio
culturale di un qualsiasi dottorando in Informatica e (b) dare un
quadro abbastanza aggiornato di questa area di ricerca.
Fortunatamente, dati gli importanti sviluppi avvenuti negli ultimi
anni, \'e possibile prendere due piccioni con una fava, anche se, data
la vastit\'a della materia, \'e stato necessario operare drastiche
scelte estromettendo del tutto alcuni importanti filoni quali, ad
esempio, la complessit\'a delle teorie logiche, il calcolo parallelo o
la complessit\'a di Kolmogorov.
Il materiale scelto, comunque, dar\'a un quadro abbastanza ampio delle
tecniche e delle tematiche di fondo. Piuttosto che saltellare da un
filone all'altro-- magari nel tentativo di coprire un maggior numero
di risultati interessanti per via del loro ``sapore diverso''-- si \'e
preferito concentrarsi su pochi filoni cercando in questo modo di
raggiungere un compromesso tra variet\'a e profondit\'a.
La scelta del risultati specifici da presentare ha seguito il criterio
della rilevanza tecnica o dell'importanza per le questioni di fondo.
Alcuni risultati di grande importanza come il Teorema PCP, la cui
dimostrazione va ben al di l\'a delle possibilit\'a di un corso di
questo tipo, saranno discussi per le loro conseguenze e significato,
ma senza presentarne la dimostrazione. Il materiale cercher\'a di
evidenziare alcuni importanti sviluppi avvenuti negli ultimi anni; in
particolare l'introduzione di tecniche algebriche e, soprattutto, del
calcolo delle probabilit\'a.
Il corso prevede una durata di 24 ore, da coprirsi in due settimane al
ritmo di tre giorni a settimana, per 4 ore al giorno (due ore la
mattina e due il pomeriggio con pausa per il pranzo).
egin{quote}
\centering {\em Esercizi ed un'esame finale, un take-home da
consegnare via e-mail, fanno parte integrante del corso.}
\end{quote}
Qualora se ne presentasse l'occasione, gli studenti presenteranno in
classe degli articoli.
Segue un programma di massima che, essendo piuttosto ambizioso,
potr\'a all'occorrenza essere ridotto, scartando alcune parti a
seconda dell'interesse della classe. La parte riguardante la
\linebreak Teoria dell'Approssimabilit\'a non \'e specificata nel
dettaglio e potr\'a variare da una chiacchierata di un paio di ore ad
un vero mini-corso di una decina di ore, sul tipo di quello da me
insegnato a Bologna lo scorso anno. A decidere tra i due estremi
sar\'a la velocit\'a e la preparazione della classe. Per esempio, \'e
possibile che la parte importantissima riguardante la NP-completezza
sia gi\'a familiare per gli studenti e che possa essere saltata o
richiamata brevemente. Le indicazioni dei tempi sono quelle stimate
per trattare l'argomento con dovizia di particolari, completo di
dimostrazioni. All'occorrenza il risultato potr\'a essere
semplicemente enuciato e discusso nella sua rilevanza.
Contenuti
egin{itemize}
\item La Teoria della Complessit\'a: discussione e Hierarchy Theorems
(2 ore)
\item P .vs. NP (8-10 ore)
egin{enumerate}
\item Importanza delle classi P ed NP (1 ora);
\item teorema di Cook (NP-completezza di SAT) (2 ore);
\item Riduzioni tra problemi {\em \`a la Karp} (3 ore);
\item esistenza di problemi incompleti (1 ora);
\item Oracoli (2 ore);
\item Congettura di Hartmanis-Berman e Teorema di Mahaney (2 ore);
\item Circuiti: lower-bound di Razborov per Clique; discussione (2
ore)
\end{enumerate}
\item Spazio e Probabilit\'a: (8 ore)
egin{enumerate}
\item classi LOG, RLOG ed NLOG (1 ora);
\item problemi completi (2 ore);
\item Teorema di Savitch (1 ora);
\item Random walks on graphs (2 ore)
\item Pseudo-randomness: Teorema di Nisan. (3 ore)
\item NSPACE = co-NSPACE (Teorema di Immerman-Slepezcenyi) (1 ora);
\end{enumerate}
\item Protocolli Interattivi e Conseguenze per l'Approssimazione. (6-8 ore)
egin{enumerate}
\item QBF is PSPACE-complete (2 ore);
\item Definizione di IP (1 ora);
\item IP = PSPACE (2 ore);
\item Il Teorema PCP e MAX SNP (2-6 ore);
\end{enumerate}
\end{itemize}
----
Titolo del Corso: graph connectivity
docente: Michele Conforti
durata: 10 ore
sede: padova
periodo: some time during late april, early may
----
Titolo del Corso: Object Oriented Languages and Type Systems
docente: Michele Bugliesi
durata: 40 ore
sede: padova
periodo: march-june
Teorie dei tipi
Introduzione alle tecniche per la formalizzazione di sistemi di tipi
con polimorfismo ed inclusione di tipi. (thanks to B. C. Pierce)
Linguaggi Object Oriented: motivazioni, terminologia, modelli.
Formalizzazione dei sistemi di tipi per linguaggi a oggetti.
M. Abadi, L. Cardelli: A theory of objects.
Modelli delegation-based. F. Honsell, K. Fisher, J. C. Mitchell:
A Lambda Calculus of Objects and Method Specialization
Modelli class-based. Matching. K. Bruce: A Paradigmatic
Object-Oriented Programming Language: Design, Static Typing and
Semantics.
Oggetti e ADT's. B. C. Pierce, D. N. Turner: Simple
Type-Theoretic Foundations For Object-Oriented Programming
Multi-methods e Overloading. G. Castagna, G. Ghelli, G. Longo: A
Calculus for Overloaded Functions with Subtyping
----
Titolo del Corso: Parallel Algorithms and Architectures
docente: Andrea Pietracaprina
durata: 20 ore
sede: padova
periodo: some time during late april, early may
contenuto:
1. Introduzione al calcolo parallelo.
2. Architetture parallele
-- Tecniche di Routing.
-- Algoritmi fondamentali (Prefix, Sorting e FFT) su
array, mesh-of-trees e reti ipercubiche.
-- Grafi a espansione, Concentratori e Superconcentratori (cenni).
3. Bridging Models: BSP e LogP. Prefix, Broadcast, Sorting
e Algoritmi su Matrici.
4. Realizzazione del modello BSP su reti di Workstation tramite PVM.
----
Titolo del Corso: Network Security
docente: Pino Italiano
durata: 20 ore
sede: via Torino 155, Mestre
orario: il 5, 12, 19, 26 giugno e 3 luglio dalle 14.00 alle 18.00
contenuto: Foundations of Cryptography. Data Encryption Standard
(DES). Differential Cryptoanalysis. Key Distribution. Public Key
Cryptography (RSA, Rabin, El Gamal, Merkle-Hellman, Mc Eliece,
...). Algorithms in Number Theory: Primality, Factoring, Discrete
Log. Digital Signatures (RSA, El Gamal, Digital Signature
Standard). Digital time stamping. Secret sharing. Authentication and
identification schemes. Zero Knowledge and its applications. Secure
Protocols (Mental Poker, Elections). Electronic commerce: payment
protocols, electronic cash. Implementations (Kerberos, RSAREF, PGP,
PEM). Internet and security.
Maggiori informazioni sul corso stesso (inclusi programma preliminare
e riferimenti bibliografici) sono disponibili su
http://www.dsi.unive.it/~italiano/Teaching/security.html
mantre informazioni su come raggiungere via Torino sono disponibili su
http://www.dsi.unive.it/~italiano/Seminars/how_to_reach_us.html
Nell'ambito del corso ci saranno probabilmente anche due piccole guest
lectures su applicazioni di network security: guest lecturers
dovrebbero essere il Dr. Michael Willett, IBM Cryptography Competency
Center (in teleconferenza dagli Stati Uniti), ed il Dr. Massimo
Bernaschi (IBM EMEA).
----
Titolo del Corso: Computer Vision
docente: Marcello Pelillo
durata: 20 ore
sede: Venezia
orario: il 6, 20, 26 giugno e 3, 10 luglio dalle 9.00 alle 13.00
contenuto:
The objective of the course is to provide a gentle introduction to the
field of machine visual perception. We will discuss the problems
encountered when equipping a machine with the sense of sight, and
present the state-of-the-art techniques developed to solve them.
Special emphasis will be given to models and algorithms inspired by
the structure of biological visual systems.
1. Introduction
2. The eye and the visual cortex
3. Image formation
4. Edge/curve detection and grouping
5. Texture
6. Stereo
7. Object recognition and classification
References
[1] V. S. Nalwa, "A guided tour of computer vision". Addison-Wesley, 1993.
[2] S. Ullman, "High-level vision". MIT Press, 1996.
----
Titolo del Corso: Universal Coalgebra: a theory of (transition) systems
docente: Jan Rutten
durata: 20 ore
sede: venezia
periodo: some time during july
contenuto: State-based dynamical systems as found throughout computing
science are traditionally described as transition systems or certain
kinds of automata. During the last decade, it has become increasingly
clear that such systems can be captured uniformly as so-called
``coalgebras'' (which are the formal duals of algebras). Coalgebra is
beginning to develop into a field of its own, with its own
(coinductive) proof methods, based on bisimulation, and definition
principles, based on finality. In this course, we shall both treat
the basic theory of coalgebras, and illustrate their use in the
theories of specification and refinement, object-based systems,
chaotical systems, and and probabilistic systems.
|
|
|
