ALGORITMI 2 - INFORMATICA (2007/08)
Nel primo corso di algoritmi sono state affrontate alcune tecniche comuni di programmazione come il metodo divide et impera, la randomizzazione e le soluzioni delle ricorrenze. Nel corso di Algoritmi e Strutture Dati 2 vengono tratti importanti tecniche avanzate per la progettazione di algoritmi: la programmazione dinamica e la programmazione greedy. Entrambe vengono applicate per la risoluzione di problemi di ottimizzazione. Unitamente verranno anche trattati alcuni algoritmi avanzati su grafi per il calcolo dei cammini minimi da singola sorgente e tra tutte le coppie, e verrà introdotta una nuova struttura dati efficiente per l'implementazione di dizionari: le tabelle Hash.Ricevimento studenti
Gli studenti possono chiedere informazioni o chiarimenti presso lo studio M21 Blocco III, Dip. di Matematica e Informatica, secondo i seguenti orari:- Venerdì : 11:00-13:00
Orario delle lezioni
Primo Semestre- lunedì, dalle 15:00 alle 17:00
- venerdì, dalle 15:00 alle 17:00
Bacheca Avvisi (ultimo avviso inserito giorno 15 settembre 2008)
- Risultati II appello - sessione Autunnale
Di seguito sono riportati i voti realtivi al primo appello della sessione autunnale di giorno 7 novembre 2008. Sono riportati esclusivamente i voti degli studenti che hanno raggiunto la sufficienza. Gli orali si svolgeranno Lunedì 20 ottobre a partire dalle ore 11:00 presso lo studio del docente.
Saeli 22
Truppia 20
Nucifora 18
Guran 18
Scuderi 26
Greco 22
- Risultati I appello - sessione Autunnale
Di seguito sono riportati i voti realtivi al primo appello della sessione autunnale di giorno 17 settembre 2008. Sono riportati esclusivamente i voti degli studenti che hanno raggiunto la sufficienza. Gli orali si svolgeranno Mercoledì 24 settembre a partire dalle ore 11:00 presso lo studio del docente.
Giannone 18
Giustolisi 20
Manzella 18
Marchesini 23
Saeli 18
Zarbano 25
- Esami orali di giorno 25 luglio
Si avvisano gli studenti che gli esami orali previsti per giorno 25 luglio si svolgeranno a partire dalle ore 16:00. - Risultati II appello - sessione Estiva
Di seguito sono riportati i voti realtivi al secondo appello della sessione estiva di giorno 15 luglio 2008. Sono riportati esclusivamente i voti degli studenti che hanno raggiunto la sufficienza. Gli orali si svolgeranno Venerdì 25 giugno a partire dalle ore 11:00 presso lo studio del docente.
Russo Carlo 22
Ridolfo Alfonso 18
Carista Giuseppe 25
Allone Antonio 19
Programma del Corso
- Hashing
- Tavole ad indirizzamento diretto
- Tavole Hash
- Risoluzione delle collisioni medinte concatenamento ed analisi
- Funzioni Hash
- Il metodo della divisione e della moltiplicazione
- Hashing Universale
- Indirizzamento aperto
- Ispezione lineare, quadratica e doppio hashing
- Analisi dell'hashing ad indirizzamento aperto
- B-Alberi
- Introduzione ai B-Alberi
- Strutture di dati nella memoria secondaria
- Definizione dei B-Alberi
- Operazioni fondamentali con i B-Alberi: Ricerca, Inserimento e Cancellazione
- Programmazione Dinamica
- Introduzione alla programmazione dinamica
- Programmazione delle catene di montaggio
- Moltiplicare una sequenza di matrici
- Elementi della programazione dinamica
- La piu' lunga sottosequenza comune
- Algoritmi Greedy
- Introduzione agli algoritmi Greedy
- Problema della selezione di atività
- Elementi della strategia Greedy
- I codici di Huffman
- Cammini minimi da sorgente singola
- Definizione e proprietà dei cammini minimi
- L'algoritmo di Bellman-Ford
- Cammini minimi da sorgente singola in grafi orientati e aciclici
- Algoritmo di Dijkstra
- Cammini minimi fra tutte le coppie
- Introduzione al problema
- Cammini minimi e moltiplicazione di matrici
- Algoritmo di Floyd-Warshall
- Algoritmo di Johnson per grafi sparsi
Appunti e dispense
- Esercizi su tabelle hash
il seguente file contiene una serie di esercizi sulle tabelle hash.
[Scarica il file (93.18 Kb)] - Esercizi sulla Programmazione Dinamica
il seguente file contiene una serie di esercizi sulla Programmazione Dinamica.
[Scarica il file (85.97 Kb)] - Esercizi sulla Programmazione Greedy
il seguente file contiene una serie di esercizi sulla Programmazione Greedy.
[Scarica il file (38.93 Kb)] - Esercizi sulla Programmazione Dinamica e Greedy
il seguente file contiene una serie di esercizi sulla programmzione dinamica e sulla programmazione greedy
[Scarica il file (73.35 Kb)] - Esercizi : Cammini minimi su Grafi
il seguente file contiene una serie di esercizi sui cammini minimi su grafi orientati e pesati.
[Scarica il file (23.40 Kb)]
Libri consigliati
- Titolo: Introduzione agli algoritmi e strutture dati
- Autore: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- Editore: MacGraw-Hill
- Descrizione:
Questo testo, già conosciuto nella precedente edizione italiana, è considerato uno dei più aggiornati e completi sulla materia. Concepito per essere utilizzato principalmente in ambito universitario, per la completezza degli argomenti trattati e in particolare perchè si occupa di tecniche ingegneristiche di progettazione degli algoritmi, si presta a essere utilizzato anche da un pubblico di professionisti. L'ampia possibilità di scelta degli argomenti trattati permette ai docenti di scegliere il percorso formativo che ritengono più idoneo, lasciando al singolo studente la possibilità di approfondire successivamente i temi affrontati durante la lezione. In ogni capitolo, dove i concetti vengono introdotti partendo dai più semplici per arrivare poi ai più avanzati, sono presentati una classe di algoritmi, le relative tecniche di progettazione, un'area di applicazioni e gli argomenti correlati. Gli autori, ritenendo importante il concetto di "efficienza", hanno incluso anche l'analisi dei tempi di esecuzione di ciascun algoritmo. Corredano il testo circa 900 esercizi e 140 problemi, costituiti da casi di studio che spesso introducono nuovi argomenti.
Appelli ed Esami
La prenotazione all'esame deve essere effettuata attraverso il Portale CEA.La lista completa degli appelli del Corso di Laurea è consultabile al seguente indirizzo.
- 08 febbraio 2008
- 26 febbraio 2008
- 17 giugno 2008
- 15 luglio 2008
- 17 settembre 2008
- 7 ottobre 2008