Appunti Algoritmi e strutture dati

Algoritmo di Euclide per il calcolo del MCD

Teorema 1.2

Dati due interi positivi a e b, risulta MCD(a, b) = MCD(b, a mod b).

Lemma 1.3

Se a >= b, allora a mod b < a/2.

function EuclidMCD(a, b)
    if b = 0 then
        return a
    end if
    return EuclidMCD(b, a mod b)

Teorema 1.4

Per numeri di n bit, l’algoritmo termina correttamente in O(n) passi.

Proof: Supponiamo che risulti a >= b, altrimenti il risultato della prima chiamata consiste semplicemente nello scambio degli argomenti. Consideriamo tre chiamate successive:

• EuclidMCD(a, b) -> EuclidMCD(b, a mod b) -> EuclidMCD(a mod b, b mod (a mod b))

Per il Lemma 1.3, gli argomenti dell’ultima chiamata soddisfano le disuguaglianze. Ne consegue che, ogni due chiamate, il valore degli argomenti quanto meno dimezza e dunque che, dopo al più 2n passi, la ricorsione termina.

Il costo computazionale dell'algoritmo di Euclide è O(n) operazioni sui bit, in quanto in ciascuno degli O(n) passi viene eseguita una divisione su numeri di al più n bit.

Tracciamento

function EuclidMCD(a, b)
    if b = 0 then
        return a
    end if
    return EuclidMCD(b, a mod b)

Nota bene

Per la limitazione che la lunghezza del messaggio M deve essere < N (modulo), scambiare in modo sicuro il protocollo simmetrico. RSA viene usato per una chiave da utilizzare in un esempio: AES.

Funzione hash

Insertion Sort

Studio del costo computazionale di algoritmi di sorting: O(n²) nel worst case scenario.

Insertion_sort(A)
    n = length(A)
    for j = 2 to n
        t = A[j]
        k = j - 1
        while k > 0 and t < A[k] do
            A[k + 1] = A[k]
            k--
        A[k + 1] = t

1) Scorri l'array con due indici: e --[k][j]-->
2) Ad ogni avanzamento controlla se a[j] < a[k] (elem. succ < del prec.?)

• A) Se a[j] > a[k], non fare nulla
• B) Se a[j] < a[k]: imposta a[k+1] = a[k] (al primo ciclo copia a[k] in a[j]), decrementa k, rifai il confronto del punto 2

3) a[k+1] = t (valore iniziale di a[j])
4) Incrementa j e riparti da 1

In sostanza, scorriamo l'array con due indici k e j = (k+1). Ad ogni avanzamento di j, k lo segue. Confrontiamo sempre j e k; se j < k, copiamo il valore in j sulla cella k e cominciamo a scorrere l'array indietro con k, ripetendo il confronto di cui sopra. In questo modo, appena viene trovato un valore fuori posto, questi (il più alto) viene spostato più a dx, e inizia una ricerca all'indietro in cui ogni valore trovato > del valore attuale, viene copiato nella cella successiva, risultando in uno slittamento dei valori verso dx >>. Quando smettiamo di trovare valori più grandi del val. attuale (o k == 0), copiamo il val. attuale alla posizione di k+1.

Merge Sort (Chiamate)

mergesort(A, l, r)
    if (l < r)
        m = (l + r) / 2
        mergesort(A, l, m)
        mergesort(A, m + 1, r)
        merge(A, l, r)

La procedura di merge ha un carico di lavoro costante per chiamata ricorsiva, O(k+l) per un tempo di esecuzione totale di. Dato che i merge sono lineari, il tempo di esecuzione totale di mergesort è:

Quick Sort

quicksort(A, l, r)
    if (l < r)
        q = partition(A, l, r)
        quicksort(A, l, q - 1)
        quicksort(A, q + 1, r)

partition(A, l, r)
    i = l
    j = r
    while (i < j)
        while (A[j] > A[i])
            j--
        if (i < j)
            scambia A[i] e A[j]
            i++
        while (A[i] < A[j])
            i++
        if (i < j)
            scambia A[i] e A[j]
            j--
    return i // (i == j)

Partition: Tempo di esecuzione T(n) = bn + a = Θ(n). Costo computazionale QS?

Studio completo del costo computazionale sulle slide quicksort.pdf.

Counting Sort

Counting sort, Radix Sort

Radix Sort

Il counting sort ha come limite il numero di elementi in input, ma può essere utilizzato intelligentemente assieme ad un altro algoritmo.

n = b
r = b/r

Supponiamo di ordinare grandi numeri di bit. Suddividere ogni numero in sotto-gruppi di dimensioni, inizio ad ordinarli dalla cifra meno alla più significativa. Otteniamo un algoritmo di ordinamento stabile su grandi numeri! Facciamo r passate, e ciascuna passata è un counting sort su numeri grandi. Tempo di esecuzione: posso scegliere r in modo che sia O(n). NB: al posto di radix sort, posso anche usare qualunque algoritmo di sorting che sia stabile.

Grafi: Definizioni

Grado di un vertice: Numero di archi che incidono su quel vertice (entrante uscente). Grado/Grado se i grafi sono orientati. Un cammino tra vertice A e C è una sequenza di archi che porta da A a C, ad esempio: A -> B -> C oppure A -> B -> D -> C.

Metodi di rappresentazione dei Grafi

• Matrice di adiacenza (m x n)
• 0 1: l'elemento i,j rappresenta il collegamento tra due nodi

Per le matrici non pesate: = non esiste, = esiste collegamento.

Grafi non orientati: Matrice simmetrica (se un elemento collega l'altro, è vero anche l'opposto).

Grafici orientati: Non necessariamente! Quadratica! Occupazione in.