Esame - #3 - 20 Mar 2023

[notedo]

Soluzione Prof

[ZGianluigi]

🟡 Codice giusto, ma calcolo del costo non va bene (vedi sotto soluzione costo) @rimaout

a) Pseudocodice:

def countValidNodes(r, sum=0, isRoot =True):
    # Se il nodo è nullo, restituisci 0 (nessun nodo valido)
    if r is None:
        return 0

    # Inizializza il conteggio dei nodi validi
    count = 0

    # Controlla se il nodo corrente è valido
    if r.key == sum or (isRoot and r.key == 0):
        count = 1

    # Aggiorna la somma degli antenati aggiungendo il valore del nodo corrente
    sum += r.key

    # Ricorsivamente conta i nodi validi nei sottoalberi sinistro e destro
    count += countValidNodes(r.left, sum, False)
    count += countValidNodes(r.right, sum, False)

    # Restituisci il conteggio totale dei nodi validi
    return count

b) Costo Computazionale:

Equazione di ricorrenza: $\ T(n) = 2T\left(\frac{n}{2}\right) + O(1) $ $\ T(n) = \theta(1) \$

$T(n) = 2T\left(\frac{n}{2}\right)$ è il tempo per processare i due sotto alberi $O(1)$ è il tempo totale per le operazioni non ricorsive

Metodo Master Theorem: $a=2$ $b =2$ $f(n)=O(1)$

Qui, $f(n) = O(1)$ quindi $c=0$ $log_b​a\=log_2​2\=1$

Confrontando $c$ con $log_b​a$: Se $c < \log_b a$, allora $T(n) = O(n^{\log_b a})$.

Quindi, $T(n) = O(n^{\log_2 2}) = O(n^1) = O(n)$.

In conclusione, il costo computazionale $T(n)$ della funzione countValidNodes è $O(n)$, dove n sono il numero di nodi dell'albero.

[rimaout]

Codice

def es(p, s_a = 0):
   # s_a è la somma degli antenati

    if p == None:    # se raggiungiamo una foglia, allora nodo non ha figli e non è valido
        return 0     # quindi ritorno zero e interrompo la ricorsione

    # se nodo è valido v = 1, se non è valido v = 0
    v = 0
    if s_a == p.key:
        v = 1

return v + es(p.left, s_a+p.key) + es(p.right, s_a+p.key)

Eq. Ricorrenza

L' equazione di ricorrenza è:

$\ T(n) = T(k) + T(n-1-k) + \theta(1) $ $\ T(1) = \theta(1) \$

dove $k$ indica il numero di nodi nel sotto albero sinistro e $n-1-k$ il numero di nodi del sotto albero destro.

oss: Non possiamo utilizzare come equazione di ricorrenza: $\ T(n) = 2T\left(\frac{n}{2}\right) + O(1) $ $\ T(1) = \theta(1) \$

Perché questo tipo di equazione si può utilizzare soltanto per gli alberi binari bilanciati (ovvero alberi che hanno metà nei nodi nel sotto albero sinistro e l'altra metà nel sotto albero destro).

Calcolo costo computazionale (Metodo Sostituzione)

• Vedi #66 o #64

[alem1105]

def es(t, somma = 0):
    if t == None:
        return 0
    val = 0
    if somma == t.key:
        val = 1
    return val + es(t.left, somma + t.key) + es(t.right, somma + t.key)