ID:
A001895
Durata (ore):
36
CFU:
6
SSD:
ALGEBRA
Url:
DATA SCIENCE/PERCORSO COMUNE Anno: 2
Anno:
2023
Dati Generali
Periodo di attività
Secondo Semestre (26/02/2024 - 31/05/2024)
Syllabus
Obiettivi Formativi
L’obbiettivo del corso è quello di presentare algoritmi fondamentali per analizzare dati che popolano il mondo dell’informazione tramite metodologie combinatorie: dati multimediali, grandi dataset.
Il dato multimediale (e.g. audio, immagini) ha al suo interno un componente periodica che si associa in modo diretto al gruppo ciclico finito. In particolare tramite i caratteri associati ad esso e la Trasformata Discreta di Fourier (DFT) è possibile estrarre tale informazione. Esempi di notevole interesse sono nella elaborazione delle immagini e dell’audio (e.g. compressione). Viene descritto l’algoritmo utilizzato in tale ambito, noto come Fast Fourier Transform.
Data un grande dataset uno dei primi obbiettivi è quello di partizionarlo adeguatamente, per ottenere una sua rappresentazione ridotta che preservi nel modo migliore le informazioni del dataset originale. Questa partizionamento viene detto “clustering”. Il clustering permette di definire gli oggetti prossimi mediante “distanze” intimamente connesse al dataset in oggetto. Anche in questo caso verranno descritti algoritmi fondamentali per il clustering: Quello non gerarchico e quello gerarchico.
In modo naturale in entrambi gli oggetti di studio (dato multimediale digitalizzato e dataset) emerge la struttura combinatoria del grafo (e.g. grafo circolante nel caso del gruppo ciclico, network nel dataset). Alcuni fondamentali invarianti del grafo verranno studiati mediante algoritmi effettivi per il calcolo.
Nel corso si farà uso di Python e di alcuni package utili per il calcolo (e.g. numpy, scipy, igraph, networkx, etc.)
Al termine del corso lo studente sarà in grado di rappresentare un gruppo abeliano finito per mezzo del suo gruppo dei caratteri, le principali proprietà della Trasformata Discreta di Fourier (DFT) definita su un gruppo, alcune applicazioni della DFT su dati multimediali. Inoltre sarà capace di definire metodi per il partizionamento di grandi dataset. Ed infine conoscerà metodi ed algoritmi per il calcolo di particolari invarianti di grafi, della FFT e di partizionamento di insiemi finiti
Il dato multimediale (e.g. audio, immagini) ha al suo interno un componente periodica che si associa in modo diretto al gruppo ciclico finito. In particolare tramite i caratteri associati ad esso e la Trasformata Discreta di Fourier (DFT) è possibile estrarre tale informazione. Esempi di notevole interesse sono nella elaborazione delle immagini e dell’audio (e.g. compressione). Viene descritto l’algoritmo utilizzato in tale ambito, noto come Fast Fourier Transform.
Data un grande dataset uno dei primi obbiettivi è quello di partizionarlo adeguatamente, per ottenere una sua rappresentazione ridotta che preservi nel modo migliore le informazioni del dataset originale. Questa partizionamento viene detto “clustering”. Il clustering permette di definire gli oggetti prossimi mediante “distanze” intimamente connesse al dataset in oggetto. Anche in questo caso verranno descritti algoritmi fondamentali per il clustering: Quello non gerarchico e quello gerarchico.
In modo naturale in entrambi gli oggetti di studio (dato multimediale digitalizzato e dataset) emerge la struttura combinatoria del grafo (e.g. grafo circolante nel caso del gruppo ciclico, network nel dataset). Alcuni fondamentali invarianti del grafo verranno studiati mediante algoritmi effettivi per il calcolo.
Nel corso si farà uso di Python e di alcuni package utili per il calcolo (e.g. numpy, scipy, igraph, networkx, etc.)
Al termine del corso lo studente sarà in grado di rappresentare un gruppo abeliano finito per mezzo del suo gruppo dei caratteri, le principali proprietà della Trasformata Discreta di Fourier (DFT) definita su un gruppo, alcune applicazioni della DFT su dati multimediali. Inoltre sarà capace di definire metodi per il partizionamento di grandi dataset. Ed infine conoscerà metodi ed algoritmi per il calcolo di particolari invarianti di grafi, della FFT e di partizionamento di insiemi finiti
Prerequisiti
Conoscenze di algebra lineare e di programmazione. Conoscenze di base su dati digitalizzati.
Metodi didattici
Lezioni teoriche e applicative. Utilizzo di software di calcolo simbolico e numerico: Python con alcuni package.
Verifica Apprendimento
Presentazione di un progetto che abbia un report dettagliato ed una implementazione in Python
Testi
Audrey Terras, Fourier Analysis on Finite Groups and Applications, 1999, London Mathematical Society Student Texts.
A. Bernasconi and B. Codenotti. “Spectral analysis of Boolean functions as a graph eigenvalue problem”. In: IEEE Transactions on Computers 48.3 (Mar. 1999), pp. 345–351.
A. Bernasconi and B. Codenotti. “Spectral analysis of Boolean functions as a graph eigenvalue problem”. In: IEEE Transactions on Computers 48.3 (Mar. 1999), pp. 345–351.
Contenuti
Strutture combinatorie
Partizioni di insiemi e relazioni. Grafi e alberi. Partizionamento nelle strutture algebriche. Strutture periodiche. Definizione di Serie di Fourier. Lo spazio di Hilbert generato da una base ortonormale indotto da: funzioni trigonometriche, funzioni esponenziali complesse. Il cerchio finito Zn. Funzioni esponenziali complesse ed il cerchio finito. Congruenze lineari.
Il toro finito
Il Teorema cinese dei resti. Corollario. Isomorfismi tra Zn e una somma diretta di anelli. Una applicazione del CRT a RSA. Prodotto cartesiano di grafi ed il toro finito. Grafi di Cayley. Gruppi moltiplicativi e funzioni complesse su Zn. Funzione di Eulero. Proprietà. Gruppo moltiplicativo (Zn)*. Teorema. (Zp)*è ciclico se p è primo.
Trasformata Discreta di Fourier su Zn.
Funzioni complesse su Zn. Lo spazio vettoriale finito su C L^2(Zn). Funzioni Delta. L'operatore di convoluzione. Il gruppo dei caratteri. Definizione della trasformata discreta di Fourier. Esempi. Proprìetà della DFT su Zn. Relazione di ortogonalità dei caratteri di Zn. La DFT come mappa lineare biettiva da L^2(Zn) a L^2(Zn). La DFT e la convoluzione. Proprietà di dilatazione e traslazione della DFT. DFT su funzioni pari e dispari. Esempi. Formula di inversione. Teorema di Plancherel.
Grafi circolanti e operatore di adjacenza.
Notazione sui grafi. Isomorfismo tra grafi. Grafi di Cayley su Zn: I grafi circolanti. Shell S(r) e isomorfismi. Regolarità dei grafi di Cayley. L'operatore di adiacenza A ed i suoi autovalori. Il numero di cammini di un grafo di lunghezza l che unisce i vertici v_i e v_j è l'entrata (i,j) di A^l. Un grafo connesso di diametro d ha almeno d+1 autovalori distinti.
Spettro di un grafo k-regolare.Esempi.
Cammini casuali su grafi di Cayley
Generatori di numeri random. Definizione di cammini random su Zn. Definizione della matrice di transizione di Markov. Convergenza dei cammini casuali alla distribuzione uniforme. Significato probabilistico della convoluzione. Upper Bound Lemma rispetto alla densità di probabilità. DFT della densità di probabilità.
DFT su un gruppo abeliano finito e
inversione del teorema di Lagrange.
Isomorfismo tra il gruppo ed il suo duale.
La relazione di ortoganalità dei caratteri su G. DFT su G. Principali proprietà. DFT su funzioni bidimensionali. La DFT sulle immagini.
Trasformata di Hadamard e grafi di Hamming sui codici.
DFT su (F_2)^n. La trasformata di Hadamard. Grafi di Cayley su (F_2)^n. Grafi e distanza di Hamming. Confronto tra le distanze. Autovalori e operatore di adiacenza dell'ipercubo di dimensione n tramite la DFT. Grafi di Cayley X(F_2^n, S(r)). Connessione con la teoria dei codici. Autovalori e l'operatore di adiacenza del grafo definiti tramite la DFT. Esempi di codici. Teorema di MacWilliams.
Crittografia e funzioni booleane. Grafi fortemente regolari.
Grafi fortemente regolari e i 3 autovalori distinti dell'operatore di adiacenza. Esempi. Funzioni booleane e grafi di Cayley con 1 e 2 autovalori.
Caratterizzazione delle funzioni bent tramite lo spettro dei grafi di Cayley.
Partizioni di insiemi e relazioni. Grafi e alberi. Partizionamento nelle strutture algebriche. Strutture periodiche. Definizione di Serie di Fourier. Lo spazio di Hilbert generato da una base ortonormale indotto da: funzioni trigonometriche, funzioni esponenziali complesse. Il cerchio finito Zn. Funzioni esponenziali complesse ed il cerchio finito. Congruenze lineari.
Il toro finito
Il Teorema cinese dei resti. Corollario. Isomorfismi tra Zn e una somma diretta di anelli. Una applicazione del CRT a RSA. Prodotto cartesiano di grafi ed il toro finito. Grafi di Cayley. Gruppi moltiplicativi e funzioni complesse su Zn. Funzione di Eulero. Proprietà. Gruppo moltiplicativo (Zn)*. Teorema. (Zp)*è ciclico se p è primo.
Trasformata Discreta di Fourier su Zn.
Funzioni complesse su Zn. Lo spazio vettoriale finito su C L^2(Zn). Funzioni Delta. L'operatore di convoluzione. Il gruppo dei caratteri. Definizione della trasformata discreta di Fourier. Esempi. Proprìetà della DFT su Zn. Relazione di ortogonalità dei caratteri di Zn. La DFT come mappa lineare biettiva da L^2(Zn) a L^2(Zn). La DFT e la convoluzione. Proprietà di dilatazione e traslazione della DFT. DFT su funzioni pari e dispari. Esempi. Formula di inversione. Teorema di Plancherel.
Grafi circolanti e operatore di adjacenza.
Notazione sui grafi. Isomorfismo tra grafi. Grafi di Cayley su Zn: I grafi circolanti. Shell S(r) e isomorfismi. Regolarità dei grafi di Cayley. L'operatore di adiacenza A ed i suoi autovalori. Il numero di cammini di un grafo di lunghezza l che unisce i vertici v_i e v_j è l'entrata (i,j) di A^l. Un grafo connesso di diametro d ha almeno d+1 autovalori distinti.
Spettro di un grafo k-regolare.Esempi.
Cammini casuali su grafi di Cayley
Generatori di numeri random. Definizione di cammini random su Zn. Definizione della matrice di transizione di Markov. Convergenza dei cammini casuali alla distribuzione uniforme. Significato probabilistico della convoluzione. Upper Bound Lemma rispetto alla densità di probabilità. DFT della densità di probabilità.
DFT su un gruppo abeliano finito e
inversione del teorema di Lagrange.
Isomorfismo tra il gruppo ed il suo duale.
La relazione di ortoganalità dei caratteri su G. DFT su G. Principali proprietà. DFT su funzioni bidimensionali. La DFT sulle immagini.
Trasformata di Hadamard e grafi di Hamming sui codici.
DFT su (F_2)^n. La trasformata di Hadamard. Grafi di Cayley su (F_2)^n. Grafi e distanza di Hamming. Confronto tra le distanze. Autovalori e operatore di adiacenza dell'ipercubo di dimensione n tramite la DFT. Grafi di Cayley X(F_2^n, S(r)). Connessione con la teoria dei codici. Autovalori e l'operatore di adiacenza del grafo definiti tramite la DFT. Esempi di codici. Teorema di MacWilliams.
Crittografia e funzioni booleane. Grafi fortemente regolari.
Grafi fortemente regolari e i 3 autovalori distinti dell'operatore di adiacenza. Esempi. Funzioni booleane e grafi di Cayley con 1 e 2 autovalori.
Caratterizzazione delle funzioni bent tramite lo spettro dei grafi di Cayley.
Lingua Insegnamento
Lingua Inglese
Corsi
Corsi
DATA SCIENCE
Laurea Magistrale
2 anni
No Results Found
Persone
Persone
Ricercatrice/tore a tempo det.
No Results Found