Scribd Logo
Carica

Benvenuto in Scribd!

  • 0 visualizzazioni

    Esempio Scritto 6

    Caricato da

    firenatsuusa

    Copyright:

    © All Rights Reserved
    Scarica in formato PDF, TXT o leggi online su Scribd

    Esempio Scritto 6

    Caricato da

    firenatsuusa
    0 visualizzazioni2 pagine

    Titolo originale

    EsempioScritto6

    Copyright

    © © All Rights Reserved

    Formati disponibili

    PDF, TXT o leggi online da Scribd

    Hai trovato utile questo documento?

    Questo contenuto è inappropriato?

    Copyright:

    © All Rights Reserved
    Scarica in formato PDF, TXT o leggi online su Scribd
    Scarica in formato pdf o txt
    0 visualizzazioni2 pagine

    Esempio Scritto 6

    Caricato da

    firenatsuusa

    Copyright:

    © All Rights Reserved
    Scarica in formato PDF, TXT o leggi online su Scribd
    Scarica in formato pdf o txt
    Sei sulla pagina 1di 2

    Dati e Algoritmi (Pietracaprina): Esempio Scritto (6) 1

    PRIMA PARTE

    1. [4 punti] Siano A e B due algoritmi che risolvono lo stesso problema Π. Si definisca


    tX (n) la complessità al caso pessimo di X e tX,i il numero di operazioni eseguite da
    X per risolvere l’istanza i, per X ∈ {A, B}. Sapendo che tB,i ≥ (1/10)tA,i per ogni
    i, e che tA (n) ∈ Θ (n2 ), cosa si può dire di tB (n)? Motivare la risposta.

    2. [4 punti] Si consideri l’array di entry: P = [(11, ∗), (9, ∗), (7, ∗), (13, ∗), (3, ∗), (4, ∗)],
    e l’approccio bottom-up per la costruzione di uno heap a partire da P . Mostrare
    l’albero associato all’array alla fine di ogni iterazione dell’approccio bottom-up. (È
    sufficiente mostrare le chiavi delle entry.)

    3. [4 punti] Si faccia riferimento alle implementazioni della Mappa basate su Alberi


    Binari di Ricerca (ABR) e (2,4)-Tree.

    (a) Descrivere brevemente ma in modo preciso come il (2,4)-Tree generalizza l’ABR.


    (b) Quali sono i vantaggi dell’implementazione della Mappa con (2,4)-Tree rispetto
    a quella con ABR?

    4. [4 punti] Sia S una sequenza di n chiavi intere da ordinare. Dire quale tra gli
    algoritmi di ordinamento che conoscete usereste nei seguenti casi, specificando la
    complessità risultante: (i) le chiavi da ordinare appartengono all’intervallo [1, n2 ];
    (ii) esistono 3 chiavi, tolte le quali S risulta già ordinata. Motivare le risposte.
    Dati e Algoritmi (Pietracaprina): Esempio Scritto (6) 2

    SECONDA PARTE

    1. [5 punti] Siano [a0 , b0 ], [a1 , b1 ], . . . , [an−1 , bn−1 ] n intervalli sulla retta reale, con ai <
    bi . Gli intervalli sono ordinati in base all’estremo sinistro (a0 ≤ a1 ≤ · · · ≤ an−1 )
    ma possono sovrapporsi. Il seguente ciclo determina la lunghezza massima di un
    segmento continuo della retta reale coperto interamente dagli intervalli.
    Acurr ← a0 ; Bcurr ← b0 ; max length ← (b0 − a0 );
    for i ← 1 to n − 1 do
    if (ai > Bcurr) then
    Acurr ← ai ;
    Bcurr ← bi ;
    else Bcurr ← max{Bcurr, bi };
    max length ← max{max length, Bcurr − Acurr};
    return max length
    Trovare un invariante per il ciclo for, che specifichi che cosa rappresentano le variabili
    Acurr, Bcurr, max length alla fine di ciascuna iterazione.

    2. [6 punti] Sia T un albero binario proprio dove ogni nodo v ∈ T contiene un valore
    binario. Un nodo v ∈ T si dice 3-balanced, se |n0 (v) − n1 (v)| ≤ 3, dove n0 (v) e
    n1 (v) denotano il numero di 0 (n0 (v)) e 1 (n1 (v)) nel sottoalbero Tv . Si progetti in
    pseudocodice un algoritmo ricorsivo All3Balanced per determinare se tutti i nodi di
    T sono 3-balanced, con complessità lineare nel numero di nodi di T .

    3. [5 punti] Sia G = (V, E) un grafo non diretto, non pesato e connesso, con n = |V | e
    m = |E|, dove ogni vertice v ha un bit v.C che vale 1 se v è un centro, e 0 altrimenti.
    Sia C ⊂ V l’insieme dei centri e k = |C|. Progettare in pseudocodice un algoritmo
    che dato un tale grafo G calcoli, per ogni vertice v ∈ V , la distanza dal centro più
    vicino a lui, ovvero mins∈C d(v, s), dove d(v, s) è il numero di archi nel cammino
    minimo da v a s, memorizzandola in un campo v.distC. Analizzare la complessità
    dell’algoritmo (per avere punteggio massimo deve essere O (km)).

    Potrebbero piacerti anche