Corso IN110 Algoritmi e Strutture Dati

Le lezioni

Diario delle lezioni dell'anno accademico 2023/2024

Le attività didattiche (lezioni, esercitazioni, tutorato) relative al corso di IN110 - Algoritmi e Strutture Dati per l'anno accademico 2023/2024 sono terminate. È disponibile il programma ufficiale del corso. Il ricevimento studenti rimane attivo tutti i venerdì dalle 9:00 alle 10:00 da remoto sulla piattaforma Teams (su appuntamento via mail). Per le date degli appelli d'esame si faccia riferimento alle pagine esami e bacheca di questo sito web.

Le lezioni si sono tenute nel primo semestre con il seguente orario:

Di seguito si riporta una sintesi degli argomenti trattati nel corso delle lezioni in aula e delle esercitazioni di laboratorio.

Lezione n. 1 - lunedì 18 settembre 2023
  • Presentazione del corso: argomenti che tratteremo, orario delle lezioni, orario delle esercitazioni, orario di ricevimento, modalità di esame (scarica il documento: “Presentazione del corso di Informatica 1”Scarica il documento in formato PDF).
  • Introduzione alla progettazione di algoritmi: un approccio intuitivo mediante alcuni esempi elementari.
Lezione n. 2 - martedì 19 settembre 2023
  • Esecutore e algoritmi: problema e istanza di un problema, caratteristiche dell'esecutore, compiti del progettista degli algoritmi, capacità del calcolatore/esecutore; algoritmi; esempi di pseudo-codifica di algoritmi per la soluzione di problemi elementari (primi k multipli di n, sommatoria dei primi n naturali, fattoriale di un numero naturale n>0). Linguaggi imperativi, istruzioni fondamentali di in linguaggio imperativo.
Lezione n. 3 - giovedì 21 settembre 2023
  • Algoritmi, diagrammi di flusso, programmazione strutturata: linguaggi imperativi, istruzioni fondamentali di un linguaggio imperativo, rappresentazione di algoritmi mediante diagrammi di flusso, strutture algoritmiche di tipo sequenziale, iterativa, condizionale; regole della programmazione strutturata, cenni sul Teorema Fondamentale della Programmazione Strutturata di Jacopini e Böhm; esempi: ricerca del massimo fra 2, 3 e n numeri, verifica dell'ordinamento di una sequenza, verifica della parità di un numero naturale, divisibilità di un numero naturale, quoziente e resto della divisione tra interi, minimo comune multiplo di due numeri naturali (scarica il documento: “Algoritmi e diagrammi di flusso”Scarica il documento in formato PDF).
Lezione n. 4 - lunedì 25 settembre 2023
  • Cenni sulla calcolabilità: alcuni problemi non risolubili per via algoritmica: esempi basati sulla congettura di Goldbach e la congettura di Ulam.
  • La Macchina di Turing: definizione della MdT come modello di calcolo astratto; esempio di MdT per il calcolo del successore di un numero naturale espresso in base 2; funzioni, macchine di Turing, algoritmi, calcolabilità delle funzioni elementari, composizione di funzioni e ricorsione come operazioni che preservano la calcolabilità; codifica di una macchina di Turing e del suo input come numeri naturali.
Lezione n. 5 - martedì 26 settembre 2023
  • Calcolabilità e modelli di calcolo: problemi calcolabili e non calcolabili, alcuni esempi; modelli di calcolo astratti: la macchina di Turing, il modello di Von Neumann; cenni sul problema della fermata, cenni sulla Tesi di Church-Turing (scarica il documento: “Appunti sui modelli di calcolo”Scarica il documento in formato PDF).
  • Linguaggi di programmazione: classificazion dei linguaggi in base al paradigma di programmazione, alcuni esempi. Linguaggi di programmazione di basso livello e di alto livello, linguaggio macchina; processo di traduzione del codice da linguaggio di programmazione di alto livello (codice sorgente) a linguaggio macchina (codice binario eseguibile), esecuzione del programma (scarica il documento: “Appunti sui linguaggi di programmazione”Scarica il documento in formato PDF).
Lezione n. 6 - giovedì 28 settembre 2023
  • Rappresentazione delle informazioni: codifica decimale e binaria di numeri interi positivi; struttura della memoria, bit, byte; rappresentazione di numeri interi “grandi”, mediante parole ottenute concatenando più byte, rappresentazione di numeri interi relativi, rappresentazione di numeri razionali (floating point), rappresentazione di caratteri alfanumerici (scarica il documento: “Appunti sulla rappresentazione delle informazioni in memoria”Scarica il documento in formato PDF).
  • Introduzione al linguaggio C: struttura e sintassi generale di un programma C, direttive del precompilatore per l'inclusione di librerie, la funzione main, dichiarazione di variabili, tipi di dato, la funzione printf, la funzione scanf.
  • Strutture di controllo condizionali e iterative: la struttura di controllo condizionale if... else..., l'istruzione while per la definizione di iterazioni; esempi.
Lezione n. 7 - venerdì 29 settembre 2023
  • Operatori di confronto: operatori di confronto, espressioni logiche, connettori logici and, or, not, valutazione di espressioni booleane, esempi.
  • Operatori aritmetici: operatori aritmetici, esempi.
  • Operatori aritmetici in forma compatta: gli operatori ++, -- in forma prefissa e postfissa; gli operatori di assegnazione +=, -=, *= e /=.
  • Struttura di controllo condizionale: la struttura di controllo condizionale if... else..., esempi.
  • Strutture di controllo iterative: le istruzioni while, do-while e for; esempi.
  • Array: definizione di vettori o array mono-dimensionali; esempi (scarica il documento: “Appunti sul linguaggio C”Scarica il documento in formato PDF).
Esercitazione in laboratorio - giovedì 5 ottobre 2023
Lezione n. 8 - venerdì 6 ottobre 2023
  • Array: array monodimensionali (vettori) e multidimensionali (matrici), dichiarazione di array, allocazione in memoria di un array; gli operatori “&” e “*”; esempi. L'operazione di cast, esempi.
Lezione n. 9 - martedì 10 ottobre 2023
  • Stringhe di caratteri: rappresentazione di stringhe di caratteri come array, il carattere nullo “\0” di terminazione di una stringa, le funzioni printf e scanf con le stringhe; esempi.
  • Numeri pseudo-casuali: generazione di sequenze di numeri pseudo-casuali, le funzioni srand e rand, esempi per la generazione di numeri interi pseudo-casuali nell'intervallo (a, b), esempi.
Esercitazione n. 2 - giovedì 12 ottobre 2023
  • Esercizi sugli array: operazioni sugli array: intersezione, differenza, inversione (documento con i testi e le soluzioni degli esercizi: esercitazione02.pdfDocumento in formato PDF).
Lezione n. 10 - venerdì 13 ottobre 2023
  • Generazione di numeri pseudo-casuali: ancora sulle funzioni srand e rand per la generazione di numeri random, esempi.
  • Definizione di funzioni: definizione di funzioni in un programma C, nome della funzione, valore restituito dalla funzione, parametri, variabili locali, esempi.
  • Passaggio dei parametri alle funzioni: passaggio di parametri per valore e per indirizzo ad una funzione, gli operatori “&” e “*”, esempi.
  • Passaggio di array a funzioni: passaggio di un array (dell'indirizzo di memoria del primo elemento dell'array) ad una funzione; le funzioni per l'acquisizione in input e la stampa di un vettore; aritmetica sui puntatori; esempi con la notazione vettoriale e con l'uso esplicito di puntatori.
Lezione n. 11 - martedì 17 ottobre 2023
  • Esercizi su array (letti in input n numeri interi memorizzarli in un array; eliminare tutti i valori dispari effettuando lo “shift” a sinistra degli elementi successivi) con l'uso di funzioni: diagramma di flusso e codifica in C.
  • Funzioni ricorsive: definizione di funzioni ricorsive, differenze ed analogie con procedure iterative, esempi (funzione fattoriale definita in modalità iterativa e ricorsiva).
Esercitazione n. 3 - giovedì 19 ottobre 2023
  • Esercizi sulle stringhe e sulle matrici: Letta una parola S, stabilire se S è palindroma (ossia se è simmetrica); acquisire in input un array A di n numeri interi minori di 100; per ogni elemento di A stampare il numero di volte che compare nel vettore; letta in input una matrice A di n × m numeri interi, stampa la colonna con il maggior numero di elementi dispari (documento con i testi e le soluzioni degli esercizi: esercitazione03.pdfDocumento in formato PDF).
Lezione n. 12 - venerdì 20 ottobre 2023
  • Crivello di Eratostene: calcolo dei numeri primi minori di n con il Crivello di Eratostene, strategia risolutiva, pseudo-codice e diagramma di flusso dell'algoritmo.
  • Problema dell'ordinamento (sort): definizione del problema dell'ordinamento di un insieme di dati, esempi.
  • Algoritmo Selection Sort: strategia risolutiva del problema di ordinamento adottata dall'algoritmo di ordinamento per selezione, pseudo-codifica dell'algoritmo Selection Sort, diagramma di flusso, codifica in linguaggio C, esempi.
  • Complessità computazionale di un algoritmo: problema, istanza di un problema, “dimensione” dell'istanza di un problema; complessità computazionale di un algoritmo come funzione che esprime una stima del numero di operazioni eseguite dall'algoritmo in funzione della dimensione dell'istanza del problema.
  • Complessità computazionale di un algoritmo: la notazione “O grande”, esempi di classi di complessità.
Lezione n. 13 - martedì 24 ottobre 2023
  • Complessità computazionale di un algoritmo: ancora sulla funzione complessità che fornisce una stima del numero di operazioni svolte eseguendo un certo algoritmo per risolvere l'istanza di dimensione n di un problema; esempi sull'algoritmo Selection Sort; esempi con classi di complessità computazionale differenti, notazione “O grande”.
  • Algoritmo Insertion Sort: strategia risolutiva dell'algoritmo Insertion Sort, pseudo-codifica, diagramma di flusso, codifica in linguaggio C, esempi; calcolo del numero di operazioni fondamentali eseguite per risolvere un'istanza del problema, nel caso migliore e nel caso peggiore, complessità dell'algoritmo.
Esercitazione n. 4 - giovedì 26 ottobre 2023
  • Esercizi su vettori di caratteri e su matrici: array di numeri casuali, riconoscimento di stringhe, trasformazione di stringhe in caratteri maiuscoli (documento con i testi e le soluzioni degli esercizi: esercitazione04.pdfDocumento in formato PDF).
Lezione n. 14 - venerdì 27 ottobre 2023
  • Algoritmo Bubble Sort: strategia risolutiva, pseudo-codifica dell'algoritmo, calcolo della complessità computazionale, codifica in linguaggio C dell'algoritmo Bubble Sort, esempi.
  • Algoritmo Quick Sort: strategia risolutiva “divite et impera” dell'algoritmo Quick Sort, profondità di un albero binario completo, pseudo-codifica dell'algoritmo.
Lezione n. 15 - martedì 31 ottobre 2023
  • Algoritmo Quick Sort: strategia risolutiva “divite et impera” dell'algoritmo Quick Sort, profondità di un albero binario completo, pseudo-codifica dell'algoritmo, complessità nel caso migliore e nel caso peggiore, esempi.
  • Algoritmo Merge Sort: algoritmo per la “fusione” di due array già ordinati, strategia di tipo “divide et impera” adottata dall'algoritmo di ordinamento per fusione, pseudo-codifica dell'algoritmo Merge Sort, calcolo della complessità computazionale, esempi (in questa pagina è disponibile la codifica in linguaggio C dell'algoritmo Merge Sort).
Esercitazione n. 5 - giovedì 2 novembre 2023
  • Esercizi su array: funzioni per la lettura e la scrittura di dati su file di testo, esercizio per la generazione di un file di dati da visualizzare graficamente con GNUplot; esercizi su array (documento con i testi e le soluzioni degli esercizi: esercitazione05.pdfScarica il documento in formato PDF).
Lezione n. 16 - venerdì 3 novembre 2023
Lezione n. 17 - martedì 14 novembre 2023
  • Pile, code, code di priorità: strutture dati di tipo pila (stack), coda (queue) e coda di priorità, cenni sull'implementazione delle operazioni di inserimento ed estrazione di elementi in pile, code e code di priorità, esempi.
  • Heap: la struttura dati di heap, caratteristiche della struttura dati, algoritmi per l'inserimento di un elemento e l'estrazione dell'elemento massimo, esempi.
  • Algoritmo Heap Sort: strategia dell'algoritmo di ordinamento heap sort, pseudo codifica dell'algoritmo, esempi, calcolo della complessità computazionale (vedi la codifica in linguaggio C dell'algoritmo). Appunti riepilogativi sugli algoritmi di ordinamento.Documento PDF
Esercitazione n. 6 - giovedì 16 novembre 2023
  • Esercizi su array e matrici: inserimento degli elementi di un vettore al centro di un altro vettore; percorso su una matrice di numeri interi (documento con i testi e le soluzioni degli esercizi: esercitazione06.pdfScarica il documento in formato PDF).
Lezione n. 18 - venerdì 17 novembre 2023
  • Allocazione dinamica della memoria: le funzioni di libreria sizeof e malloc, allocazione dinamica di array, esempi.
  • Strutture: definizione di strutture, la parola chiave struct, variabili di tipo struttura, puntatori a strutture, array di strutture, esempi.
  • Liste: definizione di una struttura per la rappresentazione di una lista rappresentata come una pila, esempi.
Lezione n. 19 - martedì 21 novembre 2023
  • Liste: definizione di una struttura per la rappresentazione di una lista rappresentata come una pila, esempi; utilizzo delle funzioni malloc e sizeof per l'allocazione degli elementi di una lista.
  • Gestione di una pila con una lista: funzione leggiLista per la costruzione di una lista come una pila, funzione iterativa per la stampa degli elementi di una lista; funzione ricorsiva per la stampa degli elementi di una lista dal primo all'ultimo e dall'ultimo al primo, funzione per la cancellazione di elementi da una lista (sorgente in C di un esempio per la cancellazione degli elementi dispari da una lista).
  • Code con le liste: funzione per la costruzione di una lista come una coda, funzione per l'accodamento di un elemento.
Esercitazione n. 7 - giovedì 23 novembre 2023
  • Esercizi sulle liste: eliminzione di elementi di una lista, concatenazione di liste, fusione di liste ordinate (documento con i testi e le soluzioni degli esercizi: esercitazione07.pdfDocumento in formato PDF).
Lezione n. 20 - venerdì 24 novembre 2023
  • Code e pile con le liste: gestione di una lista come una coda, funzioni per l'accodamento di un elemento e l'estrazione del primo elemento da una coda.
  • Cenni sulla teoria dei grafi: definizione di grafo orientato e non orientato, adiacenza, incidenza di uno spigolo su un vertice; definizione di cammino, cammino semplice, ciclo, grafo connesso, grafo orientato fortemente connesso, sottografo, esempi; definizione di albero libero e albero radicato. Alberi liberi, alberi radicati, spanning tree, esempi (scarica il documento: “Appunti sulla teoria dei grafi”Scarica il documento in formato PDF).
Lezione n. 21 - martedì 28 novembre 2023
  • Cenni sulla teoria dei grafi: grafi completi, grafi multipartiti, multipartiti completi; sottografi, sottografi indotti, clique; massimo numero di spigoli di un grafo orientato e non orientato; isomorfismi tra grafi, grafi planari, buona colorazione di grafi, cenni sul Teorema dei Quattro Colori.
  • Strutture dati per la rappresentazione di grafi e alberi: rappresentazione mediante matrici di adiacenza e mediante liste di adiacenza, esempi.
  • Operazioni sulle liste di adiacenza di un grafo: codifica in C delle funzioni che implementano alcune operazioni di base sulle strutture dati di lista di adiacenza di un grafo: funzioni leggiGrafo, stampaGrafo.
Esercitazione n. 8 - giovedì 30 novembre 2023
  • Esercizi sulle liste: compressione di sequenze numeriche con l'algoritmo RLE (Run Length Encoding), decompressione, sottoliste prive di intersezione (documento con i testi e le soluzioni degli esercizi: esercitazione08.pdfDocumento in formato PDF).
Lezione n. 22 - veneredì 1 dicembre 2023
  • Visita in ampiezza di un grafo: il problema della visita di un grafo, la strategia della visita in ampiezza, l'algoritmo BFS (Breadth First Search), pseudo-codifica dell'algoritmo, calcolo della complessità computazionale, esempi, codifica in linguaggio C dell'algoritmo BFS.
  • Applicazioni della visita in ampiezza di un grafo: verifica della connessione di un grafo, verifica della presenza di cicli, identificazione dei cammini di lunghezza minima per raggiungere i vertici di un grafo a partire da una sorgente fissata, caratteristiche degli alberi di visita prodotti dall'algoritmo BFS, esempi.
Lezione n. 23 - lunedì 5 dicembre 2023
  • Visita in profondità di un grafo: strategia della visita in profondità di un grafo, pseudo codifica dell'algoritmo DFS (Depth First Search), calcolo della complessità, esempi, vedi la codifica in linguaggio C dell'algoritmo DFS.
  • Applicazioni della visita in profondità: ordinamento topologico dei vertici di un grafo orientato aciclico, adattamento dell'algoritmo DFS per l'ordinamento topologico, esempi; costruzione di un'espressione aritmetica in notazione polacca inversa mediante una visita in profondità dell'albero sintattico dell'espressione in notazione “infissa”, esempi.
Esercitazione n. 9 - giovedì 7 dicembre 2023
  • Esercizi sulle liste e sui grafi: costruzione di un "grafo intervallo", costruzione di un grafo completo bipartito, calcolo del grado entrante dei vertici di un grafo orientato (documento con i testi e le soluzioni degli esercizi: esercitazione09.pdfDocumento in formato PDF).
Lezione n. 24 - martedì 12 dicembre 2023
  • Il problema del cammino minimo da una sorgente singola: descrizione del problema della ricerca dei cammini di peso minimo su un grafo con pesi non negativi assegnati agli spigoli, cenni preliminari sul “principio del rilassamento” adottato dall'algoritmo di Dijkstra, cenni sui problemi di ottimizzazione combinatoria, in cui è necessario identificare una soluzione ottima, che renda minimo o massimo il valore di una determinata funzione obiettivo.
  • Algoritmo di Dijkstra: pseudo-codifica dell'algoritmo di Dijkstra per il calcolo dei cammini di costo minimo da una sorgente singola su un grafo, esempi, analisi della complessità computazionale, si veda anche la codifica in linguaggio C dell'algoritmo. A proposito di E. W. Dijkstra si vedano anche le pagine a lui dedicate sul sito web dell'Università del Texas: http://www.cs.utexas.edu/users/EWD/.
Lezione n. 25 - giovedì 14 dicembre 2023
  • Classi di complessità per problemi: problemi di decisione, di ricerca, di enumerazione e di ottimizzazione, complessità di un algoritmo e di un problema, la classe di complessità P dei problemi risolubili mediante un algoritmo di complessità polinomiale; la classe di complessità NP dei problemi la cui soluzione può essere verificata con un algoritmo di complessità polinomiale; riducibilità polinomiale di un problema ad un altro, problemi NP-completi, il problema “P=NP”, esempi di problemi NP-completi (vedi le dispense sulla complessità degli algoritmi e dei problemiDocumento in formato PDF).
Lezione n. 26 - venerdì 15 dicembre 2023
  • Alberi binari di ricerca: archivi informatici e il problema della gestione di indici per eseguire più rapidamente operazioni di ricerca sull'archivio; definizione di albero binario di ricerca, esempi.
  • Operazioni sugli alberi binari di ricerca: algoritmi per l'inserimento di elementi nell'albero binario di ricerca, la ricerca dell'elemento massimo, dell'elemento minimo, la ricerca di un elemento qualsiasi, la ricerca del predecessore e del successore di un elemento, l'ordinamento dell'intero insieme; pseudo-codifica degli algoritmi, analisi della complessità computazionale.
Lezione n. 27 - martedì 19 dicembre 2023
  • Esercizi su grafi: funzioni per aggiungere ed eliminare spigoli su un grafo rappresentato con liste di adiacenza, funzione per verificare l'adiacenza di due vertici di un grafo; verifica della buona colorazione di un grafo, costruzione del grafo G con spigoli (u,v) tali che v sia un multiplo di u; dato un grafo G e un vertice v trovare tutti i vertici a distanza 2 da v; dato G trovare una coppia di vertici con massima differenza (in valore assoluto) del loro grado entrante.
Esercitazione n. 10 - giovedì 21 dicembre 2023
  • Esercizi su grafi e liste di adiacenza: costruzione delle liste di adiacenza del grafo orientato opposto al grafo letto in input; costruzione del grafo complementare; costruzione di un grafo random (documento con i testi e le soluzioni degli esercizi: esercitazione10.pdfDocumento in formato PDF).
Lezione n. 28 - venerdì 22 dicembre 2023
  • Esercizi di programmazione in C su liste e grafi: verifica di un ciclo Hamiltoniano su un grafoi; coppie di vertici dominanti e dominati su un grafo.
  • Riepilogo degli argomenti: breve riepilogo degli argomenti trattati nel corso e riferimenti bibliografici.

Università degli Studi Roma Tre - Dipartimento di Matematica e Fisica - Corso di laurea in Matematica - Corso IN110 Algoritmi e Strutture Dati

Author: Marco Liverani - Last modified: Friday December 29, 2023 - URI: http://www.mat.uniroma3.it/users/liverani/IN110/lezioni.shtml