PRESENTAZIONE

Il corso di Algoritmi e Strutture Dati ha come scopo l'ampliamento delle conoscenze e delle capacità inerenti la programmazione in piccolo mediante linguaggi imperativi; esso fornisce le basi per progettare algoritmi efficienti e per sviluppare strutture dati che permettano un’organizzazione efficace delle informazioni.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

Ampliare le conoscenze e le capacità inerenti la programmazione in piccolo mediante linguaggi imperativi, imparare a progettare algoritmi corretti ed efficienti, e implementare strutture dati che permettano un’organizzazione efficace ed efficiente delle informazioni.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

Al termine dell'insegnamento, lo studente/la studentessa sarà in grado di:

- calcolare la complessità di semplici frammenti di (pseudo-)codice e di algoritmi notevoli (ordinamento; aggiunta, ricerca e modifica di elementi in una struttura dati) in modo da individuare l'algoritmo più efficiente al variare della struttura dati considerata

- implementare i tipi di dato presentati durante l'insegnamento con strutture dati diverse che comprendono strutture indicizzate e collegate

- apprezzare la differenza nella efficienza delle funzioni previste dal tipo di dato al variare della struttura dati utilizzata

Al termine dell'insegnamento, lo studente/la studentessa che deciderà di partecipare alle iniziative di didattica innovativa  proposte dai docenti e dimostrerà di possedere i requisiti minimi disciplinari per essere coinvolto/a in tali attività innovative, avrà anche acquisito le seguenti competenze trasversali:

- Competenza alfabetica funzionale - livello avanzato (comunicare efficacemente in forma scritta e orale, adattamento della propria comunicazione al contesto, utilizzo di fonti e ausili di varia natura, pensiero critico, capacità di utilizzare,
elaborare e valutare informazioni)

- Capacità di imparare a imparare - livello avanzato (consapevolezza rispetto alle proprie strategie di apprendimento, organizzazione e valutazione dell’apprendimento personale secondo quanto compreso ed imparato, comprensione delle proprie necessità e modalità di sviluppo di competenze, capacità di individuare e perseguire obiettivi di apprendimento)

- Competenza in creazione progettuale - livello base (capacità di sviluppare la propria immaginazione e creatività, riflessione critica, pensiero strategico, problem solving con particolare riferimento a contesti di innovazione e processi
creativi in evoluzione)

PREREQUISITI

Le abilità di base che lo studente dovrebbe già possedere per affrontare senza difficoltà i contenuti dell’insegnamento sono quelle fornite dall'insegnamento "Introduzione alla Programmazione"

MODALITA' DIDATTICHE

L'insegnamento prevede l'erogazione di lezioni frontali (64 ore) e lo svolgimento di esercitazioni pratiche che si iniziano in laboratorio e si completano come compito per casa (32 ore).

L'insegnamento prevede lo sviluppo di un progetto individuale facoltativo.

Per gli studenti che intendano sviluppare le competenze trasversali illustrate negli obiettivi formativi, le modalità didattiche prevedono anche alcune tra le seguenti attività:
- produzione di brevi video su argomenti di teoria già spiegati a lezione
- produzione di documentazione che spieghi in forma scritta argomenti di teoria già presentati a lezione
- attività di peer review
- flipped classroom su un argomento per il quale i docenti hanno fornito documentazione scritta/video
- sviluppo di un progetto individuale (obbligatorio per l'ottenimento del corrispondente open badge)
 

PROGRAMMA/CONTENUTO

Modelli di calcolo e metodologie di analisi degli algoritmi: criteri di costo, notazione asintotica, metodi di analisi, analisi di complessità  degli algoritmi ricorsivi. Esempi di sviluppo ed analisi di algoritmi.
Algoritmi di ordinamento: insertion sort, selection sort, bubble sort, mergesort, quicksort (con analisi di complessità)
Strutture dati elementari: array e liste.
Tipi di dato: pila, coda, insieme, dizionario, coda con priorità.
Alberi  di ricerca: definizione, operazioni standard e loro complessità, visite, cenni ad alberi binari di ricerca bilanciati.
Alberi generici: definizione, operazioni standard e loro complessità, rappresentazioni indicizzate e collegate, alberi quasi completi, visite di alberi generici in profondità ed in ampiezza.
Heap binari: definizione, implementazione mediante liste e mediante heap memorizzati in array.
Tabelle di hash: implementazione con liste di collisione.
Grafi: definizioni, strutture dati, primitive per l'interrogazione e l'aggiornamento di grafi, visite di grafi in profondità ed in ampiezza, esempi di applicazione degli algoritmi di visita di un grafo.
Laboratorio: esercitazioni in C++ relative agli argomenti del corso

TESTI/BIBLIOGRAFIA

Tutti gli argomenti previsti dal programma vengono trattati approfonditamente a lezione. Per la comprensione degli argomenti e la preparazione dell'esame è quindi indispensabile disporre delle slide preparate dai docenti e rese disponibili con anticipo, e del materiale didattico aggiuntivo che i docenti forniscono tramite AulaWeb (ad esempio, link a materiale online, fotografie delle esercitazioni svolte alla lavagna).

Il codice C++ reso disponibile dai docenti è parte integrante del materiale didattico a disposizione degli studenti.

DOCENTI E COMMISSIONI

Commissione d'esame

VIVIANA MASCARDI (Presidente)

ARNAUD HENRI PAUL SANGNIER

MAURIZIO LEOTTA (Presidente Supplente)

LEZIONI

INIZIO LEZIONI

In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica

Orari delle lezioni

L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy

ESAMI

MODALITA' D'ESAME

Modalità d'esame

L'esame consiste in un quiz, in una prova scritta e in una prova di laboratorio. Per poter sostenere la prova scritta e la prova di laboratorio è necessario avere superato il quiz. Le prove scritte e di laboratorio sono indipendenti tra loro: è possibile prenotarsi e svolgere solo la prova scritta in un appello e prenotarsi e svolgere la prova di laboratorio in un appello successivo, e viceversa. Non è necessario superare una delle due prove per poter sostenere l'altra. E' necessario però avere superato il quiz.

E' previsto un progetto individuale a fine insegnamento, facoltativo, che se svolto adeguatamente accredita altri punti.

A giudizio dei docenti, qualora non sia evidente che lo studente/la studentessa abbia acquisito tutte le competenze previste (accertate con le modalità illustrate in seguito) sarà possibile sottoporre lo studente/la studentessa a una prova orale aggiuntiva mirata a confermare i voti di scritto e/o laboratorio.

I voti parziali conseguiti durante un anno accademico scadono allo scadere dell'anno: in altre parole, dopo le cinque sessioni d'appello relative all'insegnamento, tutti i voti incluso quello del progetto individuale vengono azzerati.

Modalità di valutazione

Il voto finale si ottiene come somma del voto del quiz + voto dello scritto + voto del laboratorio + voto del progetto individuale (se svolto). Tale somma viene arrotondata all'intero più vicino. 

MODALITA' DI ACCERTAMENTO

Le varie parti d'esame sono state accuratamente progettate dei docenti in modo da verificare se lo studente è in grado di

- calcolare la complessità di semplici frammenti di (pseudo-)codice e di algoritmi notevoli in modo da individuare l'algoritmo più efficiente (quiz con domande chiuse e prova scritta con domande aperte)

- implementare tipi di dato studiati a lezione con strutture dati diverse che comprendono strutture indicizzate e collegate (prova pratica di laboratorio, progetto individuale)

- apprezzare la differenza nella efficienza delle funzioni previste dal tipo di dato al variare della struttura dati utilizzata (quiz, prova scritta, prova pratica di laboratorio e progetto individuale in cui si chiede di implementare non solo funzioni corrette, ma anche efficienti)

Nella valutazione della prova scritta si terrà conto della chiarezza e correttezza della esposizione e della dimostrazione di senso critico.

Nella valutazione della prova di laboratorio e del progetto individuale si terrà conto della capacità di problem solving, della modularità e chiarezza del codice, della adeguatezza e della chiarezza espositiva della documentazione.

Saranno resi disponibili e discussi esempi di testi d'esame degli anni precedenti per permettere agli studenti di comprendere esattamente come viene accertata l'acquisizione delle competenze previste. Le attività di peer review saranno guidate dai criteri e le modalità di accertamento adottate dai docenti in sede d'esame.

I docenti possono inoltre accertare le competenze con una prova orale aggiuntiva qualora le prove previste non permettano di valutare in modo completo e definitivo la padronanza della materia da parte dello studente/della studentessa.

Calendario appelli

ALTRE INFORMAZIONI

Gli studenti e studentesse lavoratori/lavoratrici e con bisogni speciali sono pregati di contattare i docenti per individuare il miglior modo per fruire dell'insegnamento, anche se impossibilitati a seguire le attività in presenza.