Parte della lezione verrà dedicata ad affrontare alcune domande di esempio simili a quelle delle prove di esame di teoria. Al termine ribadiremo il programma del corso e le modalità di esame.

Materiale didattico

Esempi di domande di esame: (scarica)

Conclusione del corso: (schermo|stampa)

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

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

Gestione dei file: (schermo|stampa)

File di testo di esempio dal progetto Progetto Gutemberg, in inglese codificati UTF-8.

Questa lezione di laboratorio è dedicata ad una simulazione della prova di programmazione che faremo all'esame.

Durante la prova di programmazione (e la simulazione) non sarà consentito usare nessun libro di testo, e neppure dispense o cellulari. Non sarà neppure possibile usare internet. Potrete tenere con voi soltanto un documento e beni di ristoro (acqua, snack) in quantità personale e ragionevole.

Vi verrà fornita una copia digitale del foglio riassuntivo delle sintassi python: Memento Python.

Il testo della prova è il seguente: scarica.

Risultati della prova. Per ogni esercizio avete l'esito del test pubblico e privato. Se l'esito è T è il programma non è terminato entro 1 secondo, se è X non è stato possibile eseguire la soluzione, altrimenti viene dato il numero di test falliti.

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

Successivamente introduciamo il problema della codifica dei dati, che avrà applicazione anche quando discuteremo l'uso dei file.

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

Dizionari: (schermo|stampa)

Codifica dei dati: (schermo|stampa)

Lavoro assegnato: leggere i paragrafi 14.1-14.4 del libro di testo.

Vediamo le equazioni di ricorrenza, un metodo per esprimere la complessità computazionale di funzioni ricorsive. Queste equazioni vanno risolte per quantificare effettivamente la complessità della funzione. Per farlo vediamo tre metodi:

• metodo di sostituzione;
• metodo iterativo (anche tramite alberi di ricorsione);
• Master Theorem.

Materiale didattico: capitolo 11 degli Appunti.

Lavoro assegnato: leggere i paragrafi 11.1-11.3 e 14.1-14.4 del libro di testo.

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 il Capitolo 11 degli Appunti.

Vediamo l'algoritmo di ordinamento Quicksort. Questo è un algoritmo randomizzato, nel senso che il suo comportamento dipende da scelte casuali effettuate durante l'esecuzione. L'algoritmo può essere presentato naturalmente in modo ricorsivo, poiché basato su una strategia divide et impera simile a quella del Mergesort. Potete vedere dei grafici ottenuti misurando sperimentalmente i tempi di esecuzione su input casuali.

A lezione, durante la pausa, viene proposto di compilare il questionario OPIS per il corso. Attenzione il codice mostrato alla lezione scorsa era errato. Qui c'è il codice aggiornato (che ho corretto anche nel diario della lezione scorsa).

• Istruzioni di compilazione: scarica da qui.
• Codice del corso: AI5BC2PJ

Vediamo un algoritmo di ordinamento per confronti che impiega \(\Theta(n \log n)\) operazioni per ordinare una lista di \(n\) elementi. Questo algoritmo quindi è asintoticamente ottimo, almeno per quanto riguarda gli algoritmi per confronto.

A lezione, durante la pausa, viene proposto di compilare il questionario OPIS per il corso.

• Istruzioni di compilazione: scarica da qui.
• Codice del corso: AI5BC2PJ (attenzione in classe ho mostrato il codice errato)

Materiale didattico: capitolo 9 degli Appunti.

Lavoro assegnato: leggere il Capitolo 10 degli 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: leggere il Capitolo 9 degli Appunti.

Gli algoritmi di ordinamento visti fino ad ora sono tutti ordinamenti per confronti. Vediamo che tutti gli algoritmi di questa famiglia hanno complessità \(\Omega(n \log n)\).

Dopo ritorniamo sullo stack, in preparazione allo studio dell'algoritmo Mergesort.

A questo punto può essere utile, divertente e interessante vedere un confronto tra le prestazioni dei vari algoritmi di ordinamento, e la loro esecuzione.

• Confronto tra vari ordinamenti

Materiale didattico: capitolo 6 e 7 degli Appunti.

Lavoro assegnato: leggere il capitolo 9 degli Appunti.

Concludiamo con le notazioni asintotiche. Alla lezione 17 abbiamo visto la notazione \(O\), e in questa lezione vediamo le notazioni \(\Omega\) e \(\Theta\).

Vediamo un altro algoritmo di ordinamento di complessità quadratica, il Bubblesort.

Materiale didattico: capitolo 4 e 5 degli Appunti.

Lavoro assegnato: leggere il capitolo 6 degli 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: leggere Capitoli 4 e 5.

Vediamo il nostro primo algoritmo di ordinamento, l'Insertion sort, e ne discutiamo caratteristiche e complessità computazionale. Se avanza tempo cominciamo a discutere anche la notazione asintotica per esprimere in maniera sintetica la crescita asintotica della complessità.

Materiale didattico: capitolo 3 e 4 degli Appunti.

Lavoro assegnato: leggere il capitolo 4 degli Appunti.

Introduciamo lo studio sistematico degli algoritmi, e discutiamo di algoritmi di ricerca. Utilizzeremo come esempio la ricerca di uno zero (approssimato) in una funzione continua, e poi passeremo agli algoritmi di ricerca su sequenze:

• ricerca sequenziale su sequenze generiche;
• ricerca binaria su sequenze ordinate.

Materiale didattico: capitoli 1 e 2 degli Appunti.

Lavoro assegnato: leggere il capitolo 3 degli 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: leggere Capitoli 1 e 2.

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.

Invece la versione ricorsiva per calcolare il Massimo comun divisore è più che sufficiente.

Materiale didattico: Capitolo 7 degli Appunti.

Altri esercizi su liste e sequenze

• esercizio: calcolo di massimo e minimo;
• esercizio: verificare che una sequenza sia ordinata in modo crescente;
• funzioni sum, min, max.

Poi vedremo l'uso di parametri opzionali per le funzioni

• verifica che un segmento di una sequenza sia ordinata in modo crescente.

def ordinata(seq,start=0,stop=None):
    start=max(0,start)
    if stop is None or stop > len(seq):
        stop=len(seq)
    for i in range(start,stop-1):
        if seq[i]>seq[i+1]:
            return False
    return True

print( ordinata([7,5,4,1,4,6,2]) )
print( ordinata([7,5,4,1,4,6,2],6) )
print( ordinata([7,5,4,1,4,6,2],3,6) )

False
True
True

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]]  

• creazione di una matrice con valori uguali;
• calcolo della matrice trasposta.

import random
def matrixcreate(r,c,fillvalue=0):
    M=[]
    for i in range(r):
        M.append( [fillvalue]*c)
    return M

def matrixsize(A):
    return len(A),len(A[0])

def matrixtranspose(A):
    r,c = matrixsize(A)
    T   = matrixcreate(c,r)
    for i in range(c):
        for j in range(r):
            T[i][j] = A[j][i]
    return T

def matrixrandomfill(A):
    r,c = matrixsize(A)
    for i in range(r):
        for j in range(c):
            A[i][j] = random.randint(0,100)

A = matrixcreate(4,2)
matrixrandomfill(A)
B = matrixtranspose(A)
print(A)
print(B)

[[16, 92], [77, 52], [76, 34], [51, 42]]
[[16, 77, 76, 51], [92, 52, 34, 42]]

Lavoro assegnato: Leggere i paragrafi 3.9, 5.8, 5.9 e 5.10.

Esercitazione da fare in laboratorio: scarica.

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''

• cancellazione di elementi dalla lista
• metodo clear, index, insert
• metodo pop (con argomento e senza) e remove
• cooperazione tra stringhe e liste: join e split
• differenza tra stringhe e liste: count
• la tupla: una versione immutabile della lista
• chiarimenti su range
• liste, stringhe, tuple e range sono sequenze
• help su metodi
• esercizio: somma di numeri
• esercizio: somma cumulativa

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

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
• mutabilità (argomento delicato e importante)
• variabili come riferimenti a memoria
• ciclo su lista, per indici e per valori
• operazioni di concatenazione + e ripetizione *
• operatore in
• differenza tra in per liste e stringhe
• metodi append, extend, sort, count
• funzioni len e sorted
• differenza tra append e extend
• funzioni che modificano/non modificano la lista
• copiare una lista
• differenza tra copia e assegnamento tra liste

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.

File di test: test_lab05.py

Per la prima volta l'esercitazione sarà munita di un file di test, simile a quello che userete per l'esame. Vedremo come usare questi file di test per aiutarsi a scrivere dei programmi corretti.

In breve, dovete scrivere le funzioni che risolvono gli esercizi in un file lab05.py, e queste funzioni che avete scritto verranno usate dal programma test_lab05.py nei test. Più precisamente dovrete:

• scaricare il file test_lab05.py
• salvare le vostre funzioni in un file lab05.py
• metterli nella stessa cartella

Man mano che lavorate sui vostri esercizi potete testare le vostre soluzioni eseguendo.

$ python3 test_lab05.py

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

Vediamo come le stringhe possano essere considerate delle sequenze, e come si possa lavorare su di essere usando l'indicizzazione e lo slicing. Vediamo anche come utilizzare alcuno ``metodi'' delle stringhe. Poi discutiamo l'uso e la gestione dei moduli python, per scrivere programmi su file multipli.

Abbiamo introdotto il ciclo for su caratteri di una stringa e su sequenze di interi ottenute tramite la funzione range.

X = 'stringa di prova'

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

print('')

# Ciclo For su indici
for t in range(len(X)):
    print(X[t], end='-')

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-
s-t-r-i-n-g-a- -d-i- -p-r-o-v-a-

Materiale didattico

Uso e scrittura di moduli: (schermo|stampa)

Lavoro assegnato: ripetere gli esercizi delle esercitazioni inserendo del codice per la gestione dei parametri sbagliati, usando TypeError e ValueError dove appropriato.

Abbiamo visto come cercare le triple pitagoriche con cicli annidati.

N = 15

a = 1
while a <= N:
    b = a+1
    while b <= N:
        c = b+1
        while c <= N:
            if a**2 + b**2 == c**2:
                print(a,b,c)
            c += 1 
        b += 1
    a += 1

3 4 5
5 12 13
6 8 10
9 12 15

Vediamo degli esempi tramite Thonny, e in particolare come evolve lo stack delle chiamate a funzione. In questo contesto discutiamo

Visibilità delle variabili

# Questa funzione ridefinisce x
def prova():
    x = 6       # x interna, che
                # nasconde eventuali x
                # esterne
    print(x)

x = 10          # x esterna
prova()    
print(x)        # x esterna è immutata

Chiamate di funzioni annidate e frame di esecuzione (paragrafo 3.9 del libro)

def livello_esterno(x):
    print("Entro nel livello esterno col valore ",x)
    livello_medio(21)
    print("Esco dal livello esterno col valore",x)

def livello_medio(y):
    print("Entro nel livello medio col valore ",y)
    livello_interno('aaa')
    print("Esco dal livello medio col valore",y)

def livello_interno(z):
    print("Entro nel livello interno col valore ",z)
    print("Esco dal livello interno col valore",z)


print("Corpo principale del programma")
livello_esterno(1.2)
print("fine")

Vediamo anche come sollevare errori, simili a quelli che solleva Python in certe condizioni.

Materiale didattico

Gestione degli errori: (schermo|stampa)

Lavoro assegnato: leggere il Capitolo 8.

Esercitazione da fare in laboratorio: scarica.

Prima di iniziare l'esercitazione vedremo un pochino come funziona Thonny.

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

Abbiamo visto altri esempi di come usare il ciclo while, ed esempi di cili annidati.

Materiale didattico

Ciclo while: (schermo|stampa)

Lavoro assegnato: Installare e usare Thonny. Provare a scrivere e modificare gli esercizi presenti nelle slide, usando Thonny per il debug.

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

Materiale didattico

Ciclo while: (schermo|stampa)

Lavoro assegnato: ri-leggere il Capitolo 7.

Esercitazione da fare in laboratorio: scarica.

Prima di iniziare l'esercitazione abbiamo discusso di come gestire l'indentazione, e più in particolare di come risolvere il problema delle tabulazioni mischiate a spazi. Nel materiale didattico di questa lezione potrete trovare delle slide a riguardo.

Oltretutto gli esercizi di oggi hanno previsto la spiegazione degli assegnamenti multipli e del ritorno di valori multipli.

Materiale didattico

Indentazione: (schermo|stampa)

Lavoro assegnato: leggere il Capitolo 7.

Vediamo qualche piccola nozione aggiuntiva sulle stringhe:

• caratteri non stampabili
• confronti tra stringhe
• operatore in
• valore None e tipo NoneType

Poi vediamo insieme come fare un esercizio della scorsa esercitazione.

Lavoro assegnato: rivedere gli esercizi della scorsa esercitazione e provare a completarli, inserendo anche delle stringhe di documentazione. Mi raccomando di completare il questionario finale.

Abbiamo visto come scrivere una funzione passo passo, e come perfezionarla e inserirla nel contensto di un programma. Abbiamo anche visto come inserire una stringa di documentazione nella funzione. In questo contesto abbiamo visto le stringhe multilinea (ovvero quelle aperte e chiuse da tre apici o virgolette).

Insieme abbiamo scritto 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. *
*********************************

Lavoro assegnato: rivedere gli esercizi della scorsa esercitazione e provare a completarla. Mi raccomando di completare il questionario finale.

Esercitazione da fare in laboratorio: scarica.

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

Spieghiamo cos'è una funzione e vediamo quelle già usate a lezione più altre incluse nel modulo math. Come si scrive una funzione? Passaggio di parametri, e differenza tra parametri formali e attuali. Visibilità delle variabili, fuori e dentro la funzione. Funzioni che restituiscono dei valori.

Lavoro assegnato: scrivere i seguenti programmi

• Una funzione scontato(prezzo,sconto), che verifichi se lo sconto è un numero valido (ovvero se sia compreso tra 0 e 100) e in caso positivo stampi il prezzo scontato.
• 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.

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 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)

Logica booleana: (schermo|stampa)

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

Esercitazione da fare in laboratorio: scarica.

Lavoro assegnato: leggere i paragrafi da 5.1 a 5.7 inclusi.

Recuperiamo alcune cose che non siamo riusciti a fare alla lezione precedente per problemi logistici. Vediamo l'uso delle funzioni type, print e degli operatori su stringhe.

Vediamo come si definisce e si usa una variable, e poi cominciamo a scrivere programmi minimali su file, per poi eseguirli. Vediamo la differenza nell'output tra sessione interattiva e programma eseguito da file.

Lavoro assegnato: provare a scrivere ed eseguire sequenze di istruzioni salvate su file. O con pythonanywhere.com oppure installando python sul vostro computer.

Discutiamo prevemente 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.

Brevemente vediamo una carrellata di possibilità per lavorare in ambiente python.

Materiale didattico

Cos'è la programmazione: (schermo|stampa)

Ambienti di lavoro python: (schermo|stampa)

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

Abbiamo introdotto il corso, fornendo le informazioni logistiche di base. Poi abbiamo visto 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 al laboratorio: (schermo|stampa)

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