Tags:
create new tag
view all tags

Programma del corso di Introduzione agli Algoritmi (canale EO, A.A. 2008-2009)

Se non diversamente specificato, i riferimenti bibliografici sono relativi al libro di testo "Algoritmi e strutture dati", 2/ed. Demetrescu, Finocchi, Italiano, McGraw-Hill, 2008.

a) Introduzione

  • Progettazione ed analisi di algoritmi
    • verifica di correttezza
    • analisi del tempo di esecuzione
    • analisi dell'occupazione di memoria
  • Un esempio "giocattolo": il calcolo dei numeri di Fibonacci

Rif. Capitolo 1: tutto.

b) Metodologie di analisi

  • Ordine di grandezza delle funzioni, la notazione asintotica O, Omega, Theta
  • Algebra della notazione asintotica; analisi delle costanti additive e moltiplicative
  • Delimitazioni inferiori e superiori alla complessitā di un problema rispetto ad una data risorsa di calcolo
  • Analisi nel caso peggiore e migliore
  • Analisi di algoritmi ricorsivi:
    • equazioni di ricorrenza, albero della ricorsione
    • risoluzione di ricorrenze tramite analisi dell'albero della ricorsione
    • metodo dell'iterazione
    • metodo della sostituzione
    • il teorema fondamentale delle ricorrenze (teorema master): enunciato ed esempi.

Rif. Capitolo 2: paragrafi 2.2, 2.3, 2.4 (tranne caso medio), 2.5. Appendice: paragrafi 17.1, 17.2, 17.4

c) Algoritmi di ricerca e di ordinamento

  • Ricerca sequenziale e binaria: analisi nel caso peggiore e migliore.
  • Delimitazione inferiore al tempo di esecuzione di algoritmi di ordinamento basati su confronti: alberi di decisione
  • Algoritmi di ordinamento quadratici (con analisi nel caso peggiore): insertionSort, selectionSort, bubbleSort
  • Un algoritmo di ordinamento ottimo basato sulla tecnica del divide et impera (con analisi nel caso peggiore): mergeSort
  • Un algoritmo di ordinamento ottimo basato sull'uso di strutture dati efficienti (con analisi nel caso peggiore): heapSort
    • la struttura dati heap
    • cancellazione del minimo e costruzione di un heap in tempo lineare
    • rappresentazione posizionale di alberi binari
    • ordinamento in loco
  • Un algoritmo efficiente nel caso medio: quickSort (analisi nel caso peggiore, intuizione caso medio)
  • Il concetto di stabilitā nell'ordinamento.
  • Ordinamento in tempo lineare: algoritmi intergerSort e bucketSort

Rif. Capitolo 2: paragrafo 2.4 (tranne caso medio). Capitolo 4: tutto tranne paragrafo 4.7. Appendice: paragrafo 17.4. Paragrafi 7.1, 7.2 e 7.4.1 del libro [CLRS01].

d) Dizionari

  • Implementazioni banali: array ordinati e liste collegate
  • Alberi binari di ricerca:
    • operazioni search, insert, delete
    • ricerca del massimo, del minimo, del predecessore e del successore
  • Bilanciamento in altezza: alberi AVL
    • calcolo del fattore di bilanciamento
    • limitazione superiore all'altezza di un albero AVL
    • rotazioni semplici e doppie
    • mantenimento del bilanciamento durante inserimenti e cancellazioni * Tabelle ad accesso diretto * Tabelle hash
    • funzioni hash perfette
    • uniformitā semplice
    • paradosso del compleanno e collisioni
    • liste di collisione
    • indirizzamento aperto: scansione lineare, quadratica e doppia

Rif. Capitolo 3: paragrafo 3.1. Capitolo 6: paragrafi 6.1 e 6.2. Capitolo 7: tutto.

e) Strutture dati elementari ed alberi

  • Alberi: definizioni e proprietā fondamentali
  • Rappresentazioni in memoria
    • strutture indicizzate
    • strutture collegate
  • Algoritmo di visita generica di un albero
    • analisi del numero di iterazioni
    • tempo di esecuzione in funzione della rappresentazione usata
  • Richiami a pile e code
  • Visita in profonditā (implementazione iterativa e ricorsiva)
    • visita preorder, simmetrica e postorder
    • esempi di applicazione delle visite
  • Visita in ampiezza

Rif. Capitolo 3: tutto (tranne la tecnica del raddoppiamento-dimezzamento nel paragrafo 3.1).

Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r3 - 2009-05-26 - IreneFinocchi






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback