INFORMATICA II
Anno accademico 2024/2025 - Docente: MARIANNA NICOLOSI ASMUNDORisultati di apprendimento attesi
Il corso introduce le principali metodologie di progettazione di algoritmi (incrementale, ricorsiva, programmazione dinamica, algoritmi golosi), le tecniche per l'analisi di complessità, sia nel caso pessimo che nel caso medio, nonché gli strumenti per l'implementazione degli algoritmi e delle strutture dati trattate. Il linguaggio Python verrà usato come strumento principale per presentare le implementazioni delle strutture dati e degli algoritmi.
Conoscenza e capacità di comprensione: saranno acquisite le conoscenze riguardanti i metodi più importanti per la progettazione di algoritmi (incrementale, ricorsiva, programmazione dinamica, algoritmi golosi), le tecniche per analizzarne la complessità, sia nel caso pessimo che in quello medio, nonché il funzionamento e l'implementazione delle principali strutture dati analizzate.
Capacità di applicare conoscenza e comprensione: saranno acquisite le capacità necessarie per la risoluzione di semplici problemi che richiedono di progettare e analizzare soluzioni algoritmiche e per l'implementazione degli algoritmi progettati.
Autonomia di giudizio: lo studente avrà le competenze per giudicare la qualità di una soluzione algoritmica in termini di efficienza e possibilità di riutilizzo, del proprio lavoro progettuale e della propria implementazione.
Abilità comunicative: lo studente acquisirà adeguate abilità comunicative e proprietà di linguaggio nella comunicazione di problematiche riguardanti gli studi algoritmici, anche ad interlocutori non esperti.
Capacità di apprendimento: lo studente sarà in grado di utilizzare le conoscenze acquisite anche nell'ambito di nuovi contesti, nonché di aggiornarsi consultando fonti specialistiche del settore algoritmico.
Modalità di svolgimento dell'insegnamento
Organizzazione didattica
150 ore d'impegno totale
103 di studio individuale
35 di lezione frontale
12 di esercitazione
L'insegnamento prevede delle lezioni frontali in cui verranno spiegati, anche attraverso degli esempi, gli algoritmi in programma, e del laboratorio in cui gli algoritmi suddetti vengono implementati.
Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto dichiarato in precedenza, al fine di rispettare il programma previsto e riportato nel syllabus.
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
Aver superato l'esame di Informatica 1.
Frequenza lezioni
Al fine di poter comprendere pienamente gli argomenti del corso e le tecniche illustrate, la frequenza delle lezioni è fortemente consigliata.
Contenuti del corso
Il corso tratta le principali metodologie di progettazione di algoritmi (incrementale, ricorsiva, programmazione dinamica, algoritmi golosi), le tecniche per l'analisi di complessità, sia nel caso pessimo che nel caso medio, nonché gli strumenti per l'implementazione degli algoritmi e delle strutture dati trattate. Il linguaggio Python verrà usato come strumento principale per presentare le implementazioni delle strutture dati e degli algoritmi.
PROGRAMMA DETTAGLIATO
Introduzione
Algoritmi come tecnologia per risolvere problemi computazionali. Metodologia incrementale. Metodologia divide-et-impera.
Notazioni asintotiche e relazioni tra esse. Notazioni standard e funzioni comuni.
Ricorrenze
Il metodo di sostituzione. Il metodo iterativo e dell'albero di ricorsione. Il teorema master.
Ordinamento e statistiche d'ordine
Ordinamento in tempo lineare. Mediane e statistiche d'ordine.
Elementi della programmazione dinamica
Sottostruttura ottima, ripetizione dei sottoproblemi, ricostruzione di una soluzione ottima
Alcuni casi di studio: moltiplicazione di una sequenza di matrici, la più lunga sottosequenza comune, distanza di editing.
Algoritmi elementari per grafi
Visita in ampiezza. Visita in profondità (classificazione degli archi). Ordinamento topologico. Componenti fortemente connesse.
Elementi della strategia golosa
Proprietà della scelta golosa, sottostruttura ottima. Alcuni casi di studio: problema della selezione di attività, costruzione di un codice di Huffman.
Contributo dell’insegnamento agli obiettivi dell’Agenda 2030 per lo Sviluppo Sostenibile
Goal N. 4: ISTRUZIONE DI QUALITÁ
Assicurare un’istruzione di qualità, equa ed inclusiva, e promuovere opportunità di apprendimento permanente per tutti
Goal N. 5: PARITÁ DI GENERE
Raggiungere l'uguaglianza di genere e l'empowerment (maggiore forza, autostima e consapevolezza) di tutte le donne e le ragazze
Goal N. 8: LAVORO DIGNITOSO E CRESCITA ECONOMICA
Incentivare una crescita economica duratura, inclusiva e sostenibile, un'occupazione piena e produttiva ed un lavoro dignitoso per tutti
Testi di riferimento
Il libro di testo consigliato è:
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009
disponibile anche nella traduzione italiana
1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati 3/ed, McGraw-Hill Italia, 2010.
Programmazione del corso
| Argomenti | Riferimenti testi | |
|---|---|---|
| 1 | Introduzione. Algoritmi come tecnologia per la soluzione di problemi | Cap.1.1-1.2 di 1) |
| 2 | Divide-et-impera | Cap. 4.1 di 1) e materiale didattico integrativo |
| 3 | Ricorrenze | Cap. 4.3-4.5 di 1) e materiale didattico integrativo |
| 4 | Ordinamento in tempo lineare | Cap. 8.2 di 1) e materiale didattico integrativo |
| 5 | Mediane e statistiche d'ordine | Cap. 9.1 e 9.3 di 1) e materiale didattico integrativo |
| 6 | Elementi della programmazione dinamica | Cap. 15 di 1) e materiale didattico integrativo |
| 7 | Algoritmi elementari per grafi | Cap. 22 di 1) e materiale didattico integrativo |
| 8 | Elementi della strategia golosa | Cap. 16.1-16.3 di 1) e materiale didattico integrativo |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
L'esame si svolgerà in due prove.
La prima prova è un esame scritto sugli argomenti teorici trattati nel corso.
La seconda prova consiste nell'implementazione, in Python, di un algoritmo trattato a lezione.
La verbalizzazione sarà preceduta da una breve discussione sulle due prove sostenute e, nei casi dubbi, da una breve verifica orale.
La verifica dell’apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere.
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
Lo studente potrà trovare i compiti degli anni precedenti, riguardanti la prima e la seconda prova sul portale Studium, al link