Resumos

Consiste nel risolvere uin problema mediante un'accorta suddivisione di esso in più sotto-problemi.

Più precisamente, si risolvono ricorsivamente i k sotto-problemi individuati e si utilizzano le loro soluzioni per determinare quella del problema originale.

La ricorsione si interrompe quando le dimensioni dei sotto-problemi sono banalmente risolvibili.

Problemi risolvibili con questa tecnica sono ad esempio: ricerca binaria, Fibonacci, ecc.

In generale, un problema è caratterizzato dai seguenti elementi:

1. i dati che costituiscono l'istanza del problema che si deve risolvere
2. ciò che si deve determinare, cioè i risultati la cui determinazione fornisce la soluzione del problema
3. le relazioni (proprietà che legano i dati di input ai risultati e costituiscono la struttura del problema