Università degli Studi di Milano	Polo Didattico e di Ricerca di Crema	Dipartimento di Tecnologie dell'Informazione
Home page	Teaching page

Quinto laboratorio

Si tratta di applicare in pratica la metodologia di progettazione di algoritmi attraverso l'induzione matematica.

La spiegazione dettagliata dell'algoritmo si trova nell'articolo di Manber (PDF da 1553KB).

• Un'applicazione (file PDF da 12KB)
• Esempio di input
• Prima approssimazione: definizione delle strutture dati e struttura generale del programma, interpretazione della linea di comando, caricamento dei dati, allocazione e deallocazione delle strutture dati, stampa dei risultati
• Seconda approssimazione: algoritmo esaustivo iterativo
• Terza approssimazione: algoritmo ricorsivo progettato per induzione (equivalente al precedente)
• Quarta approssimazione: algoritmo ricorsivo con divisione del problema in due parti di ugual dimensione, scelte in modo intelligente (linea verticale) e operazioni di Combina semplificate dall'osservazione che non tutti i punti e non tutte le coppie di punti vanno considerate
• Quinta approssimazione: rafforzamento dell'ipotesi induttiva per semplificare il passo induttivo: l'ordinamento rispetto all'ordinata viene fatto ricorsivamente, anziché nella Combina

Pagina aggiornata il