Informatica, Primo canale (A-D), anno accademico 2020-2021

• 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

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

Funzione print(...)

La registrazione della lezione del 7 Ottobre 2020 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: 12^9uU&V
È 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.

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

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

Precedenza tra operatori, valutazione di una espressione: albero sintattico

Istruzione di assegnazione, binding nome - valore

Regole per la definizione di identificatori, parole riservate

La funzione type(...)

Funzioni di conversione

Stringhe, operatori su stringhe

Errori sintattici, errori semantici, eccezioni

Uso di funzioni matematiche con import math

La registrazione della lezione del 7 Ottobre 2020 è disponibile a questo link Zoom Passcode di accesso: y.v@8!SN
È 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 idle3

Funzione print()

Istruzione if :

Espressioni boolean, le costanti True e False

Indentazione del codice

Operatori logici and e and

La registrazione della lezione del 12 Ottobre 2020 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: Qf*&S3zg
È 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. Dati due intervalli I1=[a, b] e I2=[c, d], rappresentati nel programma da quattro variabili int a, b, c, d;, con a<b e c<d, decidere se l'intervallo I1 contiene l'intervallo I2 (come ad esempio nel caso I1=[3, 40] e I2=[12, 25]) oppure I2 contiene I1, oppure non c'è relazione di contenimento (come ad esempio nel caso I1=[11, 56] e I2=[28, 80]. Visualizzare gli intervalli e un messaggio che indica l'eventuale contenimento.

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 14 Ottobre 2020 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: Yh.nN64+
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Istruzione if : elif: else:

Istruzioni if nidificate

Esempi di programmi con istruzioni condizionali

Esempi di programmi con uso di contatori

La registrazione della lezione del 14 Ottobre 2020 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: AUUvPH%0
È 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 19 Ottobre 2020 è disponibile a questo link Zoom Passcode di accesso: ^pz3XXp@
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercizi sulla definizione di funzioni

Esercitazione 3

La registrazione della lezione del 21 Ottobre 2020 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: N^^$UTC3
È 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.

Passaggio dei parametri con nome, parametri opzionali

Esempi di definizione di funzioni.

1. Funzione che a partire da una durata, espressa cme un numero intero di secondi, restituisce la sua rappresentazione come stringa di caratteri nel formato hh:mm:ss. Ad esempio, partendo da 39744 secondi, che corrisponde a 11 ore, due minuti e 24 secondi, si deve restituire 11:02:24. Analogamente, a partire dal valore 8 secondi, si deve restituire 00:00:08. Notare che il numero di ore, minuti e secondi deve essee sempre espresso da due cifre, eventualmente nella forma 0x oppure 00. Si può assumere che la durata sia sempre inferiore a 100 ore, oppure ammettere che il numero di ore restituite possa anche essere espresso da più di due cifre
2. Funzione che, dato un importo in euro, espresso con al massimo due decimali, e una percentuale di sconto (ad esempio 25 per indicare uno sconto del 25%), restituisce il valore scontato arrotondato al secondo decimale. Ad esempio, a partire da un importo 100.34 e uno sconto 21 si deve restituire 79.27. Si noti che è disponibile in Python3 la funzione round(...), il comando help(round) fornisce indicazioni sul suo utilizzo.

La registrazione della lezione del 21 Ottobre 2020 non è disponibile a causa di un disguido tecnico

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.
• 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, stampi 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.
• 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 del 26 Ottobre 2020 è disponibile a questo link Zoom Passcode di accesso: QD#h20S?
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercizi sull'uso di cicli e istruzioni condizionali

Esercitazione 4

La registrazione della lezione del 26 Ottobre 2020 è disponibile a questo link Zoom Passcode di accesso: +K?P2qSN
È 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 += -= *= /= %=

Uso di variabili boolean per il controllo di cicli

Semplici programmi con cicli

Istruzione break;

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 <= n e z naturale.

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 26 Ottobre 2020 è disponibile a questo link Zoom Passcode di accesso: M#w^5Kce
È 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 2020 è disponibile a questo link Zoom Passcode di accesso: R#Jy&N8J
È 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 .... Uso del range(...)

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

Eccezioni: l'istruzione raise

Esercizi su cicli, istruzioni condizionali, stringhe

Commento della funzione di ricerca binaria ricercaZero.py

• 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

La registrazione della lezione del 4 Novembre 2020 è disponibile a questo link Zoom Passcode di accesso: 2EqqF..l
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

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(...), pop(...) ed extend(...) delle liste

Ricerca sequenziale su lista

Liste disomogenee. 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 9 Novembre 2020 è disponibile a questo link Zoom Passcode di accesso: r8mgQm^+
È 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 dell'11 Novembre 2020 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: Wa%gn^4G
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Operatore in su liste

Slicing di liste

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 dell'11 Novembre 2020 (solo la parte sulla ricerca binaria, la parte iniziale della lezione non è stata registrata) è disponibile a questo link Zoom Passcode di accesso: J++ze4T7
È 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.

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

Il paradigma divide et impera.

Somma di una sequenza applicando il paradigma divide et impera sommaListaRicorsiva.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 16 Novembre 2020 è disponibile a questo link Zoom Passcode di accesso: cXUen7R%
La registrazione contiene due parti, saltare la prima. È 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 18 Novembre 2020 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: 8qj9B?bK
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Passaggio di parametri riferimento: il caso delle liste.
Effetti collaterali.

Esempi di programmi che modificano liste.

Funzioni che restituiscono liste. Assegnazione tra riferimenti.

L'algoritmo di Euclide per il calcolo del Massimo Comun Divisore: versione ricorsiva MCDEuclideRicorsivo.py

L'algoritmo di Euclide per il calcolo del Massimo Comun Divisore: versione iterativa MCDEuclideIterativo.py

Complessità computazionale dell'algoritmo MCD di Euclide

• Funzione che, dato n, restituisce la lista dei primi n numeri della successione di Fibonacci
  • versione ricorsiva listaFibonacciRicorsiva.py
  • versione iterativa listaFibonacciIterativa.py
• Inversione di lista
  • versione che inverte la lista parametro invertiLista.py
  • versione che restituisce una copia invertira creaListaInversa.py

La registrazione della lezione del 18 Novembre 2020 è disponibile a questo link Zoom Passcode di accesso: CnKglG^8
È 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

• Creare una lista contenente 20 interi random in [0, 100) e stampare il numero di elementi pari, il numero di elementi maggiori di 70, media e varianza degli elementi;
• leggere da tastiera una sequenza di interi (la lunghezza è data anch'essa da tastiera), memorizzala in una lista, verifica se la sequenza è in ordine non decrescente;
• modificare il programma precedente per verificare se la sequenza è crescente, non decrescente, non crescente o decrescente
• data una lista di interi, creare un altra lista contenente solo gli elementi di posizione pari della prima lista;
• data una lista di interi, creare un altra lista contenente solo gli elementi di posizione dispari della prima lista;
• data una lista di interi, creare un altra lista contenente solo gli elementi pari (deve essere pari il valore, indipendentemente dalla posizione) della prima lista;
• date due liste di interi A e B, con len(A) ≥ len(B), verificare se la sequenza B compare in A, e in caso positivo indicare in quale posizione. Ad esempio, la sequenza B = 3, 2, 10 compare nella sequenza A = 12, 2, 3, 2, 8, 3, 2, 10, 4, 2 in posizione 5

La registrazione della lezione del 19 Novembre 2020 è disponibile a questo link Zoom Passcode di accesso: x^rjEP65
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Esercizi di programmazione su liste bidimensionali

• scrivere una funzione simmetrica(m) che:
  • riceve una matrice come parametro
  • verifica che sia quadrata (altrimenti solleva ValueError)
  • restituisce True se la matrice è simmetrica (rispetto alla diagonale principale), False altrimenti
• scrivere una funzione trasposta(m) che, data una matrice m di r righe e c colonne costruisce un'altra matrice e la restituisce. La matrice restituita deve essere la trasposta della matrice m, quindi avrà c righe e r colonne trasposta.py
• scrivere una funzione mat_identita(n) che, dato un naturale n, costruisce e restituisce la matrice identità di dimensione n matriceIdentita.py
• scrivere una funzione cerca(testo, parola) che, date due sequenze (liste o stringhe) testo e parola, restituisce la posizione iniziale della prima occorrenza di parola in testo. Se non c'è alcuna occorrenza restituisce -1. cercaStringa.py. Modificare poi la funzione per cercare la posizione dell'ultima occorrenza invece della prima.
• analogamente al punto precedente, scrivere una funzione cerca_matrice_in_matrice(mat_grande, mat_piccola) che, date due matrici, restituisce la posizione iniziale (coppia di coordinate) della prima occorrenza di mat_piccola in mat_grande. Se non c'è alcuna occorrenza restituisce la coppia -1, -1. Una bozza della soluzione è mostrata in cercaMatrice.py.
• scrivere una funzione che verifica (restituisce True o False) se una matrice quadrata è triangolare SUPERIORE (tutti gli elementi SOTTO la diagonale principale sono 0)

  5  2  7  0  3  5
  0  4  7  0  2  2
  0  0  6  8  4  2
  0  0  0  4  3  1
  0  0  0  0  7  3
  0  0  0  0  0  1
  

• scrivere una funzione che verifica (restituisce True o False) se una matrice quadrata è una matrice diagonale (tutti gli elementi tranne la diagonale principale sono 0)

  6  0  0  0
  0  4  0  0
  0  0  7  0
  0  0  0  0
  

  verificaDiagonale.py

La registrazione della lezione del 23 Novembre 2020 è disponibile a questo link Zoom Passcode di accesso: k*G4#c5H
È 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 del 25 Novembre 2020 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: #=WrY023
È 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

Esercizio: calcolo dei numeri primi con il crivello di Eratostene

• Animazione di algoritmi di ordinamento https://www.toptal.com/developers/sorting-algorithms
• Crivello di Eratostene https://it.wikipedia.org/wiki/Crivello_di_Eratostene, implementazione in Python eratostene.py

La registrazione della lezione del 25 Novembre 2020 è disponibile a questo link Zoom Passcode di accesso: R@p&4N7D
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Introduzione alla complessità computazionale

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

dispense del corso, oppure Cormen, Leiserson, Rivest

La registrazione della lezione del 26 Novembre 2020 è disponibile a questo link Zoom Passcode di accesso: Jou50i$Q
È 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

La registrazione della lezione del 30 Novembre 2020 è disponibile a questo link Zoom Passcode di accesso: r4kn8V#5
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

Output formattato con il metodo format di str

Esercizi su liste e liste bidimensionali.

La registrazione della lezione del 2 Dicembre 2020 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: !kCC=435
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

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

Algoritmo di ordinamento Quick Sort (codice quick sort)

Analisi della prestazioni del quick sort

dispense del corso, oppure Cormen, Leiserson, Rivest

La registrazione della lezione del 2 Dicembre 2020 è disponibile a questo link Zoom Passcode di accesso: C?0u#2t2
È 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.

Complessità computazionale del quick sort nel caso migliore e nel caso peggiore

dispense del corso, oppure Cormen, Leiserson, Rivest

La registrazione della lezione del 3 Dicembre 2020 è disponibile 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.

Si raccomanda agli studenti di compilare il questionario OPIS (OPInioni Studenti) per l'insegnamento di Informatica (primo canale).
Il codice per la compilazione del questionario è FI60RJSN

Un vademecum per la compilazione è disponibile a questo link.
(Instructions in English for filling the questionnaire are available at this link )

Algoritmo per il calcolo del k-esimo elemento: selection.py e sua complessità computazionale

Analisi della prestazioni dell'algoritmo per il k-esimo elemento

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

dispense del corso, oppure Cormen, Leiserson, Rivest

La registrazione della lezione del 7 Dicembre 2020 è disponibile a questo link Zoom Passcode di accesso: %$&E8xZH
È 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 9 Dicembre 2020 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: nQ3y9c^3
È 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:

• rappresentazione di numeri in virgola mobile (floating point), errori di troncamento
• codifica di caratteri: codice ASCII, codici ASCII estesi, codice Unicode, rappresentazione UTF-8

La registrazione della lezione del 9 Dicembre 2020 è disponibile a questo link Zoom Passcode di accesso: aR5I*pwC
È 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.

Dizionari.

1. Funzione che a partire dal nome di un file, che si assume presente nella stessa cartella del sorgente Python, legge le righe contenute nel file e le stampa stampa file di testo, con esempio di uso
2. 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.
3. Funzione che a partire da un dizionario che contiene frequenze assolute delle chiavi, restituisce il dizionario contenente le frequenze relative delle chiavi frequenzeRelative.py

La registrazione della lezione del 14 Dicembre 2020 è disponibile a questo link Zoom Passcode di accesso: B25.Gp09
È 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 file e dizionari.

La registrazione della lezione del 16 Dicembre 2020 (laboratorio) è disponibile a questo link Zoom Passcode di accesso: 4mz+!Ps6
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.

La registrazione della lezione del 16 Dicembre 2020 è disponibile a questo link Zoom Passcode di accesso: d2c@Tb#c
È proibito qualunque uso non personale del video e non è consentita la diffusione del link a persone estranee ai corsi di laurea del DSS.