Ribadiremo il programma del corso e le modalità di esame. Vedremo anche insieme un esempio di prova di teoria.

Materiale didattico:

Un esempio di prova di teoria (scarica qui).

Conclusione del corso: (schermo|stampa)

Sondaggio di fine corso: https://bit.ly/INFO2022-END

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)

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

Affrontiamo il discorso della codifica di dati che non rappresentano numeri, in particolare i testi e le codifiche ASCII, ASCII estesi e UTF-8.

Materiale didattico

Codifica dei dati: (schermo|stampa)

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

Non avremo tempo per una prova di due ore. Quindi vi prego di arrivare in laboratorio il prima possibile. Cerchiamo di essere in Aula 15 per le 8.00 (compatibilmente con l'apertura del laboratorio, ovviamente).

Saper usare i computer del laboratorio è un pre-requisito per partecipare alla simulazione. Mi raccomando di rivedere il seguente video.

Tutorial: esame di programmazione

Facciamo una simulazione della prova di programmazione. In particolare

• distribuzione automatica delle prove
• consegna automatica
• correzione semi-automatica

Questa sarà anche l'occasione per osservare la sostanziale differenza tra i test pubblici e quelli segreti. I test pubblici non verificano affatto la correttezza dei vostri programmi. Verificano solo il fatto che il vostro esercizio può essere sottoposto a correzione automatica.

Esito della simulazione: di seguito potete trovare la tabella dei punteggi ottenuti nella simulazione. Questo è il punteggio calcolato automaticamente. In rari casi il voto della prova effettiva può essere fino a 2 o 3 punti in più, quando il docente lo trovasse appropriato. Per ogni esercizio trovate il numero di test pubblici e segreti non passati. M (missing) indica che la soluzione non è stata trovata nella consegna, B (broken) che la soluzione non poteva essere testata (forse a causa di errori di sintassi nel file).

Nota: le matricole sono anonimizzate. Potete riconoscervi osservando le ultime tre cifre della matricola che sono uniche tra tutti gli studenti che hanno consegnato.

Potete scaricare la prova, con i test pubblici e segreti, qui.

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.

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)

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 1, 5 e 6: video

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 Pensare in Python.

Vediamo poi 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.

Fate gareggiare gli algoritmi di ordinamento

Materiale didattico: capitolo 10 degli Appunti.

Codice della lezione: alg_quick.py

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

Esercizi 1, 4 e 5: video

Completiamo la dimostrazione tutti gli algoritmi di ordinamento per confronti hanno complessità \(\Omega(n \log n)\).

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.

• Confronto tra vari ordinamenti

Materiale didattico: capitoli 6 e 9 degli Appunti.

Codice della lezione: alg_merge.py

Lavoro assegnato: leggere il Capitolo 10 degli Appunti.

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

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

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 5 e 6 degli Appunti.

Codice della lezione: alg_bubble.py

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

Esercizi 6 e 7: video

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

Cominciamo anche a discutere anche la notazione asintotica per esprimere in maniera sintetica la crescita asintotica della complessità. Vediamo le notazioni \(O\), \(\Omega\) e \(\Theta\).

Codice della lezione: alg_insertion.py

Materiale didattico: capitoli 3 e 4 degli Appunti.

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.

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.

Codice della lezione: alg_ricerca.py

Materiale didattico: capitoli 1 e 2 (Appunti).

Lavoro assegnato:

• Capitolo 3 (Appunti).

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.

Codice della lezione:

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

Materiale didattico:

• paragrafi 3.9, 5.8, 5.9 e 5.10 (Pensare in Python);
• Capitolo 7 e 8 (Appunti).

Lavoro assegnato:

• Capitoli 1 e 2 (Appunti)

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

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.

Lavoro assegnato:

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

Parametri opzionali per le funzioni. Esempio 1: 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],0) )

16
22
16

Esempio 2: 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

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 (Pensare in Python);

Esercizi 5 e 6: video

Approfondiamo il ciclo for e vediamo come effettuare delle operazioni con il ciclo for su liste

• calcolo del minimo
• ricerca in una lista
• verifica dell'ordinamento

Materiale didattico

Ciclo for: (schermo|stampa)

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

• cancellazione di elementi dalla lista
• metodo clear, insert
• metodo pop (con argomento e senza) e remove
• indici di lista negativi
• cooperazione tra stringhe e liste: join e split
• esercizio: leggere una lista di numeri in input
• la tupla: una versione immutabile della lista
• chiarimenti su range
• liste, stringhe, tuple e range sono sequenze
• assegnamenti multipli e unpacking
• esercizio: somma cumulativa
• uso del test if __main__ == '__name__'

Lavoro assegnato: slides sul ciclo for: (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

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
• 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: rileggere il capitolo 10 e fare gli esercizi da 10.2 a 10.5 e il 10.8.

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

Vediamo altre operazioni sulle stringhe

• conteggio e ricerca di caratteri
• verifica di stringhe palindrome
• slicing per la copia di segmenti di stringhe
• metodi delle stringhe upper, lower, find, count

Lavoro assegnato: leggere il capitolo 10.

Esercitazione da fare in laboratorio: scarica.

Esercizio 2: video

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

Guardatelo prima della lezione

Lavoro assegnato: approfondire il capitolo 8.

Gestione errori: Discutiamo un po' la "segnalazione" di errori. Utilizzando queste segnalazioni possiamo scrivere funzioni che reagiscono ad argomenti scorretti in maniera più corretta.

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

• indicizzazione di stringhe
• operatore in
• confronti di stringhe
• conteggio di caratteri

Materiale didattico

Gestione degli errori: (schermo|stampa)

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 il capitolo 8 del libro di testo.

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.

Avviso: la lezione si svolgerà in Aula 16

Esercitazione da fare in laboratorio: scarica.

Materiale didattico

Esercizio 2: video

Lavoro assegnato: leggere il Capitolo 7.

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 sul valore None e tipo NoneType.

Approfondiamo sull'identazione.

Materiale didattico

Valore None: (schermo|stampa)

Indentazione: (schermo|stampa)

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

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 e argomenti. Visibilità delle variabili, fuori e dentro la funzione.

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

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 capitolo 3 del libro di testo.

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)

Lavoro assegnato

1. Scrivete un programma che, letti 3 numeri in input, li stampi in ordine crescente.
2. 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

Continuiamo gli esempi di scomposizione di problemi complessi in problemi più semplici, svolti in modelli computazionali giocattolo.

• cercare un elemento in una sequenza
• 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:

• leggere i paragrafi da 5.1 a 5.7 (incluso) del libro di testo.
• Esercitazione da fare a casa: scarica. Video dell'esercizio 7: video

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.

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
• cercare un elemento in una sequenza
• disegnare delle figure

Materiale didattico

Esercitazione da fare a casa: scarica.

Esercizio 7: video

Lavoro assegnato

1. Usate l'interprete interattivo python, richiamandolo dal terminale, e usate quello di Thonny.
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.
3. Esercitazione da fare a casa: scarica.

Esercizio 7: video

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 Materiale didattico

Cos'è la programmazione: (schermo|stampa)

Ambienti di lavoro python: (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/)
• installate e configurate la macchina virtuale