Frame del contenuto
Salta la navigazione con i breadcrumb
Home  freccia Capitolo 3. Divide et impera  freccia Panoramica, animazioni ed esercizi svolti

Panoramica, animazioni ed esercizi svolti

Panoramica del capitolo

In questo capitolo, introduciamo una delle tecniche più note per lo sviluppo di algoritmi efficienti, ovvero il paradigma del divide et impera. Per analizzare la complessità di algoritmi sviluppati facendo uso di tale tecnica, dimostreremo il teorema delle ricorrenze, che fornisce uno strumento potente per la ricerca della soluzione di relazioni di ricorrenza. Gli esempi che mostreremo in questo capitolo spazieranno dalla ricerca all'interno di un array, all'ordinamento, all'algebra di numeri interi e di matrici, alla geometria computazionale.

Animazioni

L'animazione che state per guardare è in inglese e lo pseudo-codice in essa incluso è la naturale traduzione in inglese di quello presente nel libro. Pensiamo che ciò possa fornirvi uno spunto per contestualizzare gli argomenti studiati durante il corso nella lingua più frequentemente usata nel mondo del lavoro e della ricerca nell'ambito dell'informatica.

  1. Potete guardare l'animazione Ordinamento per fusione di un array a e fusione di due segmenti adiacenti ordinati relativa al codice 3.1 di pagina 61 e al codice 3.2 di pagina 62.
  2. Potete guardare l'animazione Ricerca binaria di una chiave k in un array a con il paradigma del divide et impera relativa al codice 3.4 di pagina 66.
  3. Potete guardare l'animazione Moltiplicazione mediante la tecnica del divide et impera, dove Somma calcola l'addizione di al più tre numeri interi rappresentati come array, in tempo lineare relativa al codice 3.8 di pagina 75.
  4. Potete guardare l'animazione Vista anticipata di un albero binario relativa al codice 3.13 di pagina 92.
  5. Potete guardare l'animazione Algoritmo ricorsivo per stabilire se un albero binario è completamente bilanciato relativa al codice 3.14 di pagina 93.
  6. Potete guardare l'animazione Algoritmo ricorsivo per individuare i nodi cardine in un albero binario relativa al codice 3.15 di pagina 94.

Esercizi svolti

  1. Fate clic qui per il download del file PDF con lo svolgimento degli esercizi 3.1, 3.2, 3.5.





Pearson Italia S.p.A. © 2013, tutti i diritti riservati, P.I. 07415430011.
Privacy policy

Torna in cima alla pagina