2. Docenti
  3. FERRAIOLI Diodato
  4. Didattica

DESIGN AND ANALYSIS OF ALGORITHMS

Diodato FERRAIOLI DESIGN AND ANALYSIS OF ALGORITHMS

0622700081
DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE ED ELETTRICA E MATEMATICA APPLICATA
CORSO DI LAUREA MAGISTRALE
INGEGNERIA INFORMATICA
2022/2023



OBBLIGATORIO
ANNO CORSO 1
ANNO ORDINAMENTO 2022
PRIMO SEMESTRE
CFUOREATTIVITÀ
540LEZIONE
324LABORATORIO
18ESERCITAZIONE


DIODATO FERRAIOLI T Curriculum
COSIMO VINCI 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
CONOSCENZA DI UN LINGUAGGIO DI PROGRAMMAZIONE ORIENTATO AGLI OGGETTI. CONOSCENZA DELLE STRUTTURE DATI ELEMENTARI E DEI PRINCIPI DELLA PROGRAMMAZIONE. 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 CHE ESERCITAZIONI IN AULA.

NELLE LEZIONI VENGONO PRESENTATI ALGORITMI E STRUTTURE DATI E VIENE DISCUSSA LA LORO UTILIZZABILITÀ PER LA SOLUZIONE DI PROBLEMI REALI. NELLE ESERCITAZIONI IN LABORATORIO GLI STUDENTI IMPLEMENTANO GLI ALGORITMI E LE STRUTTURE DATI PRESENTATI NEL CORSO. NELLE ESERCITAZIONI IN AULA VENGONO ASSEGNATI AGLI STUDENTI, DIVISI PER GRUPPI DI LAVORO, UNO O PIU' PROJECT-WORK DA SVILUPPARE DURANTE TUTTO LO SVOLGIMENTO DEL CORSO. IL PROGETTO COMPRENDE UNITARIAMENTE TUTTI I CONTENUTI DELL’INSEGNAMENTO ED È STRUMENTALE ALL’ACQUISIZIONE, OLTRE CHE DELLE CAPACITÀ DI RISOLVERE UN PROBLEMA DI PROGRAMMAZIONE, PROGETTANDO E REALIZZANDO UNA SOLUZIONE ALGORITMICA AVANZATA, ANCHE A SVILUPPARE E RAFFORZARE LE CAPACITÀ DI LAVORARE IN TEAM.
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 NELLA DISCUSSIONE DEL PROGETTO SVOLTO DURANTE IL CORSO ED UNA PROVA SCRITTA. LA PROVA SCRITTA CONSISTE DI TRE 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 IN SEMPLICI SITUAZIONI. CON IL PROGETTO SARANNO VALUTATE LE CAPACITÀ DI APPLICARE A CASI CONCRETI LE STRUTTURE DATI E LE TECNICHE DI PROGRAMMAZIONE PROPOSTE A LEZIONE E DI FORNIRNE DELLE IMPLEMENTAZIONI EFFICIENTI.

NELLA VALUTAZIONE FINALE, ESPRESSA IN TRENTESIMI, LA VALUTAZIONE DEL PROGETTO PESERÀ PER IL 60% E LA PROVA SCRITTA 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
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2024-08-21]