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

Lezione n. 1 - lunedì 23 settembre 2024

• 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”).
• Introduzione alla progettazione di algoritmi: un approccio intuitivo mediante alcuni esempi elementari.

Lezione n. 2 - martedì 24 settembre 2024

• 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, verifica della parità di un numero naturale, quoziente e resto della divisione tra interi, verifica dell'ordinamento crescente di una sequenza di numeri). Linguaggi imperativi, istruzioni fondamentali di in linguaggio imperativo.

Lezione n. 3 - giovedì 26 settembre 2024

• 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 Giuseppe Jacopini e Corrado Böhm; esempi: media aritmetica di un insieme di n numeri, ricerca del massimo fra 2, 3 e n numeri, verifica dell'ordinamento di una sequenza (scarica il documento: “Algoritmi e diagrammi di flusso”).

Lezione n. 4 - venerdì 27 settembre 2024

• Algoritmi, diagrammi di flusso, programmazione strutturata: esercizi per la pseudo-codifica di un algoritmo e la rappresentazione di un diagramma di flusso per la risoluzione dei seguenti problemi: massimo su una sequenza di n numeri, verifica della primalità di un numero naturale, fattoriale di un numero naturale, minimo comune multiplo tra due numeri naturali; un algoritmo sbagliato per il calcolo della radice quadrata di un numero naturale.

Lezione n. 5 - lunedì 30 settembre 2024

• 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.
• 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”).

Lezione n. 6 - martedì 1 ottobre 2024

• 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”).
• 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”).

Lezione n. 7 - giovedì 3 ottobre 2024

• 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..., esempi.

Lezione n. 8 - venerdì 4 ottobre 2024

• Operatori aritmetici: operatori aritmetici, anche in forma compatta (++, -- in forma prefissa e postfissa; gli operatori di assegnazione +=, -=, *= e /=).
• Operatori di confronto: operatori di confronto, espressioni logiche, connettori logici and, or, not, valutazione di espressioni booleane, esempi.
• Struttura di controllo condizionale: la struttura di controllo condizionale if... else..., esempi.
• Strutture di controllo iterative: le istruzioni while, do-while e for; esempi.

Lezione n. 9 - lunedì 7 ottobre 2024

• Array: array monodimensionali (vettori) e multidimensionali (matrici), dichiarazione di array, allocazione in memoria di un array; esempi. L'operazione di cast, e l'uso della libreria matematica, esempi.

Lezione n. 10 - martedì 8 ottobre 2024

• 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 (scarica il documento: “Appunti sul linguaggio C”).

Esercitazione in laboratorio - giovedì 10 ottobre 2024

• Introduzione all'uso del laboratorio informatico: struttura del laboratorio e della sua rete, accesso alle postazioni di lavoro, accesso al server mediante il protocollo SSH, accesso al server mediante connessioni Internet dall'esterno (scarica il documento: “Accesso alle risorse del laboratorio informatico del Dipartimento di Matematica” e le slide sull'uso del laboratorio informatico; si suggerisce di prendere visione anche del documento “UNIX: introduzione elementare” per una migliore comprensione dell'uso della shell del sistema operativo UNIX/Linux).
• Programmazione in C: scrittura di un programma in linguaggio C, compilazione, debugging ed esecuzione (documento con i testi e le soluzioni degli esercizi: esercitazione01.pdf).

Lezione n. 11 - venerdì 11 ottobre 2024

• 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. 12 - lunedì 15 ottobre 2024

• 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.
• Funzioni ricorsive: definizione di funzioni ricorsive, differenze ed analogie con procedure iterative, esempi (funzione fattoriale definita in modalità iterativa e ricorsiva).

Esercitazione n. 2 - giovedì 17 ottobre 2024

• Esercizi sugli array: operazioni sugli array: intersezione, differenza, inversione (documento con i testi e le soluzioni degli esercizi: esercitazione02.pdf).

Lezione n. 13 - venerdì 18 ottobre 2024

• 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. 14 - martedì 22 ottobre 2024

• 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.
• Algoritmo Bubble Sort: strategia risolutiva, pseudo-codifica dell'algoritmo, calcolo della complessità computazionale, codifica in linguaggio C dell'algoritmo Bubble Sort, esempi.

Esercitazione n. 3 - giovedì 24 ottobre 2024

• 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.pdf).

Lezione n. 15 - venerdì 24 ottobre 2024

• 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; codifica in linguaggio C dell'algoritmo Quick Sort.

Lezione n. 16 - martedì 29 ottobre 2024

• 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, codifica in linguaggio C, esempi (in questa pagina è disponibile la codifica in linguaggio C dell'algoritmo Merge Sort).

Esercitazione n. 4 - giovedì 31 ottobre 2024

• 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.pdf).

Lezione n. 17 - martedì 5 novembre 2024

• 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 minimo (o 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.

Esercitazione n. 5 - giovedì 7 novembre 2024

• 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.pdf).

Lezione n. 18 - venerdì 8 novembre 2024

• Riepilogo sulla complessità computazionale degli algoritmi di ordinamento e sulle diverse strategie risolutive.
• Compressione dei dati con l'algoritmo RLE (Run Lenght Encoding), descrizione della strategia di compressione, esempi (vedi la codifica in linguaggio C dell'algoritmo).
• Per la preparazione della prima prova di esonero si suggerisce di prendere visione del testo e della soluzione degli esercizi proposte nelle prove degli anni precedenti: 2023/2024, 2022/2023, 2021/2022, 2019/2020, 2016/2017, 2015/2016, 2014/2015, 2012/2013.

Lezione n. 19 - martedì 19 novembre 2024

• Allocazione dinamica della memoria: le funzioni di libreria sizeof, malloc e free, 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 di funzione per la memorizzazione di una serie di numeri in una lista (leggiLista) e la visualizzazione in output del contenuto di una lista (stampaLista).

Esercitazione n. 6 - giovedì 21 novembre 2024

• 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.pdf).

Lezione n. 20 - venerdì 22 novembre 2024

• Code con le liste: funzione per la costruzione di una lista come una coda, funzione per l'accodamento di un elemento (accoda) e l'estrazione del primo elemento da una coda (scoda).

Lezione n. 21 - martedì 26 novembre 2024

• Operazioni sulle liste: eliminazione di un elemento da una lista.
• 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, grafo completo, isomorfismo tra grafi, esempi.

Lezione n. 22 - venerdì 29 novembre 2024

• 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, grafo completo, clique, sottografo, sottografo indotto, esempi; definizione di albero, proprietà di un albero, spanning tree, esempi (scarica il documento: “Appunti sulla teoria dei grafi”).
• 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.

Lezione n. 23 - martedì 3 dicembre 2024

• 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.

Esercitazione n. 7 - giovedì 5 dicembre 2024

• 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.pdf).

Lezione n. 24 - venerdì 6 dicembre 2024

• 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. 8 - lunedì 9 dicembre 2024

• 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.pdf).

Lezione n. 25 - martedì 10 dicembre 2024

• 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. 26 - venerdì 13 dicembre 2024

• 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ì 17 dicembre 2024

• 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 problemi).

Esercitazione n. 9 - giovedì 19 dicembre 2024

• 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.pdf).

Lezione n. 28 - venerdì 21 dicembre 2024

• Esercizi di programmazione in C su liste e grafi: inversione di una lista, fusione di due liste ordinate, algoritmo selection sort su una lista, costruzione del grafo complementare.
• Riepilogo degli argomenti: breve riepilogo degli argomenti trattati nel corso e riferimenti bibliografici.