ALGORITMI E STRUTTURE DATI

A.A. di erogazione 2019/2020
Insegnamento obbligatorio

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

Docenti

Anno di corso: 
1
Tipologia di insegnamento: 
Caratterizzante
Sede: 
Varese - Università degli Studi dell'Insubria
Settore disciplinare: 
INFORMATICA (INF/01)
Crediti: 
9
Ciclo: 
Secondo Semestre
Ore di attivita' frontale: 
72

Il corso ha lo scopo di rendere gli studenti capaci di applicare le conoscenze di base relative alle principali strutture dati e ai principali algoritmi associati. A tale scopo gli studenti apprenderanno le tecniche di base per la progettazione e l'analisi degli algoritmi, insieme alla capacità di risolvere i più classici problemi legati all’elaborazione dei dati.
Al termine del corso, lo studente sarà in grado di:

1. Comprendere le caratteristiche rilevanti di un modello di calcolo astratto, nonché l’importanza della complessità di un algoritmo al fine del suo utilizzo concreto.
2. Individuare gli algoritmi e le strutture dati di base più indicate in un dato contesto applicativo.
3. Conoscere e applicare i principali paradigmi di progettazione di algoritmi.

Lo studente dovrà inoltre conseguire una consapevole autonomia di giudizio con riferimento alle problematiche tipiche della progettazione di algoritmi efficienti.
Lo studente svilupperà infine una proprietà di linguaggio tale da poter formalizzare un problema in modo idoneo a una sua trattazione informatica.

È richiesta la capacità di programmare in ambiente "sequenziale"; specificamente è necessario che lo studente padroneggi la programmazione in Java (il linguaggio usato nel corso) nonché gli elementi di base relativi all’architettura di un elaboratore. Le conoscenze e abilità necessarie per un proficuo apprendimento di questo insegnamento sono impartite nei corsi fondamentali del primo anno di Programmazione e di Architetture degli elaboratori.

Le lezioni affronteranno i seguenti argomenti:

Modelli di calcolo e complessità (14 h, obiettivo formativo 1)
- Formalizzazione dei problemi, complessità degli algoritmi, notazioni asintotiche (6h)
- Modelli di calcolo (RAM, RASP) e criteri di costo (6h)
- Caratteristiche dei linguaggi procedurali (2h)
Algoritmi e strutture dati di base (20 h, obiettivo formativo 2)
- Strutture dati elementari (vettori, matrici, liste, pile, code) (6h)
- Grafi e alberi, rappresentazioni e algoritmi di visita (10h)
- Il problema dell’ordinamento: aspetti generali e algoritmi elementari (4h)
Algoritmi e strutture dati avanzati (28 h, obiettivo formativo 2)
- Ordinamento digitale e algoritmi d’ordinamento avanzati (6h)
- Heap e Heapsort (2h)
- Tabelle hash (4h)
- Alberi binari di ricerca (6h)
- Alberi bilanciati (2-3, 2-3-4, red-black) (8h)
- Operazioni su partizioni (Union e Find) (2h)
Tecniche di progettazione (10 h, obiettivo formativo 3)
- Metodologia Divide et Impera (2h)
- Programmazione dinamica (4h)
- Algoritmi greedy (4h)

Gli argomenti verranno affrontati usando come riferimento il linguaggio di programmazione Java. Ciò nondimeno, molti degli argomenti trattati nel corso sono di validità generale, e le tecniche proposte sono applicabili con linguaggi diversi.

Il corso si articola in lezioni frontali (72 ore).
Ogni lezione presenta sia elementi teorici sia immediate applicazioni ed esempi. Il docente rende disponibile preventivamente tutto il materiale didattico e invita lo studente ad essere presente in aula dopo aver preso visione del materiale della lezione, che verrà svolta in modo tale da aumentare interazione, discussione e di conseguenza apprendimento.

L’obiettivo della prova d’esame è l'accertamento dell’acquisizione delle conoscenze e delle abilità descritte nella sezione “Obiettivi formativi”, valutando il livello di conoscenza e soprattutto la capacità di mettere in pratica, anche integrandole tra loro, le tecniche di progettazione viste a lezione.
L'esame consiste in una prova scritta da svolgersi in aula, a cui fa seguito una prova orale nel caso di esito positivo. La prova scritta–della durata indicativa di 120 minuti–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, apportando nel caso variazioni.
La conoscenza della terminologia specifica di dominio viene testata implicitamente, poiché domande e specifiche dei problemi utilizzano tale terminologia. Similmente, l’autonomia di giudizio viene rilevata attraverso quesiti che richiedono scelte ragionate di algoritmi e strutture dati in funzione del contesto.

In aggiunta alle slide e alle dispense distribuite tramite la piattaforma di e-learning, il testo di riferimento è (versione italiana e inglese)
• R. Sedgewick, Algoritmi in Java (3ed.), Pearson Education Italia.
• 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 riceve su appuntamento, previa richiesta via e-mail a paolo.massazza@uninsubria.it. Il docente risponde solo alle e-mail firmate e provenienti dal dominio studenti.uninsubria.it.

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. 2018/2019

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