Applied Computer Science and Artificial Intelligence – Informatica Applicata e Intelligenza Artificiale

DANILO FRANCATI

Obiettivi formativi

L’insegnamento fornisce agli studenti i fondamenti teorici e pratici della progettazione e dell’analisi degli algoritmi. Il corso affronta le principali tecniche di progettazione algoritmica, tra cui algoritmi greedy, divide et impera e algoritmi per grafi, introducendo inoltre concetti di complessità computazionale e di trattabilità dei problemi. Al termine del corso gli studenti saranno in grado di analizzare la correttezza e l’efficienza degli algoritmi, confrontare diverse strategie risolutive e progettare soluzioni algoritmiche per problemi di media complessità.

Conoscenza e capacità di comprensione

Gli studenti acquisiscono una solida conoscenza dei principali paradigmi di progettazione algoritmica, delle strutture dati fondamentali e degli algoritmi classici per problemi di ottimizzazione, codifica, scheduling e cammini minimi. Comprendono i metodi di analisi della complessità computazionale e i principi di correttezza degli algoritmi.

Capacità di applicare conoscenza e comprensione

Gli studenti sono in grado di modellare problemi computazionali, individuare la strategia algoritmica più appropriata, progettare algoritmi corretti ed efficienti, analizzarne la complessità temporale e spaziale e confrontare soluzioni alternative sulla base delle loro prestazioni.

Autonomia di giudizio

Gli studenti sviluppano la capacità di valutare criticamente algoritmi e strutture dati, individuandone punti di forza, limiti e ambiti di applicabilità. Sono inoltre in grado di motivare le proprie scelte progettuali considerando correttezza, efficienza e vincoli del problema.

Abilità comunicative

Gli studenti acquisiscono la capacità di descrivere algoritmi e dimostrarne la correttezza utilizzando un linguaggio tecnico appropriato, pseudocodice e notazione matematica. Sono inoltre in grado di presentare in modo chiaro il processo di progettazione e l’analisi della complessità delle soluzioni proposte.

Capacità di apprendimento

Gli studenti sviluppano un metodo di studio autonomo che consente loro di approfondire nuovi algoritmi, tecniche di progettazione e risultati teorici, applicando in modo critico le conoscenze acquisite anche a problemi non affrontati direttamente durante il corso.

1: Conoscenza e comprensione
Gli studenti dimostrano una conoscenza e una comprensione definite e applicabili in contesti concreti dei principali concetti, algoritmi e strutture dati utilizzati nell’analisi e nella progettazione degli algoritmi. Essi sono in grado di spiegare i concetti di base e le strategie di progettazione degli algoritmi.

2: Capacità di applicare conoscenze e comprensione
Gli studenti dimostrano la capacità di applicare le proprie conoscenze per risolvere problemi algoritmici, selezionando e adattando soluzioni appropriate in base ai vincoli di efficienza e correttezza, e valutando i trade-off tra diverse strategie.

3: Capacità critica e di giudizio
Gli studenti dimostrano una capacità avanzata di valutare criticamente gli algoritmi esistenti, analizzando le loro prestazioni in termini di complessità computazionale, tempo di esecuzione, spazio di memoria e scalabilità. Sono in grado di identificare e comprendere le proprietà fondamentali degli algoritmi, come la correttezza e l’ottimalità, nonché di valutare la loro adattabilità a contesti specifici.

4: Capacità di comunicare
Gli studenti dimostrano la capacità di comunicare in modo chiaro e rigoroso le soluzioni algoritmiche, esprimendo idee e concetti mediante pseudocodice o linguaggio tecnico appropriato. Saranno in grado di spiegare e giustificare le proprie scelte progettuali agli altri, dimostrando una comprensione dei concetti algoritmici.

5: Capacità di apprendere
Gli studenti dimostrano una capacità di apprendimento autonomo e di riflessione critica sul proprio apprendimento nel campo degli algoritmi. Sono in grado di individuare lacune nella propria comprensione, di identificare aree di interesse e di approfondire la propria conoscenza attraverso la ricerca indipendente e l’esplorazione di nuovi sviluppi nel campo.

Non ci sono prerequisiti formali

Algoritmi
Gale-Shapley
Heaps, Priority queues
Sorting
Greedy: Interval Scheduling, Interval Partitioning, Codici di Huffman, Shortests Paths
Programmazione dinamica: Weighted Interval Scheduling, Segmentation, Subset-Sum, Bellman-Ford
Introduzione agli Algoritmi di approssimazione.

"Algorithm Design", Kleinberg, Tardos
"Introduction to Algorithms", Cormen, Leiserson, Rivest, Stein
Dispense fornite dal docente

"Algorithm Design", Kleinberg, Tardos
"Introduction to Algorithms", Cormen, Leiserson, Rivest, Stein
"Automata and computatability", Kozen

Le attività didattiche del corso si basano esclusivamente su lezioni frontali:
- Durante le lezioni, il docente presenta (alla lavagna e/o con slides) i concetti teorici fondamentali di progettazione di algoritmi.
- Gli studenti sono incoraggiati a partecipare attivamente alle discussioni in aula, a porre domande e a risolvere esercizi proposti dal docente durante la lezione per consolidare la comprensione dei concetti.

La presenza non è obbligatoria, ma è fortemente consigliata.

Prova scritta
- Tipologia: test individuale composto da quesiti a risposta aperta e problemi pratici di analisi e progettazione di algoritmi.
- Obiettivi: verificare la conoscenza dei concetti teorici di base e la capacità di progettare e analizzare algoritmi.
- Criteri di valutazione: correttezza delle risposte, chiarezza e completezza delle spiegazioni, correttezza degli algoritmi proposti e capacità di analizzarne complessità e prestazioni.

Valutazione finale
- Il voto è espresso in trentesimi.
- Per superare l’esame (18/30), lo studente deve dimostrare di aver acquisito una conoscenza sufficiente dei concetti fondamentali di algoritmi e di saper risolvere problemi pratici con algoritmi corretti e analisi elementari della complessità.
- Per conseguire il punteggio massimo (30/30 e lode), lo studente deve dimostrare una conoscenza eccellente dei concetti trattati durante il corso, essere in grado di risolvere problemi complessi proponendo algoritmi corretti ed efficienti, in modo coerente e giustificare le scelte progettuali con spiegazioni rigorose e complete.

1. Si dia un algoritmo efficiente per la moltiplicazione di due numeri interi, dimostrandone la correttezza e analizzandone la complessità.

2. Si dia un algoritmo che trovi il cammino di lunghezza massima in un grafo acilico.

3. Si dimostri che un albero con n nodi ha esattamente n-1 archi.

• Introduzione agli algoritmi
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 1


• L’algoritmo di Gale-Shapley
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 1


• Limiti di tempo di esecuzione e notazione asintotica
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 2.1, 2.2


• Strutture dati
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 2.3, 2.4, 2.5


• Algoritmi greedy
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.1


• Interval Scheduling
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.1


• Interval Partitioning
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.1


• Posizionamento di trasmettitori radio


• Grafi
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 3


• Algoritmo di Dijkstra
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.4


• Heap
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 2.5


• Code di priorità e cammini minimi
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 2.5 , 4.4


• Codifica con prefisso
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.8


• Algoritmo di Huffman (1)
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.8


• Algoritmo di Huffman (2)
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.8


• Weighted Interval Scheduling
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 6.1, 6.2


• Segmentazione
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 6.3


• Subset Sum
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 6.4


• Bellman-Ford
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 6.8, 6.9


• Divide-and-Conquer
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 5


• Moltiplicazione di interi
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 5.5


• P e NP
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 8


• Vertex Cover
  • Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 8