Sign In

Courses 2000

Sort by AttachmentsUse SHIFT+ENTER to open the menu (new window).
Title An introduction to some combinatorial problems in computational biology
Teacher dr. Marie-France Sagot, Institut Pasteur, Paris
Period June 5-June 16

The number of hours suggested for the main parts of the course are just indicative. Time for informal discussions, as well as regularly spaced breaks will be provided. Formal exposition of concepts and algorithms will be alternated with the presentation of some easy to formulate but difficult to solve open problems for the students o consider and "play "with. This should allow them to obtain a more "concrete "grasp of the area and, hopefully, attract some of them to it. A two-level bibliography will be made available, a basic one for those who wish to get just a taste of some of the area 's main topics, and a more extensive one for those who wish to get more deeply involved with computational biology. The course will present some classic notions of the field, but will be strongly based on personal research conducted either with other researchers or with students.The elementary biological notions needed to understand the problems will be introduced all along the course, as the need arises.
1. Sequence comparison: concepts and algorithms (4 hours)
*pairwise comparison
- global alignment
- local alignment
- other variants
*multiple comparison
- global
*optimization algorithms
*statistical approaches
*combinatorial algorithms
- local
*exact algorithms

2. Regularities in sequences (7 hours)
- *motifs extraction
- simple
- structured
- tandem
- general
*structural motifs in RNA

3. Gene prediction (4 hours)
*DNA coding models
*gene finding as an exon assembly

4. Evolution and phylogeny (5 hours)
*sequence alignment revisited
*phylogenetical reconstruction

Title Distributed Algorithms
Teacher prof. Danny Krizanc, Carleton University, Ottawa
Period June 5-June 16
Six lectures on fundamentals:
1. Models of Distributed Systems and Complexity of Distributed Algorithms
2. Leader Election in the Ring - Synchronous Case
3. Leader Election in the Ring - Asynchronous Case
4. Minimum Spanning Tree in General Asynchronous Networks
5. Distributed Consensus and Byzantine Agreement
6. Routing Algorithms
Four lectures on advanced topics:
7. Compact Routing Techniques (E.g., Interval Routing)
8. Computing on Anonymous Networks
9. Distributed Search on Faulty Networks
10. Topics in Mobile Computing

Title Algebraic and Coalgebraic Semantics for Process Specification
Teacher Horst Reichel, Technical University of Dresden
Period June 13-June 30
The aim of the course is to introduce the basic concepts of algebraic specification of data types and coalgebraic specification of process types, and to show how they can be reconciled and generalized. The category theory constructions which are needed will be shortly introduced.
In particular the course will present a uniform categorical model theory for intial specifications of data types, final specifications of process types and their combinations. In order to achieve this unform approach a generalization of Lawvere theories will be developed which is based on the nesting of projective and injective Kan sketches. It will turn out that injective Kan sketches represent recursive data types and that projective Kan sketches represent recursively defined process types.
The resulting model theory is general enough to deal with algebras, co-algebras and with structural transition systems and their external behavior. By means of many examples it will be shown that in the generic model recursively defined functions on data types, co-recursively defined functions on process types and properties of observations can be defined and analysed.
Title Adaptive Processing of Data Structures
Teacher Prof. Ah Chung Tsoi, University of Wollongong
Period September 18 - september 29
Contents of the course
1. Introduction and Motivation. This introduces the students to this class of problems. There will be a number of motivating examples given, to clearly set the scene for the course materials.
2. Data Structures. This introduces the notations and some of the background materials. This will cover data structures: lists, trees, graphs.
3. Syntactical Grammars, and Grammatical Inference. This will be an overview of the classic treatment of syntactical grammars, and grammatical inference. This sets the background for adaptive processing of data structures.
4. Classic Neural Network models for data structure representation. This will cover the use of RAAM, and LRAAM.
5. Deterministic Neural Network Models. This will cover the recursive neuron concept.
6. Supervised Learning Techniques. This will consider the backprop through structure training algorithm, layer by layer training algorithm.
7. Unsupervised learning Techniques. This will consider a number of unsupervised learning techniques, including learning vector quantization.
8. Radial Basis Function Networks. This will give an architecture for data structures involving radial basis functions. Training algorithms will be given.
9. Fuzzy Models. This will give an architecture for data structure processing involving fuzzy models. Training algorithms will be given.
10. Constructive Algorithms. This will give a number of constructive algorithms for neural networks for data structure models.
11. Evolutionary Models. This will discuss the application of genetic algorithm concepts to evolving data structure models.
12. Stochastic Models. This will give an account of stochastic models, involving hidden Markov models.
13. Open problems. We will mention a number of open research problems, e.g., VC dimension and learnability, universal approximations, long term dependency.
14. Conclusions

Title Geometria Computazionale
Teacher Dr. Marco Pellegrini, CNR-IMC, Pisa (e-mail:
Period Settembre-Ottobre
Lo scopo del corso è di introdurre lo studente alla geometria computazionale attraverso le tecniche probabilistiche sviluppate nell'ultimo decennio. Si studieranno problemi applicativi di tipo planare che coinvolgono poligoni e insiemi di poligoni (mappe planari. diagrammi di Voronoi) all'interno di una teoria piu' generale di natura combinatorica (Spazi di configurazioni, Random sampling, epsilon-nets).
Si giungera' quindi a dimostrare bounds asintotici sul tempo medio di calcolo e "tail estimates" sulla deviazione dalla media.
Moduli del corso
1 Introduzione, panoramica sulla geometria computazionale, analisi asintotica degli algoritmi. metodi deterministici e metodi probabilistici.
2 Rappresentazione di punti, segmenti e poligoni. Area di un poligono semplice. Test di virate sinistre e destre. Intersezione di segmenti.
3 Interpretazione geometrica di Quicksort.
4 Skip lists: una struttura dinamica per mantenere insiemi ordinati.
5 Un algoritmo incrementale per la costruzione di mappe trapezoidali.
6 Un algoritmo incrementale per l'intersezione di semipiani.
7 Digrammi di Voronoi
8 Spazi di configurazioni e Random sampling
9 Metodo delle "Conflift lists", analisi della lunghezza media.
10 "Tail estimates" della distribuzione del tempo di calcolo.
11 "Range spaces", "VC-dimension" ed "epsilon-nets".
12 De-randomizzazione. Metodo delle Probabilita' Condizionate.
Il libro di testo consigliato su cui sono basate le lezioni e': K. Mulmuley , "Computational geometry, an introduction through randomized algorithms", Prentice Hall,1994.
Altri testi:
J. O'Rourke , "Computational geometry in C", Cambridge University Press 1994. (Piu' applicativo)
F.P. Preparata and M.I. Shamos, "Computational geometry: an introduction", Springer-Verlag, 1985. (Algoritmi deterministici)
H. Edelsbrunner, "Algorithms in Combinatorial geometry", EATCS Monograph on Theoretical Computer Science, Springer Verlag 1987. (Algoritmi deterministici)
Title Metodi matematici in complessità computazionale
Teacher Dr. Bruno Codenotti, CNR-IMC, Pisa
Period Settembre-Ottobre
1. Il problema della primalita': determinismo, nondeterminismo e tecniche probabilistiche
2. Pseudocasualita' e complessita'
3. Calcolo di forme lineari: limitazioni inferiori
4. La trasformata veloce di Fourier
5. Circuiti algebrici
A.Bernasconi e B.Codenotti, Introduzione alla complessita' computazionale, Springer Verlag, 1998.
A.Bernasconi, B.Codenotti e G.Resta, Metodi matematici in complessita' computazionale, Springer Verlag, 1999.

Title Natural Language Processing
Teacher Dr. Oliviero Stock, IRST, Trento
Period Novembre
Introduzione all'NLP 2 ore
Parsing (con particolare attenzione a chart parsing) 3 ore
Fondamenti di linguistica formale 2 ore
Strutture a feature e unificazione 2 ore
Tecniche per estrazione di informazione da testi 4 ore
Tesauri e Wordnet 2 ore
Un agente conversazionale 2 ore
Temi avanzati da definire 3 ore