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


ALGORITMI E STRUTTURE DATI

A.A. CFU
2006/2007 7
Docente Email Ricevimento studenti
Marco Bernardo mercoledì 16:30-19: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 Classi P ed NP. 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 Il problema della ricerca. 04.02 Algoritmo di ricerca lineare. 04.03 Algoritmo di ricerca binaria. 04.04 Il problema dell'ordinamento. 04.05 Insertsort. 04.06 Selectsort. 04.07 Bubblesort. 04.08 Mergesort. 04.09 Quicksort. 04.10 Heapsort. 05. Algoritmi per liste, code e pile: 05.01 Algoritmi di visita, ricerca, inserimento e rimozione per liste. 05.02 Algoritmi di inserimento e rimozione per code. 05.03 Algoritmi di inserimento e rimozione per pile. 06. Algoritmi per alberi: 06.01 Trasformazione di alberi generali in alberi binari. 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 Rappresentazione di grafi con liste e matrici di adiacenza. 07.02 Algoritmi di visita e ricerca per grafi. 07.03 Il problema dell'ordinamento topologico. 07.04 Il problema delle componenti fortemente connesse. 07.05 Il problema dell'albero ricoprente minimo. 07.06 Algoritmo di Kruskal. 07.07 Algoritmo di Prim. 07.08 Il problema del percorso pi? breve. 07.09 Algoritmo di Bellman-Ford. 07.10 Algoritmo di Dijkstra. 07.11 Algoritmo di Floyd-Warshall. 08. Tecniche algoritmiche: 08.01 Tecnica del divide et impera. 08.02 Programmazione dinamica. 08.03 Tecnica golosa. 08.04 Tecnica per tentativi e revoche. 09. Correttezza degli algoritmi: 09.01 Triple di Hoare. 09.02 Determinazione della precondizione pi? debole. 09.03 Verifica della correttezza di algoritmi iterativi. 09.04 Verifica della correttezza di algoritmi ricorsivi. 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.

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 (prove d'esame).
« torna indietro Ultimo aggiornamento: 20


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