"Diario" delle lezioni di Laboratorio di Programmazione Strutturata

"Diario" (comprendente i programmi svolti
o discussi) delle lezioni relative al corso di
Laboratorio di Programmazione Strutturata

Lezione del 30/9
- Presentazione degli obiettivi e degli strumenti del corso.
- Struttura di un calcolatore (cenni): schema dell'hardware, schema dei costituenti della CPU. Per approfondimenti, si consiglia la lettura del primo capitolo delle Note su linguaggio C e dintorni, accessibile al punto 1 di questa pagina web).
Lezione del 4/10
- Schema della CPU e del suo funzionamento; linguaggi a basso livello (assembler). Per approfondimenti, si consiglia la lettura del primo capitolo delle Note su linguaggio C e dintorni, accessibile al punto 1 di questa pagina web).
- Generalità sulla struttura fisico/logica dei dischi; partizioni e MBR (=Master Boot Record) (per approfondimenti, si consiglia la lettura del paragrafo 6.3 delle Note su linguaggio C e dintorni, accessibile al punto 1 di questa pagina web).
Lezione del 7/10
- Classificazione del software, descrizione (cenni) della procedura di accensione del computer e di avvio del sistema operativo. Per approfondimenti, si consiglia la lettura completa del primo capitolo e del paragrafo 6.3 delle Note su linguaggio C e dintorni, accessibile al punto 1 di questa pagina web).
- Tipi di dati in linguaggio C: gli interi e i numeri in virgola mobile (per approfondimenti, si consiglia la lettura del capitolo 4 delle Note su linguaggio C e dintorni, accessibile al punto 1 di questa pagina web).
- I numeri rappresentabili sul calcolatore: numero massimo, numero positivo minimo e "errore di macchina".
- Stampa della taglia (in bytes) di vari tipi di dati:
  ne si leggano e capiscano le istruzioni, lo si compili e lo si esegua.
Lezione del 11/10
- Descrizione dell'algoritmo che consente di calcolare l'"errore di macchina" e della traduzione in C di tale algoritmo.
- La struttura ad albero delle directories; breve introduzione all'utilizzo dei comandi di linea "essenziali" in Linux.
- Primo contatto con la distribuzione GNU/Linux installata sul disco rigido dei PC in laboratorio: esempio di sessione di lavoro "minima" con la distribuzione GNU/Linux attualmente installata in laboratorio, possibilmente da replicare "a casa" sul proprio PC, dopo avervi completato un'installazione.
- Scrittura in laboratorio del nostro primo programma; esso effettua il calcolo dell'"errore di macchina":
- Calcolo del minimo numero positivo rappresentabile sul calcolatore:
- Calcolo del massimo numero rappresentabile sul calcolatore:
  (questo programma include delle istruzioni che verranno descritte nelle lezioni successive; pertanto, al fine di comprendere meglio la rappresentazione dei numeri in virgola mobile, esso è interessante da eseguire, ma non è utile come esercizio di programmazione).
Lezione del 14/10
- Introduzione al concetto di programmazione strutturata: teorema di Bohm-Jacopini, non necessità dell'istruzione goto.
- L'input da tastiera: l'istruzione fscanf.
- Brevi cenni a proposito dei cicli do - while, while e for, con particolare attenzione alle relazioni che intercorrono fra di essi (per sviluppare una maggiore familiarità con le basi della programmazione illustrate in questa lezione può essere molto utile la lettura del cap. 2 e dei paragrafi 3.1-3.2 delle Note su linguaggio C e dintorni, accessibili al punto 1 di questa pagina web).
- Array 1-dimensionali: i vettori.
- Un primo algoritmo di ordinamento dei vettori: insertion sort (per approfondimenti, si rimanda alle trasparenze di una lezione sugli ordinamenti e al paragrafo 3.1 degli "Appunti di Informatica 1" (entrambi) del prof. G. Rossi.
Lezione del 18/10
- Scrittura del programma che traduce in C l'algoritmo di ordinamento insertion sort descritto nella lezione precedente:
- Prima installezione: modifica delle chiavette USB di alcuni studenti, in modo che possano emulare un CD di installazione di una distribuzione GNU/Linux.
- Si consiglia di svolgere i primi due esercizi della scheda di lavoro numero 4, tra quelle a cura del prof. A. Giorgilli, che sono accessibili al punto 2 di questa pagina web.
Lezione del 21/10
- Introduzione all'utilizzo delle function; discussione di un esempio elementare di scrittura di una function:
- Riscrittura con le function del programma che traduce in C l'algoritmo di ordinamento insertion sort (che era già stato scritto al calcolatore nella precedente lezione in laboratorio):
- Il paradigma della programmazione modulare: divide & impera. Gli stili di programmazione bottom-up e top-down.
- function ricorsive; cenni alla pila (=stack) di attivazione con procedura LIFO (=Last In First Out); discussione di un esempio: il programma che effettua il calcolo del fattoriale con un metodo ricorsivo:
- Per approfondimenti su alcuni argomenti di questa lezione può essere molto utile la lettura del cap. 2 e dei paragrafi 5.1-5.2 delle Note su linguaggio C e dintorni, accessibile al punto 1 di questa pagina web).
Lezione del 28/10
- Scrittura del programma che effettua il calcolo degli elementi della successione di Fibonacci con un metodo ricorsivo:
- Brevissima introduzione all'utilizzo del software per la grafica gnuplot. Come esempio di applicazione, viene prodotto un grafico a partire dal file CPUtime_fibo_ric.out (che raccoglie i dati relativi al tempo di utilizzo della CPU durante l'esecuzione del programma fibo_ric.c); tale grafico viene prodotto utilizzando i comandi inclusi nel seguente file:
  Per visualizzare sullo schermo una figura simile al
  non occorre fare altro che digitare il seguente comando (all'interno di una finestra di terminale che ha come directory corrente quella in cui sono presenti i files CPUtime_fibo_ric.out e CPUtime_fibo_ric.gnp):
  poi
  e, infine,
  per terminale l'esecuzione del programma gnuplot.
- Scrittura individuale (da parte di ciascuno studente) del programma che effettua il calcolo degli elementi della successione di Fibonacci con un metodo iterativo:
- Seconda installezione: modifica delle chiavette USB di alcuni studenti, in modo che possano emulare un CD di installazione di una distribuzione GNU/Linux.
- Si consiglia di svolgere i l'ultimo esercizio della scheda di lavoro numero 4 e/o la scheda di lavoro numero 5, tra quelle a cura del prof. A. Giorgilli, che sono accessibili al punto 2 di questa pagina web.
Lezione del 4/11
- Introduzione del concetto di complessità computazionale (cenni).
- Analisi della complessità degli algoritmi ricorsivo e iterativo per il calcolo degli elementi della successione di Fibonacci. Interpretazione del
- Descrizione di un classico problema che può venire elegantemente risolto con una procedura ricorsiva: le torri di Hanoi.
- Scrittura del programma che traduce in C l'algoritmo precedentemente descritto:
- Per approfondimenti su alcuni argomenti di questa lezione può si rimanda ai paragrafi 3.2 e 4.1 degli "Appunti di Informatica 1" del prof. G. Rossi.
Lezione del 8/11
- Descrizione dell'algoritmo che consente di passare dalla rappresentazione decimale a quella binaria e viceversa.
- Scrittura individuale (da parte di ciascuno studente) del programma che traduce in C l'algoritmo che consente di passare dalla rappresentazione decimale a quella binaria e viceversa (così come descritto nella lezione precedente):
  In laboratorio, la scrittura di questo programma è stata effettuata in modo da completare lo schema presente nel file
- Stampa sul video del triangolo di Tartaglia:
  La scrittura di questo programma può essere effettuata completando lo schema presente nel file
Lezione del 11/11
- Descrizione di un secondo algoritmo di ordinamento dei vettori: il merge sort. Scrittura del programma che traduce in C il suddetto secondo algoritmo di ordinamento:
- Analisi della complessità degli algoritmi di ordinamento: confronto tra l'insertion sort e il merge sort. Ottimalità del merge sort.
- Per approfondimenti sugli argomenti precedenti si rimanda ai paragrafi 3.2 e 4.1 degli "Appunti di Informatica 1" del prof. G. Rossi.
- Descrizione dell'algoritmo che consente di calcolare la somma di due numeri interi in rappresentazione binaria utilizzando solamente gli operatori logici e non il "+".
- Discussione a proposito delle procedure utilizzate dal calcolatore allo scopo di effettuare le operazioni aritmetiche elementari.
Lezione del 15/11
- Scrittura individuale (da parte di ciascuno studente) del programma che traduce in C l'algoritmo che consente di calcolare la somma di due numeri interi in rappresentazione binaria utilizzando solamente gli operatori logici e non il "+" (così come descritto nella lezione precedente):
  In laboratorio, la scrittura di questo programma è stata effettuata completando lo schema presente nel file
- Scrittura di un programma che calcola il prodotto di due numeri interi in rappresentazione binaria utilizzando solamente gli operatori logici e non il "*":
  Tale programma può essere scritto completando lo schema presente nel file
- Si consiglia di affrontare il tema d'esame del settembre 2007 per il corso di LC1, che richiede di svolgere la sottrazione e la divisione di due numeri in rappresentazione binaria utilizzando solamente gli operatori logici e non il "-" o il "/". La soluzione è disponibile a partire da questa pagina che raccoglie i temi d'esame precedentemente assegnati agli studenti di LC1 del corso di laurea in matematica.
Lezione del 18/11
- Cenni agli operatori bitwise, utilizzati per esempio per effettuare la somma di due numeri interi senza usare il "+":
  o per effettuare il prodotto di due numeri interi senza usare il "*":
- Passaggio degli argomenti delle functions per indirizzo; discussione di un esempio elementare, ma chiarificatore:
  e del suo ingenuo "alter-ego" (che è sbagliato):
- Descrizione dell'algoritmo che consente di calcolare il logaritmo per mezzo della sua espansione in serie di potenze.
- Descrizione dell'algoritmo che consente di calcolare simultaneamente le funzioni coseno e seno, per mezzo delle loro espansioni in serie di potenze.
Lezione del 22/11
- Scrittura individuale (da parte di ciascuno studente) del programma che traduce in C l'algoritmo che consente di calcolare il logaritmo per mezzo della sua espansione in serie di potenze (così come descritto nella lezione precedente):
  In laboratorio, la scrittura di questo programma è stata effettuata completando lo schema presente nel file
- Scrittura individuale (da parte di ciascuno studente) del programma che traduce in C l'algoritmo che consente di calcolare simultaneamente le funzioni coseno e seno, per mezzo delle loro espansioni in serie di potenze (così come descritto nella lezione precedente):
  In laboratorio, la scrittura di questo programma è stata effettuata completando lo schema presente nel file
- Scrittura di un programma che effettua il calcolo delle soluzioni di un'equazione polinomiale di secondo grado all'interno di una function:
  Tale programma può essere scritto completando lo schema presente nel file
Lezione del 25/11
- Descrizione del metodo di bisezione per la soluzione di equazioni del tipo f(x)=0; cenni al metodo di Newton; confronto delle caratteristiche fondamentali del metodo di bisezione e degli algoritmi "alla Newton".
- Puntatori alle functions; discussione del programma che traduce in C il metodo di bisezione (descritto in una delle lezioni precedenti), facendo uso di un puntatore a una function:
- Discussione di un metodo di calcolo numerico degli integrali definiti: il metodo del punto medio; studio dell'errore numerico commesso utilizzando tale metodo in funzione del numero di sotto-intervalli (in cui viene suddiviso l'intervallo di integrazione).
Lezione del 29/11
- Descrizione della direttiva define, cenni alla fase di precompilazione in linguaggio C.
- Scrittura individuale (da parte di ciascuno studente) del programma che traduce in C l'algoritmo di calcolo numerico degli integrali definiti utilizzando il metodo del punto medio (così come descritto nella lezione precedente):
  In laboratorio, la scrittura di questo programma è stata effettuata completando lo schema presente nel file
- Studio del grafico prodotto a partire dal file integrale.out (che raccoglie i dati prodotti in output dal programma integrale.c); la figura può essere prodotta dal software per la grafica gnuplot, utilizzando i comandi inclusi nel seguente file:
  Per visualizzare sullo schermo il
  non occorre fare altro che digitare il seguente comando (all'interno di una finestra di terminale che ha come directory corrente quella in cui sono presenti i files integrale.out e integrale.gnp):
  poi
  e, infine,
  per terminale l'esecuzione del programma gnuplot.
- La scrittura del programma che traduce in C il metodo di bisezione, facendo uso di un puntatore a una function:
  Tale scrittura può essere effettuata, eventualmente, completando lo schema presente nel file
Lezione del 9/12
- Descrizione di alcune istruzioni elementari che consentono di effettuare le operazioni di Input/Output su file: fopen, fclose, fprintf e fscanf.
- Matrici (cioè array bi-dimensionali) come argomenti delle functions; accesso alle singole righe delle matrici, grazie al meccanismo di passaggio degli argomenti per indirizzo.
- Discussione di un programma che verifica che una matrice (i cui valori degli elementi vengono letti da un file esterno di input) è ortogonale; questo programma è strutturato in modo tale da utilizzare le nozioni discusse in precedenza:
Lezione del 13/12
- Scrittura individuale (da parte di ciascuno studente) del programma che traduce in C l'algoritmo che verifica se una matrice (letta da un file esterno di input) è ortogonale (così come descritto nella lezione precedente):
  In laboratorio, la scrittura del suddetto programma è stata effettuata completando lo schema presente nel file
  Inoltre, per poter funzionare, il suddetto programma deve essere eseguito all'interno di una directory (=cartella) che contiene anche il seguente file di input:
- Scrittura di un programma che consente di determinare una matrice ortogonale (come prodotto di tante matrici di "rotazione"):
  La scrittura di questo programma può essere effettuata completando lo schema presente nel file
  Nota: tale programma (alla fine della sua esecuzione) scriverà la matrice ortogonale "risultato" nel suddetto file di output matr_ort.inp, che è il file di input per matr_ort.c.
Lezione del 16/12
- Successioni di numeri pseudocasuali, utilizzo delle functions srand, rand e time; un primo esempio elementare di scrittura di un programma su tali argomenti:
- Discussione riguardante l'equidistribuzione dei numeri pseudocasuali, evidenziata anche dal seguente
- Calcolo del determinante di una matrice: discussione del metodo di Laplace e analisi della sua complessità computazionale.
Lezione del 20/12
- Scrittura individuale (da parte di ciascuno studente) del programma che traduce in C l'algoritmo che permette di calcolare il determinante di una matrice con il metodo di Laplace (così come descritto nella lezione precedente):
  In laboratorio, la scrittura di questo programma è stata effettuata completando lo schema presente nel file
- Si propone la scrttura individuale del programma the effettua un piccolo test sulla "equidistribuzione" delle successioni di numeri pseudocasuali (così come descritto nella lezione precedente):
Lezione del 10/1
- Esercitazione "speciale" proposta in laboratorio: un tema d'esame a scelta tra quelli assegnati durante uno degli anni accademici precedenti.
Lezione del 13/1
- Discussione del metodo di Cramer per la soluzione dei sistemi lineari.
- Breve comparazione dell'efficienza algoritmica tra il metodo di Cramer e quello di eliminazione alla Gauss, per la soluzione dei sistemi lineari.
- Descrizione delle stringhe e scrittura di alcune function che fanno parte della libreria string.h (a mo' di esercizio di programmazione): strchr, strlen. Per approfondimenti, si rimanda alle trasparenze di una lezione sulle stringhe del prof. G. Rossi e al paragrafo 4.1.3 delle "Note su linguaggio C e dintorni" del prof. A. Giorgilli.
- Approfondimenti riguardanti alcune procedure per la lettura da file; utilizzo (combinato) delle istruzioni fgets e sscanf.
- Un primo esempio elementare di utilizzo della function fgets, allo scopo di leggere correttamente un file di input di cui non si conosce a priori il numero di righe:
  che, per poter funzionare, deve essere eseguito all'interno di una directory (=cartella) che contiene anche il seguente file di input:
- Ulteriori approfondimenti riguardanti alcune procedure per la lettura da file; utilizzo (combinato) delle istruzioni fgets, sscanf e strchr o strstr. Discussione del programma
  che, per poter funzionare, deve essere eseguito all'interno di una directory (=cartella) che contiene anche il seguente file di input:
  Il suddetto programma matr_ort_new.c è un'opportuna riscrittura di matr_ort.c, in modo tale da poter leggere un file di input contenente una matrice i cui elementi sono disposti nel modo tradizionale, cioè "per righe e colonne". Come in matr_ort.c, il programma matr_ort_new.c effettua anche la verifica che la matrice letta da file è ortogonale.
Lezione del 17/1
- Scrittura individuale (da parte di ciascuno studente) del programma che traduce in C l'algoritmo che permette di risolvere sistemi lineari con il metodo di Cramer (così come descritto nella lezione precedente):
  In laboratorio, la scrittura di questo programma è stata effettuata completando lo schema presente nel file
  Inoltre, per poter funzionare, il suddetto programma deve essere eseguito all'interno di una directory (=cartella) che contiene anche il seguente file di input:
  Infine, quando la sua esecuzione sta per essere terminata, il suddetto programma produce il seguente file di output (che sarà contenuto sempre all'interno della stessa directory, o cartella):
- Scrittura di un programma che consente di determinare la matrice inversa di una data matrice:
  La scrittura di questo programma può essere effettuata completando lo schema presente nel file
  Inoltre, per poter funzionare, il suddetto programma deve essere eseguito all'interno di una directory (=cartella) che contiene anche il seguente file di input: