2. Docenti
  3. Didattica

ALGORITMI

Marcella ANSELMO ALGORITMI

0512100007
DIPARTIMENTO DI INFORMATICA
CORSO DI LAUREA
INFORMATICA
2014/2015



OBBLIGATORIO
ANNO CORSO 2
ANNO ORDINAMENTO 2008
PRIMO SEMESTRE
CFUOREATTIVITÀ
648LEZIONE


UGO VACCARO T Curriculum
Obiettivi
CONOSCENZA E CAPACITÀ DI COMPRENSIONE:

IL CORSO SI PREFIGGE I SEGUENTI OBIETTIVI: 1) FORNIRE ALLO STUDENTE METODI E CONOSCENZE ATTE AL PROGETTO DI ALGORITMI EFFICIENTI; 2)

FORNIRE STRUMENTI PER L’ANALISI DELLE RISORSE (SPAZIO E TEMPO) UTILIZZATE DA ALGORITMI; 3) FORNIRE UN CATALOGO DEI PIÙ NOTI ED EFFICIENTI ALGORITMI PER PROBLEMI COMPUTAZIONALI DI BASE (ORDINAMENTO, RICERCA, OTTIMIZZAZIONE DI RISORSE, ETC.)

CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE:

IL CORSO HA COME OBIETTIVO QUELLO DI RENDERE LO STUDENTE CAPACE DI ASTRARRE MODELLI E PROBLEMI ALGORITMICI FORMALI DA PROBLEMI COMPUTAZIONALI CONCRETI, E DI PROGETTARE PER ESSI SOLUZIONI ALGORITMICHE EFFICIENTI. CIÒ VERRÀ EFFETTUATO USANDO IL
SEGUENTE METODO DIDATTICO. OGNI PROBLEMA COMPUTAZIONALE VERRÀ INTRODOTTO MOTIVANDOLO CON ESEMPI CONCRETI. LA PRESENTAZIONI DI CIASCUN ARGOMENTO SARÀ DIVISA IN QUATTRO PARTI:

1. DESCRIZIONE DEL PROBLEMA COMPUTAZIONALE REALE.

2. MODELLIZZAZIONE DEL PROBLEMA REALE MEDIANTE UN PROBLEMAASTRATTO (IN QUESTA FASE SARÀ UTILE MOSTRARE, QUALORA POSSIBILE, CHE UNA STESSA FORMULAZIONE ASTRATTA CORRISPONDE A PIÙ PROBLEMI REALI).

3. RISOLUZIONE DEL PROBLEMA ASTRATTO MEDIANTE UN ALGORITMO

OTTENUTO ATTRAVERSO L’APPLICAZIONE DELLE TECNICHE GENERALI DI PROGETTO DI ALGORITMI INTRODOTTE NEL CORSO.

4. ANALISI DELLE RISORSE UTILIZZATE DALL’ALGORITMO ELABORATO.

ABILITÀ COMUNICATIVE:

IL CORSO FAVORIRÀ LO SVILUPPO DELLE SEGUENTI ABILITÀ DELLO

STUDENTE: CAPACITÀ DI ESPORRE IN TERMINI PRECISI E FORMALIUN MODELLO ASTRATTO DI PROBLEMI CONCRETI, INDIVIDUANDO LE CARATTERISTICHE SALIENTI DI ESSI E SCARTANDONE LE CARATTERISTICHE INESSENZIALI.

AUTONOMIA DI GIUDIZIO:

GLI STUDENTI SONO GUIDATI AD APPRENDERE IN MANIERA CRITICA TUTTO CIÒ CHE VIENE LORO SPIEGATO IN CLASSE, A CONFRONTARE I DIVERSI APPROCCI PER LA SOLUZIONE DI PROBLEMI ALGORITMICI, ED AD

INDIVIDUARE E PROPORRE, IN MANIERA AUTONOMA, LA SOLUZIONE PIÙ EFFICIENTE DA LORO INDIVIDUATA.
Prerequisiti
LO STUDENTE DOVREBBE AVERE ACQUISITO LA CAPACITÀ DI
SVILUPPARE RAGIONAMENTI DI TIPO LOGICO. DOVREBBE ALTRESÌ
AVER APPRESO E PADRONEGGIATO I CONCETTI DI BASE DI UN CORSO
INTRODUTTIVO DI PROGRAMMAZIONE.
Contenuti
1. INTRODUZIONE ALLA ANALISI ASINTOTICA DEGLI ALGORITMI

2. LA TECNICA DI PROGETTO DI ALGORITMI DIVIDE ET IMPERA
E RELATIVI ESEMPI DI APPLICAZIONE: MERGESORT, QUICKSORT; RICORRENZE; MOLTIPLICAZIONE DI INTERI E MATRICI.

3. LA TECNICA DI PROGETTO DI ALGORITMI PROGRAMMAZIONE
DINAMICA E RELATIVI ESEMPI DI APPLICAZIONE: CALCOLO
DI NUMERI DI FIBONACCI, COMBINAZIONI; PROBLEMI DI
OTTIMIZZAZIONE: SCHEDULING DI RISORSE, ZAINO INTERO, PROBLEMI SU STRINGHE, CAMMINI MINIMI SU GRAFI.

4. LA TECNICA DI PROGETTO DI ALGORITMI GREEDY E RELATIVI ESEMPI DI APPLICAZIONE: SCHEDULING DI INTERVALLI; SCHEDULING CON DEADLINE; COMPRESSIONE DATI E CODICI DI HUFFMAN.

5. ALGORITMI SU GRAFI. CONNETTIVITÀ E VISITA DI GRAFI; DAG E ORDINAMENTO TOPOLOGICO. CALCOLO DI CAMMINI MINIMI
(ALGORITMO DI DIJKSTRA). CALCOLO DI ALBERI RICOPRENTI MINIMI (ALGORITMI DI PRIM E KRUSKAL).

6. CALCOLO DI FLUSSO SU GRAFI E LORO APPLICAZIONI.
Metodi Didattici
IL CORSO PREVEDE UNA PARTE DI LEZIONI DI CARATTERE TEORICO
FINALIZZATE ALL'APPRENDIMENTO DELLE TECNICHE DI BASE PER IL
PROGETTO ED ANALISI DI ALGORITMI, E UNA PARTE DI LEZIONI DI TIPO ESERCITATIVO IN CUI SI ILLUSTRERÀ, CON ABBONDANZA DI ESEMPI, IN CHE MODO LE CONOSCENZE TEORICHE ACQUISITE POSSANO ESSERE UTILIZZATE AL FINE DI RISOLVERE PROBLEMI ALGORITMICI DI INTERESSE PRATICO.
Verifica dell'apprendimento
LA VERIFICA E LA VALUTAZIONE DEL LIVELLO DI APPRENDIMENTO DELLO STUDENTE AVVERRÀ TRAMITE UN ESAME FINALE, CONSISTENTE IN UNA PROVA SCRITTA SEGUITA DA UNA PROVA ORALE. LA PROVA SCRITTA POTRÀ ESSERE SOSTITUITA DA DUE PROVE INTERCORSO. LE PROVE SCRITTE SARANNO PARTICOLARMENTE PROGETTATE PER VERIFICARE IL LIVELLO DI ACQUISIZIONE, DA PARTE DELLO STUDENTE, DELLE CAPACITÀ DI APPLICARE LE METODOLOGIE PER IL PROGETTO ED ANALISI DI ALGORITMI A SEMPLICI PROBLEMI ALGORITMICI.
Testi
KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON
WESLEY.
Altre Informazioni
ALLA PAGINA WEB HTTP://WWW.DI.UNISA.IT/~UV/ALGO/ALGO.HTML COMPARIRANNO COPIA DELLE SLIDES USATE A LEZIONI E MATERIALE UTILE PER ESERCITARSI IN VISTA DELL'ESAME.
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2016-09-30]