Workshop Caos, Complessità e Informazione III
Saranno illustrate connessioni di tipo Brudno tra la crescita dell'entropia in sorgenti quantistiche ergodiche ed una recente definizione di complessità algoritmica quantistica. Saranno anche discusse relazioni con nozioni simili in Teoria dell'Informazione quantistica.
Le sostituzioni ricorsive non sequenziali (Jimenez-Montano, Ebeling et al.) sono state recentemente studiate da Grassberger in relazione a problemi di compressione. Esse agiscono sostituendo una stringa di due caratteri (tipicamente la piu' probabile) con un nuovo simbolo. Grassberger congettura che le iteraziondo il procedimento, il contenuto informativo di una sequenza si concentri nella distribuzione delle coppie di caratteri. Questa congettura e' l'oggetto della nostra analisi.
Dynamical zeta functions provide a powerful method to analyze low-dimensional dynamical systems when the underlying symbolic dynamics is under control. On the other hand even simple one-dimensional maps can show an intricate structure of the grammar rules that may lead to a non smooth dependence of global observable on parameters changes. A paradigmatic example is the fractal diffusion coefficient arising in a simple piecewise linear one-dimensional map of the real line. Using the Baladi-Ruelle generalization of the Milnor-Thurnston kneading determinant it is possible to construct the exact dynamical zeta function for such a map and compute the diffusion coefficient from its smallest zero.
Il DNA ha un contenuto informativo ricchissimo. Allo scopo di estrarlo e comprenderlo si impiegano innumerevoli tecniche, tra cui la ricerca di correlazioni e l'analisi delle periodicita', o analisi in frequenza. Lo studio di una sequenza di DNA avviene assegnando un numero ad ognuno dei quattro nucleotidi, e studiando il corrispondente segnale a tempo discreto. Questa operazione, detta mapping, deve pero' essere affrontata con cautela. Non tutti i mapping sono infatti in grado di estrarre periodicita' "corrette". Nella presentazione si illustrera' un metodo basato sull'entropia di Shannon che permette di estrarre le periodicita' realmente esistenti in una sequenza di DNA.
I'll introduce a one-parameter family of piecewise analytic Markov interval maps interpolating between the Tent map and the Farey map, with the property that their transfer operatorsleave invariant the same Hilbert space of analytic functions and one can study the transition from discrete to continuousspectrum.These maps act as shifts on a family of binary trees which interpolate between the dyadic tree and the Farey tree, and onecan naturally associate to each row of a tree a finite dimensionalstatistical mechanical model whose interaction turns out to beferromagnetic and whose partition function is directly related to the (generalized) transfer operator of the corresponding map. Some general results as well as some open problems will be discussed.
(joint work with Nihat Ay) Stochastic interdependence of a probability distribution on a product space is measured by its Kullback-Leibler distance from the exponential family of product distributions (called multi-information). The sectional curvature of that manifold is negative. The exponential family of pure pair-interactions contains all global maximizers of the multi-information in its closure.
L'attribuzione di testi letterari per mezzo di metodi statistico-matematici ha una storia che almeno all'inizio (anni 60) prescinde dall'utilizzo di computer. Rapidamente però nell'ambito dell'humanities computing si diffonde l'interesse per la stilometria, cioè la misurazione dello stile intesa come criterio oggettivo (numerico/quantitativo) efficace per confrontare i testi, individuarne le somiglianze e, nei casi appropriati, dichiararne la provenienza da un medesimo autore. In questo ambito di ricerche è sempre stata presente una chiara somiglianza con i metodi utilizzati in biologia per le ricerche filogenetiche, tanto che alcuni lavori in ambito testuale vennero effettuati utilizzando lo stesso software impiegato dai biologi per la ricostruzione dei phyla. Un limite evidente, per i lavori di attribuzione di testi su base statistico-matematica, è sempre stato la mancanza di criteri oggettivi di valutazione: ogni studioso tende a lavorare con i suoi programmi, sui suoi materiali testuali, in base a suoi criteri. Tale situazione non permette di far uscire questi metodi di attribuzione da un ambito sperimentale privo di utilità affettiva per problemi del mondo reale. Pochi anni fa si è però svolta una gara internazionale (AAAC, Ad-hoc Authorship Attribution Competition) che ha posto alcuni importanti punti fermi e che ha permesso di passare all'utilizzo di questi metodi per affrontare e possibilmente risolvere problemi reali in ambiti disciplinari anche moto vari e distanti fra loro. Questo contributo esporrà la situazione attuale e descriverà una specifica applicazione di questi metodi nell'ambito della storia contemporanea.
La grande diffusione di XML e di simili linguaggi di markup ha reso attuale il problema della compressione, e in generale della manipolazione, di questi tipi di file. La soluzione efficiente di questi problemi richiede di prendere in considerazione la struttura ad albero implicita in questi file. Per questo motivo si considerano i problemi piu' generali della compressione, navigazione, e ricerca in alberi etichettati e si dimostra come sia possibile risolverli simultaneamente mediante una trasformazione (detta XBW) che generalizza agli alberi la trasformata di Burrows-Wheeler introdotta nel 1994 per le stringhe. Si mostreranno infine alcuni risultati sperimentali che dimostrano come questa tecnica permetta di comprimere file XML e di eseguire ricerche all'interno dei file compressi, con prestazioni superiori a quelle di tutti gli strumenti per la manipolazione di file XML attualmente noti.
Nel 1976 Lempel e Ziv hanno introdotto un parsing (detto esaustivo) le cui buone proprietà hanno permesso di sviluppare una nozione di distanza tra stringhe. Dopo averne discusso le effettive proprietà metriche, presenteremo un'applicazione a due diversi modi di codificare un segnale ECG (semplice RR e HRV) e vedremo come questa distanza permetta di interpretare i risultati in vista di una classificazione clinica dei dati.
La misura della complessità è uno dei principali problemi relativi agli Automi Cellulari (CA). A partire dal lavoro fondamentale di Wolfram del 1984, varie metriche sono state introdotte. Particolarmente efficace è risultata essere la Input-Entropy, che abbiamo utilizzato come fitness per evolvere CA con comportamento complesso. Noi presenteremo i principali risultati ottenuti per CA unidimensionali e bidimensionali. Questi ultimi risultano particolarmente interessanti in quanto si osserva l'emergenza di un grande numero di autoriproduttori, dei quali analizzeremo le principali caratteristiche e la loro tendenza a specializzare forma e funzione.
I recenti sviluppi delle tecniche di sequenziamento del genoma hanno offerto nuove direzioni di ricerca nel campo della Bioinformatica. Un esempio molto importante è costituito dalla ricerca di misure di confronto tra sequenze capaci di catturare i processi evolutivi e i meccanismi funzionali. Molti dei metodi tradizionali usati per il confronto di sequenze biologiche sono basati su tecniche di allineamento che però riescono a considerare sono mutazioni locali nelle sequenze, mentre invece si prestano poco nel caso in cui si debbano misurare eventi come lo spostamento di interi segmenti. Per trattare quindi problemi come ad esempio quello della filogenesi genomica si è rivelato più opportuno l'uso di misure "alignment-free", ovvero non basate su tecniche di allineamento. Molte tra queste sono, per esempio, basate su tecniche di compressione e su nozioni della teoria dell'Informazione. Questo contributo descriverà un nuovo metodo di confronto tra sequenze che non si basa su tecniche di allineamento ma che è invece di natura combinatoria. Tale metodo infatti usa un'estensione (denotata con ebwt) di una trasformazione molto nota e usata nell'ambito della Data Compression (la trasformata di Burrows-Wheeler). Tale trasformata consente di associare ad un insieme di sequenze un'unica sequenza ottenuta mescolando i caratteri presenti nelle sequenze dell'insieme in modo tale che i caratteri che si trovano in contesti simili risultino vicini tra loro. L'idea intuitiva sulla quale tale metodo di confronto si basa, consiste nel fatto che più sono lunghi i segmenti condivisi da due sequenze più vengono mescolati i caratteri di tali sequenze dalla trasformata ebwt. E' possibile formalizzare tale intuizione definendo quindi misure di similarità che sono per natura "alignment-free" e che ben si prestano ad affrontare problemi di tipo filogenetico o di classificazione.