Complessità e approssimazione, 2005-06

Questa è la pagina dell'insegnamento Complessità e approssimazione del corso di laurea in Scienze dell'Informazione, Università di Modena e Reggio Emilia, per l'A.A. 2005/06.

La pagina contiene le seguenti sezioni:

Orario delle lezioni

Avvisi (in ordine cronologico inverso)

28 giugno 2006
Seminari d'esame  Il primo seminario avrà luogo il giorno 11 luglio 2006, alle ore 11.00, nell'aula XII del Dipartimento di Matematica. Il titolo del seminario è "Algoritmica e Teoria dei Numeri: Test di Primalità e Fattorizzazione".
24 febbraio 2006
Variazione di orario  Si prenda nota del nuovo orario delle lezioni del terzo anno del corso di laurea in Scienze dell'Informazione (le modifiche riguardano anche il presente insegnamento)
28 gennaio 2006
Inizio lezioni  Mercoledì 1 marzo 2006

Obiettivi e programma del corso

Obiettivi formativi

Obiettivo del corso è di introdurre lo studente che ha già affrontato un corso di algoritmica di base allo studio dei problemi computazionalmente difficili e alle tecniche messe a punto per la loro analisi e risoluzione. Problemi di questa natura occorrono in molti campi della scienza e dell'economia e hanno quindi una notevole rilevanza applicativa. Verrà quindi dapprima introdotta la nozione di intrattabilità e verranno studiati criteri per individuare problemi intrattabili. Successivamente, verranno introdotte tecniche per risolvere problemi intrattabili in modo approssimato. Verrà infine dato ampio spazio all'uso in positivo della difficoltà insita nella risoluzione di certi problemi; tale uso "positivo" della complessità si attua principalmente nello sviluppo di algoritmi crittografici e di autenticazione (firma digitale).

Programma

Nozione formale di efficienza ed inefficienza di un algoritmo. Problemi intrattabili e nozione di NP-completezza, riduzioni fra problemi. Estensione dei limiti dell'intrattabilità: casi speciali, algoritmi di approssimzione, euristiche di ricerca locale. Algoritmi probabilistici. Complessità come risorsa: crittografia a chiave pubblica e firma digitale.

Lezioni e materiale didattico

Materiale didattico

Trasparenze delle lezioni (a cura del docente) e materiale disponibile in rete (verrà segnalato di volta in volta).

Lezioni

La seguente tabella descrive l'argomento delle lezioni svolte, con i riferimenti al materiale didattico utilizzato

Data lezione Argomento Materiale
1 marzo 2006 Introduzione alla complessità computazionale Trasparenze
7 marzo 2006 Introduzione alla complessità computazionale Trasparenze
8 marzo 2006 Introduzione alla complessità computazionale Trasparenze

Esami

Modalità

Seminario su un ``macro-argomento'' trattato durante il corso (scelta da concordarsi con il docente).
 
http://algo.ing.unimo.it
Ultimo aggiornamento della pagina: 28 gennaio 2006.
Mauro Leoncini (leoncini AT unimore DOT it)

Valid HTML 4.01! Valid CSS! Eurolinux Software Patent Petition