Università degli Studi di Urbino Carlo Bo / Portale Web di Ateneo


ALGORITMI E STRUTTURE DATI

A.A. CFU
2008/2009 7
Docente Email Ricevimento studenti
Valerio Freschi giovedi 15:00-17:00

Assegnato al Corso di Studio

Giorno Orario Aula

Obiettivi Formativi

Il Corso ha lo scopo di illustrare le principali tecniche di progettazione di algoritmi e di descrivere ed analizzare gli algoritmi di base più diffusi e le strutture dati in essi utilizzate, con particolare riferimento agli aspetti di complessità computazionale e di correttezza.

Programma

01. Introduzione agli algoritmi e alle strutture dati:
01.01 Algoritmi e loro tipologie.
01.02 Correttezza di un algoritmo rispetto ad un problema.
01.03 Complessità di un algoritmo rispetto all'uso di risorse.
01.04 Strutture dati e loro tipologie.

02. Classi di problemi:
02.01 Problemi decidibili e indecidibili.
02.02 Problemi trattabili e intrattabili.
02.03 Teorema di Cook.
02.04 NP-completezza.

03. Complessità degli algoritmi:
03.01 Notazioni per esprimere la complessità asintotica.
03.02 Calcolo della complessità di algoritmi non ricorsivi.
03.03 Calcolo della complessità di algoritmi ricorsivi.

04. Algoritmi per array:
04.01 Array: definizioni di base e problemi classici.
04.02 Algoritmo di visita per array.
04.03 Algoritmo di ricerca lineare per array.
04.04 Algoritmo di ricerca binaria per array ordinati.
04.05 Criteri di confronto per algoritmi di ordinamento per array.
04.06 Insertsort.
04.07 Selectsort.
04.08 Bubblesort.
04.09 Mergesort.
04.10 Quicksort.
04.11 Heapsort.

05. Algoritmi per liste:
05.01 Liste: definizioni di base e problemi classici.
05.02 Algoritmi di visita, ricerca, inserimento e rimozione per liste.
05.03 Algoritmi di inserimento e rimozione per code.
05.04 Algoritmi di inserimento e rimozione per pile.

06. Algoritmi per alberi:
06.01 Alberi: definizioni di base e problemi classici.
06.02 Algoritmi di visita e ricerca per alberi binari.
06.03 Algoritmi di ricerca, inserimento e rimozione per alberi binari di ricerca.
06.04 Criteri di bilanciamento per alberi binari di ricerca.
06.05 Algoritmi di ricerca, inserimento e rimozione per alberi binari di ricerca rosso-nero.

07. Algoritmi per grafi:
07.01 Grafi: definizioni di base e problemi classici.
07.02 Algoritmi di visita e ricerca per grafi.
07.03 Algoritmo di ordinamento topologico per grafi diretti e aciclici.
07.04 Algoritmo delle componenti fortemente connesse per grafi.
07.05 Algoritmo di Kruskal.
07.06 Algoritmo di Prim.
07.07 Proprietà del percorso più breve.
07.08 Algoritmo di Bellman-Ford.
07.09 Algoritmo di Dijkstra.
07.10 Algoritmo di Floyd-Warshall.

08. Algoritmi per stringhe:
08.01 Stringhe: definizioni di base e problemi classici.
08.02 Algoritmo ingenuo di string matching.
08.03 Algoritmo per il calcolo della distanza di edit tra stringhe.
08.04 Algoritmo per il calcolo della massima sottosequenza comune.

09. Tecniche algoritmiche:
09.01 Tecnica del divide et impera.
09.02 Programmazione dinamica.
09.03 Tecnica golosa.
09.04 Tecnica per tentativi e revoche.

10. Attività di laboratorio:
10.01 Valutazione sperimentale della complessità degli algoritmi.
10.02 Confronto sperimentale degli algoritmi di ordinamento per array.
10.03 Confronto sperimentale degli algoritmi di ricerca per alberi binari.

Eventuali Propedeuticità

Programmazione degli Elaboratori, Analisi Matematica.

Modalità Didattiche, Obblighi, Testi di Studio e Modalità di Accertamento

Modalità didattiche

Lezioni frontali ed esercitazioni di laboratorio

Obblighi

 Nessuno.

Testi di studio

Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", MIT Press, 2001
(Cormen, Leiserson, Rivest, Stein, "Introduzione agli Algoritmi e alle Strutture Dati", McGraw-Hill, 2005).

Demetrescu, Finocchi, Italiano, "Algoritmi e Strutture Dati", McGraw-Hill, 2004.

Crescenzi, Gambosi, Grossi, "Strutture di Dati e Algoritmi", Pearson/Addison-Wesley, 2006.

Sedgewick, "Algorithms in C", Addison-Wesley, 1997
(Sedgewick, "Algoritmi in C", Pearson/Prentice Hall, 2002).

Modalità di
accertamento

Progetto individuale di laboratorio, prova scritta e prova orale .

Note

Il corso è erogato sia nel "percorso in presenza" che nel "percorso online" del Corso di Laurea di Informatica Applicata.

« torna indietro Ultimo aggiornamento: 14/07/2008


Condividi


Questo contenuto ha risposto alla tua domanda?


Il tuo feedback è importante

Raccontaci la tua esperienza e aiutaci a migliorare questa pagina.

Se sei vittima di violenza o stalking chiama il 1522

Il 1522 è un servizio pubblico promosso dalla Presidenza del Consiglio dei Ministri – Dipartimento per le Pari Opportunità. Il numero, gratuito è attivo 24 h su 24, accoglie con operatrici specializzate le richieste di aiuto e sostegno delle vittime di violenza e stalking.

Posta elettronica certificata

amministrazione@uniurb.legalmail.it

Social

Performance della pagina

Università degli Studi di Urbino Carlo Bo
Via Aurelio Saffi, 2 – 61029 Urbino PU – IT
Partita IVA 00448830414 – Codice Fiscale 82002850418
2021 © Tutti i diritti sono riservati

Top