Ricorsione

Question 1

Una funzione ricorsiva può essere…

Answer 1

diretta o indiretta

Question 2

Una soluzione è ricorsiva se può essere espressa come…

Answer 2

S(D) = f(S(D’))
S(D_0) = S_0

Question 3

In S(D) = f(S(D’)), S(D_0) = S_0 cosa indica l’ultima condizione?

Answer 3

Indica che ogni algoritmo deve terminare e che la ritorsione ha un numero di passi finito

Question 4

In che modo la dimensione n dei dati si può ridurre in una chiamata ricorsiva?

Answer 4

Si può ridurre di un valore costante (decrease) o di un fattore costante (divide)

Question 5

Da cosa è data la complessità nel tempo?

Answer 5

T(n) = D(n) + T(n’) + C(n)

Question 6

Qual è la forma generale della complessità nel tempo di una ricorsione divide and conquer e di una decrease and conquer?

Answer 6

• divide: T(n) = D(n) + aT(n/b) + C(n)
• decrease: T(n) = D(n) + sum_{i = 0} ^ {a-1} (n - k_i) + C(n)

Question 7

Definizione di Stack

Answer 7

ADT che supporta operazioni di push e pop, tipo LIFO

Question 8

Definizione e caratteristiche di stack frame

Answer 8

Struttura dati che contiene parametri formali, viabili locali, indirizzi di ritorno della funzione, puntatore al codice della funzione. Viene creato e distrutto a ogni chiamata e se ce ne sono troppi può esserci stack overflow. Gli stack frame vengono memorizzati nello stack di sistema

Question 9

cosa contiene lo SP

Answer 9

indirizzo del primo SF disponibile

Question 10

come crescono gli indirizzi dello stack?

Answer 10

da maggiori a minori

Question 11

definizione e caratteristiche di funzione tail-recursive

Answer 11

funzione in cui la chiamata ricorsiva è l’ultima operazione
- solo discesa -> più efficiente
- la chiamata successiva sostituisce la precedente
- no stack overflow
- no stack -> trasformabile direttamente in iterativa

Question 12

Caratteristiche del merge sort (no complessità)

Answer 12

• il vettore viene diviso ogni volta al centro
• chiamata ricorsiva nel vettore sx e dx
• terminazione: quando il vettore ha un solo elemento -> ordinato
• fusione dei due sottovettori (lì avviene il vero e proprio ordinamento)
• stabile, non in loco

Question 13

Complessità del merge sort

Answer 13

libro, comunque NlogN

Question 14

caratteristiche del quicksort (no complessità)

Answer 14

• divisione non per forza al centro
• partizione con pivot
• in loco, non stabile
• terminazione: sottovettore di un elemento

Question 15

complessità del quick sort e della partiton

Answer 15

• partition: theta(n)
• quick, caso peggiore: un sottovettore di n-1 elementi e l’altro di un solo elemento, il pivot è il min o il max -> O(n^2)
• quick, caso medio e migliore: sottovettori di n/2 -> O(nlogn)

Question 16

codice della void MergeSort(Item *A, int N) e quindi delle void MergeSortR(Item *A, Item *B, int l, int r) e void Merge(Item *A, Item *B, int l, int q, int r)

Answer 16

appunti

Question 17

codice della void QuickSort(Item *A, int N) e quindi delle void QuickSortR(Item *A, int l, int r) e int partition(Item *A, int l, int r)

Answer 17

appunit