1008041 - INFORMATICA II
Risultati di apprendimento attesi
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.
Modalità di svolgimento dell'insegnamento
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.
Prerequisiti richiesti
Frequenza lezioni
Contenuti del corso
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
Testi di riferimento
T. H Cormen
Introduction to Algorithms
The MIT Press
Programmazione del corso
| Argomenti | Riferimenti testi | |
|---|---|---|
| 1 | Progettazione e complessità degli algoritmi | |
| 2 | Strutture dati fondamentali | |
| 3 | Grafi e algoritmi su grafi | |
| 4 | Analisi di algoritmi ricorsivi e ordinamento | |
| 5 | Laboratorio: Python per la matematica computazionale | |
| 6 | Introduzione all’Intelligenza Artificiale e al Machine Learning |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
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.
Criteri per l’attribuzione del voto.
Si terrà conto: della chiarezza espositiva, della completezza delle conoscenze, della capacità di ragionamento. Lo studente deve dimostrare di aver acquisito una conoscenza sufficiente dei principali argomenti trattati durante il corso, e di essere in grado di svolgere almeno i più semplici tra gli esercizi assegnati.
Per l'attribuzione del voto si seguiranno di norma i seguenti criteri:
non approvato: lo studente non ha acquisito i concetti di base, non è in grado di svolgere gli esercizi e di implementare i programmi richiesti.
18-23: lo studente dimostra una padronanza minima dei concetti di base, le sue capacità di esposizione sono modeste, riesce a risolvere semplici esercizi, riesce solo in parte a implementare i programmi richiesti.
24-27: lo studente dimostra una buona padronanza dei contenuti del corso, le sue capacità di esposizione sono buone, risolve gli esercizi e implementa i programmi con pochi errori.
28-30 e lode: lo studente ha acquisito tutti i contenuti del corso ed è in grado di esporli compiutamente e con spirito critico; risolve gli esercizi e implementa i programmi in modo completo e senza errori.
Esempi di domande e/o esercizi frequenti
English version