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

Lezione n. 1 - lunedì 22 settembre 2025

• 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ì 23 settembre 2025

• 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, verifica dell'ordinamento crescente di una sequenza di numeri). Linguaggi imperativi, istruzioni fondamentali di in linguaggio imperativo.

Lezione n. 3 - giovedì 25 settembre 2025

• 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, verifica della divisibilità di un numero naturale (scarica il documento: “Algoritmi e diagrammi di flusso”).

Lezione n. 4 - venerdì 26 settembre 2025

• 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: divisibilità di un numero naturale per un altro, calcolo del quoziente e del resto nella divisione di due numeri naturali, verifica della primalità di un numero naturale, minimo comune multiplo tra due numeri naturali; un algoritmo sbagliato per il calcolo della radice quadrata di un numero naturale.
• Cenni sulla calcolabilità: alcuni problemi non risolubili per via algoritmica: esempi basati sulla congettura di Goldbach e la congettura di Collatz / Ulam.

Lezione n. 5 - lunedì 29 settembre 2025

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

Lezione n. 6 - martedì 30 settembre 2025

• Calcolabilità e modelli di calcolo: il modello di Von Neumann; cenni sul problema della fermata, cenni sulla Tesi di Church-Turing (scarica il documento: “Appunti sui modelli di calcolo”).
• 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.

Lezione n. 7 - giovedì 2 ottobre 2025

• Rappresentazione delle informazioni:, 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”).
• 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.
• Struttura di controllo condizionale: la struttura di controllo condizionale if... else..., esempi.
• Operatori di confronto: operatori di confronto, espressioni logiche, connettori logici and, or, not, valutazione di espressioni booleane, esempi.

Lezione n. 8 - venerdì 3 ottobre 2025

• Strutture di controllo iterative: le istruzioni while, do-while e for; esempi.
• Operatori aritmetici: operatori aritmetici, anche in forma compatta (++, -- in forma prefissa e postfissa; gli operatori di assegnazione +=, -=, *= e /=). L'operazione di cast. L'operatore modulo “%” per il calcolo del resto nella divisione tra interi.

Lezione n. 9 - lunedì 6 ottobre 2025

• Array: array monodimensionali (vettori) e multidimensionali (matrici), dichiarazione di array, allocazione in memoria di un array; esempi.
• 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.

Lezione n. 10 - martedì 7 ottobre 2025

• Stringhe di caratteri: esempi ed esercizi sulle stringhe di caratteri, cenni sulle funzioni della libreria string.h.
• Numeri pseudo-casuali: generazione di sequenze di numeri pseudo-casuali, le funzioni srand e rand, la funzione time, 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ì 9 ottobre 2025

• 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 di alcuni esercizi che non abbiamo avuto il tempo di svolgere durante la lezione: esercitazione01.pdf).

Lezione n. 11 - venerdì 10 ottobre 2025

• 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 - martedì 14 ottobre 2025

• 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ì 16 ottobre 2025

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

Lezione n. 13 - venerdì 17 ottobre 2025

• 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ì 21 ottobre 2025

• 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ì 23 ottobre 2025

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

• 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ì 28 ottobre 2025

• 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ì 30 ottobre 2025

• 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 - venerdì 31 ottobre 2025

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

Lezione n. 18 - martedì 4 novembre 2025

• Counting sort: strategia risolutiva, pseudo-codice dell'agoritmo, esempi e calcolo della complessità computazionale, codifica in linguaggio C, diagramma di flusso.
• Esercizi di preparazione all'esonero.

Esercitazione n. 5 - giovedì 6 novembre 2025

• 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. 19 - venerdì 7 novembre 2025

• Esercizi sugli array per la preparazione alla prova d'esonero.

Lezione n. 20 - martedì 18 novembre 2025

• Allocazione dinamica della memoria: le funzioni di libreria sizeof, malloc e free, allocazione dinamica di array e matrici, 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).

Esercitazione n. 6 - giovedì 20 novembre 2025

• 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. 21 - venerdì 21 novembre 2025

• 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).
• 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 (estrai).