Schema della sezione

  • Minimizza Espandi

    INQ1097771 - DATI E ALGORITMI (A) 2025-2026 - PROF. ANDREA ALBERTO PIETRACAPRINA

    Minimizza tutto Espandi tutto




  • Minimizza Espandi

    Progetto di Programmazione Facoltativo: Scadenza 11/01/2026 (23:59)

  • Minimizza Espandi

    NOZIONI di BASE

     

    Lezione 1: 30/09/25

    • Introduzione al corso
    • Concetti fondamentali: problema computazionale, algoritmo, modello di calcolo
     

    Lezione 2: 01/10/25

    • Concetti fondamentali: pseudocodice
    • Esempio (trasposta).
    • Concetti fondamentali: taglia dell'istanza, struttura dati.
    • Analisi di algoritmi: complessità e correttezza.
    • Definizione della funzione complessità e analisi asintotica. 
     

    Lezione 3: 02/10/25

    • Ordini di grandezza O-grande, Omega-grande, Theta-grande, o-piccolo.
    • Proprietà degli ordini di grandezza. 
    • Strumenti matematici (parte bassa e alta, sommatorie notevoli).
    • Analisi di complessità: procedimento per provare limiti superiori e inferiori alla complessità.
    • Esempi (PrefixAverages quadratico e lineare).

    Lezione 4: 07/10/25

    • Esercizio simile a R-4.29 del testo.
      Complessità polinomiale vs complessità esponenziale: esempio: RSA.
    • Caveat relativi all'analisi asintotica al caso pessimo.
    • Induzione: tecnica generale; esempio (serie di Gauss).

    Lezione 5: 08/10/25
     
    • Induzione: esempio di induzione fallace (F( n)=0 per ogni n).
    • Analisi di correttezza: approccio generale.
    • Invarianti: definizione; utilizzo di un invariante per provare la correttezza di un ciclo; esempi (arrayMax e arrayFind).
    • Algoritmi ricorsivi: definizione; esempi (MergeSort, linearSum, reveseArray)

    Lezione 6: 09/10/25

    • Albero della Ricorsione: definizione; esempi (MergeSort, linearSum, reveseArray)
    • Gestione della memoria nell'esecuzione di un algoritmo ricorsivo: stack e heap
    • Analisi di complessità di un algoritmo ricorsivo tramite l'Albero della Ricorsione ed esempi (linearSum e reverseArray).
    • Calcolo di potenze: algoritmo power e sua applicazione al calcolo dell'n-esimo numero di Fibonacci (powerFib).
    • Analisi di correttezza di un algoritmo ricorsivo tramite induzione ed esempi (linearSum).

    Lezione 7: 14/10/25

    • Esercizi dalle Slide 48-49, 77, 79 sulle nozioni di base

    Lezione 8: 15/10/25

    • Esercizi dalle Slide 78 (secondo esercizio), 101 (secondo esercizio), 103 sulle nozioni di base

    Lezione 9: 16/10/25

    • Invariante per l'esercizio sulla maggioranza (Slide 103 sulle nozioni di base)

    Materiale:

     

  • Minimizza Espandi

    RIPASSO DI JAVA

    Lezione 9: 16/10/25

    • Java: programma stand-alone; modularity; information hiding; Abstract Data Type (ADT); interfacce e classi; ereditarietà: programmazione generica.
    • ADT elementari: Lista (index-based e position-based); Pila; Coda.
    • Java Collection Framework e API di Java (package java.util)

     

    Materiale: 

  • Minimizza Espandi

    ALBERI

    Lezione 9: 16/10/25

    • Alberi: applicazioni; definizioni; terminologia.

    Lezione 10: 21/10/25

    • Alberi: applicazioni; definizioni; terminologia.
    • Dimostrazione Proposizione 8.3 del testo (esercizio R-8.2)
    • Interfacce: Iterator, Iterable e Tree
    • Calcolo della profondità di un nodo (algoritmi ricorsivo e iterativo);
    • Calcolo dell'altezza di un nodo e di un albero;
    • Proposizione 8.4 del testo.

    Lezione 11: 22/10/25

    • Visite in preorder e postorder (pseudocodici, analisi ed esempi).
    • Algoritmi AllDepths e DiskSum.
    • Alberi binari: definizione; interfaccia.
    • Alberi binari propri: definizione; relazioni tra foglie, nodi interni, nodi e altezza.

    Lezione 12: 23/10/25

    • Alberi binari propri: dimostrazione delle relazioni tra foglie, nodi interni, nodi e altezza; visita inorder.
    • Parse Tree di un'espressione.
    • Rappresentazione infissa e postfissa (polacca inversa) di una espressione e uso della rappresentazione postfissa.
    • Algoritmi infix e postfix per la generazione di una espressione a partire dal suo Parse Tree, in rappresentazione rispettivamente infissa e postfissa.

    Lezione 13: 28/10/25

    • Esercizi: calcolo altezza tramite max profondità di una foglia e algoritmo LCA (Slide 60 sugli Alberi Generali); algoritmo allLiveAncestors (Slide 61 sugli Alberi Generali); relazione tra foglie e nodi interni quando ogni nodo interno ha >= 2 figli e algoritmo preorderNext (Slide 44 sugli Alberi Binari).

    Lezione 14: 29/10/25

    • Esercizi: algoritmi heightSum, All3Balanced, e maxOnHeight (Slide 37-43, 45 e 46 sugli Alberi Binari); 
    • Cenni sulla implementazione in Java di Alberi Generali e Binari. 

    Materiale:

  • Minimizza Espandi

    PRIORITY QUEUE

    Lezione 14: 29/10/25

    • Definizione di Priority Queue; Interfacce Entry(K,V) e PriorityQueue(K,V); applicazioni reali.

    Lezione 15: 04/11/25

    • Implementazione di una Priority Queue tramite liste (ordinate e non).
    • Heap: definizione; proprietà; realizzazione tramite array (level numbering).
    • Esercizi: relazione tra array ordinato e heap; esercizio R-9.15 del testo.

    Lezione 16: 05/11/25

    • Implementazione di min e insert tramite heap su array (pseudocodice e analisi).
    • Implementazione di removeMin tramite heap su array (pseudocodice e analisi).
    • Construzione di uno Heap a partire da un array P di n entry: approccio top-down (pseudocodice e analisi)

    Lezione 17: 06/11/25
     
    • Construzione di uno Heap a partire da un array P di n entry: approccio bottom-up (pseudocodice e analisi).
    • pqSort: SelectionSort, InsertionSort, HeapSort come casi particolari.
    • Implementazione in-place di HeapSort
     
    Lezione 18: 11/11/24
     
    • Esercizi: esercizio dalla Slide 58,  algoritmi Top(S,tau) (dalle Slide 7,8, e 74), removeEntry(P,ell) (dalla Slide 59), Print (T,i,k) (dalla Slide 68 - esercizio C-9.34 di [GTG14]).

    Lezione 19: 12/11/25
     
    • Implementazione delle Priority Queue in Java: classe PriorityQueue<E>

    Materiale:

  • Minimizza Espandi

    MAPPE

    Lezione 19: 12/11/25

    • Definizione di Mappa; applicazioni; interfaccia Map.
    • Implementazione di una Mappa tramite lista position-based o array di taglia |U|, con la complessità dei metodi get, put e remove.
    • Tabelle Hash: ingredienti principali; nozione di uniform hashing; scelta dell'hash code; scelta della compression function; risoluzione collisioni tramite separate chaining; cenni su open addressing.
     
    Lezione 20:  13/11/25
     
    • Tabelle Hash: implementazione dei metodi get(k), put(k,x) e remove(k); definizione di load factor; complessità dei metodi get(k), put(k,x) e remove(k) al caso pessimo e a caso medio in funzione del load factor; analisi del costo medio di ricerca di una chiave non presente in una tabella hash; rehashing con analisi ammortizzata.
    • Alberi Binari di Ricerca (ABR): definizione; proprietà della vista in-order; metodo TreeSearch(k,v) e sua complessità; implementazione del metodo get(k) e sua analisi. 
     
    Lezione 21:  18/11/25
     
    • Alberi Binari di Ricerca (ABR): implementazione dei metodi della mappa put(k,x) e remove(k), e loro analisi.
    • Esercizi: versione iterativa di TreeSearch.
    • Multi-Way Search Tree: definizione ed esempi; Proposizione 11.2 (ed esercizio C-11.46) del testo; metodo MWTreeSearch(k,v).

     

    Lezione 22:  19/11/25

     

    • Multi-Way Search Tree: metodo get(k); analisi di MWTreeSearch(k,v) e get(k) in funzione dell'altezza h e del massimo numero di figli di un nodo dmax.
    • (2,4)-Tree: definzione, altezza (Proposizione 11.3 del testo) e complessità del metodo get(k).
    • Implementazione del metodo put(k,x) (con Split) e sua complessità.
    • Esempi di esecuzione di put(k,x) su un (2,4)-Tree.
    • Metodo remove(k): idea.

    Lezione 23:  20/11/25

    • Metodo remove(k): pseudocodice; descrizione di Delete; esempi; analisi della complessità.
    • Red-Black Tree: definizione; relazione con il (2,4)-Tree; altezza e complessità dei metodi get, put e remove (senza dimostrazione).
    • Multimappa: definizione; motivazione; specifica dei metodi get(k), put(k,v), remove(k,v); implementazione tramite Mappa e Lista position-based.
     
    Lezione 24:  25/11/25

    • Multimappa: esempio di applicazione dei metodi; complessità dei metodi.
    • Esercizi: algoritmo 24Height (Slide 83 - Parte 2); algoritmo CountLE con variabili size (Slide 73 - Parte 1) e con/senza metodo T.size (primi due esercizi di Slide 81 - Parte 1); algoritmo MinPositive (secondo esercizio di Slide 80 - Parte 1). 
     
    Lezione 25:  26/11/25

    • Esercizi: algoritmo MinMatStraniero (Slide 82 - Parte 1); algoritmo MostFrequentWord (Slide 5 - Parte 1, e Slide 87 - Parte 2); algoritmo 24TreeMergeEq (primo esercizio di Slide 88 - Parte 2); cenni sulla generalizzazione di 24TreeMergeEq al caso di alberi con altezze differenti (secondo esercizio di Slide 88 - Parte 2).
     
    Materiale:
     
  • Minimizza Espandi

    GRAFI

    Lezione 26:  27/11/25
     
    • Definizione di grafo; terminologia; esempi applicativi
    • Concetti fondamentali: cammino, ciclo, grafo connesso, subgraph, spanning subgraph, albero (rooted, free e loro equivalenza), spanning tree/forest.
    • Proprietà dei grafi: Proposizioni 14.8, 14.10, 14.11 ed esercizio C-14.34 del testo.
    • Rappresentazione di grafi: strutture di base L_E e L_V; liste di adiacenza; matrice di adiacenza.

    Lezione 27: 02/12/25

    • Visite (traversal): nozione di visita.
    • Algoritmo BFS: pseudocodice; esempio; proprietà; analisi di complessità; estensione della visita a tutto il grafo.

    Lezione 28: 03/12/25

    • Applicazioni della BFS: connettività, spanning tree, cammini minimi, ciclicità.
    • Algoritmo DFS:  pseudocodice; esempio; proprietà; analisi di complessità.
     
    Lezione 29: 04/12/25
     
    • Algoritmo DFS:  proprietà; analisi di complessità.
    • Esercizi: algoritmo ReachablePairs (Slide 82 - Parte 1); MaxSeparation (Slide 24 e 90 - Parte 1); IsBipartite (Slide 90, secondo esercizio - Parte 1).

    Lezione 30: 09/12/25
     
    • Esercizi: algoritmo IsBipartite (Slide 90, secondo esercizio - Parte 1); esercizio dalla Slide 87 - Parte 1.
    • Cammini minimi pesati: definizioni di grafo pesato, lunghezza di un cammino, e cammino minimo; proprietà dei cammini minimi; 
    • Problema dei Single-Source Shortest  Paths (SSSP).
    • Algoritmo di Dijkstra: strategia ad alto livello e pseudocodice; esempio.

    Lezione 31: 10/12/25 
     
    • Algoritmo di Dijkstra: analisi di correttezza; analisi di complessità implementando Q con Heap, Lista (e con Fibonacci Heap ma senza prova).
    • Grafi Diretti: terminologia (grado uscente/entrante, cammino/ciclo diretto, vertici raggiungibili da un vertice v, versione non diretta di un grafo diretto, nozione di grafo fortemente/debolmente connesso); proprietà relative alla somma dei gradi uscenti/entranti; rappresentazione tramite liste di adiacenza.
    • BFS e DFS di grafi diretti: esempi 

    Lezione 32: 11/12/25
     
    • BFS e DFS di grafi diretti: complessità e proprietà.
    • Esercizio: identificazione dei BACK EDGE nella DFS diretta (Slide 67 - Parte 2).
    • Grafi diretti aciclici (DAG=Directed Acyclic Graph): definizione e ordinamento topologico.
    • Algoritmo TopologicalSort(G): esempio; analisi di di complessità.
    • Esercizio:  identificazione di un ciclo in un grafo diretto (Primo esercizio di Slide 75 - Parte 2) 
     
    Lezione 33: 16/12/25
     
    • Esercizi: modifica di ShortestPaths per grafi non connessi (Slide 42 - Parte 2);  trasformazione di un grafo non diretto in un DAG (terzo esercizio Slide 92 - Parte 2); scheduling di task tramite TopologicalSort (Slide 93 - Parte 2).

    Materiale:

  • Minimizza Espandi

    ORDINAMENTO

    Lezione 33: 16/12/25

     
    • Introduzione al problema dell'ordinamento. Definizione di algoritmo basato su confronti. Design Pattern Divide and Conquer.
    • MergeSort: MergeSort (pseudocodice); Merge (pseudocodice); complessità di Merge; complessità di MergeSort.
    • QuickSort: strategia generale; QuickSortInPlace (pseudocodice).

    Lezione 34: 17/12/25

    • QuickSort: Partition (pseudocodice, correttezza, complessità); complessità di QuickSortInPlace tramite Albero della Ricorsione.
    • Randomized QuickSort: differenze rispetto a QuickSortInPlace.
    • Complessità probabilistica di Randomized QuickSort (alta probabilità e media).
    • InsertionSort: algoritmo in place; definizione di inversione; analisi in funzione della taglia dell'input e del numero di inversioni.

    Lezione 35: 18/12/25
     
    • Lower bound sulla complessità di un qualsiasi algoritmo di ordinamento basato su confronti (senza prova).
    • BucketSort: pseudocodice e analisi di complessità.
    • Nozione di ordinamento stabile.
    • RadixSort: algoritmo; analisi di complessità e di correttezza.
    • Caso di studio: ordinamento dei cittadini italiani per codice fiscale.

    Lezione 36: 23/12/25

    • Dimostrazione del lower bound sulla complessità di un qualsiasi algoritmo di ordinamento basato su confronti
    • Esercizi: ordinamento di n chiavi in [0,n^2-1] (Slide 86 e C-13.39 di [GTG14]); algoritmo CountIntersection per l' intersezione di 2 sequenze ordinate (primo esercizio di Slide 21); ordinamento di una sequenza di n bit (primo esercizio di Slide 43); calcolo del numero di inversioni tramite MergeSort (secondo esercizio di Slide 21)

    Materiale:

  • Minimizza Espandi

    LEZIONE 8 Gennaio 2026

    Lezione 37: 08/01/26

    • Domande (D) ed esercizi (E) dagli esempi di esami scritti (S): S6 D1; S2 D2; S3 D3; S1 D4; S1 E1; S5 E1; S4 E2.
    • Selezione di domande dai Quiz sulle nozioni di base e sugli alberi

    Materiale: