Fondamenti di informatica 2

DIZIONARI

Una funzione su un dominio discreto può essere vista come una serie di coppie e rappresentata in forma tabellare. Il primo valore della coppia appartiene al dominio il secondo al codominio della funzione. Una lista può essere vista come una funzione tra il dominio degli indici e i valori degli elementi. Ma se una funzione non rispetta il dominio degli indici non può essere rappresentata come una lista e quindi Python introduce i dizionari.

Un dizionario è un insieme di coppie il cui primo elemento si chiama chiave e il secondo valore. Le chiavi sono univoche. In Python un dizionario (dict) è denotato da una sequenza di coppie chiave/valore tra parentesi graffe, dove ciascuna chiave è separata dal relativo valore dal carattere ":".

Esempio: Temperature = { "Chieti":21, "L'Aquila":18, "Pescara":22, "Teramo":20 }

Per accedere agli elementi di un dizionario o per modificarli si può utilizzare

l'operatore di indicizzazione [ ]. Si può copiare un dizionario usando la funzione dict. Se si usa l'operatore di indicizzazione per modificare il dizionario, ma la chiave non esiste allora un nuovo elemento viene creato con quella chiave e con il valore indicato. Il numero di coppie per un dizionario è dato dalla funzione len. Due dizionari possono essere confrontati con gli operatori == e !=. L'operatore booleano in determina se una chiave è nel dizionario. Altri metodi:

• Metodo pop: elimina una coppia di valori dal dizionario
• Metodo values: restituisce tutti i valori
• Metodo get: se una chiave è presente restituisce il suo valore, altrimenti restituisce un valore indicato
• Metodo items: restituisce tutte le coppie come tuple

TABELLE E MATRICI

Una tabella (o matrice) è una disposizione di valori costituita da righe e colonne. Useremo il termine matrice quando i valori sono numerici. Il Python non ha un tipo di dato

Specifico per le tabelle, ma si può creare una struttura bidimensionale utilizzando liste di liste, cioè si può creare una lista di righe, che sono a loro volta liste di valori. Se però la tabella è molto grande si deve crearla a partire dalla tabella vuota inserendo una riga alla volta.

Per accedere agli elementi di una tabella possiamo usare l'operatore di indicizzazione [ ], ricordando che questa è una lista di liste. Se si inseriscono due parentesi quadre, la prima indicherà quale lista prendere e la seconda quale elemento di quella lista prendere.

Se serve, esiste la libreria numpy per le operazioni tra matrici.

FILE

Nell'elaborazione di dati reali è necessario leggere e scrivere file. Come abbiamo visto, i file sono sequenze finite di byte che risiedono in memoria secondaria.

Nel caso in cui i byte codificano caratteri, parliamo di file di testo e quindi le operazioni di lettura e scrittura riguardano stringhe. Se i byte non

• w: per scrivere (o sovrascrivere se esiste) un file
• r: per leggere un file
• a: per aggiungere nuovi dati alla fine del file
• r+: per leggere e scrivere

Dati vengono trasferiti su file. Per assicurarsi che tutti i dati del buffer siano trasferiti nel file bisogna, al termine della scrittura, utilizzare il metodo close(). Esf1.close()

Per leggere una riga di un file di testo si usa il metodo readline(). I seguenti programmi svolgono lo stesso compito di stampare il contenuto di un file di testo.

Esempio:

f1 = open("mio_file.txt","r") # apre il file in lettura
line = f1.readline() # legge una riga
while line != "": # la stringa vuota indica la fine del file
    print(line, end="") # stampa la riga (line contiene già \n)
    line = f1.readline()

Un file testo può essere visto come un' unica stringa. Il metodo read() utilizzato senza parametri legge l'intero file e può prendere come parametro il numero di caratteri da leggere. Per esempio se è 1 legge un singolo carattere.

Il metodo split() restituisce la lista di parole: in realtà stringhe separate da spazi (o da un separatore passato).

per parametro).Esempio s = " Il mattino ha l'oro in bocca. \n"a = s.split() #a vale ['Il', 'mattino', 'ha', 'l'oro', 'in', 'bocca.'] b = s.split("'") #b vale [' Il mattino ha l', 'oro inbocca. \n']Il metodo strip toglie i caratteri indesiderati all'interno della stringaEsempio c = s.strip() #c vale "Il mattino ha l'oro in bocca."d = s.strip(" .\n") #d vale "Il mattino ha l'oro in bocca"LA COMPLESSITA' DEGLI ALGORITMIL'analisi delle prestazioni degli algoritmi è generalmente basata sulnumero di istruzioni di codice macchina che vengono eseguite perrisolvere un problema.Nel caso di un programma per la macchina URM queste possonoessere semplicemente contate in funzione dell'ingresso. Percalcolare f (x, y) = x + y dalla configurazione iniziale dei registri x,y, 0, 0, . . . , il programma

aggiunge 1 a r0 e r2 y volte:

I1 J(2, 1, 5)

I2 S(0)

I3 S(2)

I4 J(0, 0, 1)

Il calcolo terminerà quando r2 = r1, lasciando x + y in R0. Al termine saranno eseguite esattamente 4y + 1 istruzioni.

Per misurare le prestazioni di un algoritmo un approccio è lanciare il relativo programma e misurare il tempo trascorso dall'inizio dell'esecuzione alla fine. Parleremo in questo caso di misurazione delle prestazioni (profiling).

Un altro approccio è quello di misurare le visite alle variabili (lettura o scrittura) o altre operazioni basilari come l'incremento di indici, le operazioni aritmetiche, o il confronto tra valori. Tutte queste operazioni richiedono più o meno la stessa quantità di lavoro a livello di linguaggio macchina. Parleremo in questo caso di analisi delle prestazioni.

SELECTION SORT

Un algoritmo di ordinamento sposta gli elementi di una lista di dati in modo tale che al termine siano memorizzati in qualche ordine specifico.

Ci poniamo il problema

valori da ordinare. Si entra in un ciclo for con una variabile i che cresce fino alla lunghezza della lista di valori. Viene richiamata la funzione che trova la posizione dell'elemento più piccolo (si mettono le variabili lista e i). Dopodiché si inserisce il valore più piccolo della lista in una variabile (valore[minPos]), quel valore si inserisce poi nella prima posizione della lista (cioè i), mentre il valore nella posizione i si inserisce nella posizione minPos.

PROFILING

Per eseguire il profiling del selection sort utilizziamo la libreria time del modulo time che conta i secondi dalla mezzanotte del 1 gennaio 1970. Per misurare il tempo che impiega la funzione attiviamo il tempo, mandiamo in esecuzione il programma e fermiamo il tempo. Infine stampiamo la differenza tra il tempo finale e quello iniziale.

ANALISI

Il grafico che misura le prestazioni del SelectionSort mostra un andamento che ricorda una parabola. Per dimostrarlo possiamo contare il numero di visite

agli elementi della lista. La prima volta, per trovare l'elemento minimo visitiamo n elementi. La seconda visitiamo n - 1 elementi, la terza n - 2 elementi. Ci fermiamo quando restano 2 elementi. Quindi le visite per la ricerca dei minimi sono:

n + (n - 1) + (n - 2) + . . . + 3 + 2 = sommatoria da i=2 a n di i = (n(n+1)/2) - 1

Inoltre, per ogni volta facciamo 2 visite per scambiare gli elementi, per un totale di 2(n - 1) visite. Di conseguenza in tutto le visite sono:

(n(n + 1)/2) - 1 + 2(n - 1) = (½)n^2 + (5/2)n - 3

Quindi l'andamento è quello di una parabola. Semplificando ancora osserviamo che il contributo maggiore al crescere di n lo dà il termine 1/2n^2. Infatti questo per n = 2000 vale 2000000 mentre gli altri termini contribuiscono per 4997: un valore insignificante rispetto a 2000000. Il numero delle visite cresce, con ottima approssimazione, come 1/2n^2.

Cosa succede se raddoppiamo la lunghezza della lista, per esempio, da n

= 1000 a n= 2000? Facendo il rapporto del numero delle visiteotteniamo :([(1/2)2000^2]/[(1/2)1000^2])= 4

Quindi, al raddoppio della lunghezza degli elementi le visitequadruplicano e per una lunghezza tripla le visite diventano novevolte maggiori.

Il coefficiente 1/2 si semplifica sempre: dunque, possiamo dire chele visite sono "dell'ordine di n^2".

LA NOTAZIONE O- GRANDE

Per il SelectionSort, il tempo T(n) per elaborare una lista di nelementi, è proporzionale al numero di visite, cioè T(n) = c*((1/2)n^2+(5/2)n-3), dove c rappresenta il tempo per eseguire unavisita.

Possiamo quindi dire che anche il tempo T(n) è "dell'ordine di n^2".