Tecniche di Programmazione - Appunti di immediata comprensione

Tecniche di programmazione

Introduzione

1.1 Differenza tra programma e algoritmo

Un algoritmo è un procedimento che descrive una sequenza di passi ben definiti per risolvere un certo problema. Gli algoritmi, quindi, devono funzionare a prescindere dal linguaggio di programmazione e devono essere:

• Corretti: restituiscono esattamente il risultato desiderato
• Efficienti: usano poche risorse di calcolo (tempo e memoria)

Un programma è la codifica dell’algoritmo in linguaggio di programmazione.

1.2 Alcune definizioni

Istanza
È un caso specifico su cui applicare un problema, è un input del problema. Ad esempio, nel problema “Trovare il minimo in un vettore”, l’istanza è il vettore stesso.

Caso Peggiore
È il caso che comporta il costo computazionale massimo.

1.3 Richiami su Python

Python è un linguaggio interpretato: vi è un interprete (software) che riceve un comando, lo valuta e ne riporta un risultato. Inoltre, è un linguaggio tipizzato dinamicamente, cioè non esiste alcuna dichiarazione che associa il tipo di oggetto all’identificatore: lo fa direttamente l’interprete Python in automatico. L’identificatore è un puntatore ad una zona di memoria che contiene il dato.

Ad esempio:
temperature=98.6
L’identificatore “temperature” serve a capire in quale zona di memoria si trova il 98.6. È possibile anche stabilire un alias assegnando un secondo identificatore ad un oggetto già esistente. Nell’esempio che segue viene creato un nuovo identificatore (original): vediamo come il comando alla riga 6 stampa lo stesso id di memoria della riga 3, perché l’alias original punta alla stessa locazione di memoria di temperature.

temperature = 98.6
print(temperature)
print(id(temperature))
original = temperature
print(original)
print(id(original))

1.4 Gestione della memoria in Python

Esistono due tipologie di allocazione della memoria in Python:

Allocazione Statica

• Le variabili allocate staticamente sono permanenti: sono allocate in anticipo e durano finché il programma viene eseguito.
• La memoria allocata non può più essere riutilizzata.
• È l’allocazione tipica dello stack.

Allocazione Dinamica

• Le variabili allocate dinamicamente sono non permanenti: possono essere allocate durante l’esecuzione del programma.
• La memoria allocata può essere rilasciata e riutilizzata.
• È l’allocazione tipica dell’heap.

Esistono due tipologie di memoria in Python:

Memoria Stack
Vi vengono memorizzati i record di attivazione dei metodi (parametri, indirizzi). Quando viene chiamato un metodo viene allocato uno stack frame che gestirà le variabili del metodo ma verrà distrutto dopo che il metodo viene restituito.

Memoria Heap
Vi vengono memorizzati gli oggetti e le variabili di istanza. Questa memoria permette alle variabili di essere accessibili globalmente da tutti i metodi del programma.

1.5 Record di attivazione

Un Record di Attivazione è un blocco di memoria che viene creato non appena si chiama un metodo. Il record di attivazione contiene:

• Parametri ricevuti (input)
• Return address (l’indirizzo del chiamante, e cioè della linea di codice che ha chiamato il metodo) necessario a riprendere l’esecuzione del programma principale
• Link address: il valore di ritorno del metodo

Il Record di Attivazione:

1. Viene creato dinamicamente nel momento in cui viene chiamata la funzione.
2. Rimane nello stack per tutto il tempo in cui la funzione è in esecuzione.
3. Viene deallocato quando la funzione termina.

1.6 Copia profonda e non profonda

Copia Profonda
È la copia che si esegue quando si duplica il dato e si crea una nuova area di memoria con lo stesso oggetto copiato. La modifica di un oggetto non corrisponde alla modifica della sua copia.

Copia Non Profonda
È la copia che si esegue quando si punta allo stesso dato.

2. Analisi degli algoritmi (complessità)

Introduzione

Lo scopo è quello di confrontare gli algoritmi in termini di tempo di esecuzione (running time) ma anche di altri fattori (come ad esempio spazio di memoria, semplicità della soluzione ecc…). Si analizzeranno in particolare:

• Complessità Temporale: Running Time, cioè numero di passi elementari (es. lettura, scrittura, assegnamento)
• Complessità Spaziale: Quanta memoria viene occupata nello stack

L’obiettivo è identificare una funzione che indichi, in base a come cambia la dimensione dell’input, come varia il costo dell’algoritmo.

Quindi:

• Non va bene confrontare i tempi relativi all’esecuzione dell’algoritmo: dipendono dal particolare computer
• Non va bene confrontare il numero di istruzioni: dipende dal linguaggio di programmazione
• Va bene contare il numero di passi elementari (uguale per ogni linguaggio di programmazione)

Analisi Asintotica

Con l’Analisi Asintotica si utilizza il tasso di crescita come misura per confrontare algoritmi, tramite funzioni (si effettua un confronto asintotico). Siano allora:

Notazione O-Grande

La notazione O (Asintoticamente Minore di…) implica che:
f(n) = O(g(n)) esiste C, |f(n) ≤ C · g(n) ∀ n > n₀
Si dice che g(n) è un Limite Superiore rispetto a f(n) e quindi f(n) è al massimo di ordine g(n).

Notazione Ω-Grande

La notazione Ω (Asintoticamente Maggiore di…) implica che:
f(n) = Ω(g(n)) esiste c, |f(n) ≥ c · g(n) ∀ n > n₀
Si dice che g(n) è un Limite Inferiore rispetto a f(n) e quindi f(n) è al massimo di ordine g(n).

Notazione Θ-Grande

La notazione Θ (Asintoticamente Uguale a…) implica che:
f(n) = Θ(g(n)) esistono c₁ e c₂, |c₁ · g(n) ≤ f(n) ≤ c₂ · g(n) ∀ n > 1
Si dice che f(n) è asintoticamente approssimabile a g(n).

3. Algoritmi di ordinamento

3.1 Selection Sort

Spiegazione

Si tratta di un algoritmo intuitivo che viene usato quando l’insieme da ordinare non ha dimensioni eccessive: il codice ha una complessità temporale non efficiente però ha una codifica semplice. Alla prima iterazione si esegue una scansione del vettore per cercare l’elemento più piccolo, che andrà inserito nella prima posizione del vettore. A questo punto si considera il vettore suddiviso in due sottovettori:

• Un sottovettore ordinato a sinistra (a sinistra della seconda posizione dopo la prima iterazione, poi a sinistra della terza posizione dopo la seconda iterazione e così via…)
• Un sottovettore non ordinato a destra (della posizione evidenziata)

Viene rieseguita la scansione relativamente al sottovettore non ordinato e l’elemento minore andrà in prima posizione del sottovettore non ordinato. Si procede in questo modo fino a quando non si raggiunge l’ordine completo del vettore.

Esempio

6 4 2 9 3 2 8 4
2 4 6 9 3 2 8 4
2 2 6 9 3 4 8 4
2 2 3 9 6 4 8 4
2 2 3 4 6 9 8 4
2 2 3 4 4 9 8 6
2 2 3 4 4 6 8 9

Codice

def SelectionSort(v):
    for i in range(len(v) - 1):
        min_pos = i
        for j in range(i + 1, len(v)):
            if (v[min_pos] > v[j]):
                min_pos = j
        v[i], v[min_pos] = v[min_pos], v[i]

Analisi di complessità

Complessità temporale

def SelectionSort(v):
    (1) * for i in range(len(v) - 1): # (1) · n
        min_pos = i # (1) * [(n - 1) + ... + 2 + 1]
        for j in range(i + 1, len(v)): # (1) · [(n - 1) + ... + 2 + 1]
            if (v[min_pos] > v[j]): # (1) · [(n - 1) + ... + 2 + 1]
                min_pos = j
        v[i], v[min_pos] = v[min_pos], v[i] # (1) · (n - 1)

Nel Caso migliore l’istruzione non viene eseguita mai e succede quando il vettore è già ordinato in ordine crescente. (n-1)(n - 1) + ... + 2 + 1 = Θ(n²)

Da notare che è la somma dei primi numeri (n-1).² Θ(n²) = Θ(n²) + 2·Θ(n) + Θ(1) = Θ(n²)

Nel Caso peggiore invece l’istruzione viene sempre eseguita (n - 1) 2 Θ(n²) = Θ(n) + 3·Θ(n) + Θ(1) = Θ(n²)

Complessità spaziale

Non utilizzando alcuna struttura dati e non avendo metodi ricorsivi: Θ(1)

3.2 Insertion Sort

Spiegazione

Questo algoritmo di ordinamento consiste nel prendere il primo elemento ed isolarlo (il primo elemento è il minimo di se stesso). Si assume che la sequenza da ordinare sia partizionata in:

• Una sottosequenza già ordinata (all’inizio composta da un solo elemento)
• Una sottosequenza ancora da ordinare

Alla iterazione la sequenza ordinata contiene elementi. In ogni iterazione viene rimosso il primo elemento della sottosequenza non ordinata e inserito nella posizione corretta della sottosequenza ordinata, estendendola così di un elemento.

Esempio

5 2 8 4 7
5>2? Si, si scambiano
5 2 8 4 7
5>8? No
2 5 8 4 7
5>4? Si, si scambiano
2>4? No
8>7? Si, si scambiano
2 4 5 8 7
2 4 5 7 8

Codice

def InsertionSort(v):
    for i in range(1, len(v)):
        minv = v[i]
        j = i
        while (j > 0 and v[j - 1] > minv):
            v[j] = v[j - 1]
            j = j - 1
        v[j] = minv

Analisi di complessità

Complessità temporale

def InsertionSort(v):
    (1) · for i in range(1, len(v)): # (1) · (n - 1)
        minv = v[i] # (1) · (n - 1)
        j = i # (1) · [1 + 2 + ... (n - 1)]
        while (j > 0 and v[j - 1] > minv):
            v[j] = v[j - 1] # (1) · [1 + 2 + ... (n - 1)]
            j = j - 1 # (1) · [1 + 2 + ... (n - 1)]
        v[j] = minv # (1) · (n - 1)

Nel Caso migliore tutti gli elementi precedenti all’elemento estratto sono minori e quindi le operazioni in grigio non vengono eseguite: Θ(n)

Nel Caso peggiore tutti gli elementi precedenti all’elemento estratto sono maggiori e quindi le operazioni in grigio vengono eseguite: (n - 1) 2 [1 ( ) Θ(n²) = Θ(n) + 3·Θ(n) = Θ(n²)

Nel caso peggiore Selection Sort e Insertion Sort hanno la stessa complessità ma se il vettore è parzialmente ordinato conviene l’Insertion Sort.

Complessità spaziale

Non utilizzando alcuna struttura dati e non avendo metodi ricorsivi: Θ(1)

3.3 Bubble Sort

Spiegazione

L’idea di base di questo algoritmo è quella di far risalire gli elementi più grandi verso l’alto (nelle posizioni con indice maggiore) e contemporaneamente far ridiscendere gli elementi più piccoli verso il basso. Per fare ciò si scorre più volte il vettore confrontando ad ogni iterazione l’ordinamento reciproco di elementi contigui, scambiando posizioni di eventuali coppie non ordinate.

Codice

def bubble_sort(v):
    n = len(v)
    for i in range(len(v) - 1):
        for j in range(len(v) - 1 - i):
            if (v[j] > v[j + 1]):
                v[j], v[j + 1] = v[j + 1], v[j]

Analisi di complessità

Complessità temporale

def bubble_sort(v):
    (1)
    n = len(v) # (1)
    for i in range(len(v) - 1): # (1) · 
        for j in range(len(v) - 1 - i): # (1) · [(n - 1) + ... + 2 + 1]
            if (v[j] > v[j + 1]): # (1) · [(n - 1) + ... + 2 + 1]
                v[j], v[j + 1] = v[j + 1], v[j] # (1) · [(n - 1) + ... + 2 + 1]

Nel Caso migliore e peggiore: Θ(n²)

Complessità spaziale

Non utilizzando alcuna struttura dati e non avendo metodi ricorsivi: Θ(1)

4. Algoritmi di ricerca di un elemento

L’obiettivo è quello di ricercare un elemento in una lista e restituire la posizione della sua prima occorrenza. In caso l’elemento non fosse presente si restituisce -1.

4.1 Ricerca lineare

Spiegazione

L’algoritmo di ricerca lineare si utilizza per la ricerca di un elemento in liste che non sono ordinate. L’algoritmo controlla in sequenza gli elementi della lista, arrestandosi alla prima occorrenza.

Codice

def RicercaLineare(A, x):
    for i in range(len(A)):
        if (x == A[i]):
            return i
    return -1

Analisi di complessità

Complessità temporale

def RicercaLineare(A, x):
    (1)
    for i in range(len(A)): # (1)
        if (x == A[i]): # (1) · (n - 1)
            return i
    return -1

Nel Caso migliore l’elemento che si sta ricercando è in prima posizione e quindi: Θ(1)

Nel Caso peggiore l’elemento che si sta ricercando è in ultima posizione o non è proprio presente e quindi: Θ(n)

Complessità spaziale

Θ(1)

4.2 Ricerca binaria (iterativa)

Spiegazione

L’algoritmo di ricerca binaria si utilizza per la ricerca di un elemento in liste che sono ordinate secondo un certo criterio (supponiamo in ordine crescente in questo caso). L’algoritmo effettua il confronto dell’elemento con l’elemento in posizione centrale della lista:

• Se sono uguali allora si restituisce la posizione centrale
• Se x > A[middle] allora si ricerca nella metà di destra della lista e si scarta la porzione di sinistra
• Se x < A[middle] allora si ricerca nella metà di sinistra della lista e si scarta la porzione di destra

Si procede così iterativamente finché non si trova l’elemento.

Codice

def RicercaBinaria(A, x):
    first = 0
    last = len(A) - 1
    while (first <= last):
        middle = (first + last) // 2
        if (x == A[middle]):
            return middle
        if (x > A[middle]):
            first = middle + 1
        else:
            last = middle - 1
    return -1

Analisi di complessità

Complessità temporale

Nel Caso migliore l’elemento che si sta ricercando è in posizione centrale e quindi intuitivamente: Θ(1)

Nel Caso peggiore l’elemento che si sta ricercando non è presente e il ciclo while viene eseguito un numero di volte pari a log₂ n perché ogni iterazione si va a ricercare nella metà del sottovettore che si considera: Θ(log n)

5. Tecnica del Divide et Impera

5.1 Generalità sul Divide et Impera

La tecnica del Divide et Impera si basa su tre passi principali:

• Suddivisione del problema principale in sottoproblemi
• Soluzione ricorsiva di ciascun sottoproblema
• Combinazione delle soluzioni dei sottoproblemi per ottenere la soluzione del problema principale

5.2 Ricerca binaria ricorsiva

Utilizzando la tecnica del Divide et Impera, il metodo di ricerca binaria diventa un metodo ricorsivo, in quanto i sottoproblemi generati vengono risolti ricorsivamente applicando la soluzione del caso base (quindi basta saper risolvere il caso base).

Codice

def BinarySearch(x, A, first, last):
    if (first > last):
        return -1
    else:
        middle = (first + last) // 2
        if (x == A[middle]):
            return middle
        if (x < A[middle]):
            return BinarySearch(x, A, first, middle - 1)
        else:
            return BinarySearch(x, A, middle + 1, last)

5.3 Merge Sort

Spiegazione

Il Merge Sort è un algoritmo di ordinamento efficiente che sfrutta un processo risolutivo ricorsivo basato sulla tecnica del Divide et Impera. Consideriamo un vettore di interi da ordinare: 6 5 12 10 9 1

Fase di Divide

L’algoritmo va a suddividere il vettore in due parti e, finché è possibile suddividere il vettore, si procede in questo modo (fino a quando non si otterranno vettori di un elemento). La suddivisione avverrà log₂ n volte (quindi sottoproblemi).

6 5 12 10 9 1
10 9 1
6 5 12
9 1
6 5
10
9
5
6

Fase di Impera

Al termine della prima fase si hanno vettori di dimensione 1, che banalmente sono già ordinati con se stessi. Inizia quindi l’ordinamento e si vanno a creare dei vettori di due elementi mettendo in prima posizione.