Che cosa si intende per pila (o stack) in un contesto di programmazione, che tipo di logica di programmazione può essere modellata con questo strumento?

Discutiamo la scrittura di funzioni in maniera ricorsiva, ovvero attraverso del codice Python che richiama sé stesso. La ricorsione porta a scrivere programmi molto eleganti ma se usata senza attenzione pone dei problemi:

• uso eccessivo dello stack;
• ripetizione di calcoli già effettuati con esplosione del tempo di esecuzione.

In questi casi è conveniente riscrivere le funzioni in versione iterativa. Questo è particolarmente vero per funzioni che calcolano

• fattoriale;
• numeri di Fibonacci.

Codice della lezione:

• alg_esempiopila.py
• alg_fattoriale.py
• alg_fib.py

Materiale didattico:

• paragrafi 3.9, 5.8, 5.9 e 5.10, 6.5, 6.6, 6.7 (Pensare in Python);
• Capitolo 7 (Appunti su algoritmi e complessità).

Lavoro assegnato:

• Capitoli 1, 2, 8 (Appunti)

Esercitazione da fare in laboratorio: scarica.

Man mano che lavorate sui vostri esercizi potete testare le vostre soluzioni eseguendo i file di test corrispondenti.

Lavoro assegnato:

• paragrafi 3.9, 5.8, 5.9 e 5.10, 6.5, 6.6, 6.7 (Pensare in Python);
• Capitoli 7 e 8 (Appunti su algoritmi e complessità).

Introduciamo lo studio sistematico degli algoritmi.

Accenniamo al problema della modellizzazione, della scelta del modello che usiamo per trasformare un problema reale in un problema informatico che può essere affrontato con dei programmi.

Definiamo la nozione di algoritmo come la descrizione di una procedura di calcolo che:

• termina sempre;
• dato un input produce sempre uno specifico output;
• descrizione finita di dimensione limitata;
• costituito da passi elementari.

Nelle precedenti lezioni abbiamo già visto due algoritmi di ricerca:

• ricerca sequenziale
• ricerca binaria

Oggi vediamo un algoritmo di ordinamento, l'Insertion sort e introduciamo la notazione asintotica per indicarne le prestazioni.

Vediamo il nostro primo algoritmo di ordinamento, l'Insertion sort, e ne discutiamo caratteristiche e complessità computazionale.

Codice della lezione: alg_insertion.py

Materiale didattico: capitoli 1, 3, 4 (Appunti)

Lavoro assegnato:

• paragrafi 3.9, 5.8, 5.9 e 5.10, 6.5, 6.6, 6.7 (Pensare in Python);
• Capitoli 7 e 8 (Appunti su algoritmi e complessità).

Vediamo come accedere/scrivere/leggere/modificare file di testo con Python.

Materiale didattico: i paragrafi 14.1-14.5 del libro di testo.

Gestione dei file: (schermo|stampa)

Seguono dei file di testo di esempio dal progetto Progetto Gutemberg, in inglese codificati UTF-8.

Esercitazione da fare in laboratorio: scarica.

Man mano che lavorate sui vostri esercizi potete testare le vostre soluzioni eseguendo i file di test corrispondenti.

Lavoro assegnato: Leggere i paragrafi 14.1-14.5 del libro Pensare in Python.

Presentiamo e descriviamo l'algoritmo di ricerca binaria.

Vediamo come si generano e si gestiscono segnali di errore all'interno di un programme.

Materiale didattico

Sollevare errori: (schermo|stampa)

Gestire errori : (schermo|stampa)

Materiale didattico: sezione 2.2 e 2.3 degli Appunti

Lavoro assegnato: Leggere i paragrafi 14.1-14.5 del libro Pensare in Python.

Vediamo un tipo di dato particolarmente efficiente per la gestione di ricerche: il dizionario. Ne vediamo le caratteristiche principali e come usarli con un esempio.

Materiale didattico: i paragrafi 11.1-11.3 del libro di testo.

Esercizio: frequenze di parole

Dizionari: (schermo|stampa)

Esercitazione da fare in laboratorio: scarica.

Man mano che lavorate sui vostri esercizi potete testare le vostre soluzioni eseguendo i file di test corrispondenti.

Esercizi 3 e 4: video

Per l'ultimo esercizio si devono utilizzare i parametri opzionali per le funzioni. Esempio: somma di una lista con valore iniziale.

def somma(seq,init=0):
    acc=init
    for x in seq:
        acc += x
    return acc

print( somma([7,5,4]) )
print( somma([7,5,4],6) )
print( somma([7,5,4],12) )
print( somma([7,5,4],0) )

16
22
28
16

Durante la lezione di laboratorio dedicheremo del tempo alla compilazione OPIS. Lo potete fare anche dal cellulare. Qui ci sono le istruzioni e il codice OPIS di questo corso è 3DD0X6YY.

Rappresentazione Python di matrici come liste di liste. Ad esempio una matrice

viene rappresentata in Python come la lista

[[1,2,3], [4,5,6], [7,8,9], [10,11,12]]  

Negli esercizi di questo corso riguardanti le matrici, una matrice di \(R\) righe e \(C\) colonne sarà tipicamente rappresentata come una lista contenente \(R\) liste, ognuna contenente a sua volta \(C\) elementi. Tipicamente con \(R \geq 1\) e \(C \geq 1\).

Esercizio: scrivete una funzione che restituisca True se l'argomento è una matrice secondo le condizioni spiegate nel paragrafo precedente. E che restituisca False altrimenti.

Nel corso della lezione abbiamo visto altri esempi

• creazione di una matrice con valori uguali;
• riempimento di una matrice con valori casuali in \([0,1)\)
• stampa di matrice
• creazione della matrice identità
• somma dei valori in una matrice
• calcolo della matrice trasposta
• posizione di una riga che ha somma massima

Materiale didattico:

slides su matrici: (schermo|stampa)

Lavoro assegnato: i paragrafi 11.1-11.3 del libro di testo.

Altre informazioni su liste, sequenze, cicli:

• break, continue
• conversione tra sequenze
• list comprehension
• funzioni sum, min, max
• cooperazione tra stringhe e liste: join e split
• liste di liste
• rappresentazioni di matrici

Continuiamo ad esercitarci con cicli e sequenze.

Esercitazione da fare in laboratorio: scarica.

Esercizi 3 e 4: video

Man mano che lavorate sui vostri esercizi potete testare le vostre soluzioni eseguendo i file di test corrispondenti.

Continuiamo con le liste, e allarghiamo il discorso a quelle che in Python vengono definite "sequenze"

• esercizio: leggere una lista di numeri in input
• esercizio: somma cumulativa
• metodo clear, insert
• metodo pop (con argomento e senza) e remove
• cooperazione tra stringhe e liste: join e split
• la tupla: una versione immutabile della lista
• chiarimenti su range
• liste, stringhe, tuple e range sono sequenze
• esempio: calcolo del minimo
• esempio: ricerca in una lista
• esempio: verifica che una lista sia ordinata

Lavoro assegnato: slides sul ciclo for: (schermo|stampa)

Introduciamo un utilissimo modo di strutturare dati in modo sequenziale, ovvero le liste. Le liste sono uno dei tipi di dati più utilizzati in python.

• definizione di liste
• indicizzazione e slicing, funzione len
• indici di lista negativi
• mutabilità (argomento delicato e importante)
• variabili come riferimenti a memoria
• copiare una lista
• differenza tra copia e assegnamento tra liste
• ciclo su lista, per indici e per valori
• esercizio: somma di numeri
• operazioni di concatenazione + e ripetizione *
• operatore in
• differenza tra in per liste e stringhe
• funzione sorted e metodo sort
• metodi append, extend, index, count
• differenza tra append e extend
• operatore += su liste, e differenze con x=x+a

Lavoro assegnato: slides sul ciclo for: (schermo|stampa)

Lavoro assegnato: rileggere il capitolo 10 e fare gli esercizi da 10.2 a 10.5 e il 10.8.

Esercitazione da fare in laboratorio: scarica.

Esercizio 3: video

È stato pubblicato il video tutorial per i file di test: esercitazione e test: link

Guardatelo prima della lezione

Man mano che lavorate sui vostri esercizi potete testare le vostre soluzioni eseguendo i file di test corrispondenti.

Lavoro assegnato: leggere il capitolo 10.

Introduciamo il ciclo for su caratteri di una stringa.

X = 'stringa di prova'

# Ciclo while
i = 0
while i < len(X):
    print(X[i], end='-')
    i += 1

print('')

# Ciclo For su caratteri
for c in X:
    print(c, end='-')

s-t-r-i-n-g-a- -d-i- -p-r-o-v-a-
s-t-r-i-n-g-a- -d-i- -p-r-o-v-a-

Vediamo altre operazioni sulle stringhe

• operatore in
• confronti di stringhe
• conteggio e ricerca di caratteri
• metodi delle stringhe upper, lower, find, count, trim

Moduli in preparazione dell'esercitazione vediamo come scrivere i file python in modo che siano adatti ad essere importati, usando la clausola

if __name__ == "__main__":
    <codice>

Materiale didattico

Uso dei moduli: (schermo|stampa)

Lavoro assegnato: guardate TUTTO il video di istruzioni sui test automatici.

Lavoro assegnato: realizzare una versione artigianale dell'operatore in. Ovvero una funzione che date due stringhe testo e chiave, restituisca True se e solo se chiave è un segmento di testo. Naturalmente la vostra versione non deve utilizzare in.

Bisezione: vediamo due modi di scrivere un programma che esegue la ricerca di uno zero in una funzione continua.

Stringhe: Vediamo come le stringhe possano essere considerate delle sequenze di caratteri. Vediamo

• indicizzazione di stringhe
• slicing per la copia di segmenti di stringhe

Algoritmo su stringhe:

• stringa palindroma

Lavoro assegnato: guardate TUTTO il video di istruzioni sui test automatici.

Esercitazione da fare in laboratorio: scarica.

Esercizi 2, 3 e 4: video

Lavoro assegnato:

• leggere la sezione 2.1 degli Appunti
• leggere il capitolo 8 del libro di testo
• leggere l'appendice A del libro di testo

Durante la lezione di laboratorio dedicheremo del tempo alla compilazione OPIS. Lo potete fare anche dal cellulare. Qui ci sono le istruzioni e il codice OPIS di questo corso è 3DD0X6YY.

Vediamo altri esempi di come usare il ciclo while, ed esempi di cicli annidati.

Materiale didattico

Ciclo while: (schermo|stampa)

Lavoro assegnato: leggere l'appendice A del libro di testo.

Vediamo come ripetere l'esecuzione di blocchi di codice con il costrutto while. Vediamo degli esempi di come usare il ciclo while.

Materiale didattico

Ciclo while: (schermo|stampa)

Lavoro assegnato: approfondire il Capitolo 7.

Esercizio 7.1 del libro.

Esercitazione da fare in laboratorio: scarica.

Esercizio 1: video

Lavoro assegnato: leggere il Capitolo 7.

Durante la lezione di laboratorio dedicheremo del tempo alla compilazione OPIS. Lo potete fare anche dal cellulare. Qui ci sono le istruzioni e il codice OPIS di questo corso è 3DD0X6YY.

Il docente non sarà presente, ma il laboratorio rimarrà aperto per gli studenti che vogliono esercitarsi. Ci saranno i tutor, e il laboratorio verrà sorvegliato dal Prof. Franciosa.

Esercitazione: scarica.

Lavoro assegnato:

• ripassate il capitolo 3 e le sezioni da 6.1 a 6.4
• rivedete le sezioni Debug, Glossario, Esercizi dei capitoli 1, 2, e 3 del libro di testo.

Funzioni che restituiscono un valore usando return.

Vediamo anche come inserire una stringa di documentazione nella funzione. In questo contesto vediamo le stringhe multilinea (ovvero quelle aperte e chiuse da tre apici o virgolette).

Insieme studiamo il programma:

def hello(nome,età):
    """Produce un saluto personalizzato

    Questa funzione produce un saluto di presentazione
    che include le informazioni di `nome` ed `età`.
    """
    coda = " anni."
    if età == 1:
        coda = " anno."
    return "Ciao, sono "+nome+". Ho "+str(età)+coda

def stampa_incorniciato(testo):
    lunghezza = len(testo) 
    cornice = '*' * (lunghezza + 4) 
    print(cornice)
    print("* "+testo+' *')
    print(cornice)

stampa_incorniciato(hello('Marcello',23))
stampa_incorniciato("Testo arbitrario.")
stampa_incorniciato(hello('Giulia',1))

************************************
* Ciao, sono Marcello. Ho 23 anni. *
************************************
*********************
* Testo arbitrario. *
*********************
*********************************
* Ciao, sono Giulia. Ho 1 anno. *
*********************************

Approfondiamo sull'identazione e sulle tuple. A proposito di tuple cosa succede in questi quattro assegnamenti?

t = (-121,"ciao","posizione 2",293)

x0 = t
x0,x1 =  t
x0,x1,x2 = t
x0,x1,x2,x3 = t

In python è possibile che una funzione restituisca più valori insieme (ad esempio restituisca una coppia o una tripla di valori). Questo si può fare restituendo una tupla. Ad esempio:

def divresto(N,d):
    quoziente = N // d
    resto     = N % d
    return quoziente, resto

x,y = divresto(12,7)
print(x,y)

x,y = divresto(21,5)
print(x,y)

1 5
4 1

Qui la funzione restituisce due numeri (usando la sintassi return expr1,expr2). L'espressione divresto(21,5) per esempio restituisce la coppia di numeri 4 e 1. Il numero 4 viene assegnato ad x, mentre il numero 1 viene assegnato a y.

Materiale didattico

Indentazione: (schermo|stampa)

Lavoro assegnato: rivedere gli esercizi della scorsa esercitazione e provare a completarla scrivendo funzioni per ogni esercizio. Le funzioni dovrebbero

• ricevere i dati attraverso i parametri
• restituire il risultato attraverso return

La lettura di parametri da tastiera e la stampa a video dei risultati non deve essere all'interno della funzione che risolve l'esercizio.

Rivedere le sezioni 3.11 e 6.2

Rivedere le sezioni Debug, Glossario, Esercizi dei capitoli 1, 2, e 3 del libro di testo.

Vediamo come scrivere nuove funzioni. Due ragioni per cui le funzioni sono utili sono la possiblilità di riutilizzare codice, e suddividere la complessità di un problema.

Parliamo di passaggio di parametri, e differenza tra parametri e argomenti. Visibilità delle variabili, fuori e dentro la funzione (anche usando le funzioni di debug di Thonny). Le funzioni di debug permettono di eseguire il programma passo passo:

• Step over esegue interamente le istruzioni
• Step into (faster) entra dentro le istruzioni
• Step into (nicer) entra dentro le istruzioni e le espressioni

Potete provare questi comandi su questo programma

# Esempio: debug funzione
def stampa_minmax(x,y):
    if x < y:
        a = x
        b = y
    else:
        a = y
        b = x
    print("min:",a,"max:",b)

stampa_minmax(10,12+30)
stampa_minmax(10,-3)

o su questo programma

# Esempio: debug if/else
num = 121
if num % 2 == 0:
    print("Pari")
else:
    print("Dispari")

num = 74    
if num % 2 == 0:
    print("Pari")
else:
    print("Dispari")

Lavoro assegnato: scrivere i seguenti programmi

• Una funzione scontato(prezzo,sconto), che verifichi che lo sconto sia un numero valido (ovvero se sia compreso tra 0 e 100) e che il prezzo sia un numero non negativo. Se queste condizioni sono verificate, il programma stampi il prezzo scontato. In caso di argomenti errati, il programma non deve stampare nulla.
• scrivere una funzione eqsecondogrado(A,B,C), che calcoli e stampi le soluzioni dell'equazione di secondo grado \(Ax^2 + Bx + C =0\).
• scrivere una funzione ordina(A,B,C) che stampi in ordine dal più piccolo al più grande i valori (non necessariamente numerici) passati come argomenti. Non vi preoccupate di gestire gli errori dovuti al passaggio di argomenti che non sono confrontabili tra loro.
• scrivere una funzione massimodicinque(A,B,C,D,E) che stampi il più grande tra i cinque valori passati come argomenti.

Lavoro assegnato: leggere i paragrafi da 6.1 a 6.4 inclusi.

Esercitazione da fare in laboratorio: scarica.

Esercizi 3 e 6: video

Lavoro assegnato: leggere il resto del capitolo 3 del libro di testo.

Attenzione: La lezione si svolgerà straordinariamente in Aula 2 di via del Castro Laurenziano 7A.

Terminiamo la discussione su operatori ed espressioni alla fine delle slide della lezione scorsa.

Introduciamo anche il concetto di tupla di valori, cioè un espressione il cui valore è una sequenza di valori elementari. Ad esempio:

• le coordinate di un punto in un piano cartesiano (12.5, 5.4)
• una quintupla come ("Leopardi","Giacomo",29,6,1837)

Spieghiamo cos'è una funzione. A che servono, come si usano, come si inseriscono all'interno di un'espressione? Esistono funzione chi restituiscono un valore, e funzioni che non ne restituiscono nessuno (convenzionalmente restituiscono un valore speciale None).

Vediamo delle funzioni: ci sono quelle già usate a lezione, come int, print, len, input, e altre incluse nel modulo math. Come si importano funzioni da moduli?

Se avanza tempo, iniziamo a vedere come scrivere una nuova funzione con il comando def.

Materiale didattico

Il valore None: (schermo|stampa)

Le prime 9 slides di Uso/Scrittura di moduli: (schermo|stampa)

Ricordiamo velocemente le funzioni print, input, le conversioni tra tipi, e la differenza tra errori TypeError e ValueError.

Vediamo come fare in modo che il programma faccia delle scelte. In primo luogo introduciamo il tipo booleano che rappresenta la scelta vero/falso. Vediamo poi come costruire espressioni booleane usando operatori logici e di confronto.

L'uso principale di queste espressioni logiche è quello di definire condizioni in base alle quali eseguire o meno pezzi di codice. Introduciamo le clausole if, else, elif per l'esecuzione codizionale di blocchi di istruzioni.

Materiale didattico

Il vero e il falso: (schermo|stampa)

Lavoro assegnato

1. Leggete i paragrafi da 3.1 a 3.3 (incluso) del libro di testo.
2. Scrivete un programma che, letti 3 numeri in input, li stampi in ordine crescente utilizzando catene di if/then/else
3. Valutare a mano, e poi verificare in Python, il valore della seguente espressione python.

not -5 // 2**4 < -1 and 3**2**(5 + -3) >= 2 * 4

Esercitazione da fare in laboratorio: scarica.

Esercizio 7: video

Lavoro assegnato:

• leggere i paragrafi da 5.1 a 5.7 (incluso) del libro di testo.

Tramite esercizi esploriamo cosa voglia dire risolvere un problema di programmazione. Come sono formulati questi problemi? Vediamo alcuni esempi di problemi tipici che possono essere risolti tramite piccoli programmi. Non scriviamo ancora programmi che li risolvino, ma cerchiamo di ragionare su come possa essere impostata una soluzione, avendo a disposizione una serie di operazioni atomiche semplici. Ad esempio:

• calcolare la media di una sequenza di numeri
• ordinare tre elementi
• disegnare delle figure

Vediamo delle funzioni per l'input e l'output. In particolare

• print per stampare in output in valure di un'espressione
• input per leggere una stringa in input

In questo contesto vediamo come convertire dati da un tipo all'altro, quando possibile. Vediamo l'errore TypeError e ValueError.

Lavoro assegnato

1. Usate l'interprete interattivo python nella finestra in basso di Thonny, e poi quello da terminale.
2. Scrivete dei file python con delle istruzioni, salvateli ed eseguiteli sia in Thonny (cliccando sull'icona "Play" oppure con il tasto F5) che usando il comando python3 dal terminale.

Discutiamo brevemente la struttura di un calcolatore e alcune delle persone coinvolte nel suo sviluppo. Spieghiamo la differenza tra linguaggi naturali e artificiali, linguaggi di alto e basso livello, linguaggi compilati e interpretati.

Nella seconda parte della lezione cominciamo a vedere delle operazioni interattive con python. In questo contesto discutiamo il concetto di valore e tipo del dato, e vediamo come costruire espressioni utilizzando operazioni (aritmetiche e non) tra dati. Descriviamo il funzionamento di variabili e assegnamenti, e come funziona a grandi linee il modello di associazione nome/valore in python.

Materiale didattico

Cos'è la programmazione: (schermo|stampa)

Lavoro assegnato: leggere il capitolo 2 del libro di testo.

Introduciamo il corso, fornendo le informazioni logistiche di base. Poi vediamo come effettuare i primi passi nell'ambiente Linux del laboratorio: come trovare i programmi necessari allo svolgimento delle esercitazioni e come utilizzare il terminale.

Materiale didattico

Introduzione: (schermo|stampa)

Tutorial del laboratorio: (schermo|stampa)

Ambienti di lavoro python: (schermo|stampa)

Lavoro assegnato:

• leggere il capitolo 1 del libro di testo.
• installare Thonny sul vostro PC (https://thonny.org/)