INFORMATICA II

Anno accademico 2023/2024 - Docente: MARIANNA NICOLOSI ASMUNDO

Risultati 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

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 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, prof. Filippo Stanco. 

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.

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
1Introduzione. Algoritmi come tecnologia per la soluzione di problemiCap.1.1-1.2 di 1)
2Divide-et-imperaCap. 4.1 di 1) e materiale didattico integrativo
3RicorrenzeCap. 4.3-4.5 di 1) e materiale didattico integrativo
4Ordinamento in tempo lineareCap. 8.2 di 1) e materiale didattico integrativo
5Mediane e statistiche d'ordineCap. 9.1 e 9.3 di 1) e materiale didattico integrativo
6Elementi della programmazione dinamicaCap. 15 di 1) e materiale didattico integrativo
7Algoritmi elementari per grafiCap. 22 di 1) e materiale didattico integrativo
8Elementi della strategia golosaCap. 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 

https://studium.unict.it/dokeos/2023/main/document/document.php?cidReq=6408FB46A3563199&curdirpath=/shared_folder&teacher_table_page_nr=2