Annalisa DE BONIS | PROGETTAZIONE DI ALGORITMI

cod. 0512100043

PROGETTAZIONE DI ALGORITMI

	0512100043
	DIPARTIMENTO DI INFORMATICA
	CORSO DI LAUREA
	INFORMATICA
	2018/2019

PERCORSO COMUNE

	OBBLIGATORIO
	ANNO CORSO 2
	ANNO ORDINAMENTO 2017
	SECONDO SEMESTRE

MODULI

	SSD	CFU	ORE	ATTIVITÀ	TIPO DI ATTIVITÁ FORMATIVA
	INF/01	9	72	LEZIONE	CARATTERIZZANTE

	Obiettivi
	CONOSCENZA E CAPACITÀ DI COMPRENSIONE L’INSEGNAMENTO SI PREFIGGE I SEGUENTI OBIETTIVI: • FORNIRE ALLO STUDENTE METODI E CONOSCENZE ATTI AL PROGETTO DI ALGORITMI EFFICIENTI • FORNIRE STRUMENTI PER L’ANALISI DELLE RISORSE (SPAZIO E TEMPO) UTILIZZATE DA ALGORITMI • 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 L’INSEGNAMENTO 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.

CONOSCENZA E CAPACITÀ DI COMPRENSIONE
L’INSEGNAMENTO SI PREFIGGE I SEGUENTI OBIETTIVI:
• FORNIRE ALLO STUDENTE METODI E CONOSCENZE ATTI AL PROGETTO DI ALGORITMI EFFICIENTI
• FORNIRE STRUMENTI PER L’ANALISI DELLE RISORSE (SPAZIO E TEMPO) UTILIZZATE DA ALGORITMI
• 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
L’INSEGNAMENTO 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.

	Prerequisiti
	LO STUDENTE DOVREBBE AVERE ACQUISITO LE NOZIONI DI MATEMATICA INSEGNATE NEL PRECEDENTE ANNO ACCADEMICO E LA CAPACITÀ DI SVILUPPARE RAGIONAMENTI DI TIPO LOGICO. DOVREBBE ALTRESÌ AVER APPRESO I CONCETTI DI BASE DI UN INSEGNAMENTO INTRODUTTIVO ALLE STRUTTURE DATI.

	Contenuti
	ORE DI LEZIONI FRONTALI: 72 1. ANALISI ASINTOTICA DEGLI ALGORITMI (6 ORE FRONTALI) 2. DERIVAZIONE RICORRENZE E LORO SOLUZIONE (4 ORE FRONTALI) 3. LA TECNICA DI PROGETTO DI ALGORITMI DIVIDE ET IMPERA E RELATIVI ESEMPI DI APPLICAZIONE: MERGESORT, QUICKSORT. CALCOLO MEDIANA, MOLTIPLICAZIONE VELOCE DI NUMERI, ALGORITMI RICORSIVI SU ALBERI BINARI. (12 ORE FRONTALI) 4. 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. (12 ORE FRONTALI). 5. LA TECNICA DI PROGETTO DI ALGORITMI GREEDY E RELATIVI ESEMPI DI APPLICAZIONE: SCHEDULING DI INTERVALLI; SCHEDULING CON DEADLINE; COMPRESSIONE DATI E CODICI DI HUFFMAN. (12 ORE FRONTALI). 6. 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). (12 ORE FRONTALI). 7. CALCOLO DI FLUSSO SU GRAFI E LORO APPLICAZIONI. (8 ORE FRONTALI). 8. ALGORITMI INTELLIGENTI DI RICERCA ESAUSTIVA: BACKTRACKING E BRANCH-AND-BOUND. (6 ORE FRONTALI).

Contenuti

ORE DI LEZIONI FRONTALI: 72

1. ANALISI ASINTOTICA DEGLI ALGORITMI (6 ORE FRONTALI)
2. DERIVAZIONE RICORRENZE E LORO SOLUZIONE (4 ORE FRONTALI)
3. LA TECNICA DI PROGETTO DI ALGORITMI DIVIDE ET IMPERA E RELATIVI ESEMPI DI APPLICAZIONE: MERGESORT, QUICKSORT. CALCOLO MEDIANA, MOLTIPLICAZIONE VELOCE DI NUMERI, ALGORITMI RICORSIVI SU ALBERI BINARI. (12 ORE FRONTALI)
4. 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. (12 ORE FRONTALI).
5. LA TECNICA DI PROGETTO DI ALGORITMI GREEDY E RELATIVI ESEMPI DI APPLICAZIONE: SCHEDULING DI INTERVALLI; SCHEDULING CON DEADLINE; COMPRESSIONE DATI E CODICI DI HUFFMAN. (12 ORE FRONTALI).
6. 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). (12 ORE FRONTALI).
7. CALCOLO DI FLUSSO SU GRAFI E LORO APPLICAZIONI. (8 ORE FRONTALI).
8. ALGORITMI INTELLIGENTI DI RICERCA ESAUSTIVA: BACKTRACKING E BRANCH-AND-BOUND. (6 ORE FRONTALI).

	Metodi Didattici
	L’INSEGNAMENTO PREVEDE UNA PARTE DI LEZIONI FRONTALI DI CARATTERE TEORICO/METODOLOGICO FINALIZZATE ALL'APPRENDIMENTO DELLE TECNICHE DI BASE PER IL PROGETTO ED ANALISI DI ALGORITMI, E UNA PARTE DI LEZIONI FRONTALI DI TIPO ESERCITATIVO IN CUI SI ILLUSTRERÀ, CON ABBONDANZA DI ESEMPI, IN CHE MODO LE METODOLOGIE ACQUISITE POSSANO ESSERE UTILIZZATE AL FINE DI RISOLVERE PROBLEMI ALGORITMICI DI INTERESSE PRATICO.

Metodi Didattici

L’INSEGNAMENTO PREVEDE UNA PARTE DI LEZIONI FRONTALI DI CARATTERE TEORICO/METODOLOGICO FINALIZZATE ALL'APPRENDIMENTO DELLE TECNICHE DI BASE PER IL PROGETTO ED ANALISI DI ALGORITMI, E UNA PARTE DI LEZIONI FRONTALI DI TIPO ESERCITATIVO IN CUI SI ILLUSTRERÀ, CON ABBONDANZA DI ESEMPI, IN CHE MODO LE METODOLOGIE ACQUISITE POSSANO ESSERE UTILIZZATE AL FINE DI RISOLVERE PROBLEMI ALGORITMICI DI INTERESSE PRATICO.

	Verifica dell'apprendimento
	IL RAGGIUNGIMENTO DEGLI OBIETTIVI DELL’INSEGNAMENTO È CERTIFICATO MEDIANTE IL SUPERAMENTO DI UN ESAME CON VALUTAZIONE IN TRENTESIMI. L'ESAME PREVEDE UNA PROVA SCRITTA ED UNA PROVA ORALE. LA PROVA SCRITTA POTRÀ ESSERE SOSTITUITA DA DUE PROVE INTERCORSO. LA PROVA SCRITTA SI SVOLGE IN DATA PRECEDENTE ALLA PROVA ORALE E LA SI CONSIDERA SUPERATA CON IL RAGGIUNGIMENTO DEL PUNTEGGIO MINIMO PRESTABILITO. 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 CONCRETI. LA PROVA ORALE CONSISTE IN UN COLLOQUIO CON DOMANDE E DISCUSSIONE SULLE METODOLOGIE DI PROGETTO DI ALGORITMI STUDIATE DURANTE IL CORSO. ESSA È FINALIZZATA AD ACCERTARE IL LIVELLO DI CONOSCENZA E DI COMPRENSIONE RAGGIUNTO DALLO STUDENTE, AD ACCERTARE LA CAPACITÀ DI ESPOSIZIONE DI ORGANIZZAZIONE DELL'ESPOSIZIONE SUGLI STESSI ARGOMENTI A CONTENUTO TEORICO. LA VOTAZIONE FINALE È, DI NORMA, LA MEDIA DELLE VALUTAZIONI DELLA PROVA SCRITTA E DELLA PROVA ORALE.

Verifica dell'apprendimento

IL RAGGIUNGIMENTO DEGLI OBIETTIVI DELL’INSEGNAMENTO È CERTIFICATO MEDIANTE IL SUPERAMENTO DI UN ESAME CON VALUTAZIONE IN TRENTESIMI. L'ESAME PREVEDE UNA PROVA SCRITTA ED UNA PROVA ORALE. LA PROVA SCRITTA POTRÀ ESSERE SOSTITUITA DA DUE PROVE INTERCORSO. LA PROVA SCRITTA SI SVOLGE IN DATA PRECEDENTE ALLA PROVA ORALE E LA SI CONSIDERA SUPERATA CON IL RAGGIUNGIMENTO DEL PUNTEGGIO MINIMO PRESTABILITO. 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 CONCRETI. LA PROVA ORALE CONSISTE IN UN COLLOQUIO CON DOMANDE E DISCUSSIONE SULLE METODOLOGIE DI PROGETTO DI ALGORITMI STUDIATE DURANTE IL CORSO. ESSA È FINALIZZATA AD ACCERTARE IL LIVELLO DI CONOSCENZA E DI COMPRENSIONE RAGGIUNTO DALLO STUDENTE, AD ACCERTARE LA CAPACITÀ DI ESPOSIZIONE DI ORGANIZZAZIONE DELL'ESPOSIZIONE SUGLI STESSI ARGOMENTI A CONTENUTO TEORICO. LA VOTAZIONE FINALE È, DI NORMA, LA MEDIA DELLE VALUTAZIONI DELLA PROVA SCRITTA E DELLA PROVA ORALE.

	Testi
	LIBRI DI TESTO: KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY. S. DASGUPTA, C.H. PAPADIMITRIOU, AND U.V. VAZIRANI. ALGORITHMS. MCGRAW-HILL ULTERIORE MATERIALE DIDATTICO DI SUPPORTO (ESERCIZI, TEST PER L’AUTOVALUTAZIONE) SARANNO RESI DISPONIBILI SUI SITI WEB PERSONALI DEI DOCENTI.

	Altre Informazioni
	LO SVOLGIMENTO DELLE ESERCITAZIONI E LA FREQUENZA ALLE LEZIONI SONO CONSIGLIATE. È RAGIONEVOLE SUPPORRE CHE UNA PREPARAZIONE SODDISFACENTE RICHIEDA IN MEDIA 2 ORE DI STUDIO PER CIASCUNA ORA TRASCORSA IN AULA.

BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2019-10-21]

Annalisa DE BONIS | PROGETTAZIONE DI ALGORITMI