ALGORITHM DESIGN

Computer science ALGORITHM DESIGN

0512100043
COMPUTER SCIENCE
EQF6
COMPUTER SCIENCE
2022/2023

OBBLIGATORIO
YEAR OF COURSE 2
YEAR OF DIDACTIC SYSTEM 2017
SPRING SEMESTER
CFUHOURSACTIVITY
648LESSONS
324EXERCISES


Objectives
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 DAGLI ALGORITMI
- FORNIRE UN CATALOGO DEI PIÙ NOTI ED EFFICIENTI ALGORITMI PER PROBLEMI COMPUTAZIONALI DI BASE (ORDINAMENTO, RICERCA, OTTIMIZZAZIONE DI RISORSE, ECC.)

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.

Prerequisites
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.
Contents
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).
Teaching Methods
L’INSEGNAMENTO PREVEDE UNA PARTE (48 ORE) DI LEZIONI FRONTALI DI CARATTERE
TEORICO/METODOLOGICO FINALIZZATE ALL'APPRENDIMENTO DELLE TECNICHE
DI BASE PER IL PROGETTO ED ANALISI DI ALGORITMI, E UNA PARTE (24 ORE) DI LEZIONI
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.
LA FREQUENZA ALLE LEZIONI NON E` OBBLIGATORIA MA CONSIGLIATA.
Verification of learning
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 PRIMA A CIRCA METÀ DEL CORSO E LA SECONDA ALLA FINE DELLO STESSO. LA PROVA SCRITTA HA SOLITAMENTE DURATA VARIABILE TRA 90 E 120
MINUTI. ESSA 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.
Texts
LIBRI DI TESTO:
KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY.
S. DASGUPTA, C.H. PAPADIMITRIOU, AND U.V. VAZIRANI. ALGORITHMS. MCGRAW-HILL

ULTERIORI MATERIALI E SUPPORTI NECESSARI PER AFFRONTARE LO STUDIO E LA GESTIONE DELLA PROVA DI
VERIFICA POTRANNO ESSERE FORNITI TRAMITE LE PAGINE DEI DOCENTI E/O LA PIATTAFORMA E-LEARNING
ALL’INDIRIZZO HTTP://ELEARNING.INFORMATICA.UNISA.IT/ .
More Information
È RAGIONEVOLE SUPPORRE CHE UNA PREPARAZIONE SODDISFACENTE RICHIEDA IN MEDIA 2 ORE DI STUDIO PER CIASCUNA ORA TRASCORSA IN AULA.
  BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2022-10-03]