Insegnamento
|
CFU
|
SSD
|
Ore Lezione
|
Ore Eserc.
|
Ore Lab
|
Ore Altro
|
Ore Studio
|
Attività
|
Lingua
|
72368 -
ALGORITMI E COMPLESSITA'
-
CANTONE Domenico
( programma)
Descrizione generale del corso
Vengono presentate e analizzate, anche mediante la tecnica dell'analisi ammortizzata, diverse strutture dati avanzate (quali B-tree, splay tree, heap binomiali e heap di Fibonacci) e le procedure per la loro gestione. Inoltre vengono studiati, progettati e analizzati algoritmi su grafi per la soluzione efficiente di svariati problemi di ottimizzazione.
PROGRAMMA PARTICOLAREGGIATO DEL CORSO
Analisi ammortizzata Stack con multipop e contatore binario Metodi dell'aggregazione, degli accantonamenti e del potenziale Tabelle dinamiche con inserimenti e cancellazioni
Strutture dati avanzate B-alberi: applicazioni, altezza, ricerca, inserimenti e cancellazioni Splay trees: ricerca, inserimenti e cancellazioni, analisi ammortizzata di m operazioni di cui n sono inserimenti; top-down splay trees Strutture dati per insiemi disgiunti: unione per ranghi, compressione dei cammini, algoritmo Union-Find, notazione di Knuth, funzione di Ackermann e sua inversa Heap binomiali: alberi binomiali, operazioni di inserimento, minimo ed estrazione del minimo, decremento di una chiave, cancellazione di una chiave, unione di due heap binomiali Heap di Fibonacci: alberi binomiali non ordinati, operazioni di inserimento, minimo ed estrazione del minimo, decremento di una chiave, cancellazione di una chiave, unione di due heap di Fibonacci, analisi ammortizzata
Cammini minimi da una singola sorgente in grafi orientati Grafo dei cammini minimi, albero dei cammini minimi, algoritmo generico per i camminimi minimi da singola sorgente, algoritmo di Bellman-Ford, algoritmo di Dijkstra, algoritmo lineare su grafi aciclici
Cammini minimi tra tutte le coppie di nodi in grafi orientati Algoritmo di Floyd-Warshall, chiusura transitiva, algoritmo di Johnson su grafi sparsi
Alberi ricoprenti minimi Passi rossi e passi blu, invariante del colore, algoritmi di Boruvka, di Kruskal e di Prim, clustering di massima separazione
Reti di flusso e applicazioni Flusso reale e flusso netto in una rete di flusso, proprietà del flusso netto, reti con sorgenti e pozzi multipli, notazione di sommatoria implicita, il metodo di Ford-Fulkerson, capacità e rete residue, cammini aumentanti, tagli in reti di flusso, teorema del massimo flusso/minimo taglio, analisi della procedura di Ford-Fulkerson, abbinamento massimo in grafi bipartiti, algoritmo di Edmonds-Karp e sua analisi di complessità, edge-connectivity.
Il libro di testo consigliato è:
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009
disponibile anche nella traduzione italiana
1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati 3/ed, McGraw-Hill Italia, 2010.
Altra fonte:
2) M.A. Weiss. Data structures and algorithmic analysis in C (Second Edition), Addison-Wesley, 1996.
|
9
|
INF/01
|
36
|
36
|
-
|
-
|
-
|
Attività formative caratterizzanti
|
ITA |
1014456 -
OTTIMIZZAZIONE
-
SCRIMALI Laura Rosa Maria
( programma)
1. PROGRAMMAZIONE LINEARE (circa 12 ore)
Problemi di PL. Algoritmo del Simplesso. Teoria della Dualità.
2. PROGRAMMAZIONE LINEARE INTERA (circa 6 ore)
Esempi di problemi di PLI. Metodo dei piani di taglio. Metodo del Branch and Bound. Problema dello zaino. Il commesso viaggiatore.
3. PROGRAMMAZIONE NON LINEARE (circa 6 ore)
Condizioni di ottimalità. Metodi risolutivi per l'ottimizzazione vincolata e non vincolata.
4. RISOLUZIONE DI PROBLEMI DI OTTIMIZZAZIONE (circa 24 ore)
Risoluzione analitica e con l'utlizzo di software (GeoGebra, Excel, Matlab, Mathematica).
[1] R. Tadei, F. Della Croce, “Elementi di Ricerca Operativa”, Società Editrice Esculapio, 2010;
[2] R. Baldacci, M. Dell’Amico, “Fondamenti di Ricerca Operativa”, Pitagora Editrice, 2002
[3] M. Bruglieri, A. Colorni, “Ricerca Operativa”, Zanichelli, 2012;
[4] F. Fumero, Metodi di ottimizzazione. Esercizi ed applicazioni, Società Editrice Esculapio, 2013
|
6
|
MAT/09
|
24
|
24
|
-
|
-
|
-
|
Attività formative affini ed integrative
|
ITA |
1015941 -
INGEGNERIA DEI SISTEMI DISTRIBUITI E LABORATORIO
|
|
1015942 -
INGEGNERIA DEI SISTEMI DISTRIBUITI
-
TRAMONTANA EMILIANO ALESSIO
( programma)
Design pattern per sistemi distribuiti: Proxy, Broker, Forward-Receiver, Remote Facade, Data Transfer Object, Session State, Serialized Large Object. Design pattern per la sicurezza: Role-based Access Control, Authenticator. Progettazione ed implementazione del software orientato agli aspetti. Design pattern ad aspetti e Refactoring ad aspetti. Implementazione di chiamate asincrone in Java. Reactive programming con design pattern Circuit Breaker, Bulkheads, Timeout. Middleware orientato ai messaggi RabbitMQ. Tecnologia Blockchain.
1.F. Buschmann, R. Meunier, H. Rohnert, P. Sommerlad, M. Stal. Pattern-Oriented Software Architecture A System of Patterns. John Wiley and Sons, 1996
2.M. Fowler. Patterns of Enterprise Application Architecture. Addison-Wesley, 2003
3. M. Schumacher, E. Fernandez-Buglioni, D. Hybertson, F. Buschmann, P. Sommerlad. Security Patterns: Integrating Security and Systems Engineering. John Wiley and Sons, 2006
4. R. Laddad. AspectJ in Action: Enterpriese AOP with Spring Applications. Manning Publications. 2010.
5. R.-G. Urma, M. Fusco, A. Mycroft. Java 8 in Action: Lambdas, streams, and functional-style programming. Manning, 2015
6.G. Hohpe, B. Woolf. Enterprise Integration Patterns. Addison-Wesley, 2003
7. A. Videla, J.J.W. Williams. RabbitMQ in Action. Manning, 2012
8. A. M. Antonopoulos. Mastering Bitcoin. Programming the open blockchain. O'Reilly, 2017
9.R. Kuhn. Reactive Design Patterns. Manning, 2017
|
6
|
INF/01
|
24
|
24
|
-
|
-
|
-
|
Attività formative caratterizzanti
|
ITA |
1015943 -
LABORATORIO
-
FORNAIA ANDREA FRANCESCO
( programma)
Introduzione ai DevOps. Git Workflow e sviluppo distribuito. Maven. Unit Testing e generazione automatica di test. Mutation Testing. Testing Combinatoriale. Microservizi. Microservizi con Spring Boot. Distributed Tracing.
G. Kim et al.: The DevOps Handbook.It Revolution Press, 2016 S. Chacon and B. Straub: Pro Git.Apress, 2014 Sonatype Company:Maven: The Definitive Guide.O'Reilly, 2008 D. R. Kuhn et al.: Practical Combinatorial Testing.NIST Special Publication, 2010 M. Young and M. Pezze: Software Testing and Analysis: Process, Principles and Technique. John Wiley and Sons, 2008 B. Laboon:A Friendly Introduction to Software Testing.CreateSpace Independent Publishing,2017 S. Newman: Building Microservices.O'Reilly, 2015 M. Macero: Learn Microservices with Spring Boot.Apress, 2017 Yuri Shkuro:Mastering Distributed Tracing: Analyzing performance in microservices and complex systems.Packt Publishing, 2019
|
3
|
INF/01
|
12
|
-
|
12
|
-
|
-
|
Attività formative caratterizzanti
|
ITA |
1015109 -
CRITTOGRAFIA
-
CATALANO Dario
( programma)
1. Introduzione e breve panoramica del corso
Materiale: Cap 1 di [1]
2. Cifrari Storici e One Time Pad. Il cifrario shift cipher. Il cifrario substituition cipher. Crittanalisi di substitution cipher. Perfetta Sicurezza. Subst. Cipher non offre perfetta sicurezza (dimostrazione). One time pad. One time pad offre perfetta sicurezza (dimostrazione). One time pad è ottimo (dimostrazione). Teorema di Shannon (enunciato)
Materiale: Cap 2 di [1] e cap. 2 di [3]
3. Cifrari a Blocchi: AES
Materiale: Cap 3 di [1]
4. Funzioni e permutazioni Pseudo Casuali. Introduzione e definizioni. Applicazioni ai cifrari a blocchi. Qualche esempio. La sicurezza in senso prf implica sicurezza in senso key recovery (dimostrazione). Il paradosso del compleanno.
Materiale: Cap. 4 e Appendice di [1]
5. Cifrari Simmetrici: modi d'operazione. Modo ECB, Modo CBC$, Modi CTR (a stati e randomizzato). Nozione di sicurezza per cifrari simmetrici: IND-CPA. Attacchi a messaggio scelto e attacchi a crittotesto scelto. Prova che un cifrario deterministico non può essere sicuro. Ind-cpa security implica plaintext recovery security (dimostrazione). Indistinguibilità relativamente ad attacchi a crittotesto scelto: IND-CCA security. Ind-cpa security non implica ind-cca security: il caso di CTR$ (dimostrazione)
Materiale: Cap 5 di [1] e Cap 3 di [3]
6. Funzioni Hash.. Resistenza alle collisioni: funzioni universali, funzioni universali unidirezionali, funzioni resistenti alle collisioni. Attacchi generici alle funzioni hash. Attacchi alle funzioni MD4, MD5, SHA1 (cenni). La trasformazione Merkle-Damgard. Cenni su SHA3.
Materiale: Cap 6 di [1] e Appunti
7. Message Authentication. Definizione di sicurezza per MAC. Il paradigma PRF as a MAC. CBC-MAC. Basic CBC-MAC se applicato a messaggi di lunghezza variabile non è sicuro (dimostrazione). (In)sicurezza di CBC-MAC randomizzato. CBC-MAC per messaggi di lunghezza variabile. MAC da funzioni hash: HMAC.
Materiale: Cap 7 di [1] e Cap 4 di [3]
8. Introduzione alla crittografia asimmetrica. Funzioni unidirezionali e funzioni trapdoor. Richiami di teoria dei numeri computazionale. Generalità sui gruppi. Algoritmo di Euclide, teorema cinese del resto. Quadrati residui.
Materiale: Cap 9 di [1], capitoli vari di [2]
9. Primitive Asimmetriche. Il problema del logaritmo discreto su campi finiti. Il problema computazionale Diffie Hellman. Il problema decisionale Diffie-Hellman. Fattorizzazione. La funzione RSA. Cenni su test di primalità. Algoritmo Miller-Rabin. L'algoritmo square and multiply.
Materiale: Cap 10 di [1]. Appunti delle lezioni.
10. Cifrari Asimmetrici. Definizioni di sicurezza per cifrari asimmetrici. Cifrari Asimmetrici. Definizione di sicurezza per cifrari asimmetrici. Il cifrario El Gamal. Il cifrario El Gamal è sicuro (in senso IND-CPA) relativamente all'ipotesi decisional Diffie-Hellman (dimostrazione).
Il cifrario Paillier. Preliminari matematici. Il cifrario Paillier gode della proprietà di omomorfismo additivo (dimostrazione).
Il cifrario RSA-OAEP. Proprietà del cifrario.
Cifrari basati sull'identità: il cifrario Boneh Franklin. Mappe bilineari. Proprietà del cifrario.
Materiale: Cap 11 di [1] Cap 11 di [3] e appunti delle lezioni.
11. Firme digitali. Preliminari. Definizione di sicurezza per firme digitali. Hash and Sign.
Materiale: Cap 12 di [1] Appunti delle lezioni.
12. Advanced Encryption Mechanisms. Fully Homomorphic Encryption. Functional Encryption
Materiale: MAteriale fornito dal docente
[1] M. Bellare, P. Rogaway “Introduction to Modern Cryptography”
Scaricabile dahttp://www.cs.ucsd.edu/~mihir/cse107/classnotes.html
[2] V. Shoup A Computational Introduction to Number Theory and Algebra
Scaricabile dahttp://shoup.net/ntb/
[3] J. Katz, Y. Lindell “Introduction to Modern Cryptography” CRC press
|
9
|
INF/01
|
36
|
36
|
-
|
-
|
-
|
Attività formative caratterizzanti
|
ITA |