ITA | ENG
B012497 - ALGORITMICA
Principali informazioni
Lingua Insegnamento
Contenuto del corso
Libri di testo consigliati
Obiettivi Formativi
Prerequisiti
Metodi Didattici
Altre Informazioni
Modalità di verifica apprendimento
Programma del corso
Anno Accademico 2011-12
Coorte 2011 - Laurea Magistrale in Informatica
Anno di corso
Primo Anno - Secondo Semestre
Dipartimento di Afferenza
Statistica, Informatica, Applicazioni "G. Parenti" (DiSIA)
Tipo insegnamento
Attività formativa monodisciplinare
Settore Scientifico disciplinare
INF/01 - INFORMATICA
Crediti Formativi
6
Ore Didattica
48
Periodo didattico
01/03/2012 ⇒ 15/06/2012
Frequenza Obbligatoria
No
Tipo Valutazione
Voto Finale
Contenuto del corso
mostra
Programma del corso
mostra
Docenza
Lingua Insegnamento
ITALIANO
Contenuto del corso
Reti di flusso: il problema del flusso massimo, flusso massimo e taglio minimo, applicazioni. Algoritmi di approssimazione: tecniche greedy, programmazione lineare. Introduzione agli algoritmi genetici. Algoritmi di ricerca locale. Algoritmi randomizzati.
Libri di testo consigliati (Cerca nel catalogo della biblioteca)
J. Kleinberg, E. Tardos "Algorithm Design", Addison-Wesley, 2006.
Obiettivi Formativi
Conoscenze: Il corso intende presentare le principali tecniche per affrontare problemi computazionalmente intrattabili, presentando sia la progettazione di algoritmi, sia metodi per valutare la bontà di una soluzione.
Prerequisiti
Corsi vincolanti: Algoritmi e Strutture Dati.
Corsi raccomandati: Progettazione di Algoritmi e Complessità Computazionale.
Corsi raccomandati: Progettazione di Algoritmi e Complessità Computazionale.
Metodi Didattici
Numero di ore totali del corso: 150
Numero di ore per studio personale e altre attività formative di tipo individuale: 102
Numero di ore relative alle attività in aula: 48
Numero di ore per studio personale e altre attività formative di tipo individuale: 102
Numero di ore relative alle attività in aula: 48
Altre Informazioni
Frequenza delle lezioni ed esercitazioni: Raccomandata
Strumenti a supporto della didattica
UniFi E-Learning: http://e-l.unifi.it
Orario di ricevimento:
Mercoledì, dalle 10.00 alle 11.00, oppure previo appuntamento via e-mail.
Dipartimento di Sistemi e Informatica
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 4237439 Fax: 055 4796363 - 4237436
E-Mail: mariacecilia.verri@unifi.it
URL: http://www.dsi.unifi.it/~cecilia/
Strumenti a supporto della didattica
UniFi E-Learning: http://e-l.unifi.it
Orario di ricevimento:
Mercoledì, dalle 10.00 alle 11.00, oppure previo appuntamento via e-mail.
Dipartimento di Sistemi e Informatica
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 4237439 Fax: 055 4796363 - 4237436
E-Mail: mariacecilia.verri@unifi.it
URL: http://www.dsi.unifi.it/~cecilia/
Modalità di verifica apprendimento
Esame orale ed un elaborato scritto
Programma del corso
Reti di flusso: il problema del flusso massimo, flusso massimo e taglio minimo. Applicazioni: grafi bipartiti e corrispondenza perfetta; cammini disgiunti in grafi orientati; circolazione su richiesta; progettazione di un sondaggio; scheduling di linee aeree; sementazione di un'immagine; selezione di progetti; baseball elimination . Algoritmi di approssimazione: tecniche greedy (center selection problem). Riduzione di problemi: copertura di insiemi, copertura dei vertici, insieme di vertici indipendenti. Programmazione lineare. Approssimazioni arbitrariamente buone: problema dello zaino. Algoritmi di ricerca locale: algoritmo di Metropolis. Reti di Hopfield. Equilibri di Nash. Algoritmi randomizzati: risoluzione di conflitti. Pattern matching.