PROGETTAZIONE DI ALGORITMI

Informatica PROGETTAZIONE DI ALGORITMI

0512100043
DIPARTIMENTO DI INFORMATICA
CORSO DI LAUREA
INFORMATICA
2020/2021

OBBLIGATORIO
ANNO CORSO 2
ANNO ORDINAMENTO 2017
SECONDO SEMESTRE
CFUOREATTIVITÀ
648LEZIONE
324ESERCITAZIONE


Obiettivi
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.)


RISULTATI DI APPRENDIMENTO ATTESI:

CONOSCENZA E CAPACITÀ DI COMPRENSIONE

- CONOSCENZA DELLE NOTAZIONI ASINTOTICHE USATE NELL'ANALISI DI ALGORITMI
- CONOSCENZA DEI METODI PER LA VALUTAZIONE DELLE RISORSE USATE DA ALGORITMI
- CONOSCENZA DELLA METODOLOGIA DIVIDE ET IMPERA PER IL PROGETTO DI ALGORITMI
- CONOSCENZA DELLA METODOLOGIA PROGRAMMAZIONE DINAMICA PER IL PROGETTO DI ALGORITMI
- CONOSCENZA DELLA METODOLOGIA GREEDY PER IL PROGETTO DI ALGORITMI
- CONOSCENZA DELLE TECNICA DI VISITE SU GRAFI
- CONOSCENZA DEI METODI PER IL CALCOLO DI CAMMINI MINIMI IN GRAFI
- CONOSCENZA DEI METODI PER IL CALCOLO DI ALBERI RICOPRENTI DI PESO MINIMO IN GRAFI
- CONOSCENZA DELLA METODOLOGIA BACKTRACK
- CONOSCENZA DELLE METODOLOGIA BRANCH AND BOUND

CAPACITÀ DI APPLICARE CONOSCENZE E COMPRENSIONE

- CAPACITÀ DI VALUTARE LA COMPLESSITÀ ASINTOTICA DI ALGORITMI
- CAPACITÀ DI PROGETTARE ALGORITMI BASATI SULLA METODOLOGIA DIVIDE ET IMPERA
- CAPACITÀ DI PROGETTARE ALGORITMI BASATI SULLA METODOLOGIA PROGRAMMAZIONE DINAMICA
- CAPACITÀ DI PROGETTARE ALGORITMI BASATI SULLA METODOLOGIA GREEDY
- CAPACITÀ DI PROGETTARE ALGORITMI SU GRAFI
- CAPACITÀ DI PROGETTARE ALGORITMI BASATI SULLA METODOLOGIA BACKTRACK
- CAPACITÀ DI PROGETTARE ALGORITMI BASATI SULLA METODOLOGIA BRANCH AND BOUND

AUTONOMIA DI GIUDIZIO

LO STUDENTE SARÀ IN GRADO DI VALUTARE IN AUTONOMIA:
- L'EFFICIENZA (O MENO) DI UN ALGORITMO
- LA CORRETTEZA (O MENO) DI UN ALGORITMO
- IL DOMINIO DI APPLICABILITÀ DELLA METODOLOGIA DIVIDE ET IMPERA E LA SUA OPPORTUNITÀ D'USO
- IL DOMINIO DI APPLICABILITÀ DELLA METODOLOGIA PROGRAMMAZIONE DINAMICA E LA SUA OPPORTUNITÀ D'USO
- IL DOMINIO DI APPLICABILITÀ DELLA METODOLOGIA GREEDY E LA SUA OPPORTUNITÀ D'USO
- IL DOMINIO DI APPLICABILITÀ DELLA METODOLOGIA BACK TRACK E LA SUA OPPORTUNITÀ D'USO
- IL DOMINIO DI APPLICABILITÀ DELLA METODOLOGIA BRANCH AND BOUND E LA SUA OPPORTUNITÀ D'USO

ABILITÀ COMUNICATIVE
LO STUDENTE SARÀ IN GRADO DI SOSTENERE CONVERSAZIONI TECNICHE SUL PROGETTO ED ANALISI DI ALGORITMI.
LO STUDENTE SARÀ ALTRESÌ IN GRADO DI ILLUSTRARE LE DIFFERENTI TECNICHE PER IL PROGETTO DI ALGORITMI
(DIVIDE ET IMPERA, PROGRAMMAZIONE DINAMICA, GREEDY, BACKTRACK E BRANCH AND BOUND).
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: 48
ORE DI ESERCITAZIONI: 24

1.INTRODUZIONE ALLE NOTAZIONI ASINTOTICHE O GRANDE, OMEGA, TETA E
LORO APPLICAZIONI ALL'ANALISI ASINTOTICA DEGLI ALGORITMI (4 ORE TEORIA + 2 DI ESERCITAZIONI)
2.STUDIO DELL'EQUAZIONI DI RICORRENZA PER L'ANALISI DELLA COMPLESSITÀ DI
ALGORITMI RICORSIVI E DERIVAZIONE DI METODI PER LA LORO SOLUZIONE (2 ORE TEORIA + 2 DI ESERCITAZIONI)
3.STUDIO DELLA TECNICA DIVIDE ET IMPERA PER LA PROGETTAZIONE DI ALGORITMI E RELATIVI
ESEMPI DI APPLICAZIONE (10 ORE TEORIA + 4 DI ESERCITAZIONI)
4.STUDIO DELLA TECNICA PROGRAMMAZIONE DINAMICA PER LA PROGETTAZIONE DI ALGORITMI
E RELATIVI ESEMPI DI APPLICAZIONE (10 ORE TEORIA + 4 DI ESERCITAZIONI).
5.STUDIO DELLA TECNICA GREEDY PER LA PROGETTAZIONE DI ALGORITMI E RELATIVI ESEMPI DI
APPLICAZIONE (10 ORE TEORIA + 4 DI ESERCITAZIONI).
6.GRAFI ED ALGORITMI SU GRAFI. VISITA IN AMPIEZZA E VISITA IN PROFONDITÀ DI GRAFI E
LORO APPLICAZIONI. GRAFI DIRETTI ACICLICI ED ORDINAMENTO TOPOLOGICO. ALGORITMI PER IL
CALCOLO DI CAMMINI DI COSTO MINIMO IN GRAFI CON COSTI SU ARCHI. ALGORITMI PER IL
CALCOLO DI ALBERI RICOPRENTI DI COSTO MINIMO IN GRAFI CON COSTI SU ARCHI
(8 ORE TEORIA + 6 DI ESERCITAZIONI).
7.ALGORITMI INTELLIGENTI DI RICERCA ESAUSTIVA: BACKTRACKING, BRANCH-AND-BOUND E RELATIVI
ESEMPI DI APPLICAZIONE. (4 ORE TEORIA + 2 DI ESERCITAZIONI).
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.
Testi
LIBRI DI TESTO:
1. KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY.
2. S. DASGUPTA, C.H. PAPADIMITRIOU, AND U.V. VAZIRANI. ALGORITHMS. MCGRAW-HILL
3. NOTE FORNITE DAL DOCENTE

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: 2020-11-20]