Seguici su
Cerca

INFORMATICA II

Anno accademico 2017/2018 - 3° anno
Docente: Marianna NICOLOSI ASMUNDO
Crediti: 6
Organizzazione didattica: 150 ore d'impegno totale, 102 di studio individuale, 48 di lezione frontale
Semestre:

Obiettivi formativi

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.


Prerequisiti richiesti

Strutture dati elementari e loro manipolazioni (liste, code, pile, alberi). Nozioni base di programmazione e del linguaggio di programmazione Python. Elementi 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.

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

 *ArgomentiRiferimenti testi
1*Introduzione. Algoritmi come tecnologia per la soluzione di problemiCap.1.1-1.2 di 1)  
2*Divide-et-imperaCap. 4.1 di 1) e materiale didattico integrativo  
3*RicorrenzeCap. 4.3-4.5 di 1) e materiale didattico integrativo  
4*Elementi della programmazione dinamicaCap. 15 di 1) e materiale didattico integrativo  
5*Algoritmi elementari per grafiCap. 22 di 1) e materiale didattico integrativo  
6*Elementi della strategia golosaCap. 16.1-16.3 di 1) e materiale didattico integrativo  
* Conoscenze minime irrinunciabili per il superamento dell'esame.

N.B. La conoscenza degli argomenti contrassegnati con l'asterisco è condizione necessaria ma non sufficiente per il superamento dell'esame. Rispondere in maniera sufficiente o anche più che sufficiente alle domande su tali argomenti non assicura, pertanto, il superamento dell'esame.

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, alla voce "Documenti".