Università degli studi dell'Insubria

ALGORITMI E STRUTTURE DATI

A.A. di erogazione 2018/2019
Insegnamento obbligatorio

Laurea triennale in INFORMATICA
 (A.A. 2018/2019)

Docenti

Anno di corso: 
1
Tipologia di insegnamento: 
Caratterizzante
Settore disciplinare: 
INFORMATICA (INF/01)
Lingua: 
Italiano
Crediti: 
9
Ciclo: 
Secondo Semestre
Ore di attivita' frontale: 
72
Dettaglio ore: 
Lezione (72 ore)

Il corso fornisce le conoscenze di base relative alle principali strutture dati e ai principali algoritmi associati. Vengono acquisite le tecniche di base per la progettazione e l'analisi degli algoritmi, insieme alla capacità di sviluppare programmi software per i più classici problemi legati all’elaborazione dei dati.

Viene inoltre sviluppata la capacità di trasferimento delle conoscenze dagli ambiti teorici e metodologici a quelli più generalmente professionali.

I risultati di apprendimento attesi comprendono la capacità di saper individuare gli algoritmi e le strutture dati di base più indicate in un dato contesto, acquisendo al tempo stesso una proprietà di linguaggio tale da poter formalizzare un problema in modo idoneo a una sua trattazione informatica.
La conoscenza delle tecniche di base inerenti il mondo degli algoritmi e delle strutture di dati permette l’acquisizione di adeguate capacità per l'approfondimento delle proprie conoscenze e per lo sviluppo individuale di nuove competenze.

Prerequisiti: 

Viene richiesta la conoscenza di un linguaggio di programmazione di tipo procedurale, meglio se corredata da elementi di base relativi all’architettura di un elaboratore.

L'acquisizione delle diverse conoscenze ed abilità attese si svilupperà in modo parallelo lungo tutto l'insegnamento, attraverso lo studio dei seguenti argomenti:

1) Formalizzazione dei problemi, complessità degli algoritmi, notazioni asintotiche (6h)
2) Modelli di calcolo (RAM, RASP) e criteri di costo (6h)
3) Caratteristiche dei linguaggi procedurali (2h)
4) Strutture dati elementari (vettori, matrici, liste, pile, code) (6h)
5) Grafi e alberi, rappresentazioni e algoritmi di visita (10h)
6) Il problema dell’ordinamento: aspetti generali e algoritmi elementari (4h).
7) Tecnica di progettazione Divide et Impera (2h)
8) Ordinamento digitale e algoritmi d’ordinamento avanzati (6h)
9) Heap e Heapsort (2h)
10) Tabelle hash (4h)
11) Alberi binari di ricerca (6h)
12) Alberi bilanciati (2-3, 2-3-4, red-black) (8h)
13) Operazioni su partizioni (Union e Find) (2h)
14) Problemi di ottimizzazione (4h)
15) Programmazione dinamica (4h)

Il corso prevede 72 ore di lezioni frontali, tutte impartite dal docente titolare del corso. Ogni lezione presenta sia elementi teorici sia immediate applicazioni ed esempi. Per la quasi totalità degli argomenti trattati vengono preventivamente distribuite slide attraverso il sito di e-learning. Si consiglia fortemente la frequenza.

Modalita' di verifica dell'apprendimento: 

L’esame consiste in una prova scritta, a cui fa seguito una prova orale nel caso di esito positivo. Durante il corso sono previste due prove parziali il cui superamento comporta l’esonero dalla prova scritta. Lo scritto, della durata di 2 ore, prevede una serie di 5 quesiti relativi agli argomenti trattati a lezione (6 punti disponibili per ogni quesito). L’esito positivo (valutato in trentesimi) della prova scritta permette l’accesso alla successiva prova orale. Tale prova consiste in una visione congiunta della prova scritta in cui l’allievo viene informato sui criteri di correzione e chiamato a fornire eventuali precisazioni, permettendo così al docente di verificare la correttezza della votazione assegnata.

In aggiunta alle slide e alle dispense distribuite tramite la piattaforma di e-learning, il testo di riferimento è (versione italiana e inglese)

1) R. Sedgewick, Algoritmi in Java (3ed.), Pearson Education Italia.
2) R. Sedgewick, K. Wayne, Algorithms, 4th Edition, Addison-Wesley Professional 2011.

Una trattazione alternativa ed approfondita degli stessi argomenti si può trovare anche su
Thomas H. Cormen - Charles E. Leiserson - Ronald L. Rivest - Clifford Stein, Introduzione agli algoritmi e strutture dati, McGraw Hill education, 2010

Il docente è a disposizione per il ricevimento studenti, direttamente in aula al termine di ciascuna lezione o su appuntamento in dipartimento (da concordare tramite posta elettronica).

Cerchi il programma? Potrebbe non essere ancora stato caricato o riferirsi ad insegnamenti che verranno erogati in futuro.
Seleziona l‘anno in cui ti sei immatricolato e troverai le informazioni relative all'insegnamento del tuo piano di studio.

A.A. 2019/2020

Anno di corso: 1
Curriculum: PERCORSO COMUNE

A.A. 2017/2018

Anno di corso: 1
Curriculum: PERCORSO COMUNE

A.A. 2016/2017

Anno di corso: 1
Curriculum: PERCORSO COMUNE

A.A. 2015/2016

Anno di corso: 1
Curriculum: PERCORSO COMUNE

A.A. 2014/2015

Anno di corso: 1
Curriculum: PERCORSO COMUNE

A.A. 2013/2014

Anno di corso: 1
Curriculum: PERCORSO COMUNE