Menzioniamo che gli algoritmi di ordinamento cosiddetti per confronti devono fare circa \(n \log n\) confronti come minimo, per ordinare una sequeza. Vediamo poi l'algoritmo Mergesort che da questo punto di vista è asintoticamente ottimo perché ordina un sequenza di \(n\) elementi usando \(O(n \log n)\) operazioni.

• Confronto tra vari ordinamenti

Materiale didattico: Capitolo 9 degli Appunti.

Codice della lezione: alg_merge.py

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: capitolo 9 degli Appunti.

Completiamo la discussione sulla ricorsione e vediamo l'esempio dell'algoritmo MCD, che calcola il massimo comun divisore.

Codice della lezione: alg_mcd.py

Materiale didattico: capitolo 8 (Appunti).

Lavoro assegnato:

• Capitolo 9 (Appunti).

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:

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

Esercizi 3 e 4: video

Esercizio 6: video

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.

Lavoro assegnato: capitoli 1, 3, 4 (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 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.

Esercizio: frequenze di parole

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

Materiale didattico

Dizionari: (schermo|stampa)

Sollevare errori: (schermo|stampa)

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

Presentiamo e descriviamo l'algoritmo di ricerca binaria. E lo confrontiamo con la ricerca sequenziale.

Torniamo a poi a python e vediamo come si generano i segnali di errore all'interno di un programma.

Codice della lezione: alg_ricerca.py

Materiale didattico: sezione 2.2 e 2.3 degli Appunti

Sollevare errori: (schermo|stampa)

Lavoro assegnato: i paragrafi 11.1-11.3 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.

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

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:

• esempio: ricerca in una lista
• esempio: verifica che una lista sia ordinata
• list comprehension
• funzioni sum, min, max
• liste di liste
• rappresentazioni di matrici

Materiale didattico: slides sul ciclo for: (schermo|stampa)

Esercitazione da fare in laboratorio: scarica.

Attenzione: nel video scrivo la funzione ignorando il problema delle cifre decimali. Integratelo con la funzione round come visto a lezione.

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
• modifiche nel mezzo di una lista
• cooperazione tra stringhe e liste: join e split
• la tupla: una versione immutabile della lista
• indici di lista negativi
• ciclare su un contatore con range
• liste, stringhe, tuple e range sono sequenze
• ciclare sugli indici di una lista
• esempio: calcolo del minimo

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
• conversione tra sequenze
• mutabilità (argomento delicato e importante)
• variabili come riferimenti a memoria
• copiare una lista
• differenza tra copia e assegnamento tra liste
• ciclo su lista
• 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

• operazione di slicing
• operatore in
• confronti di stringhe
• conteggio e ricerca di caratteri
• metodi delle stringhe upper, lower, find, count, strip
• metodi isalpha, isdigit, isalnum, …

Compilazione OPIS Lo potete fare anche dal cellulare. Qui ci sono le istruzioni e il codice OPIS di questo corso è Y9WL6KDL.

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.

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>

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 l'indicizzazione di stringhe.

Algoritmo su stringhe:

• stringa palindroma

Compilazione OPIS Lo potete fare anche dal cellulare. Qui ci sono le istruzioni e il codice OPIS di questo corso è Y9WL6KDL.

Materiale didattico

Uso dei moduli: (schermo|stampa)

Sezione 2.1 degli Appunti

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

Esercitazione da fare in laboratorio: scarica.

Esercizi 2, 3 e 4: video

Compilazione OPIS Lo potete fare anche dal cellulare. Qui ci sono le istruzioni e il codice OPIS di questo corso è Y9WL6KDL.

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

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

Materiale didattico

Ciclo while: (schermo|stampa)

Due loop infiniti: Wave, WaveColor

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.

Mettiamo a punto alcuni dettagli sulle funzioni: funzioni senza return o con return senza espressione.

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

Approfondiamo sulle tuple. A proposito di tuple cosa succede in questi quattro assegnamenti? Questo fenomeno è lo spacchettamento di tuple.

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

x0 = t                     # è quello che volevi?
x0,x1 =  t                 # no
x0,x1,x2 = t               # no  
x0,x1,x2,x3 = t            # si

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, magari poi spacchettandola. 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. Vediamo come restituire None nel caso di divisore uguale a 0. E se restituissimo math.nan.

Se avanza tempo vediamo le funzioni

• random.randint(a,b)
• random.random()
• random.gauss()

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.

Scriviamo le nostre implementazioni di abs, min, max.

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). Restituzioni di valori usando return.

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 minmax(x,y):
    if x < y:
        a = x
        b = y
    else:
        a = y
        b = x
    return (a,b)

print(minmax(10,12+30))
print(minmax(10,-3))

o su questo programma

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 cornice(testo):
    lunghezza = len(testo) 
    cornice = '*' * (lunghezza + 4) 
    return cornice+"\n* "+testo+' *\n'+cornice
    print(cornice)

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

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

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 restituisca il prezzo scontato. In caso di argomenti errati, il programma non deve stampare nulla.
• scrivere una funzione eqsecondogrado(A,B,C), che calcoli e restituisca le soluzioni dell'equazione di secondo grado \(Ax^2 + Bx + C =0\). Restituite None in caso di nessuna soluzione, e restituite due copie della soluzione, in caso di soluzione unica.
• scrivere una funzione ordina(A,B,C) che restituisca 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 restituisca 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.

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

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 il valore 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. Notiamo come tra gli operatori aritmetici ci sia un ordine di precedenza (PEMDAS). 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/)