Complementi di analisi matematica

Alberto Abbondandolo      Tel. 050 2213242

Calcolo differenziale ed integrale per funzioni di una variabile reale.

Tema centrale del corso e' la ”Combinatoria analitica”, ossia la scienza del contare oggetti strutturati di una data dimensione n e fornire sviluppi asintotici per n che tende all’infinito. Problemi tipici sono i seguenti:

• Quanti sono i grafi con n vertici? Quanti gli alberi? Quanti gli alberi binari? Come mai i modi di dividere un poligono in triangoli sono tanti quanti gli alberi?

• Quante volte la stringa ”complementidianalisimatematica” e' nascosta in un testo random di n lettere?

• Riordiniamo i numeri da 1 a n in modo casuale. Quale lunghezza possiamo aspettarci che avra' la piu' lunga stringa di numeri consecutivi che risulti ordinata in modo crescente? Di quante stringhe di questo tipo sara' composta l’intera sequenza?

• I 100 studenti di un corso vengono valutati nel seguente modo: il docente scrive i 100 numeri di matricola su 100 foglietti che distribuisce casualmente nei 100 cassetti del suo schedario. Gli studenti entrano nello studio del docente uno alla volta, possono scegliere 50 dei cassetti ed aprirli alla ricerca del proprio numero di matricola. Non possono comunicare tra loro. Passeranno tutti l’esame se ognuno di loro avra' trovato il proprio numero di matricola. Se anche un solo studente non lo trovera', saranno tutti bocciati. La probabilita' che vengano promossi e' davvero molto bassa (ad esempio due elevato alla -100) o possono elaborare una strategia che migliori di molto le loro possibilita'?

Saper risolvere problemi di questo tipo e' importante nei campi piu' disparati: dall’analisi degli algoritmi alla crittografia, dallo studio delle sequenze genomiche alla chimica analitica, dalla teoria dei giochi alla meccanica statistica. Gli strumenti matematici per affrontare questi problemi sono le serie generatrici e, sorprendentemente, l’ analisi delle funzioni definite sul campo complesso, una disciplina centrale in molti altri campi della matematica e delle sue applicazioni.

The main topic of this class is "analytic combinatorics". In a nutshell, this means counting structured objects of dimension n, and deriving asymptotics as n tends to infinity. Such problems arise naturally in various fields: from the analysis of algorithms to cryptography, from the study of genomic sequences to analytical chemistry, from game theory to statistical mechanics.

The mathematical tools required to solve problems of this sort include generating functions and, quite surprisingly, the theory of functions on the complex domain. Several examples will be discussed, as well as the mathematical theory behind them.

Gran parte del corso sara' rivolta alla discussione di esempi. La parte teorica comprende i seguenti argomenti:

1. Combinatoria.
  (a) Contare insiemi strutturati.
  (b) Serie generatrici ordinarie ed esponenziali.
  (c) Dizionario: operazioni combinatorie su insiemi strutturati versus operazioni algebriche sulle funzioni generatrici.
  (d) La formula di Stirling e prime stime asintotiche.

2. Analisi complessa.
  (a) Serie di potenze.
  (b) Funzioni olomorfe.
  (c) La formula di Cauchy e il calcolo dei residui.

3. Combinatoria asintotica.
  (a) Studio delle singolarita' di funzioni olomorfe.
  (b) Stime asintotiche.
  (c) Alla ricerca di pattern in strutture random.

Il testo piu' completo ed aggiornato sulla combinatoria analitica e':

Philippe Flajolet, Robert Sedgewick, Analytic combinatorics, 2007.

Si tratta di un volume non ancora pubblicato, ma reperibile in rete all’indirizzo:

http://algo.inria.fr/flajolet/Publications/books.html

Il capitolo iniziale, ”An invitation to Analytic Combinatorics”, riassume bene i contenuti e lo spirito di questo corso. Di piu' agile lettura, il classico:

Herbert S. Wilf, Generatingfunctionology, Academic Press 1990.

I primi tre capitoli del libro:

Henri Cartan, Elementary theory of analytic functions of one or several complex variables, Dover 1995.

contengono tutta l'analisi complessa di cui avremo bisogno. Per un’introduzione all’analisi complessa con un occhio attento alle applicazioni, si consultino i due volumi di:

Peter Henrici, Applied and computational complex analysis, John Wiley, 1974.

Infine, per imparare a fare i conti, il classico:

Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete mathematics, Addison Wesley 1989.

Prova scritta ed orale. Su richiesta degli studenti potranno essere organizzati dei compitini.