Offerta Didattica

 

ENGINEERING AND COMPUTER SCIENCE

ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS (yearly)

Classe di corso: LM-32, 18 - Classe delle lauree magistrali in Ingegneria informatica
AA: 2021/2022
Sedi: MESSINA
SSDTAFtipologiafrequenzamoduli
INF/01Affine/IntegrativaLiberaLibera
CFUCFU LEZCFU LABCFU ESEOREORE LEZORE LABORE ESE
128049648048
Legenda
CFU: n. crediti dell’insegnamento
CFU LEZ: n. cfu di lezione in aula
CFU LAB: n. cfu di laboratorio
CFU ESE: n. cfu di esercitazione
FREQUENZA:Libera/Obbligatoria
MODULI:SI - L'insegnamento prevede la suddivisione in moduli, NO - non sono previsti moduli
ORE: n. ore programmate
ORE LEZ: n. ore programmate di lezione in aula
ORE LAB: n. ore programmate di laboratorio
ORE ESE: n. ore programmate di esercitazione
SSD:sigla del settore scientifico disciplinare dell’insegnamento
TAF:sigla della tipologia di attività formativa
TIPOLOGIA:LEZ - lezioni frontali, ESE - esercitazioni, LAB - laboratorio

Obiettivi Formativi

Far conoscere le teorie e le metodologie algoritmiche per la soluzione di problemi decisionali in differenti ambiti con particolare riguardo alla modellazione mediante grafi di relazioni tra gli elementi di un sistema complesso. Far conoscere costi e benefici legati all'adozione di algoritmi e strutture dati. Far conoscere i principi base di un moderno linguaggio di programmazione utilizzato per l'efficace modellazione di sistemi complessi. Far conoscere i principi base dei moderni sistemi di esecuzione distribuita di algoritmi ottimizzati per la risoluzione di problemi complessi, e i principi base della teoria dell’informazione utile alla conoscenza, codifica e compressione dei dati. Far applicare le teorie e le metodologie algoritmiche a casi di studio da analizzare criticamente affiancando alle lezioni frontali relative agli aspetti teorici esercitazioni pratiche di programmazione e analisi. Far riconoscere: 1) gli aspetti significativi (entità e relazioni) in un problema da modellare, 2) le conseguenze, in termini di comportamento del modello, delle ipotesi di partenza. Sviluppare un adeguato grado di autonomia di giudizio nella analisi di problemi complessi. Far apprendere un linguaggio specifico della disciplina. Sviluppare la capacità di comunicare efficacemente e con linguaggio tecnico nell’ambito della definizione e descrizione di problemi in sistemi complessi delineandone le soluzioni algoritmiche. Fare acquisire un metodo di studio e di analisi adeguato all'analisi autonoma di problemi avanzati. Sviluppare la capacità di verifica e aggiornamento nel settore del software necessari all’implementazioni di nuove soluzioni adeguate.

Learning Goals


Metodi didattici

Al fine di raggiungere gli obiettivi formativi previsti, il corso si articola attraverso lezioni frontali, esercitazioni in aula, esercitazioni guidate dal docente. Tutte le attività sono svolte con supporto di slide delle lezioni. Le slide presentate sono condivise tramite la classe MS Teams dedicata.

Teaching Methods


Prerequisiti

Conoscenze di base di Algoritmi e Strutture Dati, conoscenza di un linguaggio di programmazione. Conoscenza di base di architetture di calcolo distribuito.

Prerequisites


Verifiche dell'apprendimento

Test on-line disponibile tramite la piattaforma di e-learning dell’Università. Gli studenti effettuano il test il giorno stabilito dell’esame nei laboratori messi a disposizione dall’Ateneo e concordati con il docente. La valutazione del test è compresa tra 0 e 15. E’ necessario prendere almeno 10 al test per accedere alla verifica orale. Il risultato del test rimane valido per 12 mesi, entro cui lo studente dovrà completare l’esame. La verifica orale ha una valutazione compresa tra 0 e 10. L’esame prevede un progetto opzionale, a scelta dello studente. Il progetto viene discusso in sede di verifica orale ed ha una valutazione compresa tra 0 e 5. Il voto finale, in trentesimi, è dato dalla somma del voto del test, quello dell’esame orale ed, eventualmente, del progetto.

Assessment


Programma del Corso

------------------------------------------------------------ Modulo: 6094/1 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS A ------------------------------------------------------------ MODULO A -INTRODUZIONE A PYTHON: Oggetti in Python, Espressioni, operatori e precedenza, Flusso di controllo, Funzioni, Gestione dell’I/O, Gestione delle eccezioni, Iteratori e generatori, Visibilità e spazio dei nomi, Moduli -PROGRAMMAZIONE ORIENTATA AGLI OGGETTI: Obiettivi, principi di progettazione e pattern della programmazione orientata agli oggetti, Definizione delle classi: overloading e metodi speciali, iteratori, Ereditarietà, Spazio dei nomi e orientazione agli oggetti, Copia superficiale e profonda -ANALISI DEGLI ALGORITMI: Operazioni primitive, Analisi asintotica: notazione Theta, O e Omega -ALGORITMI SUI GRAFI: Il tipo di dato astratto grafo, Strutture dati per i grafi: lista di archi, lista di adiacenza, mappa di adiacenza, matrice di adiacenza, Attraversamento dei grafi: ricerca in profondità, ricerca in ampiezza, Chiusura transitiva, Grafi diretti aciclici: ordinamento topologico, Percorsi minimi: grafi pesati, algoritmo di Dijkstra, Alberi di ricopertura minimi: algoritmo di Prim-Jarnik, algoritmo di Kruskal -INTRODUZIONE ALLA NETWORK SCIENCE: Grado, grado medio e distribuzione di grado, Reti pesate, reti bipartite, Percorsi e distanze –Connessione – Coefficiente di clustering, Leggi di potenza e reti scale-free, Hub, Invarianza di scala -RETI MODELLO: Il modello di rete random, Numero di link, Distribuzione di grado, Evoluzione di reti random, Le reti reali sono supercritiche, Small world, Coefficiente di clustering, Crescita e aggregazione preferenziale, Il modello di Barabasi-Abert, Dinamica del grado, distribuzione di grado, Assenza di crescita o aggregazione preferenziale, Il modello di Bianconi-Barabasi – Misura della fitness -CORRELAZIONE DI GRADO: Introduzione, Assortatività e disassortatività, Misura delle correlazioni di grado -COMUNITÀ: Introduzione – Fondamenti delle comunità, Clusterizzazione gerarchica (algoritmo di Ravasz, algoritmo di Girvan-Newman), Modularità, Individuazione di comunità: algoritmo goloso di Newman -FENOMENI DIFFUSIVI: Introduzione, Modellazione di epidemie: modelli SI, SIS, SIR, Epidemie su reti MODULO B -PROBLEMI RAPPRESENTATIVI: Cinque problemi rappresentativi, Pianificazione degli intervalli, Corrispondenza stabile e corrispondenza perfetta, Intervallo di Scheduling ponderato. PROGRAMMAZIONE DINAMICA: Schedulazione degli intervalli ponderati, Minimi quadrati segmentati: scelte a più vie, Struttura secondaria del RNA: programmazione dinamica su intervalli. FLUSSO DI RETE: Il problema del flusso massimo, L'algoritmo Ford-Fulkerson, Flussi massimi e tagli minimi in una rete, La scelta dei buoni percorsi di miglioramento, L'algoritmo Preflow-Push Maximum-Flow, Applicazioni ALGORITMI NEI SISTEMI DISTRIBUITI: L'approccio Map-reduce, Hadoop INCERTEZZA E INFORMAZIONE: Entropia: scelta e incertezza, Scelta con probabilità nota, Entropia condizionale, Determinazione assiomatica dell'entropia, Informazione e sua misura, Divergenza Kullback-Leibler, Probabilità come informazione CODIFICA EFFICIENTE DELLE INFORMAZIONI: Codifica di una singola variabile casuale, Codici privi di prefisso, Alberi n-ari per la codifica, Disuguaglianza Kraft, Codici efficienti, Lunghezza e incertezza del percorso degli alberi n-ari probabilizzati, Teorema di codifica senza rumore, Codici Huffman, Codifica da variabile a lunghezza fissa, codice Tunstall, Algoritmo di costruzione del codice Tunstall, Codifica dei numeri interi positivi, Codifica di sorgenti con codifica Memory Huffman di slice, Schema di codice sorgente Elias-Willems, Codici Lempel-Ziv, gzip e bzip2 CODIFICA PER TRASMISSIONE RUMOROSA: Canali di comunicazione, Lemma di Fano, Il teorema della codifica rumorosa, Codici di ripetizione ------------------------------------------------------------ Modulo: 6094/2 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS B ------------------------------------------------------------ -PROBLEMI RAPPRESENTATIVI: Cinque problemi rappresentativi, Pianificazione degli intervalli, Corrispondenza stabile e corrispondenza perfetta, Intervallo di Scheduling ponderato. PROGRAMMAZIONE DINAMICA: Schedulazione degli intervalli ponderati, Minimi quadrati segmentati: scelte a più vie, Struttura secondaria del RNA: programmazione dinamica su intervalli. FLUSSO DI RETE: Il problema del flusso massimo, L'algoritmo Ford-Fulkerson, Flussi massimi e tagli minimi in una rete, La scelta dei buoni percorsi di miglioramento, L'algoritmo Preflow-Push Maximum-Flow, Applicazioni ALGORITMI NEI SISTEMI DISTRIBUITI: L'approccio Map-reduce, Hadoop INCERTEZZA E INFORMAZIONE: Entropia: scelta e incertezza, Scelta con probabilità nota, Entropia condizionale, Determinazione assiomatica dell'entropia, Informazione e sua misura, Divergenza Kullback-Leibler, Probabilità come informazione. CODIFICA EFFICIENTE DELLE INFORMAZIONI: Codifica di una singola variabile casuale, Codici privi di prefisso, Alberi n-ari per la codifica, Disuguaglianza Kraft, Codici efficienti, Lunghezza e incertezza del percorso degli alberi n-ari probabilizzati, Teorema di codifica senza rumore, Codici Huffman, Codifica da variabile a lunghezza fissa, codice Tunstall, Algoritmo di costruzione del codice Tunstall, Codifica dei numeri interi positivi, Codifica di sorgenti con codifica Memory Huffman di slice, Schema di codice sorgente Elias-Willems, Codici Lempel-Ziv, gzip e bzip2. CODIFICA PER TRASMISSIONE RUMOROSA: Canali di comunicazione, Lemma di Fano, Il teorema della codifica rumorosa, Codici di ripetizione

Course Syllabus


Testi di riferimento: ------------------------------------------------------------ Modulo: 6094/1 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS A ------------------------------------------------------------ Slides Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser, Data Structures and Algorithms in Python, Wiley and sons, 2013, ISBN : 978-1-118-54958-2 Albert Laszlo Barab'asi, Network Science, freely available Algorithm Design: Pearson New International Edition of Kleinberg Jon (Author), Tardos Eva (Author). Pearson Education; Edition 01st of June 2013 An Introduction to Information Theory and Applications F. Bavaud J.-C. Chappelier J. Kohlas version 2.04 ------------------------------------------------------------ Modulo: 6094/2 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS B ------------------------------------------------------------ Algorithm Design: Pearson New International Edition of Kleinberg Jon (Author), Tardos Eva (Author). Pearson Education; Edition 01st of June 2013 An Introduction to Information Theory and Applications F. Bavaud J.-C. Chappelier J. Kohlas version 2.04

Elenco delle unità didattiche costituenti l'insegnamento

Docente: GIACOMO FIUMARA

Orario di Ricevimento - GIACOMO FIUMARA

GiornoOra inizioOra fineLuogo
Lunedì 11:30 13:30Edificio principale dell'ex facoltà di Scienze MM. FF. NN. (secondo piano), blocco dell'ex direzione del Dipartimento di Matematica. Prenotarsi mediante email
Mercoledì 11:30 13:30Edificio principale dell'ex facoltà di Scienze MM. FF. NN. (secondo piano), blocco dell'ex direzione del Dipartimento di Matematica. Prenotarsi mediante email
Note:

Docente: MARIA FAZIO

Orario di Ricevimento - MARIA FAZIO

Dato non disponibile
  • Segui Unime su:
  • istagram32x32.jpg
  • facebook
  • youtube
  • twitter
  • UnimeMobile
  • tutti