Presentazione del corso.
Introduzione all'informatica e agli algoritmi.
Modello di esecutore: la Random Access Machine e complessità computazionale.

Giovedì 25 febbraio 2021 - Lezione 2 (Notazione Asintotica)

Notazione asintotica: O, \Omega, \Theta.
Algebra della notazione asintotica e metodo del limite.

Lunedì 1 marzo 2021 - Lezione 3 (Pseudocodice e complessità computazionale)

Introduzione al calcolo del costo computazionale: criterio del costo uniforme e criterio del costo logaritmico per le operazioni aritmetiche.
Pseudocodice e costo delle istruzioni. Assegnazione, selezione e cicli.
Esempi: valutazione di un polinomio, somma dei primi n numeri.

Giovedì 4 marzo 2021 - Lezione 4 (Ricerca e Ricorsione I)

Il problema della ricerca: ricerca sequenziale e binaria.
Introduzione alla ricorsione: terminazione e correttezza delle definizioni ricorsive.
Funzioni definite induttivamente e programmi ricorsivi.
Ricerca binaria ricorsiva.

Lunedì 8 marzo 2021 - Lezione 5 (Ricorsione II)

Versioni ricorsive di semplici programmi visti in forma iterativa: minimo, ricerca, somma degli elementi di un vettore.
Tranelli delle definizioni ricorsive: Il caso di Fibonacci.
Modello computazionale della ricorsione: attivazione delle chiamate ricorsive e albero delle chiamate ricorsive.
Fibonacci efficiente ricorsivo.
Problemi inerentemente ricorsivi: la Torre di Hanoi.

Giovedì 11 marzo 2021 - Lezione 6 (Equazioni di Ricorrenza I)

Complessità dei programmi ricorsivi: le equazioni di ricorrenza.
Soluzioni delle equazioni di ricorrenza: metodo iterativo, metodo di sostituzione, metodo dell'albero e Teorema Principale.
Primi esempi di soluzioni con questi metodi.

Lunedì 15 marzo 2021 - Lezione 7 (Equazioni di Ricorrenza II)

Revisione del Teorema Principale.
Soluzioni di Equazioni di Ricorrenza con tutti e 4 i metodi.

Giovedì 18 marzo 2021 - Lezione 8 (Algoritmi Elementari di Ordinamento)

Algoritmi Elementari di Ordinamento: InsertionSort, SelectionSort e BubbleSort.
Limite Inferiore al problema dell'ordinamento basato su confronti.

Lunedì 22 marzo 2021 - Lezione 9 (Ordinamento per fusione: mergeSort)

L'algortimo di ordinamento mergeSort. La funzione di fusione ordinata merge. Analisi di Complessità.
Alcuni esercizi: uso di insertionSort dentro mergesort. InsertionSort con ricerca binaria del punto dove inserire.
Un altro esercizio sulle relazioni di Ricorrenza.

Giovedì 25 marzo 2021 - Lezione 10 (L'algortimo quickSort)

L'algortimo di ordinamento quickSort. La funzione di partizionamento partiziona (versione originale di Hoare). Cenni a funzioni alternative.
Analisi di complessità di partiziona. Analisi del caso ottimo e caso pessimo di quickSort.
Alcune considerazioni intuitive sul rischio di incappare nel caso pessimo.
Analisi del caso medio di quickSort. Cenni a tecniche di randomizzazione per evitare il caso pessimo.

Lunedì 29 marzo 2021 - Lezione 11 (L'algortimo heapSort)

Struttura dati heap e sua rappresentazione dentro un vettore.
Funzione heapify che risistema un heap in cui al più la radice sia fuori posto.
Funzione buildHeap che costruisce un heap, in tempo O(n). Analisi della complessità di heapify e buildHeap.
Costruzione di un vettore ordinato partendo da un heap: l'algoritmo heapSort e sua analisi di complessità.

Giovedì 8 aprile 2021 - Lezione 12 (Algortimi di ordinamento lineari)

L'algortimo di ordinamento countingSort: ipotesi sui valori delle chiavi.
Adattamento di countingSort al caso di presenza di dati satellite.
Algoritmo bucketSort: ipotesi sui valori delle chiavi.
Soluzioni di esercizi su mergeSort: mergeSort iterativo e merge ricorsiva.

Lunedì 12 aprile 2021 - Lezione 13 (Strutture dati I: vettori e liste)

Tipi di dato e strutture dati.
Rappresentazione di insiemi dinamici con vettori: caso ordinato e non ordinato. Pro e contro.
La struttura dati lista concatenata. Algoritmi base: ricerca, inserimento, eliminazione.
Cenni alle liste doppiamente concatenate.
Esercizio Svolto: inserimento ordinato in lista ordinata.

Giovedì 15 aprile 2021 - Lezione 14 (Strutture dati II: code e pile)

Tipo di dato coda e sua implementazione con liste e vettori.
Cenni alle applicazioni delle code e alle code di priorità.
Tipo di dato pila e sua implementazione con liste e vettori.
Applicazioni delle pile: la pila di sistema.
Esercizio Svolto: simulazione di una coda con due pile.

Lunedì 19 aprile 2021 - Lezione 15 (Strutture dati III: alberi)

Alberi come grafi connessi aciclici: caratterizzazioni.
Alberi radicati e nomenclatura associata: radici, foglie, padri, figli, fratelli, antenati, livelli etc.
Rappresentazione posizionale (simil-heap), a puntatori, a vettori di padri.
Confronti delle rappresentazioni in alcuni semplici problemi: determinazione del padre, dei figli, distanza dalla radice.

Esercizi Svolti: Problemi sugli Heap: trovare il minimo, usare min-Heap per Heapsort.

Giovedì 22 aprile 2021 - Lezione 16 (Strutture dati III: alberi: visite)

Visite in profondità: pre-order, in-order, post-order.
Complessità computazionale delle visite in profondità.
Applicazioni delle visite: alcuni problemi elementari su alberi.
Tecnica di passare parametri ausiliari: conteggio nodi a livello k.
Visita per livelli e sua complessità.

Lunedì 26 aprile 2021 - Lezione 17 (Strutture dati IV: alberi binari di ricerca)

Definizioni. Il problema della ricerca e dell'inserimento negli alberi binari di ricerca.

Giovedì 29 aprile 2021 - Lezione 18 (Strutture dati V: tabelle Hash)

Tabelle Hash come implementazione dei dizionari.
Risoluzione dei conflitti: liste di trabocco e indirizzamento aperto.
Cenni a buone funzioni di hashing.

Lunedì 3 maggio 2021 - Lezione 19 (Strutture dati VI: alberi red-black)

Definizioni e proprietà dei red-black: numero di nodi rispetto all'altezza nera.
Rotazioni destre e sinistre.
Inserimento in un albero red-black.

Giovedì 6 maggio 2021 - Lezione 20 (Strutture dati Comparate: il problema dell'ordinamento sulle liste)

Gli algoritmi di ordinamento su liste:

• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Bubble Sort

Vantaggi e svantaggi (computazionali e di programmazione) rispetto agli stessi algoritmi su vettori.

Lunedì 10 maggio 2021 - Lezione 21 (Grafi I: introduzione ai Grafi)

Definizione di grafo e sue varianti (orientato, pesato, etc.).
Definizioni di grado, passeggiata, cammino, circuito, ciclo, componente connessa.
Rappresentazione in memoria dei grafi: matrici di incidenza, adiacenza, liste di adiacenza, lista di archi.

Giovedì 13 maggio 2021 - Lezione 22 (Esercizi di Riepilogo I: Equazioni di Ricorrenza, Quicksort, Liste)

Un'equazione di ricorrenza non risolvibile col metodo principale.
Dallo pseudocodice alle equazioni di ricorrenza.
Caso pessimo di Quicksort. Ordinamento di vettori con soli due valori usando partiziona.
Il problema del rovesciamento di una lista.

Lunedì 17 maggio 2021 - Lezione 23 (Grafi II: Visite)

Introduzione alle visite: albero di visita, archi all'indietro e archi di attraversamento.
Visita in ampiezza: distanze minime. Assenza di archi all'indietro.
Visita in profondità. Assenza di archi di attraversamento.
Differenze dovute alle diverse rappresentazioni dei grafi.

Giovedì 20 maggio 2021 - Lezione 24 (Esercizi di Riepilogo II: Alberi, Ordinamenti Lineari)

Ultime due equazioni di ricorrenza.
Esercizi su alberi: rappresentazioni a vettore dei padri.
Stabilità di Counting Sort ed Efficienza di Bucket Sort.

Lunedì 24 maggio 2021 - Lezione 25 (Grafi III: Cammini Minimi)

Cenni ad alcuni esempi di problemi modellabili come cammini minimi: routing di Internet.
L'algoritmo di Dijkstra su grafi diretti con pesi positivi: idea e correttezza.
Complessità dell'algoritmo di Dijkstra: implementazione della coda di priorità con heap e vettore.
Complessità nei grafi sparsi e densi.
Esempio di non funzionamento su grafi con pesi negativi.

Giovedì 27 maggio 2021 - Lezione 26 (Esercizi di Riepilogo III: Alberi, ABR e Alberi Red-Black)

Alcuni esercizi da compiti passati:

• somma chiavi al più k in un albero;
• estrazione k minimi da un ABR;
• stampa foglie in un albero rappresentato a liste di adiacenza e in rappresentazione posizionale.

Esempio di costruzione di un albero red-black
Uso di ABR e alberi red-black in una procedura di ordinamento.

Lunedì 31 maggio 2021 - Lezione 27 (Esercizi di Riepilogo IV: Grafi I)

Esercizi su grafi e visite:

• trasformazioni tra rappresentazioni: liste di adiacenza e matrici di adiacenza;
• distanze usando la BFS, diametro di un grafo;
• ricerca di cicli e determinazione delle componenti connesse.

Ultimi esercizi su liste semplici.

Giovedì 3 giugno 2021 - Lezione 28 (Esercizi da vecchi compiti I)

• Alberi binari di ricerca;
• heap e Red Black Tree;
• cicli in grafo colorato;
• k elmenti minori in un vettore.

Lunedì 7 giugno 2021 - Lezione 29 (Esercizi da vecchi compiti II)

Miscellanea: _k_-mediana usando partiziona di quickSort e applicazioni.
Altri esercizi da vecchi scritti:

• chiavi maggiori di a in un ABR;
• differenza simmetrica tra insiemi;
• punto di sella in una matrice;
• cancellazione da un heap;
• verifica se un grafo è semplice.

Un paio di osservazioni su grafi e algoritmi greedy.

Giovedì 10 giugno 2021 - Lezione 30 (Test di autovalutazione)

Distanza tra due insiemi di nodi in un grafo.

Giovedì 1 luglio 2021 - Lezione 31 (Correzione Scritto 21 giugno)

• Il problema del calcolo dei numeri di Cappanacci.
• Bilanciamento delle parentesi con pile e code.
• Nodi equidistanti da due nodi dati.
• Lista dei nodi a distanza k da un nodo dato.

-- Ivano Salvo - 2021-02-25