Salta al contenuto principale
CODICE 80298
ANNO ACCADEMICO 2023/2024
CFU
SETTORE SCIENTIFICO DISCIPLINARE INF/01
LINGUA Italiano
SEDE
  • GENOVA
PERIODO 2° Semestre
PROPEDEUTICITA
Propedeuticità in uscita
Questo insegnamento è propedeutico per gli insegnamenti:
  • INFORMATICA 8759 (coorte 2023/2024)
  • ANALISI E PROGETTAZIONE DI ALGORITMI 80306
MATERIALE DIDATTICO AULAWEB

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 sviluppare strutture dati che permettano un’organizzazione efficace ed efficiente delle informazioni.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

Al termine dell'insegnamento, lo studente/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/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:
- 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 ampio anticipo, e degli appunti presi durante le lezioni in aula.

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.

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

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.

Calendario appelli

Dati Ora Luogo Tipologia Note
10/01/2024 09:00 GENOVA Scritto
08/02/2024 09:00 GENOVA Scritto
11/06/2024 09:00 GENOVA Scritto
12/06/2024 09:00 GENOVA Laboratorio
15/07/2024 09:00 GENOVA Scritto
16/07/2024 09:00 GENOVA Laboratorio
03/09/2024 09:00 GENOVA Scritto
04/09/2024 09:00 GENOVA Laboratorio
08/01/2025 09:00 GENOVA Scritto
06/02/2025 09:00 GENOVA Scritto

OpenBadge

 PRO3 - Soft skills - Creazione progettuale base 1 - A
PRO3 - Soft skills - Creazione progettuale base 1 - A
 PRO3 - Soft skills - Imparare a imparare avanzato 1 - A
PRO3 - Soft skills - Imparare a imparare avanzato 1 - A
 PRO3 - Soft skills - Alfabetica avanzato 1 - A
PRO3 - Soft skills - Alfabetica avanzato 1 - A