• Non ci sono risultati.

Si discuta se la complessit`a ottenuta rappresenti un limite inferiore per il problema

N/A
N/A
Protected

Academic year: 2021

Condividi "Si discuta se la complessit`a ottenuta rappresenti un limite inferiore per il problema"

Copied!
1
0
0

Testo completo

(1)

008AA – ALGORITMICA E LABORATORIO Quinto Appello 21 gennaio 2019

Cognome Nome: N. Matricola: Corso: A B

Esercizio 1. (4+3+3 punti) E dato un array A di interi di dimensione N = n × n:`

1. Si definisca un algoritmo ricorsivo basato sulla tecnica Divide et Impera che calcoli la somma degli ele- menti di A e la cui complessit`a in tempo al caso pessimo obbedisca all’equazione di ricorrenza:

T (n) = 4T (n/2) + Θ(1)

2. Si risolva l’equazione di ricorrenza.

3. Si discuta se la complessit`a ottenuta rappresenti un limite inferiore per il problema.

Esercizio 2. (4+4) Si mostri la tabella di Programmazione Dinamica per il problema della Edit Distance tra due stringhe S1 = ALTERO e S2 = LALTRO, e si indichino tutte le soluzioni ottime.

Esercizio 3. (4+4 punti) Si consideri il seguente problema decisionale e NP-completo Partizione:

Data un insieme di interi positivi S = s1, ..., sn, esiste un sottoinsieme S0⊆ S tale che la somma degli elementi che appartengono a S0 sia uguale alla somma degli elementi che appartengono a S − S0?

1. Si indichi un certificato polinomiale per il problema Partizione.

2. Si definisca un algoritmo esponenziale di risoluzione del problema Partizione.

Esercizio 4. (4 punti) Si spieghi il motivo per cui la struttura dati Heap pu`o essere memorizzata in esattamente n locazioni di memoria.

Riferimenti

Documenti correlati

Area del triangolo: 6 problemi semplici con triangoli generici. Problema 3). Calcola l'area di un triangolo che ha l'altezza di 24 cm e la base uguale ai

Per concludere, in Figura 5.1 troviamo i profili di convergenza del metodo della falsa posizione applicato all’equazione di Kepler con M = π/4 ed ec- centricità una volta e = 0.2

nell’allineamento: caratteri uguali hanno distanza zero, indicata con Ø (match); caratteri diversi hanno distanza 1 (mismatch); un carattere allineato a uno spazio ha distanza

Si mostri la matrice di programmazione dinamica per il calcolo della Edit Distance tra le stringhe x = ARSO e y = IROSO, dove ogni operazione di editing (inserzione,

(4+4) Si definisca la relazione che consente di calcolare mediante Programmazione Dinamica la Edit Distance di due stringhe S1 e S2, nell’ipotesi che l’errore di mismatch abbia costo

Tutte e quattro le fenditure giacciono nello stesso piano (quello della figura)... Traccia

Cosa si intende per “predizione con modelli regressivi”: sulla base di dati noti, si identi…ca quantitativamente il legame tra certi fattori X 1 ; :::; X d ed una variabile da predire

[r]