Informatica, terzo canale,
anno accademico 2023-2024

• Introduzione al corso
• Concetto di problema e di algoritmo
• Linguaggi ed esecutori, architettura di Von Neumann
• Esempi di algoritmi
• Linguaggi di programmazione
  • dall'algoritmo al programma eseguibile
  • compilazione/interpretazione
  • il caso del linguaggio Python
Errori sintattici, errori semantici

• Architettura di un calcolatore: CPU, RAM, ROM, unità periferiche
• Esecuzione di programmi, fetch, execute. Il Bootstrap
• Il Sistema Operativo: gestione memoria, gestione processi, gestione utenti

Cenni sulla struttura di un file system gerarchico: dischi logici, files, cartelle

Uso della shell Linux (o Terminale in Mac OS, o Prompt dei comandi in Windows)

Navigazione nel file system: comando ls (o dir in Windows) comando cd. Path assoluti e relativi.

Uso dell'interprete Python 3 in modalità interattiva

Operatori aritmetici

Espressioni, precedenza tra operatori, valutazione di una espressione: albero sintattico

Istruzione di assegnazione, binding nome - valore

Esempi di semplici problemi risolubili in modalità interattiva

La funzione type(...)

Script vs. modalità interattiva, uso dell'ambiente Thonny, uso del debugger

Funzioni input(...) e print(...)

Regole per la definizione di identificatori, parole riservate

Funzioni di conversione

Stringhe, operatori su stringhe

Errori sintattici, errori semantici, eccezioni

Uso di funzioni matematiche con import math

Chiamata di funzioni. Significato in una espressione.

Un tutorial per l'installazione di Python3 in ambiente Windows è disponibile su https://www.youtube.com/watch?v=ij1HTDpVTBI (a cura del prof. Massimo Lauria)

1. Verificare, utilizzando l'interprete Python 3, qual è il massimo valore float rappresentabile
2. Sperimentare la differenza tra l'operatore / e l'operatore //, sia con operandi int che con operandi float.
3. Esprimere 8430 secondi in ore, minuti e secondi.
4. Generalizzare il problema precedente immettendo da tastiera il numero di secondi.
5. Calcolare quanti secondi sono 3 ore, 5 minuti e 18 secondi
6. Generalizzare il problema precedente immettendo da tastiera il numero di ore, minuti e secondi.
7. Trovare la lunghezza dell'ipotenusa di un triangolo rettangolo i cui cateti misurano rispettivamente 18.6 metri e 15 metri
8. Come sopra, immettendo le lunghezze dei cateti da tastiera
9. Dato capitale iniziale (inserire a piacere) e interesse annuo (ad esempio 4.5 se l'interesse è del 4,5% annuo), calcolare il capitale dopo un anno e dopo 3 anni.

Istruzione if ... : else: ...

Espressioni boolean, le costanti True e False

Indentazione del codice

Operatori logici and, or e not

1. Dati tre valori float distinti a piacere, che rappresentano i coefficienti di una equazione di secondo grado in una variabile, trovare le soluzioni (se reali) oppure stampare un messaggio (se complesse). Il programma deve funzionare correttamente per qualsiasi terna di coefficienti.
2. Ordina tre numeri. Dati tre numeri interi distinti stamparli in ordine crescente. Si può decidere di eseguire i confronti e stampare i tre valori nell'ordine richiesto oppure di usare altre tre variabili alle quali assegnare rispettivamente il valore minimo, mediano e massimo e poi stampare le tre variabili.
3. Verifica se tre interi possono essere le misure dei lati di un triangolo e individua il tipo di triangolo. Per esempio, 3, 2 e 8 non possono esserlo perché ... non si riesce a "chiudere" il triangolo!
4. Come al punto precedente, ma in caso affermativo decidere se il triangolo è rettangolo, acutangolo od ottusangolo (suggerimento: se vale il teorema di Pitagora è rettangolo, altrimenti ...)
5. Date (inserire a piacere questi valori) le coordinate di tre punti a=(xa, ya), b=(xb, yb), c=(xc, yc), calcolare la lunghezza dei lati del triangolo definito dai tre punti
6. Siano x1, y1, x2, y2, x3, y3, x4, y4 le coordinate (inserire a piacere questi valori) di quattro punti. Calcolare e stampare le pendenze (coefficiente angolare) della retta passante per (x1, y1) e (x2, y2) e della retta passante per (x3, y3) e (x4, y4).

Invocazione di metodi e uso del valore restituito

Generazione di numeri pseudocasuali con random.random() e random.randint(a, b)

Semplici programmi con l'istruzione if

Esercitazione 2

Istruzione if ... : elif: ... elif: ... else: ...

Esempi di programmi con if

Definizione di funzioni con def .... :

1. Dati due intervalli I1=[a, b] e I2=[c, d], rappresentati nel programma da quattro variabili int a, b, c, d;, con a<b e c<d, decidere se l'intervallo I1 contiene l'intervallo I2 (come ad esempio nel caso I1=[3, 40] e I2=[12, 25]) oppure I2 contiene I1, oppure non c'è relazione di contenimento (come ad esempio nel caso I1=[11, 56] e I2=[28, 80]. Visualizzare gli intervalli e un messaggio che indica l'eventuale contenimento.
2. Si vuole studiare un insieme di 5 pazienti a, b, c, d, e, dei quali conosciamo il peso espresso in kg (pa, pb, pc, pd, pe) e l'altezza espressa in metri (ha, hb, hc, hd, he) (inserire a piacere questi valori).
   Calcolare e stampare il body mass index (BMI) dei 5 soggetti. Il BMI di una persona è definito dal peso in kg diviso il quadrato dell'altezza in metri.
3. Dato capitale iniziale (inserire a piacere) e interesse annuo (ad esempio 4.5 se l'interesse è del 4,5% annuo), calcolare il capitale dopo un anno e dopo 3 anni.
4. Stampare (per ora usando una sequenza di istruzioni molto simili tra loro) una tabella con il valore del seno e del coseno degli angoli da 0 a 90 gradi, con incrementi di 10 gradi.

   angolo   seno         coseno
   0        0.0          1.0
   10       0.17364...   0.98480...
   20       0.34202...   0.93969...
   30   .....
   ...
   90       1.0          0.0
   
   

   È anche possibile definire una funzione che, data l'ampiezza x di un angolo in gradi, stampa la riga corrispondente comprendente ampiezza, seno e coseno di x. Basterà poi chiamare ripetutamente questa funzione.

Stack di attivazione delle funzioni. Variabili locali.

Passaggio dei parametri. Assenza di effetti collaterali su parametri

Funzioni vuote, funzioni che restituiscono valori. Parametri ed argomenti.

1. dati tre reali maggiori di zero, stampare la media aritmetica e la media geometrica
2. generare casualmente 5 numeri interi in [1, 6] e stampare:
   • il massimo
   • la molteplicità del massimo (quanti valori sono uguali al massimo)
3. dato l'orario di inizio di un evento (espresso da tre interi: ore, minuti, secondi, con ore compreso in [0,23], minuti compreso in [0, 59] e secondi compreso in [0, 59]) e data la durata dell'evento (espressa in ore, minuti e secondi con gli stessi vincoli definiti sopra), calcola e stampa l'istante di fine dell'evento (espressa nello stesso modo), indicando se l'istante di fine è nello stesso giorno dell'inizio o nel giorno successivo
4. Funzione che restituisce la somma di due numeri, con esempio di uso
5. Funzione che date le misure di due cateti di un triangolo rettangolo restituisce la misura dell'ipotenusa, con esempio di uso
6. Funzione che verifica se tre numeri costituiscono una terna pitagorica, cioè se il quadrato di uno dei tre è uguale alla somma dei quadrati degli altri due, con esempi di uso. Questa funzione deve restituire True o False

Assegnazione con modifica: += -= *= /=

Esercizi sulla definizione di funzioni

Esercitazione 3

L'istruzione di ciclo while

Esercizi sull'uso di cicli e istruzioni condizionali

• Scrivere un programma che stampa il seno e il coseno degli angoli di ampiezza 0, 10, 20, ..., 90 gradi.
• Scrivere un programma che legge da tastiera un intero n e stampa una riga contenente n asterischi. La stampa deve essere ottenuta chiamando una apposita funzione, e senza usare l'operatore di moltiplicazione su stringhe.
• Scrivere un programma che mostra quante volte bisogna ripiegare in due un foglio dello spessore di 0,1 millimetri affinché si raggiunga lo spessore di 500 mm.. Stampare lo spessore ottenuto dopo ciascun ripiegamento.
• Modificare il programma precedente, stampando solo il numero di ripiegamenti necessari. Deve essere stampato un solo numero. Provare poi a raggiungere la distanza Terra-Luna, circa 380000 km (380.000.000.000 mm, 3.8e+11 mm).
• Modificare il programma precedente, definendo una funzione che prende come parametri lo spessore del foglio e la distanza che si intende raggiungere, e restituisce il numero di ripiegamenti necessari. Scrivere un programma che chiama la funzione appena definita con vari valori dei parametri.
• Scoprire cosa fa il programma ignoto.py
• Fare in modo che il programma ignoto.py funzioni anche quando a e/o b contengono valori negativi
• Scrivere un programma che, dati due numeri naturali a e b, stampa il valore di ab, senza utilizzare l'operatore **
• Definire una funzione che restituisce il numero di anni necessari per raggiungere un dato importo a partire da un capitale iniziale e un tasso di interesse annuo. Alla fine di ciascun anno gli interessi maturati vengono aggiunti al capitale, in modo che nell'anno successivo anche gli interessi aggiunti al capitale diano luogo ad interessi.

Istruzioni break e continue

Esempi di definizione di funzioni con cicli.

• Verifica se un naturale è primo. La funzione ha come parametro il numero naturale e restituisce True o False. Per verificare se un numero a è divisibile per b basta verificare se il valore a % b è zero.
• Considerazioni sull'efficienza degli algoritmi per il test di primalità.
• Stampa il numero di divisori di un naturale (si possono utilizzare alcune delle idee a proposito del test di primalità)
• Scrivere una funzione che stampi i numeri della successione di Fibonacci minori o uguali a un parametro dato.
• Scrivere un programma che stampi i primi n elementi della successione di Fibonacci.

Uso di variabili boolean per il controllo di cicli

Istruzioni break e continue

Esercizi sull'uso di cicli e istruzioni condizionali

Esercitazione 4

Un tutorial per la soluzione degli esercizi proposti in questa esercitazione è disponibile su https://uniroma1.zoom.us/rec/share/y1e1iV7eWkmpzA64b8YagAa0oxUOcgo5sddgvLwcOE74WL1SWynldwoOpzPoEX_d.7bIp7_EXPwBROov6 passcode: Vh.bsy4U

Algoritmo per approssimare uno zero di una funzione continua ricercaZero.py

Esempi di programmi con cicli multipli e istruzioni di selezione

Introduzione alle stringhe. Indicizzazione, funzione len, operatore in

• funzione che verifica se una stringa è palindroma
• funzione che conta gli spazi in una stringa
• funzione che conta le vocali in una stringa
• funzione che, data una stringa, stampa una parola della stringa su ciascuna riga
• migliorare la funzione precedente facendo sì che NON vengano stampati a capo multipli in presenza di spazi adiacenti nella stringa

Istruzione for ... in ...

Uso del range(...)

Differenza tra:

• scansione delle posizioni for i in range(len(sequenza)):
• scansione degli elementi for valore in sequenza:

Semplici programmi con cicli

Esempi di programmi con cicli e istruzioni di selezione

• Dato un numero naturale n, stampare un quadrato (pieno) di asterischi di lato n. Il quadrato sarà formato da n righe, ciascuna contenente n asterischi.

    **********
    **********
    **********
    **********
    **********
    **********
    **********
    **********
    **********
    **********
  
  

• Dato un numero naturale n, stampare un quadrato (solo il bordo) di asterischi di lato n. Il quadrato dovrà avere l'aspetto seguente:

    ********** . . . ****
    *                   *
    *                   *
    *                   *
      . . . . . . . .
      
    *                   *
    ********** . . . ****
  
  

• Dati due numeri naturali n e b, con b < n/2, stampare un quadrato di asterischi di lato n con il bordo di spessore b. Ad esempio, se il valore di b fosse 3, il quadrato dovrebbe avere l'aspetto seguente:

    ********** . . . ****
    ********** . . . ****
    ********** . . . ****
    ***               ***
    ***               ***
    ***               ***
      . . . . . . . .
      
    ***               ***
    ********** . . . ****
    ********** . . . ****
    ********** . . . ****
  
  

• Dato un numero naturale n, stampare un triangolo rettangolo (pieno) di asterischi di lato n. Il triangolo sarà formato da n righe di lunghezza crescente.

    *
    **
    ***
    ****
     . . .
    
    *********
    **********
  
  

• Dato un numero naturale n, stampare un triangolo rettangolo (solo il bordo) di asterischi di lato n. Il triangolo dovrà avere l'aspetto seguente:

    *
    **
    * *
    *  *
     . . .
    
    *      *
    *       *
    **********
  
  

• Stampare la somma dei primi n termini della serie armonica: 1/1 + 1/2 + 1/3 + ... + 1/n
• Come sopra, mostrando la differenza tra il risultato ottenuto eseguendo la somma in un senso o in senso opposto: 1/1 + 1/2 + 1/3 + ... + 1/n rispetto a 1/n + 1/(n-1) + 1/(n-2) + ... + 1/2 + 1/1

• Mostrare l'andamento della somma della serie armonica, visualizzandone il valore ogni 100 termini aggiunti fino a un massimo numero di termini immesso da tastiera.
  Mostrare che la differenza tra la somma dei primi n termini e il logaritmo naturale (Math.log) di n, al crescere di n, tende a una costante.
• Stampa della tavola pitagorica n × n assumendo che che l'input (n) sia compreso nell'intervallo [1,18] (Suggerimento: per ottenere la tabella ben incolonnata usare il cosiddetto "modulo tra stringhe" o "string interpolation")

Somme di quadrati

Scrivere un programma che, dato in input un numero naturale n, stampa tutte le coppie di naturali x, y tali che x^2 + y^2 = z^2, con x, y, z ≤ n.

Per n = 20 le soluzioni dovrebbero essere le seguenti:

3^2 + 4^2 = 5^2
5^2 + 12^2 = 13^2
6^2 + 8^2 = 10^2
8^2 + 15^2 = 17^2
9^2 + 12^2 = 15^2
12^2 + 16^2 = 20^2
	

Soluzione: cercaTernePitagoriche.py

Esercizi su stringhe, cicli.

Esercitazione 5

Liste

Accesso e modifica di elementi di una lista.

I metodi append(...) ed extend(...) delle liste

Costruzione di liste

Assegnazione vs. copia: riferimenti multipli a liste

Slicing

Funzioni che modificano liste

Funzioni che restituiscono liste

• funzione che restituisce la somma degli elementi di una lista
• funzione che restituisce la media degli elementi di una lista
• funzione che restituisce minimo e massimo di una lista
• funzione che restituisce le posizioni del minimo e del massimo di una lista
• funzione che, data una lista di numeri L e una soglia s, restituisce il numero di elementi di L maggiori di s
• funzione che crea e restituisce una lista di float random
• funzione che moltiplica gli elementi di una lista L, passata come parametro, per una costante data c, passata come parametro. La funzione deve modificare la lista L, senza restituire nulla.

Funzione isinstance(...)

Sollevare eccezioni con raise

Esercizi su liste

I metodi index(...), pop(...), remove(...) e insert(...) delle liste

Implementazione della ricerca sequenziale su lista

Liste disomogenee. Verifica del tipo degli elementi di una lista con la funzione isinstance(val, tipo)

Ricerca sequenziale

Ricerca binaria in sequenze ordinate ricercaBinaria.py

Esercizi di base su liste:

• Leggi da tastiera una sequenza di numeri, memorizzala in una lista, stampa la somma degli elementi sommaSequenzaInLista.py
• Leggi da tastiera una sequenza di double, memorizzala in una lista, crea un lista che contiene una copia degli elementi della prima lista, ma in ordine inverso copiaOrdineInverso.py
• Leggi da tastiera una sequenza di interi che rappresentano delle frequenze, memorizzala in una lista, crea una lista che contiene le frequenze cumulate e stampa, in due colonne, la sequenza delle frequenze (sulla sinistra) e la sequenza delle frequenze cumulate (sulla destra) cumula.py
• Ricerca sequenziale in una lista ricercaSequenziale.py

Data in input una sequenza di interi che rappresentano frequenze:

• stampare la frequenza massima e la frequenza minima;
• calcolare la lista delle frequenze relative e stamparlo;
• calcolare la lista delle frequenze relative cumulate e stamparlo;

Soluzione: frequenze.py

Esercizi su liste.

Creazione di liste con list comprehension

Algoritmo di ordinamento insertion sort insertionSort.py

Complessità computazionale dell'insertion sort

Esercizi su liste.

Liste di liste per la rappresentazione di matrici. Esercizi su liste di liste:

• Scansione di matrici: per elementi o per posizioni.
• Creazione di una matrice n per m con elementi 0 creaMatrice.py.
• Creazione della matrice identità n per n.
• Somma degli elementi di una matrice sommaMatrice.py.
• Conta elementi uguali a x in una matrice.
• Verifica di matrice ben formata.

• Funzione che, data una matrice, la stampa sotto forma di tabella,
• funzione che data una matrice restituisce la matrice trasposta,
• funzione che, data una matrice m e un valore numerico c, modifica m moltiplicando ciascun elemento per x,
• funzione che verifica se una matrice data è simmetrica.

Dizionari: definizione, indicizzazione, scansione con ciclo for, metodi keys(), values(), items().

Condizione in su dizionari.

Il metodo get

• Funzione che a partire da una lista di valori, restituisce un dizionario in cui ciascun valore presente nella lista è associato al numero di occorrenze (frequenza) frequenza.py.
• Funzione che a partire da un dizionario che contiene frequenze assolute delle chiavi, restituisce il dizionario contenente le frequenze relative delle chiavi frequenzeRelative.py

Scrivere le seguenti funzioni, che hanno tutte come parametri un dizionario esami in cui ogni chiave è il titolo di un insegnamento e il corrispondente valore è il voto riportato, e un secondo dizionario crediti in cui ogni chiave è il titolo di un insegnamento e il corrispondente valore è il numero di crediti.

1. Restituire il numero di esami sostenuti.
2. Restituire il numero di esami sostenuti, escluse le idoneità (le idoneità non sono presenti nel secondo dizionario).
3. Restituire la media (non pesata) dei voti conseguiti, escluse le idoneità.
4. Restituire il numero di crediti conseguiti, incluse le idoneità.
5. Restituire una coppia formata dal numero totale di crediti conseguiti e il numero di crediti conseguiti come idoneità.
6. Restituire la media dei voti conseguiti, escluse le idoneità, pesata in base ai crediti.
7. Restituire il voto più alto e il voto più basso.
8. Come il punto precedente, includendo anche i titoli di uno qualsiasi degli esami con voto massimo e uno di quelli con voto minimo. La funzione deve restituire una stringa composta dai due titoli e i rispettivi voti.
9. Come il punto precedente, includendo tutti gli esami con voto massimo e tutti quelli con voto minimo.
10. Restituire il dizionario contenente solo gli esami, con i relativi voti, nel cui titolo compare la stringa "Statistic". La stringa da cercare nel titolo può essere un parametro opzionale della funzione.
11. Come il punto precedente, ma la ricerca della stringa non deve tener conto della differenza tra lettere maiuscole e minuscole.

Esercizi su liste bidimensionali.

Introduzione alla ricorsione.

Esempio di algoritmo ricorsivo per il calcolo del fattoriale fattorialeRicorsivo.py

Esempio di algoritmo iterativo per il calcolo del fattoriale fattorialeIterativo.py

Esempio di algoritmo ricorsivo per il calcolo di un elemento della sequenza di Fibonacci fibonacciRicorsivo.py

Somma dei numeri contenuti in una lista attraverso bipartizione sommaListaBipartizione.py

Somma dei numeri contenuti in una lista di liste di liste ... sommaListaRicorsiva.py

• scrivere un metodo ricorsivo che data una lista di numeri restituisce il massimo elemento nella lista
• scrivere un metodo ricorsivo che data una lista di numeri restituisce il numero di elementi negativi contenuti nella lista

Algoritmo di ordinamento per fusione - Merge Sort (codice merge sort)

Analisi della prestazioni del merge sort

Esercizi su dizionari.

Codifica di caratteri: codice ASCII, codici ASCII estesi, codice Unicode, rappresentazione UTF-8

Lettura e scrittura di file di testo.

Funzioni open e print con parametro file = .

Metodi write, close. Uso di metodi di str su righe di testo: strip, split, join.

Ciclo for su file in lettura

• Funzione che mostra la scrittura di un file di testo interiSuFile.py
• Lettura di un file di testo leggiFile.py. Assume che esista un file pippo.txt contente un intero per riga nella stessa cartella.
• Funzione che, dati due nomi di file di testo, copia il contenuto del primo file nel secondo file
• Funzione che, dato il nome di un file di testo contenente un numero float su ciascuna riga, restituisce il numero di valori maggiori di 10
• Funzione che, dato un intero n e il nome di un file, genera un file di testo contenente n valori random nell'intervallo [0,1)
• Funzione che, dati tre nomi di file di testo, legge le righe del primo file e le copia negli altri due file, separando le righe più lunghe di 10 caratteri (nel secondo file) da quelle più corte (nel terzo file)

Uso dell'istruzione with

Istruzione try ... except ...

Metodi read() e readline() ...

Esercizi su file di testo.

Precisazioni sulla notazione asintotica per esprimere la complessità computazionale

Algoritmo per il Massimo Comune Divisore di Euclide:

• versione ricorsiva MCDEuclideRicorsivo.py
• versione iterativa MCDEuclideIterativo.py

Algoritmo di bisezione per calcolare uno zero di una funzione continua ricercaZero.py

List comprehension per costruire dizionari

Esercizi di programmazione

• Prodotto di matrici
• Matrice trasposta
• Calcolo frequenze cumulate
• Calcolo somma di elementi in liste di liste di liste ....
  P.es.: [12, [4, 3], [1], 45, [[2, 4], 1]]

Esercizi su stringhe e matrici.

Esercitazione 11a

Esercitazione 11b

Codifica di numeri interi:

• generalità sulla notazione posizionale per numeri naturali, interpretazione di numeri espressi in base b
• conversione da base b a base 10 e da base 10 a base 2
• codifica esadecimale, conversione dalla base 2 alla base 16
• cenni sulla rappresentazione in complemento a 2

Esempio di calcolo delle medie mobili di ordine k di una sequenza di lunghezza n in tempo O(n) invece di O(nk).

Uso della libreria matplotlib per la visualizzazione.
Per l'installazione utilizzare dal prompt dei comandi (Terminale in Mac OS X o Linux) il comando pip install matplotlib, oppure, in Thonny, andare sul menu' Tools -> Manage packages

Codice disponibile in medieMobiliGrafico.py

Calcolo dei numeri primi con il crivello di Eratostene:

• Crivello di Eratostene https://it.wikipedia.org/wiki/Crivello_di_Eratostene
• implementazione in Python eratostene.py

Simulazione prova d'esame: scaricare e decomprimere il materiale d'esame, che contiene anche i file di test pubblici

Sono disponibili i risultati della prova

Discussione degli esercizi della simulazione d'esame.

Uso dei metodi .split() e .splitlines() nella lettura di file di testo.

Esercizi.

Esercizi su file e dizionari