INFORMATICA II
Anno accademico 2019/2020 - 2° annoCrediti: 6
Organizzazione didattica: 150 ore d'impegno totale, 103 di studio individuale, 35 di lezione frontale, 12 di esercitazione
Semestre: 1°
Obiettivi formativi
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
L'insegnamento predeve 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.
Prerequisiti richiesti
Aver superato l'esame di Informatica I.
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.
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, svolta in laboratorio e della durata di due ore, consisterà nell'implementazione, in Python, di una o più tre le strutture dati studiate a lezione.
La verbalizzazione sarà preceduta da una breve discussione sulle due prove sostenute e, nei casi dubbi, da una breve verifica orale.
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