INFORMATICA II

Il corso introduce i fondamenti della progettazione e dell’analisi degli algoritmi, con particolare attenzione alle strutture dati fondamentali e agli algoritmi su grafi e di ordinamento. Una parte del corso è dedicata all’utilizzo di Python e delle principali librerie scientifiche per la matematica computazionale, con un’introduzione ai concetti di Intelligenza Artificiale e Machine Learning.

Conoscenza e capacità di comprensione: saranno acquisite conoscenze riguardanti le tecniche principali di progettazione algoritmica (incrementale, divide-et-impera), i criteri di analisi della complessità e il funzionamento delle strutture dati fondamentali (pile, code, alberi, grafi). Verranno inoltre introdotti i concetti base di regressione e clustering.

Capacità di applicare conoscenza e comprensione: lo studente svilupperà competenze nella progettazione e implementazione di algoritmi in Python, nella gestione di dataset mediante librerie scientifiche e nella risoluzione di problemi computazionali concreti. Sarà in grado di applicare modelli di apprendimento supervisionato e non supervisionato a semplici casi di studio.

Autonomia di giudizio: lo studente maturerà la capacità di scegliere le strutture dati e gli algoritmi più adeguati a seconda del problema, valutando l’efficienza e i limiti delle soluzioni proposte e interpretando criticamente i risultati ottenuti.

Abilità comunicative: lo studente acquisirà la capacità di presentare in modo chiaro e rigoroso soluzioni algoritmiche e progetti di programmazione, anche attraverso la documentazione del codice e la discussione dei risultati.

Capacità di apprendimento: lo studente sarà in grado di approfondire in autonomia algoritmi e tecniche di IA non trattati nel corso, utilizzando testi specialistici e documentazione tecnica, e di applicare le conoscenze acquisite a nuovi contesti informatici e matematici.

Informatica 2 - 6 CFU - 47 ore totali
Organizzazione didattica
150 ore d'impegno totale
103 di studio individuale
35 di lezione frontale

12 di esercitazione

L'insegnamento prevede delle lezioni frontali e di laboratorio

NOTA BENE: Informazioni per studenti con disabilità e/o DSA

A garanzia di pari opportunità e nel rispetto delle leggi vigenti, gli studenti interessati possono chiedere un colloquio personale in modo da programmare eventuali misure compensative e/o dispensative, in base agli obiettivi didattici ed alle specifiche esigenze. 

E' possibile rivolgersi anche al docente referente CInAP (Centro per l’integrazione Attiva e Partecipata - Servizi per le Disabilità e/o i DSA) del nostro Dipartimento o al Presidente del Corso di Studi. 

Il corso introduce le basi della progettazione e dell’analisi degli algoritmi, con applicazioni pratiche all’informatica e alla matematica computazionale. Completa il percorso una parte introduttiva sull’Intelligenza Artificiale e il Machine Learning, con l’utilizzo di Python e librerie scientifiche.

Progettazione e complessità degli algoritmi

• Algoritmi come tecnologia per risolvere problemi computazionali
  
• Tecniche di progettazione: metodologia incrementale e divide-et-impera
• Concetto di complessità di un algoritmo e sue implicazioni pratiche

Strutture dati fondamentali

• Classi e Oggetti: definizione, metodi e implementazione
• Pile, code, liste concatenate: definizioni, operazioni fondamentali e implementazione
  
• Tabelle hash: concetti base e implementazione
• Alberi binari di ricerca: struttura, operazioni fondamentali e implementazione

Grafi e algoritmi su grafi

• Definizione di grafo: orientato e non orientato
  
• Rappresentazioni e implementazione (liste di adiacenza, matrici)
• Visite: BFS (Breadth-First Search) e DFS (Depth-First Search) – definizione e implementazione
• Algoritmi di cammino minimo:
• Dijkstra – descrizione e implementazione
• Bellman-Ford – descrizione e implementazione

Analisi di algoritmi ricorsivi e ordinamento

• Risoluzione di ricorrenze:
  
• Metodo di sostituzione
• Metodo iterativo e metodo dell’albero di ricorsione
• Teorema master
• Algoritmi di ordinamento:
• MergeSort, QuickSort – descrizione e implementazione
• Ordinamento in tempo lineare: Counting Sort, Radix Sort – descrizione e implementazione
• Mediane e statistiche d’ordine: algoritmo di selezione lineare – descrizione e implementazione

Laboratorio: Python per la matematica computazionale

• Introduzione a Python per il calcolo scientifico
  
• Uso delle principali librerie:
• NumPy: array, operazioni vettoriali/matriciali
• SciPy: algebra lineare, integrali, ottimizzazione
• Pandas: gestione di dataset tabellari (in forma semplificata)

Introduzione all’Intelligenza Artificiale e al Machine Learning 

• Cenni storici e motivazioni dell’IA
  
• Tipi di apprendimento:
• Supervisionato
• Non supervisionato
• Algoritmi di base:
• Regressione lineare: modello, funzione di costo, ottimizzazione – e implementazione
• Clustering (k-means): distanza, centroide, algoritmo iterativo – e implementazione

T. H Cormen

Introduction to Algorithms

The MIT Press 

 Per partecipare all'esame finale è necessario avere effettuato la prenotazione sul portale SmartEdu. Per eventuali problemi tecnici relativi alla prenotazione occorre rivolgersi alla Segreteria didattica.

L'esame si svolgerà in due parti.

La prima parte è un esame di laboratorio sugli argomenti in Python trattati nel corso. 

La seconda parte consiste nella stesura di un progetto relativo ad uno degli argomenti trattati durante il corso.

La verbalizzazione sarà preceduta da una breve discussione sulle due prove sostenute e, nei casi dubbi, da una breve verifica orale.