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

• 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
  • errori sintattici/in esecuzione/semantici
  • 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(...)

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 definizine di identificatori, parole riservate

La funzione type(...)

Funzioni di conversione

Stringhe, operatori su stringhe.

Uso di funzioni matematiche con import math

Script vs. modalità interattiva

Funzione print()

Istruzione if :

Espressioni boolean, le costanti True e False

Indentazione del codice

Istruzione if : else:

Istruzione if : elif: else:

Istruzioni if nidificate

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

Espressioni bool: gli operatori logici and. or e not

Variabili bool

Esempi di programmi con istruzioni condizionali

Esempi di programmi con uso di contatori e flag

Chiamata di funzioni. Significato in una espressione.

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

Funzioni di conversione.

La funzione input(...)

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

Esercizi sulla definizione di funzioni

Esercitazione 3

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.

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

Esercizi sull'uso di cicli e istruzioni condizionali

Esercitazione 4

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

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 ì che NON vengano stampati a capo multipli in presenza di spazi adiacenti nella stringa

Esercizi su stringhe, cicli.

Istruzione for ... in .... Uso del range(...)

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

Liste

Accesso e modifica di elementi di una lista. Slicing di liste

Cicli su liste. Istruzione for ... in ... su liste. Operatore in

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

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

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.

Esercizi su liste.

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

Ricerca sequenziale su 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 sequenziale in una lista ricercaSequenziale.py
• Ricerca binaria in una lista ordinata crescente ricercaBinaria.py

Introduzione alla ricorsione.

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

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

Il paradigma divide et impera.

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

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

• 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

Esercizi su liste.

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

Esempi di programmi che modificano liste.

Funzioni che restituiscono liste. Assegnazione tra riferimenti.

• 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

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

Esercizi su liste bidimensionali.

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

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

Analisi della prestazioni del bubble sort

Esercizi su liste e liste bidimensionali.

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

Analisi della prestazioni del merge sort

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: selection sort, bubble sort, ricerca sequenziale e ricerca binaria

dispense del corso, oppure Cormen, Leiserson, Rivest

Esercizi su stringhe di caratteri e liste.

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

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

Esercizi di programmazione.

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

Analisi della prestazioni dell'algoritmo pe ril 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
• codifica di caratteri: codice ASCII, codice Unicode, rappresentazione UTF-8

dispense del corso, oppure Cormen, Leiserson, Rivest

Lettura e scrittura di file di testo.

Dizionari.

1. Funzione che a partire dal nome di un file, che si assume present enella 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

Simulazione della prova d'esame di programmazione in Python.
Materiale disponibile in questo link sarà attivo dal 20 dicembre 2019.
È ammesso l'uso della tavola sinottica Python3, disponibile in versione PDF

Simulazione della prova d'esame di teoria.
Materiale disponibile in questo link sarà attivo dal 20 dicembre 2019.

dispense del corso, oppure Cormen, Leiserson, Rivest