Tags:
create new tag
view all tags

Programma del Corso A.A. 2005/06 (Provvisorio)

Gli argomenti in rosso sono per il solo canale Informatica

Gli argomenti in blu sono per il solo canale Tecnologie Informatiche

a) Richiami di concetti fondamentali

  • Specifica di algoritmi; astrazione dei dati.
  • Progettazione, validazione, analisi e verifica di algoritmi.
  • Esempi di progetto di algoritmi.

b) Analisi di algoritmi

  • Analisi di algoritmi: analisi del caso peggiore, medio, migliore.
  • Ordine di grandezza delle funzioni, notazione asintotica.
  • Algebra della notazione asintotica; analisi delle costanti additive e moltiplicative.
  • Richiamo degli algoritmi di ordinamento Bubble, Selection e Insertion Sort.
  • Calcolo della complessitÓ degli algoritmi di ordinamento in forma iterativa.
  • Alberi di decisioni, limiti inferiori per l'ordinamento.
  • Il concetto di stabilitÓ nell'ordinamento.
  • Ordinamento in tempo O(n): ordinamento per conteggio.
  • Algoritmi ricorsivi.
  • Confronto fra implementazione ricorsiva e iterativa di uno stesso algoritmo.
  • Risoluzione di ricorrenze per iterazione e tramite albero.
  • Calcolo della complessitÓ nel caso peggiore dell'algoritmo di mergesort in forma ricorsiva.
  • Calcolo della complessitÓ nel caso peggiore e migliore dell'algoritmo quicksort in forma ricorsiva.

c) Strutture dati:

  • Gli alberi come tipi di dati astratti. Alberi binari, alberi m-ari.
  • Rappresentazione in memoria di alberi: rappresentazione tramite vettore o tramite struttura linkata; vettore dei padri. Rappresentazione degli alberi m-ari come alberi binari.
  • Generazione del codice di Prufer in tempo lineare. Ricostruzione di un albero a partire dal codice di Prufer in tempo lineare.
  • Visita di un albero per livelli.
  • Pile e code: notazione infissa e postfissa; passaggio da notazione infissa a postfissa; calcolo dell'espressione in notazione postfissa.
  • Heap e code di prioritÓ: costruzione di un heap, operazioni di inserimento e cancellazione.
  • Heapsort.
  • Calcolo della complessitÓ nel caso peggiore dell'algoritmo heapsort in forma iterativa e ricorsiva.
  • I grafi come tipi di dati astratti.
  • Rappresentazione in memoria di un grafo: matrici e liste di adiacenza; matrici di incidenza; lista di archi. Ordinamento in tempo lineare di una lista di adiacenza.
  • Visita di un grafo: visita in ampiezza e in profonditÓ.
  • Alberi ricoprenti.
  • Caratterizzazione di alberi ricoprenti ottenuti per visite in ampiezza e profonditÓ.
  • Numerazione dei nodi degli alberi di copertura rispetto alla visita eseguita.
  • Partizione degli spigoli degli alberi di copertura rispetto alla visita eseguita.

d) Algoritmi su alberi e su grafi:

  • Generazione del grafo complemento e del grafo trasposto.
  • Ricerca delle componenti connesse di un grafo.
  • Ricerca dei cammini minimi da sorgente singola.
  • Come verificare se un grafo Ŕ bipartito o aciclico.
  • Caratterizzazione dei grafi bipartiti.
  • Ricerca di un accoppiamento massimale in un grafo.
  • Ricerca delle componenti debolmente e fortemente connesse in un grafo orientato.
  • Ricerca delle componenti biconnesse.
  • 2 algoritmi per la generazione di un ordinamento topologico.

e) Gestione di dizionari:

  • Alberi binari di ricerca : operazioni di ricerca, inserimento e cancellazione.
  • Ricerca del max, del min, del predecessore e del successore in un albero binario di ricerca.
  • Confronto della complessitÓ delle operazioni di base sulle diverse strutture dati analizzate.
  • Alberi di ricerca bilanciati: alberi AVL.
  • Computo del fattore di bilanciamento.
  • Calcolo delle limitazioni inferiori e superiori per l'altezza di un albero AVL.
  • Operazioni di rotazione per ribilanciare un albero AVL dopo l'inserimento e la cancellazione.
  • B-alberi: definizione, inserimento e cancellazione. Altezza di un B-albero.

Riferimenti bibliografici:

  • Alsuwaiyel, Algorithms - Design Techniques and Analysis, Word Scientific, 1999.
  • Cormen T.H., Leiserson C.E. e Rivest R.L., Introduction to Algorithms, Mc Graw Hill, 1990.
  • Demetrescu C., Finocchi I. e Italiano G.F., Algoritmi e Strutture Dati, Mc Graw Hill, 2004.
  • Horowitz E. , Sahni S. e S.Anderson-Freed, Strutture Dati in C , Mc Graw Hill, 1993.
  • Appunti del corso in rete.

Programma del Corso A.A. 2003/04

Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r3 - 2005-12-20 - TizianaCalamoneri






 
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