Courses organized by Dipartimento di Matematica e Informatica

you must be logged-in to have full access to course material

Combinatorial methods for the independent set problem

Description
Course outline: 

The maximum independent set problem is the problem of finding, in a given graph, the maximum size of a subset of pairwise non-adjacent vertices. Closely related to the vertex cover and the maximum clique problems, this NP-hard problem is one of the basic problems of algorithmic graph theory. Since the 1970s, various methods have been developed to obtain polynomial time solutions to the problem when the input is restricted to particular graph classes.

We will present an overview of classical as well as more recent combinatorial approaches for the maximum independent set problem. In particular, we will discuss the method of augmenting graphs, the decomposition by clique separators, the modular decomposition, bounded tree-width and bounded clique-width. Some applications of various combinations of these methods will also be mentioned.

Ehrenfeucht-Fraisse Games: Applications and Complexity

Description
Course outline: 

The method of Ehrenfeucht-Fraisse (EF-game for short) provides a characterisation of m-equivalence for first-order logic, which can be easily adapted to other logical languages (second-order logics, fixed-point logics, modal logics, etc...). Besides, it has special relevance to finite model theory, where other model-theoretic techniques, such as the Compactness Theorem or the Loewenhein-Skolem theorem, cannot be applied.

In the first part of the course, we introduce the fundamental notions related to EF-games as logical combinatorial games. In particular, we describe the correspondence between formulae and games, we analyze the notions of winning strategies, the remoteness of a game and the optimal (as opposed to winning) strategies for a player. Then, we illustrate some important applications of the Ehrenfeucht-Fraisse method, such as Hanf's theorem.

In the second part of the course, we show how EF-games can be exploited to prove inexpressivity results. Besides a description of the proof techniques and of some classical examples, we present some general sufficient conditions that can be used to prove inexpressivity results, such as Arora and Fagin's theorem and Schwentick's theorem. Moreover, we provide a detailed account of Gaifman's theorem and subsequent results about normal forms for first-order logic.

In the third part of the course, we focus on algorithmic questions related to EF-games. We discuss the known algorithmic and complexity results about EF-games (e.g., how can the winner of a game and/or its winning strategy be computed? How hard is it to them? What is the remoteness of an unbounded game?), in general and for specific classes of relational structures.

Course material available at http://sole.dimi.uniud.it/~angelo.montanari/courses.php

Introduction to Software Configuration Management

Description
Course outline: 

Software Configuration Management (SCM) is one of the fundamental key process areas of the Capability Maturity Model for software development. It will have to be in place if an organization wants to progress from the initial level of maturity that is characterized by chaos and confusion.
SCM has two different focus areas: what the company needs to control changes to its products and ensure their integrity? and what a team of developers need to manage and co-ordinate their collaboration on a project. For many aspects the needs are quite similar in nature, but will be implemented in different ways. However, there are also some needs that are particular for each focus area.
In two pairs of lecture-exercises, this short course will introduce the students to the main concepts and principles of SCM for each of the two focus areas. The lectures will explain and motivate the concepts and principles and during the exercises the students will discuss how to apply and use the concepts and principles and how to relate and adapt them to different situations and contexts. In addition, there is a computer lab where the students will have the opportunity to experiment with different work models and co-ordination mechanisms and will obtain a general template for evaluating version control tools.

Computational Complexity (Complessita` computazionale)

Description
Course outline: 

Obiettivi del corso (italiano)

Il corso vuole introdurre alla teoria ed alla pratica della complessita` computazionale. Tale disciplina, profonda fonte metodologica, consente di dare unitarieta` alla moltitudine di problemi che vengono affrontati nella pratica algoritmica, nell'informatica teorica, e nella matematica discreta tutta. Le competenze offerte dal corso sono di primario interesse per chi, incuriosito dall'algoritmica, o piu` in generale dall'intersezione tra matematica discreta ed informatica teorica, volesse potenziare le proprie capacita` nel risolvere problemi e nel dimostrare teoremi. Primo obiettivo del corso e` quello di trasmettere frammenti e squarci sulla fondamentale benche` spesso misconosciuta arte del ridurre un problema ad un altro.

La prima parte del corso vuole essere un'introduzione ``chiavi in mano'' all'uso della teoria dell'NP-completezza. Adotteremo in questo un approccio pragmatico del tipo ``riduzioni fai da te''. Cio` nonostante cercheremo di far apprezzare anche in questo contesto il ruolo principe che la teoria della complessita` e` chiamata a giocare quale fondamentale strumento di indagine in matematica discreta.

La seconda parte del corso vertera` su argomenti piu` avanzati ed avra` lo scopo di far assaporare lo spirito della complessita` computazionale come disciplina autonoma.

Obiettivi del corso (inglese)

After the course, you will be able to prove that a certain problem of yout interest is NP-complete. And, actually, you will enjoy this fascinating game, namely "the art of reducing one problem to another". Hopefully, you will also grow up a sort of sensitivity which in most cases which allow you to tell simply by heart whether a problem can be solved or not. You will also have the tools to distinguish between good and bad theorems, and a base from which to access the realm of Discrete Mathematics. A last target, to be more explicitly and specifically addressed only as far as some space remains after the previous ones, is to get a flavour of Computational Complexity and its deep but fascinating and fundamental questions.

Prerequisiti (italiano)

  • Interesse nei contenuti del corso.
  • Conoscenza di un qualsiasi linguaggio di programmazione imperativo.
  • Conoscenza di alcuni algoritmi e di strumenti per l'analisi di algoritmi.
  • Aver appreso le nozioni base di informatica teorica:
    • problemi come linguaggi su alfabeto finito,
    • macchine di Turing,
    • decidibilita`, indecidibilita` e semidecidibilita`.
    • Conoscenze di base in probabilita` ci consentiranno eventualmente di toccare questioni legate a classi di complessita` nel randomizzato.

Prerequisiti (inglese)

  • Knowledge of some basic english + human gesture and willingness to communicate.
  • Interest in the topics of the course.
  • Having some experience in programming, and/or having learned at least one imperative programming language, so as to have a feeling of what can be done or not with a computer, and how it has to be done at a sufficiently low level.
  • Some knowledge and interst in algorithms.
  • Having the basic underpinnings of Computer Science Theory: problems as languages over finite alphabet, Turing machines.
  • (What needed here you can get through self-study, I can point you to some source material).

Contenuti del corso (italiano)

Ipotesi di Programma (tutta da contrattare con voi, e poi da adattare al divenire)

  • La pigra arte del ridurre un problema ad un altro
    • Alcuni problemi della classe P: 2-SAT, HornSAT, reachability, bipartiteness, bipartite matching.
    • La classe co-NP: cos'e` un buon teorema? accoppiamenti bipartiti, massimo flusso, la leggenda di Mago Merlino e Re Artu`.
    • Problemi NP-completi: uno per tutti e tutti per uno.
    • Riduzioni a go go.
    • Il teorema di Cook.
  • Problemi di difficile classificazione
    • Se P$\neq$NP allora esistono problemi intermedi.
    • La gerarchia polinomiale.
    • Giochi di Mago Merlino e Re Artu`.
    • L'isomorfismo di grafi e la sua combriccola.
  • Risorsa Spazio
  • Famiglie di Circuiti
  • Randomizzazione

Contenuti del corso (inglese)

  • The lazy art of reducing one problem to another.
  • Some problems in the P-class: 2-SAT, HornSAT, reachability, bipartiteness, bipartite matching, flows.
  • P, NP, coNP.
  • Good theorems and characterizations: the tale of King Arthur and Wizard Merlin.
  • Structural complexity beyond NP and other topics to be choosen together,
    accordingly to our likes and dislikes.

Metodi didattici (italiano)

L'impegno maggiore spetta agli studenti, i quali sono chiamati ad apprendere ed utilizzare nozioni a loro piu` nuove. Il docente si pone l'obbiettivo di facilitare l'assimilazione di competenze e conoscenze per le quali esiste una consolidata letteratura, fornendo un accesso diretto a quella che e` la parte viva e di pragmatica nascosta che i testi fanno fatica a trasmettere. La parte formale, per altro fondamentale in queste discipline, e` invece meglio attingerla direttamente dai testi e sfruttare le ore di lezione per crescere assieme dubbi, curiosita` ed entusiasmi, e soprattutto soluzioni autonome piu` o meno corrette. Il docente confida nell'aiuto e nella partecipazione attiva da parte degli studenti.

MODALITA` DI VALUTAZIONE

Sostanzialmente dovete scegliervi voi il problema o la tematica di vostro interesse, su cui lavorare e/o approfondire eventualmente con la mia assistenza ed aiuto. Certo, durante il corso proporro` esercizi da svolgere a casa e forse assegnero` letture che aprano spunti di discussione in classe e che stimolino una partecipazione attiva rovesciando magari talvolta il rapporto docente-alunno. Ma avere dei vostri problemi, o giocare di anticipo su uno dei testi consigliati o di riferimento, potra` aiutarvi nell'assumere un ruolo attivo o propositivo da subito e meglio centrato sui vostri interessi. Tutto questo e` per me gia` esame. Confido individuiate voi un argomento di vostro interesse il cui eventuale approfondimento vada poi a costituire il vostro esame (con una discussione/presentazione pubblica? lascio a voi ...). Nella modalita' provetta avete l'occasione di comporre una vostra prima dimostrazione di NP-completezza gia' durante il corso. Anche se avete svolto la provetta, potete comunque optare per un ulteriore esame non tradizionale in cui concordare con me un argomento da approfondire. Se invece non ne avete la voglia o il tempo, siete liberi di non approfittare ne' di provetta ne' di esame.

Metodi didattici (inglese)

I expect the students to put their effort to get as much as possible. Good books (better than I can possibly teach) are available. If students actively participate to the course, also studying authonomously, posing questions, and sharing doubts and interests, we will all enjoy a stimulating learning environment. The depth, beauty, and centrality of the arguments covered, as you will also help me to choose, will be the sole lasting payoff to our efforts.

Testi

Michael R. Garey/ David S. Johnson,
COMPUTERS AND INTRACTABILITY - A Guide to the Theory of NP-Completeness,
W.H. Freeman and Company, San Francisco (1979).

Christos H. Papadimitriou,
Computational complexity,
Addison-Wesley Publishing Company, Reading, MA, 1994.
ISBN: 0-201-53082-1

Lane A. Hemaspaandra and Mitsunori Ogihara,
The Complexity Theory Companion,
Springer-Verlag, 2002.
ISBN 3-540-67419-5