Ingegneria Informatica e Automatica

LUCA BECCHETTI
GIUSEPPE ANTONIO DI LUNA

Obiettivi generali:
Conoscere gli algoritmi e le strutture dati fondamentali. Essere in grado di implementarli in un linguaggio di programmazione avanzato (Java o C) ed essere in grado di effettuare scelte progettuali per la risoluzione di problemi in domini applicativi reali.
Essere in grado di progettare algoritmi per la soluzione di problemi nuovi, usando o modificando algoritmi e strutture dati viste a lezioni.


Obiettivi specifici:
Capacità di:
- progettare/implementare soluzioni algoritmiche basate su tecniche studiate o su semplici varianti;
- valutare approssimativamente le risorse computazionali necessarie a una soluzione algoritmica;
- effettuare scelte progettuali consapevoli per la soluzione di problemi;

Conoscenza e comprensione:
Conoscere le strutture dati e gli algoritmi fondamentali. Comprendere i concetti di correttezza e complessità computazionale di un algoritmo. Conoscere i principali paradigmi per la progettazione di algoritmi.

Applicare conoscenza e comprensione:
Essere in grado di progettare un algoritmo che risolva un problema e di realizzarlo in un linguaggio di programmazione evoluto.

Capacità critiche e di giudizio:
Essere in grado di valutare la correttezza, l'adeguatezza e l'efficienza della soluzione algoritmica di un problema.

Capacità comunicative:
Essere in grado di descrivere in modo efficace le specifiche di un problema e di comunicare ad altri le scelte adottate e le motivazioni sottostanti a tali scelte.

Capacità di apprendimento:
Il corso consentirà lo sviluppo di capacità di approfondimento autonomo su argomenti del corso o ad essi correlati. Consentirà inoltre allo studente di poter agevolmente consultare manuali avanzati e/o specifici per l'apprendimento autonomo di soluzioni algoritmiche ad hoc.

Conoscenze matematiche di base equivalenti a quelle offerte in un corso di Analisi I
Nozioni di base di calcolo delle probabilità
Conoscenze di base di programmazione e di strutture dati elementari e loro implementazione, corrispondenti grosso modo agli argomenti insegnati nei corsi di Fondamenti di Informatica e Tecniche di programmazione

1. Ricorsione

2. Introduzione e modello a costi uniformi (limiti)
2.1. Modelli di costo degli algoritmi: modello a costi uniformi
2.2. Analisi del caso peggiore e analisi asintotica

3. Ordinamento e Selezione
3.1. Introduzione della tecnica divide-and-conquer
3.2. Algoritmi Merge-Sort e Quick-Sort
3.3. Limiti inferiori al costo dell'ordinamento
3.4. Algoritmi lineari di ordinamento: Bucket Sort e Radix Sort
3.5. Il problema della selezione. Algoritmi di selezione in tempo lineare


4. Tecniche algoritmiche di base
4.1. Algoritmi greedy
4.2. Divide et impera
4.3. Programmazione dinamica


5. Strutture dati
5.1. Code di priorità e heap
5.2. Mappe
5.3. Tabelle hash
5.4. Mappe ordinate: alberi binari di ricerca



6. Algoritmi su grafi diretti e indiretti
6.1. Visita
6.2. Componenti connesse e applicazioni delle visite in profondità e ampiezza
6.3. Algoritmi per la ricerca di cammini minimi
6.4. Algooritmi per l'individuazione di alberi ricoprenti minimi
6.5. Union Find



7. Algoritmi su stringhe
7.1. Pattern matching: algoritmi di Boyer-Moore e Knuth-Morris-Pratt
7.2. Compressione e algoritmo di Huffman
7.3. DNA e allineamento di sequenze



8. Randomizzazione
8.1. Quicksort e Quickselect
8.2. Test di primalità
8.3. Algoritmi randomizzati efficienti per il test di primalità

- Testo di riferimento: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduzione agli Algoritmi e Strutture Dati - IV edizione. McGraw Hill, Milano, Italia, 2023.
- Testo consigliato in alternativa (in Lingua Inglese): Tim Roughgarden. Algorithms Illuminated - Omnibus Edition. Soundlikeyourself Publishing LLC, New York, NY, 2022.

La modalità di svolgimento è in presenza. L'attività consisterà in lezioni di tipo teorico accompagnate da altri di tipo pratico, nel corso delle quali gli studenti metteranno in pratica, insieme al docente, i concetti appresi

Frequenza non obbligatoria

- Prova pratica al calcolatore su progetto e implementazione di algoritmi e strutture dati
- Prova scritta sugli argomenti del corso

1.
Si consideri il seguente array A: 4 13 7 1 8. Si descriva l’evoluzione dell’algoritmo Heap-Sort a partire dall’array A, mostrando l’albero che rappresenta il max-heap al termine di ogni chiamata di Max-Heapify

2. Sia dato un insieme S di n interi compresi fra 1 e K; bisogna partizionare l’insieme S in due sottoinsiemi S1 e S2 in modo che W1 e W2, le somme degli elementi nel sottoinsieme S 1 e S 2 rispettivamente, siano le più vicine possibili fra loro. Equivalentemente si chiede di trovare la partizione che minimizza |W1 − W2|, il valore assoluto della differenza fra W1 e W2.
(a) Scrivere lo pseudo-codice algoritmo efficiente che, dato in input S restituisce una coppia di insiemi S1 e S2 che rappresentano una partizione di S e verificano la condizione posta.
(b) Calcolare la complessità dell’algoritmo proposto.

• Introduzione al corso e concetti fondamentali


• Ordinamento e Selezione


• Grafi e Strutture Dati Fondamentali


• Tecniche Algoritmiche