Tags:
create new tag
view all tags

Programma del corso di Algoritmi I (Informatica, 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
  • Un secondo esempio: ricerca di duplicati.

Rif. Capitolo 1: tutto. Paragrafi 1.1, 1.2 e 1.3 del libro [DFFI07].

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.3, 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: paragrafi 17.3 e 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

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

e) Alberi e grafi

  • Alberi
    • rappresentazioni indicizzate
    • rappresentazioni collegate
    • visite
  • I grafi come tipi di dati astratti
  • Definizioni e proprietÓ fondamentali
  • Rappresentazioni in memoria
    • matrice di adiacenza
    • liste di adiacenza
    • matrice di incidenza
    • lista di archi
  • Algoritmo di visita generica di un grafo
    • albero di copertura generato da una visita
    • analisi del tempo di esecuzione in funzione della rappresentazione usata
  • Algoritmi di visita in ampiezza e in profonditÓ (sia per grafi orientati che non)
    • implementazione ricorsiva della visita in profonditÓ
    • implementazioni iterative di entrambe le visite basate su code e pile
    • proprietÓ degli alberi di copertura ottenuti dalle visite
    • partizione degli archi indotta dalle visite
  • Calcolo delle componenti connesse in grafi non orientati

Rif. Capitolo 3: paragrafo 3.3. Capitolo 12: tutto tranne paragrafo 12.5. Appendice: paragrafo 17.5.1

Edit | Attach | Watch | Print version | History: r20 < r19 < r18 < r17 < r16 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r20 - 2009-01-20 - 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-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback