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

Quarto laboratorio (6 dicembre 2007)

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 10KB)
• Esempio di input
• Prima approssimazione: definizione delle strutture dati e struttura generale del programma
• Seconda approssimazione: interpretazione della linea di comando, caricamento dei dati, allocazione e deallocazione delle strutture dati, stampa dei risultati
• Terza approssimazione: algoritmo esaustivo
• Quarta approssimazione: algoritmo progettato per induzione (praticamente identico al precedente)
• Quinta approssimazione: rafforzamento dell'ipotesi induttiva per semplificare il passo induttivo: si prende ogni volta l'intervallo con primo estremo minimo, in modo da eliminare il controllo sul primo estremo di ogni frammento
• Sesta approssimazione: rafforzamento dell'ipotesi induttiva per semplificare il passo induttivo: si calcola e si aggiorna il valore del massimo secondo estremo, in modo da semplificare il relativo controllo
• Settima approssimazione: scelta di una struttura dati più adeguata: per prendere ogni volta l'intervallo con primo estremo minimo, si costruisce e aggiorna uno heap

Pagina aggiornata il