Ribadiremo il programma del corso e le modalità di esame. Il tempo rimanente della lezione verrà dedicata ad affrontare esercizi.

Materiale didattico

Esempi di prove d'esame: (teoria, programmazione)

Conclusione del corso: (schermo|stampa)

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

Parleremo di sfuggita di alcune funzionalità del linguaggio python che non abbiamo visto durante il resto del corso.

• metodo format delle stringhe
• range con tre parametri
• slicing con tre parametri
• indici di lista negativi
• sintassi della list comprehension
• scrittura di moduli
• uso del test if __main__ == '__name__'
• menzione di matplotlib e pandas

Materiale didattico

Uso e scrittura di moduli: (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.

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.

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.

Il resto della lezione lo passeremo a fare esercizi.

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.

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 11.1-11.3 e 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.

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.

Fate gareggiare gli algoritmi di ordinamento

Materiale didattico: capitolo 10 degli Appunti.

Lavoro assegnato: leggere il Capitolo 11 degli Appunti.

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.

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

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 degli Appunti.

Concludiamo con le notazioni asintotiche. Abbiamo già visto la notazione \(O\), e ora 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.

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.

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 3 e 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.

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.

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

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
• la tupla: una versione immutabile della lista
• chiarimenti su range
• liste, stringhe, tuple e range sono sequenze
• help su metodi
• esercizio: somma cumulativa
• Ricerca Sequenziale

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
• esercizio: somma di numeri
• 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
• operatore += su liste, e differenze con x=x+a
• 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.

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

Esercitazione da fare in laboratorio: scarica.

Materiale didattico

Gestione degli errori: (schermo|stampa)

Lavoro assegnato: leggere il Capitolo 10.

Vediamo altre operazioni sulle stringhe

• slicing per la copia di segmenti di stringhe
• metodi delle stringhe upper, lower, find, count

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-

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

• indicizzazione di stringhe
• conteggio e ricerca di caratteri
• verifica di stringhe palindrome
• operatore in
• confronti di stringhe

Esercitazione da fare in laboratorio: scarica.

Lavoro assegnato: leggere i capitolo 8 del libro di testo.

Abbiamo visto 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.

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: approfondire il Capitolo 7.

Esercitazione da fare in laboratorio: scarica.

Approfondiamo la questione dell'indentazione, in particolare il problema di mischiare spazi e tabulazioni.

Materiale didattico

Indentazione: (schermo|stampa)

Lavoro assegnato: leggere il Capitolo 7.

Funzioni incluse nel modulo math. Funzioni che restituiscono un valore. Istruzione return, valore None e tipo NoneType. Assegnamenti multipli. Funzioni che restituiscono valori multipli.

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

Materiale didattico

Valore None: (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 formali e attuali. Visibilità delle variabili, fuori e dentro la funzione.

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.

Esercitazione da fare in laboratorio: scarica.

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

Continuiamo con la costruzione di espressioni complesse, usando i valori booleani. Esercitiamoci sulla valutazione di espressioni complesse.

Materiale didattico

Logica booleana: (schermo|stampa)

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 (e magari in thonny), il valore della seguente espressione python.

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

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

Esercitazione da fare in laboratorio: scarica.

Lavoro assegnato:

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

Cosa vuol 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

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

Materiale didattico

Ambienti di lavoro python: (schermo|stampa)

Lavoro assegnato

1. Utilizzare l'interprete interattivo python, richiamandolo dal terminale, oppure da IDLE
2. Scrivere dei file python con delle istruzioni, salvarli ed eseguirli in python da terminale.

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.

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)

Lavoro assegnato:

• leggere il capitolo 1 del libro di testo.
• installare python sul vostro PC (video tutorial)