2. Docenti
  3. FERRAIOLI Diodato
  4. Didattica

DESIGN AND ANALYSIS OF ALGORITHMS

Diodato FERRAIOLI DESIGN AND ANALYSIS OF ALGORITHMS

0623200001
DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE ED ELETTRICA E MATEMATICA APPLICATA
CORSO DI LAUREA MAGISTRALE
INFORMATION ENGINEERING FOR DIGITAL MEDICINE
2024/2025



OBBLIGATORIO
ANNO CORSO 1
ANNO ORDINAMENTO 2022
PRIMO SEMESTRE
CFUOREATTIVITÀ
540LEZIONE
432ESERCITAZIONE
DIODATO FERRAIOLI T Curriculum
Obiettivi
L’INSEGNAMENTO FORNISCE LA CAPACITÀ DI ANALIZZARE UN PROBLEMA, DI PROGETTARE UNA SOLUZIONE EFFICIENTE, ANCHE ATTRAVERSO L’UTILIZZO DI TECNICHE DI PROGRAMMAZIONE EVOLUTE E STRUTTURE DATI AVANZATE, E DI REALIZZARNE UN'IMPLEMENTAZIONE IN UN LINGUAGGIO DI PROGRAMMAZIONE ORIENTATO AGLI
OGGETTI.

CONOSCENZE E CAPACITÀ DI COMPRENSIONE
TECNICHE DI PROGRAMMAZIONE EVOLUTE E STRUTTURE DATI AVANZATE. IMPLEMENTAZIONE DELLE STRUTTURE DATI COMUNEMENTE FORNITE NELLE LIBRERIE STANDARD DEI LINGUAGGI DI PROGRAMMAZIONE PIÙ DIFFUSI.
TERMINOLOGIA UTILIZZATA NEGLI AMBITI DI APPROFONDIMENTO DEL CORSO.

CONOSCENZA E CAPACITÀ DI COMPRENSIONE APPLICATE
APPLICARE LE TECNICHE DI PROGRAMMAZIONE E LE STRUTTURE DATI PROPOSTE NELLA RISOLUZIONE DI PROBLEMI COMPLESSI. IMPLEMENTARE GLI ALGORITMI E LE STRUTTURE DATI AVANZATE IN UN LINGUAGGIO DI PROGRAMMAZIONE AD OGGETTI.
Prerequisiti
SI PRESUPPONE: LA CONOSCENZA DI UN LINGUAGGIO DI PROGRAMMAZIONE ORIENTATO AGLI OGGETTI, LA CONOSCENZA DELLE STRUTTURE DATI ELEMENTARI E DEI PRINCIPI DELLA PROGRAMMAZIONE, LA CONOSCENZA DELLE TECNICHE DI ANALISI DEGLI ALGORITMI.
Contenuti
UNITÀ DIDATTICA 1: PYTHON
(ORE LEZIONE/ESERCITAZIONE 4/0)
- 1 (2 ORE LEZIONE): INTRODUCTION TO PYTHON
- 2 (2 ORE LEZIONE): PYTHON: CLASSI E FUNZIONI
CONOSCENZE E CAPACITÀ DI COMPRENSIONE: COMPRENSIONE DEI CONCETTI E DEI TERMINI CHIAVE DI PYTHON
CONOSCENZE E CAPACITÀ DI COMPRENSIONE APPLICATE: ABILITÀ DI SCRIVERE SEMPLICI PROGRAMMI PYTHON

UNITÀ DIDATTICA 2: BALANCED BINARY SEARCH TREES
(ORE LEZIONE/ESERCITAZIONE 11/6)
- 3 (3 ORE LEZIONE): ABSTRACT DATA TYPES AND DATA STRUCTURES
- 4 (2 ORE LEZIONE): BINARY SEARCH TREES
- 5 (2 ORE LEZIONE): AVL TREES
- 6 (3 ORE ESERCITAZIONE): BINARY SEARCH TREES AND AVL TREES
- 7 (2 ORE LEZIONE): MULTIWAY SEARCH TREES AND B-TREES
- 8 (2 ORE LEZIONE): RED-BLACK TREES
- 9 (3 ORE ESERCITAZIONE): BALANCED BINARY SEARCH TREES
CONOSCENZE E CAPACITÀ DI COMPRENSIONE: COMPRENSIONE DELLE FUNZIONALITÀ DELL'ADT DICTIONARY; COMPRENSIONE DEGLI ALGORITMI PER L'INSERIMENTO, LA CANCELLAZIONE, LA RICERCA E IL BILANCIAMENTO IN UN BINARY SEARCH TREE
CONOSCENZE E CAPACITÀ DI COMPRENSIONE APPLICATE: ABILITÀ DI SCEGLIERE LA GIUSTA STRUTTURA DATI IN BASE AI REQUISITI, DI PROGETTARE VARIANTI ALLE IMPLEMENTAZIONI VISTE A LEZIONE

UNITÀ DIDATTICA 3: HASH TABLES AND PRIORITY QUEUES
(ORE LEZIONE/ESERCITAZIONE 4/5)
- 10 (2 ORE LEZIONE): HASH TABLE
- 11 (3 ORE ESERCITAZIONE): HASH TABLE
- 12 (2 ORE LEZIONE): PRIORITY QUEUES
- 13 (2 ORE ESERCITAZIONE): PRIORITY QUEUES
CONOSCENZE E CAPACITÀ DI COMPRENSIONE: COMPRENSIONE DEGLI ALGORITMI DI INSERIMENTO, CANCELLAZIONE E RICERCA NELLE HASH TABLE E NELLE PRIORITY QUEUES
CONOSCENZE E CAPACITÀ DI COMPRENSIONE APPLICATE: ABILITÀ DI SCEGLIERE LA GIUSTA STRUTTURA DATI IN BASE AI REQUISITI, DI PROGETTARE VARIANTI ALLE IMPLEMENTAZIONI VISTE A LEZIONE

UNITÀ DIDATTICA 4: PATTERN MATCHING ALGORITHMS
(ORE LEZIONE/ESERCITAZIONE 5/2)
- 14 (2 ORE LEZIONE): PATTERN MATCHING AND SUFFIX TRIES
- 15 (3 ORE LEZIONE): SUFFIX TRIES APPLICATIONS
- 16 (2 ORE ESERCITAZIONE): SUFFIX TRIES
CONOSCENZE E CAPACITÀ DI COMPRENSIONE: COMPRENSIONE DEGLI ALGORITMI DI PATTERN MATCHING, E DI CREAZIONE ED UTILIZZO DI UN SUFFIX TRIE
CONOSCENZE E CAPACITÀ DI COMPRENSIONE APPLICATE: ABILITÀ DI PROGETTARE SUFFIX TRIES PER RISOLVERE SPECIFICI PROBLEMI

UNITÀ DIDATTICA 5: PROGRAMMING TECHNIQUES
(ORE LEZIONE/ESERCITAZIONE 6/9)
- 17 (2 ORE LEZIONE): GREEDY PROGRAMMING
- 18 (3 ORE ESERCITAZIONE): GREEDY PROGRAMMING
- 19 (2 ORE LEZIONE): DYNAMIC PROGRAMMING
- 20 (3 ORE ESERCITAZIONE): DYNAMIC PROGRAMMING
- 21 (2 ORE LEZIONE): LOCAL SEARCH
- 22 (3 ORE ESERCITAZIONE): PROGRAMMING TECHNIQUES
CONOSCENZE E CAPACITÀ DI COMPRENSIONE: COMPRENSIONE DEI PRINCIPI E DEI LIMITI DELLE TECNICHE DI PROGRAMMAZIONE
CONOSCENZE E CAPACITÀ DI COMPRENSIONE APPLICATE: ABILITÀ DI ANALIZZARE UN PROBLEMA REALE ED INDIVIDUARE LA TECNICA DI PROGRAMMAZIONE PIÙ ADATTA A RISOLVERLO; CAPACITÀ DI PROGETTARE ALGORITMI EFFICIENTI CHE ADOPERINO LE SUDDETTE TECNICHE DI PROGRAMMAZIONE

UNITÀ DIDATTICA 6: GRAPHS
(ORE LEZIONE/ESERCITAZIONE 12/8)
- 23 (2 ORE LEZIONE): GRAPHS
- 24 (2 ORE LEZIONE): GRAPH VISIT
- 25 (3 ORE ESERCITAZIONE): UNWEIGHTED GRAPHS
- 26 (2 ORE LEZIONE): SHORTEST PATHS
- 27 (2 ORE LEZIONE): MINIMUM SPANNING TREES
- 28 (3 ORE ESERCITAZIONE): WEIGHTED GRAPHS
- 29 (2 ORE LEZIONE): MAX FLOW
- 30 (2 ORE ESERCITAZIONE): MAX FLOW APPLICATIONS
- 31 (2 ORE LEZIONE): APPROXIMATION ALGORITHMS
CONOSCENZE E CAPACITÀ DI COMPRENSIONE: COMPRENSIONE DEI CONCETTI CHIAVI, DEI VANTAGGI E DEGLI SVANTAGGI DELLE DIVERSE IMPLEMENTAZIONI, E DEI DIVERSI ALGORITMI PER RISOLVERE GLI SPECIFICI PROBLEMI
CONOSCENZE E CAPACITÀ DI COMPRENSIONE APPLICATE: ABILITÀ DI PROGETTARE ALGORITMI CHE ADOPERINO I GRAFI E GLI ALGORITMI SU GRAFI PER LA RISOLUZIONE

TOTALE ORE LEZIONE/ESERCITAZIONE/LABORATORIO 42/30/0
Metodi Didattici
L’INSEGNAMENTO CONTEMPLA SIA LEZIONI TEORICHE (42 ORE) CHE ESERCITAZIONI IN AULA (30 ORE).

NELLE LEZIONI VENGONO PRESENTATI ALGORITMI E STRUTTURE DATI E VIENE DISCUSSA LA LORO UTILIZZABILITÀ PER LA SOLUZIONE DI PROBLEMI REALI. NELLE ESERCITAZIONI IN AULA VENGONO PREVISTE ATTIVITÀ CHE PREVEDONO L'APPLICAZIONE, L'ANALISI, LA PROGETTAZIONE E L'IMPLEMENTAZIONE DI ALGORITMI VISTI A LEZIONE E DI SUE VARIANTI.
Verifica dell'apprendimento
LA PROVA DI ESAME È FINALIZZATA A VALUTARE NEL SUO COMPLESSO IL LIVELLO DI CONOSCENZA E COMPRENSIONE DEI CONCETTI PRESENTATI A LEZIONE, NONCHÉ LA CAPACITÀ DI APPLICARE TALI CONOSCENZE NELLA PROGETTAZIONE E REALIZZAZIONE DI UN PROGRAMMA PER RISOLVERE PROBLEMI COMBINATORIALI NON BANALI.

LA PROVA D’ESAME SI ARTICOLA IN UNA PROVA SCRITTA E DI UNA DISCUSSIONE DELLO SCRITTO. LA PROVA SCRITTA CONSISTE DI QUATTRO ESERCIZI ED E' FINALIZZATA A VALUTARE LE CONOSCENZE ACQUISITE IN MERITO A STRUTTURE DATI AVANZATE E TECNICHE DI PROGRAMMAZIONE EVOLUTE E LA CAPACITA' DI APPLICARLE ED IMPLEMENTARLE. LA DISCUSSIONE DELLO SCRITTO PREVEDERÀ UNA PIÙ DETTAGLIATA VALUTAZIONE DELLE CAPACITÀ DI PROGETTARE, IMPLEMENTARE, E VALUTARE SOLUZIONI ALGORITMICHE AI PROBLEMI EMERSI NELLA PROVA SCRITTA O A VARIANTI DI ESSI.

NELLA VALUTAZIONE FINALE, ESPRESSA IN TRENTESIMI, LA VALUTAZIONE DELLO SCRITTO PESERÀ PER IL 60% E LA DISCUSSIONE PER IL RESTANTE 40%. LA LODE POTRÀ ESSERE ATTRIBUITA AGLI STUDENTI CHE DIMOSTRINO UNA PIENA CONOSCENZA E PADRONANZA DI TUTTE LE PRINCIPALI TEMATICHE AFFRONTATE AL CORSO E CAPACITÀ DI APPLICARLI ANCHE A CONTESTI DIFFERENTI DA QUELLI ANALIZZATI A LEZIONE.
Testi
M.T. GOODRICH, M. TAMASSIA, M.H. GOLDWASSER, “DATA STRUCTURES & ALGORITHMS IN PYTHON”,
WILEY 2013

KLEINBERG, TARDOS, "ALGORITHM DESIGN", PRENTICE HALL, 2005.

MATERIALE DIDATTICO INTEGRATIVO SARÀ DISPONIBILE NELLA SEZIONE DEDICATA DELL'INSEGNAMENTO ALL'INTERNO DELLA PIATTAFORMA E-LEARNING DI ATENEO (HTTP://ELEARNING.UNISA.IT) ACCESSIBILE AGLI STUDENTI DEL CORSO TRAMITE LE CREDENZIALI UNICHE DI ATENEO

LETTURE CONSIGLIATE:
T.H. CORMEN, C.E. LEISERSON, R.L. RIVEST, C. STEIN, “INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI”, SECONDA EDIZIONE, MCGRAW-HILL, 2005.
M. VENTO, P. FOGGIA, “ALGORITMI E STRUTTURE DATI”, MCGRAW-HILL.
P. MORIN, ”OPEN DATA STRUCTURES", (HTTP://WWW.OPENDATASTRCTURES.ORG).
C. DEMETRESCU, I. FINOCCHI, G. ITALIANO, “ALGORITMI E STRUTTURE DATI”, MCGRAW HILL, 2008.
Altre Informazioni
L'INSEGNAMENTO E' EROGATO IN INGLESE
Orari Lezioni

  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2024-11-29]