Informatica, terzo canale (cognomi da Pb* a Z*),
anno accademico 2021-2022

• Introduzione al corso
• Concetto di problema e di algoritmo
• Linguaggi ed esecutori, architettura di Von Neumann
• Esempi di algoritmi
• Linguaggi di programmazione
  • dall'algoritmo al programma eseguibile
  • compilazione/interpretazione
  • il caso del linguaggio Python
Errori sintattici, errori semantici

• Esempi di algoritmi in linguaggio naturale: ricerca del massimo, ordinamento.
• Architettura di un calcolatore: CPU, RAM, ROM, unità periferiche
• Esecuzione di programmi, fetch, execute. Time sharing.
• Il Sistema Operativo
• Esempio di sessione con interprete Python

Cenni sulla struttura di un file system gerarchico: dischi logici, files, cartelle

Uso della shell Linux (o Terminale in Mac OS, o Prompt dei comandi in Windows)

Navigazione nel file system: comando ls (o dir in Windows) comando cd. Path assoluti e relativi.

Uso dell'interprete Python 3 in modalità interattiva

Operatori aritmetici, espressioni, variabili, assegnazioni

Esempi di semplici problemi risolubili in modalità interattiva

La funzione type(...)

La registrazione della lezione del 23 Settembre 2021 è disponibile a questo link Zoom Passcode di accesso: Kdk&DV33
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Script vs. modalità interattiva, uso dell'ambiente Thonny, uso del debugger

Funzioni input(...) e print(...)

Espressioni, precedenza tra operatori, valutazione di una espressione: albero sintattico

Istruzione di assegnazione, binding nome - valore

Regole per la definizione di identificatori, parole riservate

Funzioni di conversione

Stringhe, operatori su stringhe

Errori sintattici, errori semantici, eccezioni

Uso di funzioni matematiche con import math

La registrazione della lezione del 27 Settembre 2021 è disponibile a questo link Zoom Passcode di accesso: mbKG6K^S
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Un tutorial per l'installazione di Python3 in ambiente Windows è disponibile su https://www.youtube.com/watch?v=ij1HTDpVTBI (a cura del prof Massimo Lauria)

Verificare, utilizzando l'interprete Python 3, qual è il massimo valore float rappresentabile

Verificare, utilizzando l'interprete Python 3, qual è il massimo valore int rappresentabile

Sperimentare la differenza tra l'operatore / e l'operatore //

Esprimere 8430 secondi in ore, minuti e secondi.

Generalizzare il problema precedente immettendo da tastiera il numero di secondi.

Calcolare quanti secondi sono 3 ore, 5 minuti e 18 secondi

Generalizzare il problema precedente immettendo da tastiera il numero di ore, minuti e secondi.

Trovare la lunghezza dell'ipotenusa di un triangolo rettangolo i cui cateti misurano rispettivamente 18.6 metri e 15 metri

Istruzione if : else: ...

Espressioni boolean, le costanti True e False

Indentazione del codice

Istruzione if : elif: elif: else:

Istruzione if : senza else:

La registrazione della lezione del 28 Settembre 2021 è disponibile a questo link Zoom Passcode di accesso: ?ldr48Sn
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

1. Dati tre valori float distinti a piacere, che rappresentano i coefficienti di una equazione di secondo grado in una variabile, trovare le soluzioni (se reali) oppure stampare un messaggio (se complesse). Il programma deve funzionare correttamente per qualsiasi terna di interi.
2. Ordina tre numeri. Dati tre numeri interi distinti stamparli in ordine crescente. Si può decidere di eseguire i confronti e stampare i tre valori nell'ordine richiesto oppure di usare altre tre variabili alle quali assegnare rispettivamente il valore minimo, mediano e massimo e poi stampare le tre variabili.
3. Verifica se tre interi possono essere le misure dei lati di un triangolo e individua il tipo di triangolo. Per esempio, 3, 2 e 8 non possono esserlo perché ... non si riesce a "chiudere" il triangolo!
4. Come al punto precedente, ma in caso affermativo decidere se il triangolo è rettangolo, acutangolo od ottusangolo (suggerimento: se vale il teorema di Pitagora è rettangolo, altrimenti ...)
5. Date (inserire a piacere questi valori) le coordinate di tre punti a=(xa, ya), b=(xb, yb), c=(xc, yc), calcolare la lunghezza dei lati del triangolo definito dai tre punti
6. Siano x1, y1, x2, y2, x3, y3, x4, y4 le coordinate (inserire a piacere questi valori) di quattro punti. Calcolare e stampare le pendenze (coefficiente angolare) della retta passante per (x1, y1) e (x2, y2) e della retta passante per (x3, y3) e (x4, y4).

Operatori logici and e and

Invocazione di metodi e uso del valore restituito

Generazione di numeri pseudocasuali con random.random() e random.randint(a, b)

Semplici programmi con l'istruzione if

Esercitazione 2

La registrazione della lezione del 30 Settembre 2021 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: ya7B.+dN
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Il problema dell'ordinamento per confronti: numero minimo di confronti per ordinare n numeri

Esempi di programmi con istruzioni condizionali, anche nidificate, ed espressioni booleane complesse

1. dati tre reali maggiori di zero, stampare la media aritmetica e la media geometrica
2. dati gli estremi di due intervalli di reali, decidere se gli intervalli sono:
   • disgiunti
   • uno contenuto nell'altro
   • nessuno dei due casi precedenti
3. generare casualmente 5 numeri interi in [1, 6] e stampare:
   • il massimo
   • la molteplicità del massimo (quanti valori sono uguali al massimo)
4. dato l'orario di inizio di un evento (espresso da tre interi: ore, minuti, secondi, con ore compreso in [0,23], minuti compreso in [0, 59] e secondi compreso in [0, 59]) e data la durata dell'evento (espressa in ore, minuti e secondi con gli stessi vincoli definiti sopra), calcola e stampa l'istante di fine dell'evento (espressa nello stesso modo), indicando se l'istante di fine è nello stesso giorno dell'inizio o nel giorno successivo

La registrazione della lezione del 4 Ottobre 2021 è disponibile a questo link Zoom Passcode di accesso: O0T=8s@B
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Chiamata di funzioni. Significato in una espressione.

Funzioni vuote, funzioni che restituiscono valori. Parametri ed argomenti.

Funzioni di conversione.

Definizione di funzioni con def .... :

1. Funzione che restituisce la somma di due numeri, con esempio di uso
2. Funzione che date le misure di due cateti di un triangolo rettangolo restituisce la misura dell'ipotenusa, con esempio di uso
3. Funzione che verifica se tre numeri costituiscono una terna pitagorica, cioè se il quadrato di uno dei tre è uguale alla somma dei quadrati degli altri due, con esempi di uso

La registrazione della lezione del 5 Ottobre 2021 è disponibile a questo link Zoom Passcode di accesso: V.S!x91q
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Passaggio dei parametri con nome, parametri opzionali

Esercizi sulla definizione di funzioni

Esercitazione 3

La registrazione della lezione del 7 Ottobre 2021 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: C3v!a7qz
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Stack di attivazione delle funzioni. Variabili locali.

Passaggio dei parametri. Assenza di effetti collaterali su parametri semplici.

L'istruzione di ciclo while

Esercizi sull'uso di cicli e istruzioni condizionali

• Scrivere un programma che mostra quante volte bisogna ripiegare in due un foglio dello spessore di 0,1 millimetri affinché si raggiunga lo spessore di 500 mm.. Stampare lo spessore ottenuto dopo ciascun ripiegamento.
• Modificare il programma precedente, stampando solo il numero di riipegamenti necessari. Deve essere stampato un solo numero. Provare poi a raggiungere la distanza Terra-Luna, circa 380000 km (380.000.000.000 mm, 3.8e+11 mm).
• Modificare il programma precedente, definendo una funzione che prende come parametri lo spessore del foglio e la distanza che si intende raggiungere, e restituisce il numero di ripiegamenti necessari. Scrivere un programma che chiama la funzione appena definita con vari valori dei parametri.
• Scoprire cosa fa il programma ignoto.py
• Fare in modo che il programma ignoto.py funzioni anche quando a e/o b contengono valori negativi
• Scrivere un programma che, dati due numeri naturali a e b, stampa il valore di ab, senza utilizzare l'operatore **
• Definire una funzione che restituisce il numero di anni necessari per raggiungere un dato importo a partire da un capitale iniziale e un tasso di interesse annuo. Alla fine di ciascun anno gli interessi maturati vengono aggiunti al capitale, in modo che nell'anno successivo anche gli interessi aggiunti al capitale diano luogo ad interessi.
• Verifica se un naturale è primo. La funzione ha come parametro il numero naturale e restituisce True o False. Per verificare se un numero a è divisibile per b basta verificare se il valore a % b è zero.
• Stampa il numero di divisori di un naturale (si possono utilizzare alcune delle idee a proposito del test di primalità)
• Scrivere una funzione che stampi i numeri della successione di Fibonacci minori o uguali a un parametro dato.
• Scrivere un programma che stampi i primi n elementi della successione di Fibonacci

La registrazione della lezione dell'11 Ottobre 2021 è disponibile a questo link Zoom Passcode di accesso: ^Sf02xSK
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esempi di definizione di funzioni con cicli.

La registrazione della lezione dell'11 Ottobre 2021 è disponibile a questo link Zoom Passcode di accesso: RJ6!@V71
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Uso di variabili boolean per il controllo di cicli

Istruzione break;

Esercizi sull'uso di cicli e istruzioni condizionali

Esercitazione 4

La registrazione della lezione del 14 Ottobre 2021 è disponibile a questo link Zoom Passcode di accesso: *Jp32=X!
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Istruzioni di assegnazione con modifica += -= *= /= %=

Istruzione for ... in ...

Uso del range(...)

Semplici programmi con cicli

Esempi di programmi con cicli e istruzioni di selezione

• Dato un numero naturale n, stampare un quadrato (pieno) di asterischi di lato n. Il quadrato sarà formato da n righe, ciascuna contenente n asterischi.

    **********
    **********
    **********
    **********
    **********
    **********
    **********
    **********
    **********
    **********
  
  

• Dato un numero naturale n, stampare un quadrato (solo il bordo) di asterischi di lato n. Il quadrato dovrà avere l'aspetto seguente:

    ********** . . . ****
    *                   *
    *                   *
    *                   *
      . . . . . . . .
      
    *                   *
    ********** . . . ****
  
  

• Dati due numeri naturali n e b, con b < n/2, stampare un quadrato di asterischi di lato n con il bordo di spessore b. Ad esempio, se il valore di b fosse 3, il quadrato dovrebbe avere l'aspetto seguente:

    ********** . . . ****
    ********** . . . ****
    ********** . . . ****
    ***               ***
    ***               ***
    ***               ***
      . . . . . . . .
      
    ***               ***
    ********** . . . ****
    ********** . . . ****
    ********** . . . ****
  
  

• Dato un numero naturale n, stampare un triangolo rettangolo (pieno) di asterischi di lato n. Il triangolo sarà formato da n righe di lunghezza crescente.

    *
    **
    ***
    ****
     . . .
    
    *********
    **********
  
  

• Dato un numero naturale n, stampare un triangolo rettangolo (solo il bordo) di asterischi di lato n. Il triangolo dovrà avere l'aspetto seguente:

    *
    **
    * *
    *  *
     . . .
    
    *      *
    *       *
    **********
  
  

• Stampare la somma dei primi n termini della serie armonica: 1/1 + 1/2 + 1/3 + ... + 1/n
• Come sopra, mostrando la differenza tra il risultato ottenuto eseguendo la somma in un senso o in senso opposto: 1/1 + 1/2 + 1/3 + ... + 1/n rispetto a 1/n + 1/(n-1) + 1/(n-2) + ... + 1/2 + 1/1

• Mostrare l'andamento della somma della serie armonica, visualizzandone il valore ogni 100 termini aggiunti fino a un massimo numero di termini immesso da tastiera.
  Mostrare che la differenza tra la somma dei primi n termini e il logaritmo naturale (Math.log) di n, al crescere di n, tende a una costante.
• Stampa della tavola pitagorica n per n assumendo che che l'input (n) sia compreso nell'intervallo [1,18] (Suggerimento: per ottenere la tabella ben incolonnata usare il cosiddetto "modulo tra stringhe" o "string interpolation")

Somme di quadrati

Scrivere un programma che, dato in input un numero naturale n, stampa tutte le coppie di naturali x, y tali che x^2 + y^2 = z^2, con x, y, z ≤ n.

Per n = 20 le soluzioni dovrebbero essere le seguenti:

3^2 + 4^2 = 5^2
5^2 + 12^2 = 13^2
6^2 + 8^2 = 10^2
8^2 + 15^2 = 17^2
9^2 + 12^2 = 15^2
12^2 + 16^2 = 20^2
	

Soluzione: cercaTernePitagoriche.py

La registrazione della lezione del 18 Ottobre 2021 è disponibile a questo link Zoom Passcode di accesso: RTn*ZW0M
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Algoritmo per approssimare uno zero di una funzione continua ricercaZero.py

Esempi di programmi con cicli multipli e istruzioni di selezione

Introduzione alle stringhe. Indicizzazione, slicing, funzione len, metodi upper e find, operatore in

• funzione che verifica se una stringa è palindroma
• funzione che conta gli spazi in una stringa
• funzione che conta le vocali in una stringa
• funzione che, data una stringa, stampa una parola della stringa su ciascuna riga
• migliorare la funzione precedente facendo sì che NON vengano stampati a capo multipli in presenza di spazi adiacenti nella stringa

La registrazione della lezione del 26 Ottobre 2021 è disponibile a questo link Zoom Passcode di accesso: #1M9Ax@2
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercizi su stringhe, cicli.

Istruzione for ... in ...

Differenza tra:

• scansione delle posizioni for i in range(len(sequenza)):
• scansione degli elementi for valore in sequenza:

Esercitazione 5

Una soluzione del problema sulla stampa delle stringhe in colonna è in stampaColonna.py

La registrazione della lezione del 21 Ottobre 2021 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: mqw+?3t.
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercizi su cicli, istruzioni condizionali, stringhe

Commento della funzione di ricerca binaria ricercaZero.py

Liste

Accesso e modifica di elementi di una lista.

Scansione di liste con for elem in lista: oppure con for i in range(len(lista)):

I metodi append(...) ed extend(...) delle liste

Costruzione di liste

• funzione che verifica se un numero è perfetto
• funzione che restituisce il k-esimo elemento della sequenza di Fibonacci
• funzione che restituisce il primo elemento della successione di Fibonacci maggiore di un valore dato come parametro
• funzione che a partire da una stringa di caratteri restituisce la stessa stringa privata degli eventuali spazi iniziali e finali
• funzione che, a partire da una parola, restituisce la stessa parola privata delle vocali
• funzione che dato n restituisce il minimo numero primo maggiore di n
• funzione che dati due naturali a, b restituisce il Massimo Comun Divisore di a e b
• funzione che dati due naturali a, b restituisce il minimo comune multiplo di a e b

• funzione che restituisce la somma degli elementi di una lista
• funzione che restituisce la media degli elementi di una lista
• funzione che, data una lista di parole, restituisce una stringa composta dalle parole intervallate da spazi
• funzione che restituisce minimo e massimo di una lista
• funzione che, data una lista di numeri L e una soglia s, restituisce il numero di elementi di L maggiori di s

La prossima esercitazione si svolgerà secondo le modalità descritte nel video del prof. Massimo Lauria disponibile a questo link

La registrazione della lezione del 25 Ottobre 2021 è disponibile a questo link Zoom Passcode di accesso: @i=RXSz6
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercizi su liste

I metodi index(...), pop(...), remove(...) e insert(...) delle liste

Implementazione della ricerca sequenziale su lista

Liste disomogenee. Verifica del tipo degli elementi di una lista con la funzione isinstance(val, tipo)

Esercizi di base su liste:

• Leggi da tastiera una sequenza di numeri, memorizzala in una lista, stampa la somma degli elementi sommaSequenzaInLista.py
• Leggi da tastiera una sequenza di double, memorizzala in una lista, crea un lista che contiene una copia degli elementi della prima lista, ma in ordine inverso copiaOrdineInverso.py
• Leggi da tastiera una sequenza di interi che rappresentano delle frequenze, memorizzala in una lista, crea una lista che contiene le frequenze cumulate e stampa, in due colonne, la sequenza delle frequenze (sulla sinistra) e la sequenza delle frequenze cumulate (sulla destra) cumula.py
• Ricerca sequenziale in una lista ricercaSequenziale.py

Data in input una sequenza di interi che rappresentano frequenze:

• stampare la frequenza massima e la frequenza minima;
• calcolare la lista delle frequenze relative e stamparlo;
• calcolare la lista delle frequenze relative cumulate e stamparlo;
• stampare in quale posizione si trovano la frequenza massima e la frequenza minima.

Soluzione: frequenze.py

La registrazione della lezione del 26 Ottobre 2021 è disponibile a questo link Zoom Passcode di accesso: UAUW=*v3
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercizi su liste.

La registrazione della lezione del 28 Ottobre 2021 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: I^0G^M&9
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Ricerca di massimo valore o della sua posizione in una lista non ordinata.

Ricerca binaria su liste ordinate.

Complessità della ricerca binaria

• Ricerca di massimo e minimo in una lista maxMinLista.py
• Ricerca della posizione di massimo e minimo in una lista posMaxMinLista.py
• Ricerca binaria in una lista ordinata crescente ricercaBinaria.py

La registrazione della lezione del 2 Novembre 2021 è disponibile a questo link Zoom Passcode di accesso: .r$64sFG
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Funzioni che creano liste

Funzioni che modificano liste

Esercizi su liste

La registrazione della lezione del 4 Novembre 2021 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: q^$^bH1y
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Liste di liste per la rappresentazione di matrici. Esercizi su liste di liste:

• Creazione di una matrice n per m con elementi 0 creaMatrice.py.
• Somma degli elementi di una matrice sommaMatrice.py.
• Calcolo della somma di ciascuna riga sommaRigheMatrice.py.

La registrazione della lezione del 9 Novembre 2021 è disponibile a questo link Zoom Passcode di accesso: Pa+W@&t8
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercizi su liste bidimensionali.

La registrazione della lezione dell'11 Novembre 2021 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: yU!b=f22
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Algoritmo di ordinamento insertion sort insertionSort.py

Introduzione alla ricorsione.

Esempio di algoritmo ricorsivo per il calcolo del fattoriale fattorialeRicorsivo.py

Esempio di algoritmo iterativo per il calcolo del fattoriale fattorialeIterativo.py

• scrivere un metodo ricorsivo che dato un array di numeri restituisce il massimo elemento dell'array
• scrivere un metodo ricorsivo che dato un array di numeri restituisce il numero di elementi negativi contenuti nell'array

La registrazione della lezione del 15 Novembre 2021 è disponibile a questo link Zoom Passcode di accesso: 2V?Q5WCM
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Algoritmo di ordinamento a bolle - Bubble Sort (codice Bubble sort semplice) e suoi miglioramenti (codice Bubble sort migliorato)

Analisi della prestazioni del bubble sort

Introduzione alla complessità computazionale

La notazione asintotica O()

Esempi di classi di funzioni

• Animazione di algoritmi di ordinamento https://www.toptal.com/developers/sorting-algorithms

La registrazione della lezione del 16 Novembre 2021 è disponibile a questo link Zoom Passcode di accesso: n8ec9V*G
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercizi su liste e liste bidimensionali.

La registrazione della lezione del 18 Novembre 2021 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: H4@8Ea.P
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Le notazioni asintotiche O(), Ω(), Θ()

Esempi di classi di funzioni

Uso delle notazioni asintotiche per esprimere limitazioni superiori e inferiori della complessità di algoritmi

Complessità computazionale di semplici algoritmi: insertion sort, bubble sort, ricerca sequenziale e ricerca binaria

Esercizio: calcolo dei numeri primi con il crivello di Eratostene

Il paradigma divide et impera.

Somma di una sequenza applicando il paradigma divide et impera sommaListaRicorsiva.py.

Introduzione all'algoritmo di ordinamento per fusione (merge sort)

dispense del corso, oppure Cormen, Leiserson, Rivest

La registrazione della lezione del 22 Novembre 2021 è disponibile a questo link Zoom Passcode di accesso: %8EgsI01
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Algoritmo di ordinamento per fusione - Merge Sort (codice merge sort)

Analisi della prestazioni del merge sort

Dimostrazione della complessità minima possibile (lower bound) per il problema dell'ordinamento basato su confronti

La registrazione della lezione del 23 Novembre 2021 è disponibile a questo link Zoom Passcode di accesso: 8N*3#Am1
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercizi su stringhe di caratteri e liste.

La registrazione della lezione del 25 Novembre 2021 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: R2bVjy.*
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Algoritmo di ordinamento Quick Sort (codice quick sort)

Analisi della prestazioni del quick sort nel caso migliore e nel caso peggiore.

dispense del corso, oppure Cormen, Leiserson, Rivest

La registrazione della lezione del 29 Novembre 2021 è disponibile a questo link Zoom Passcode di accesso: .!82b!T@
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Analisi della complessità computazionale di algoritmi ricorsivi.

• Equazioni di ricorrenza.
• Soluzione di equazioni di ricorrenza attraverso il teorema principale (senza dimostrazione).
• Esempi di applicazione del teorema principale: ricerca binaria, merge sort, quick sort.

dispense del corso, oppure Cormen, Leiserson, Rivest

La registrazione della lezione del 30 Novembre 2021 non è disponibile. Una lezione sugli stessi argomenti è visibile, a partire dal minuto 23 circa, a questo link Zoom Passcode di accesso: #5kdB^+R
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercitazione su algoritmi di ordinamento.

La registrazione della lezione del 2 Dicembre 2021 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: R%5g3y$S
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Lettura e scrittura di file di testo.

L'algoritmo di Euclide per il calcolo del Massimo Comun Divisore.

• Funzione che mostra la lettura e la scrittura di file di testo fileInOut.py
• Lettura di un file CSV letturaCSV.py. Assume che esista un file datiProva.txt nella stessa cartella.
• Algoritmo MCD di Euclide:
  • versione ricorsiva MCDEuclideRicorsivo.py
  • versione iterativa MCDEuclideIterativo.py
  • complessità computazionale dell'algoritmo MCD di Euclide

La registrazione della lezione del 6 Dicembre 2021 è disponibile a questo link Zoom Passcode di accesso: uQx.%9eq
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Dizionari: definizione, scansione, indicizzazione, funzione get

Algoritmo per il calcolo del k-esimo elemento: selection.py

Analisi di complessità dell'algoritmo per il k-esimo elemento

• Funzione che a partire da una stringa contenente parole separate da spazi, restituisce un dizionario con le parole come chiavi e le rispettive frequenze come valori frequenzeDizionario.py.
• Funzione che a partire da un dizionario che contiene frequenze assolute delle chiavi, restituisce il dizionario contenente le frequenze relative delle chiavi frequenzeRelative.py

dispense del corso, oppure Cormen, Leiserson, Rivest

La registrazione della lezione del 7 Dicembre 2021 è disponibile a questo link Zoom Passcode di accesso: Xc%@6sKz
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercitazione su files e dizionari.

La registrazione della lezione del 9 Dicembre 2021 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: 07@bGpB.
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Codifica dell'informazione:

• Generalità sulla notazione posizionale per numeri naturali, interpretazione di numeri espressi in base b
• conversione da base b a base 10 e da base 10 a base 2
• codifica esadecimale, conversione dalla base 2 alla base 16
• rappresentazione di numeri in virgola mobile (floating point), errori di troncamento

La registrazione della lezione del 16 Dicembre 2021, ore 12, è disponibile a questo link Zoom Passcode di accesso: ^gzX1$bI
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

• Codifica di caratteri: codice ASCII, codici ASCII estesi, codice Unicode, rappresentazione UTF-8
• Esercizi di programmazione.

La registrazione della lezione del 16 Dicembre 2021, opre 16, è disponibile a questo link Zoom Passcode di accesso: $21r9jtF
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.